Std:: list vs std::vector итерация

Говорят, что итерация через вектор (как при чтении всего этого элемента) происходит быстрее, чем повторение через список из-за оптимизированного кеша.

Есть ли в Интернете какой-либо ресурс, который бы определял, насколько он влияет на производительность?

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

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

Является ли тот факт, что элементы являются последовательными, влияет на кеш, или потому, что я все равно вызову list_element->next вместо ++list_element, он ничего не улучшит?

Ответ 1

Повышение эффективности от когерентности кэша из-за компактного представления структур данных может быть довольно драматичным. В случае векторов по сравнению со списками компактное представление может быть лучше не только для чтения, но даже для вставки (сдвига в векторах) элементов до порядка 500 К элементов для некоторой конкретной архитектуры, как показано на рисунке 3 этой статьи Бьярне Страуструп:

http://www2.research.att.com/~bs/Computer-Jan12.pdf

(сайт издателя: http://www.computer.org/portal/web/csdl/doi/10.1109/MC.2011.353)

Я думаю, что если это критический фактор для вашей программы, вы должны профилировать его в своей архитектуре.

Ответ 2

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

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

С list-s, поскольку элементы везде разрежены, "переход к следующему" означает обращение к адресу, который не может находиться на одной и той же странице памяти предыдущего, и, следовательно, кеш необходимо обновлять на каждой итерации шаг, доступ к более медленной ОЗУ на каждой итерации.

Разница в производительности сильно зависит от процессора и от типа памяти, используемой как для основной ОЗУ, так и для кэша, а также того, как реализованы std::allocator (и в конечном итоге operator new и malloc), поэтому общее число невозможно дать. (Примечание: большая разница означает плохое отношение к ОЗУ к кешу, но может также означать неудачную реализацию в списках)

Ответ 3

Не уверен, могу ли я это объяснить правильно, но здесь мой взгляд (я думаю по строкам переведенной машинной инструкции ниже:),

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

Список итераторов (связанный список http://www.sgi.com/tech/stl/List.html): Когда вы увеличиваете итератор списка (заостренный объект), местоположение прямой линии связи расположено путем добавления некоторого числа к основанию объекта, указанного и затем загруженного как новое значение итератора. Для этого имеется более одного доступа к памяти и работает медленнее, чем операция векторной итерации.