Производительность массива очень похожа на LinkedList - Что дает?

Question

Так что название несколько вводит в заблуждение ... Я буду упрощать: я сравниваю эти две структуры данных:

1. Массив, в котором он начинается с размера 1, и для каждого последующего добавления существует вызов realloc () для расширения памяти, а затем добавление нового (malloced) элемента в позицию n-1.
2. Связанный список, по которому я отслеживаю голову, хвост и размер. Кроме того, добавление включает в себя неправильный поиск нового элемента и обновление указателя и размера хвоста.

Не беспокойтесь ни о каких других деталях этих структур данных. Это единственная функция, которая мне нужна для этого тестирования.

Теоретически, LL должен работать лучше. Тем не менее, они практически идентичны по времени испытаний с участием 10, 100, 1000 ... до 5 000 000 элементов.

Мое ощущение, что куча большая. Я думаю, что сегмент данных по умолчанию 10 МБ на Redhat? Я могу ошибаться. В любом случае, realloc () сначала проверяет, доступно ли пространство в конце уже выделенного непрерывного расположения памяти (0- [n-1]). Если n-я позиция доступна, перемещение элементов не производится. Вместо этого realloc () просто резервирует старый пробел + непосредственно следующий пробел. Мне трудно найти доказательства этого, и мне все труднее доказать, что этот массив на практике должен работать хуже, чем LL.

Вот некоторый дальнейший анализ после прочтения постов ниже:

[Обновление № 1] Я изменил код, чтобы иметь отдельный список, который распределяет память каждую 50-ю итерацию как для LL, так и для массива. На 1 миллион дополнений в массиве почти всегда есть 18 ходов. Там нет концепции переезда для LL. Я сделал сравнение времени, они все еще почти идентичны. Вот некоторые результаты для 10 миллионов дополнений:

(Array)
time ./a.out a 10,000,000
real    0m31.266s
user    0m4.482s
sys     0m1.493s
(LL)
time ./a.out l 10,000,000
real    0m31.057s
user    0m4.696s
sys     0m1.297s

Я бы ожидал, что время будет резко отличаться от 18 ходов. Для добавления массива требуется еще 1 присваивание и еще 1 сравнение, чтобы получить и проверить возвращаемое значение realloc, чтобы убедиться, что произошло перемещение.

[Обновление № 2] Я запустил ltrace для тестирования, которое я опубликовал выше, и я думаю, что это интересный результат ... Похоже, что realloc (или некоторый менеджер памяти) превентивно перемещает массив в более крупные смежные местоположения на основе текущего размера. Для 500 итераций перемещение памяти было запущено на итерациях: 1, 2, 4, 7, 11, 18, 28, 43, 66, 101, 154, 235, 358 Что довольно близко к последовательности суммирования. Я нахожу это довольно интересным - думал, что я отправлю это.

Answer 1

Вы правы, realloc будет просто увеличивать размер выделенного блока, если это не будет запрещено.В реальном сценарии у вас, скорее всего, будут другие объекты, расположенные в куче между последующими добавлениями в список?В этом случае realloc придется выделить совершенно новый кусок памяти и скопировать элементы, уже находящиеся в списке.

Попробуйте выделить другой объект в куче, используя malloc для каждых десяти вставок или около того, и посмотрите, все ли они по-прежнемувыполнить то же самое.

Answer 2

Итак, вы тестируете, как быстро вы можете расширить массив, используя связанный список?

В обоих случаях вы вызываете функцию выделения памяти.Обычно функции выделения памяти захватывают часть памяти (возможно, страницу) из операционной системы, а затем разделяют ее на более мелкие части, как того требует ваше приложение.

Другое предположение состоит в том, что время от времени realloc() будет плюнуть на пустышку и выделять большой кусок памяти в другом месте, потому что он не мог получить смежные куски в пределах текущей выделенной страницы.Если вы не делаете никаких других вызовов функциям распределения памяти между расширениями списка, этого не произойдет.И, возможно, использование вашей операционной системой виртуальной памяти означает, что куча вашей программы непрерывно увеличивается независимо от того, откуда поступают физические страницы.В этом случае производительность будет идентична группе вызовов malloc ().

