C++ Academy

🖥 Что нужно учитывать, используя std::vector?



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



std::vector имеет:



➕ Доступ к произвольному элементу за O(1).



➖ Проблема: При превышении capacity — долгая вставка нового элемента (даже в конец), требующая поэлементного копирования.



Решение: С этим можно побороться, если зарезервировать заранее всю нужную память под все элементы, но мы редко знаем каким будет максимальное количество элементов. И памяти на все процессы так не напасёшься, даже учитывая оптимизацию современных ОС: когда ОС физически выделяет память только когда процесс начинает её использовать.





Хороший cache coherence:

➕ В общем случае это означает более быстрый обход контейнера vector по сравнению с контейнерами а-ля list (map, set, forward_list etc).



➖ Проблема: В частности, нужно разбираться с cache sharing.

Если vector параллельно обходят два потока и каждый из них модифицирует его содержимое, то вероятно кэши этих потоков будет смотреть на смежную область памяти vector-а. Тогда каждая из записей будет инвалидировать содержимое кеша ядра другого потока, тем самым приводя к регулярному refetch-у. В некоторых корнер кейсах замена vector на list может внезапно привести к улучшению перфоманса.



Решение: Лечится такая проблема обычно увеличением размера элемента до размера кешлайна. Либо же выдачей каждому потоку по N элементов, где (N * sizeof(ElementT)) == cacheline size.



@cpluspluc