Обход списка медленнее обхода вектора при равной сложности
Модуль хранит 2 млн записей в std::list и полностью обходит их каждую секунду. После замены контейнера на std::vector (с тем же алгоритмом и той же асимптотикой O(n)) время обхода упало в несколько раз, perf показал резкое падение промахов кэша.
Как вы объясните результат на собеседовании?
- У `std::list` обход имеет сложность O(n log n) из-за хранения размера, у вектора — O(n)
- Дело в аллокаторе по умолчанию: с пуловым аллокатором узлы легли бы плотно, и `std::list` показал бы ровно ту же скорость обхода, что и вектор
- Узлы списка разбросаны по куче, и каждый переход по указателю — промах кэша; вектор лежит подряд, и префетчер читает данные наперёд
- `std::vector` при обходе автоматически распараллеливается компилятором, а узловые контейнеры — нет