Ожидается, что производительность изменится в случае смешивания вызовов malloc () и realloc ().

Answer 3

Производительность решения на основе массива, расширенного с realloc(), будет зависеть от вашей стратегии по созданию большего пространства.

Если вы увеличиваете объем пространства, добавляя фиксированный объем памяти при каждом перераспределении, вы получите расширение, которое в среднем зависит от количества элементов, сохраненных в массиве. Это при условии, что realloc потребуется (иногда) выделять место в другом месте и копировать содержимое, а не просто расширять существующее распределение.

Если вы увеличите объем пространства, добавив пропорцию текущего количества элементов (удвоение является довольно стандартным), вы получите расширение, которое в среднем занимает постоянное время.

Answer 4

Предполагая, что ваш связанный список является указателем на первый элемент, если вы хотите добавить элемент в конец, вы должны сначала пройти список.Это операция O(n).

Предполагая, что realloc должен переместить массив в новое место, он должен пересечь массив, чтобы скопировать его.Это операция O(n).

С точки зрения сложности обе операции одинаковы.Однако, как отмечали другие, realloc может избежать перемещения массива, и в этом случае добавление элемента в массив будет O(1).Другие также отметили, что подавляющее большинство времени вашей программы, вероятно, тратится на malloc / realloc, который обе реализации вызывают один раз за добавление.

Наконец, еще одна причина, по которой массив, вероятно, быстрее, это кэшсогласованность и в целом высокая производительность линейных копий.Перескочить на ошибочные адреса со значительными пробелами между ними (как с большими элементами, так и с malloc бухгалтерией) обычно не так быстро, как сделать массовую копию того же объема данных.

Answer 5

Это не реальная жизненная ситуация. Предположительно, в реальной жизни вы заинтересованы в просмотре или даже удалении элементов из ваших структур данных, а также их добавлении.

Если вы разрешаете удаление, но только из головы, связанный список становится лучше, чем массив, поскольку удаление элемента является тривиальным, и, если вместо освобождения удаленного элемента вы помещаете его в свободный список для повторного использования, вы может убрать много ненужных ссылок при добавлении элементов в список.

С другой стороны, если вам нужен произвольный доступ к структуре, очевидно, что массив превосходит связанный список.

Answer 6

Будет ли вывод компилятора сильно отличаться в этих двух случаях?

Answer 7

На чем основывается ваша теория, что связанный список должен работать лучше для вставок в конце? Я бы не ожидал, что именно по той причине, которую вы указали. realloc будет копироваться только тогда, когда это необходимо для поддержания непрерывности; в других случаях может потребоваться объединить свободные порции и / или увеличить размер порции.

Однако каждый узел связанного списка требует нового выделения и (при условии двойного связанного списка) двух записей. Если вы хотите узнать, как работает realloc, вы можете просто сравнить указатель до и после realloc. Вы должны найти, что это обычно не меняется.

Я подозреваю, что, поскольку вы звоните realloc для каждого элемента (очевидно, не мудр в производстве), сам вызов realloc / malloc является самым большим узким местом для обоих тестов, хотя realloc часто не не указывать новый указатель.

Кроме того, вы путаете сегмент кучи и данных. Куча - это место, где живет испорченная память. Сегмент данных предназначен для глобальных и статических переменных.

Answer 8

(Обновлено.) Как уже отмечали другие, если между реаллоками нет других распределений, копирование не требуется.Также, как отмечали другие, риск копирования памяти уменьшается (но, конечно же, и его влияние) для очень маленьких блоков, меньших, чем страница.

Кроме того, если все, что вы когда-либо делаете в своем тесте, - это выделение новогопространство памяти, я не очень удивлен, что вы видите небольшую разницу, поскольку системные вызовы для выделения памяти, вероятно, занимают большую часть времени.

Вместо этого выбирайте структуры данных в зависимости от того, как вы хотите их использовать.Например, фрейм-буфер, вероятно, лучше всего представлен непрерывным массивом.

Связанный список, вероятно, лучше, если вам нужно быстро реорганизовать или отсортировать данные в структуре.

Тогда this операции будут более или менее эффективными в зависимости от того, что вы хотите сделать.

(Спасибо за комментарии ниже, я изначально был озадачен тем, как эти вещи работают.)