Исправление pftBest, (текущая версия) :
в режиме вставка в случайное место, вектор работает быстрее связного списка.
Объясни почему не понимаю.
Все верно, просто надо учитывать особенности работы современных процессоров. Обращение к оперативной памяти в 20 - 200 раз дольше чем обращение в кеш.
Разница в том, что элементы связного списка все находятся в разных местах в памяти, и когда ты ищешь место для вставки, на каждом переходе происходит cache miss и данные берутся из оперативки. А в векторе все элементы лежат рядом, и потому процессор может легко предсказать обращения к ним, и они все попадают в кеш.
Вот например график
https://kjellkod.files.wordpress.com/2012/02/pod_x64_10k_elements.png
по которому видно, что vector становится медленнее списка только тогда когда размер каждого элемента превышает 200 байт, и ему приходится действительно много данных копировать.
Исходная версия pftBest, :
Объясни почему не понимаю.
Все верно, просто надо учитывать особенности работы современных процессоров. Обращение к оперативной памяти в 20 - 200 раз дольше чем обращение в кеш.
Разница в том, что элементы связного списка все находятся в разных местах в памяти, и когда ты ищешь место для вставки, на каждом переходе происходит cache miss и данные берутся из оперативки. А в векторе все элементы лежат рядом, и потому процессор может легко предсказать обращения к ним, и они все попадают в кеш.
Вот например график
https://kjellkod.files.wordpress.com/2012/02/pod_x64_10k_elements.png
по которому видно, что vector становится медленнее списка только тогда когда размер каждого элемента превышает 200 байт, и ему приходится действительно много данных копировать.
