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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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