|
Страница 3 из 3
Выглядит на первый взгляд несколько сомнительно: ведь преимущества обычных списков с указателями заключаются как раз в том, что общее количество выделенных элементов будет равно нужному, а при вставке нового элемента не требуется модификация всего остального списка. В данном же случае, количество выделенных элементов, размер которых, правда, меньше предыдущего в два раза, всегда кратно 16, а изменение списка влечет за собой копирование всех данных из старой области памяти в новую.
Тем не менее, надо попробовать еще раз запустить тест:
alk:~$ g++ -O5 t2.cpp -o t2
alk:~$ time t2
Iterations: 7478165
real 0m0.296s
user 0m0.296s
sys 0m0.000s
alk:~$ time t2
Iterations: 7477196
real 0m0.296s
user 0m0.296s
sys 0m0.000s
alk:~$ time t2
Iterations: 7489060
real 0m0.296s
user 0m0.295s
sys 0m0.000s
alk:~$ time t2
Iterations: 7492167
real 0m0.298s
user 0m0.282s
sys 0m0.008s
Если вас не удивили полученные числа, то читать дальше вам будет совершенно неинтересно.
Стоит отметить, что общее количество сравнений практически одинаково в обоих случаях. Разница в затраченном времени между вторым и первым вариантом программы достаточно просто объяснима, для этого достаточно представлять себе в общих чертах устройство современных микропроцессоров. Все дело в том, что память не является чем-то однородным, более того, память образует иерархию по своей скорости, например: регистры процессора, кеш первого уровня, кеш второго уровня, оперативная память, жесткие диски... несмотря на то, что каждый "вид" памяти предназначен, по сути, для одного и того же --- хранения данных --- скорость доступа может сильно отличаться. Когда процессор желает что-то прочитать из оперативной памяти, эти данные "оседают" в кешах, доступ к которым быстрее, и если через некоторое время (пока запись еще не была удалена из кешей) процессор вновь обратится к тому же адресу, что и раньше, то обращения к относительно медленной оперативной памяти не будет. Кроме того, кеш разбит на области фиксированного размера (линии, в случае обычного Пентиума --- 32 байта), и именно такими блоками происходит чтение данных из оперативной памяти. Таким образом, если, как во втором случае, происходит чтение последовательного массива целых чисел, то считывая один элемент, в кеш попадут как минимум 8 элементов этого массива и все они больше не будут требовать обращений к оперативной памяти в ближайшее время. В случае же "с указателями", невозможно предсказать какой элемент будет следующим в списке, потому что он зависит от содержимого внутри прочитанной области данных (указателя) и, скорее всего, следующий элемент не попадет в кеш. Поэтому итерация по списку будет требовать еще столько операции чтения из оперативной памяти, сколько будет в списке элементов. Кроме того, современные умные микропроцессоры, или не менее умные оптимизаторы, умеют делать предварительное чтение данных в кеш. То есть, если читается блок в кеш, то пока процессор с ним работает, можно прочитать в кеш следующий блок памяти в расчете на последовательный доступ к данным (prefetch). Поэтому скорость последовательного доступа к элементам массива будет выше, чем доступ к элементам "списка с указателями" даже когда размер структур более размера целого числа. Кстати сказать, в таких случаях выгодно выравнивать размер структур по размеру кешлайнов, потому что чтение одного кешлайна из оперативной памяти тоже операция неоднородная и начало кешлайна появится в кеше быстрее, чем окончание, на чем тоже можно "сыграть". Резюме Таким образом, процессор всегда рассчитывает на последовательный доступ к данным и использование этого факта может сильно ускорить работу программы. Это относится не только к организации списков на массивах (не в случае, когда указатели на следующий элемент заменяются индексами внутри массива, а когда положение элемента в списке определяется его индексом в массиве), но и, например, к обработке двумерных массивов (значительно выгоднее читать массив по возрастанию реальных адресов ячеек).
PS Кстати сказать, существуют эффективные вариации сортировки слиянием для данных, находящихся в оперативной памяти. Просто именно такой, достаточно простой способ сортировки, позволяет учитывать в алгоритме иерархичность оперативной памяти и легко распараллеливается на несколько процессоров. |