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

Question

Я видел это видео на YouTube: https://www.youtube.com/watch?v=YQs6IC-vgmo в котором Бьярне говорит, что лучше использовать векторы, а не связанные списки. Я не в состоянии понять все это, поэтому кто-нибудь может объяснить, что он говорит, с точки зрения непрофессионала?

PS: я учусь в старшей школе и могу легко справляться со связанными списками, но я изо всех сил пытаюсь выучить векторы самостоятельно. Не могли бы вы предложить какие-либо источники для изучения векторов?

Answer 1

Преимущества вектора против связанного списка

Основным преимуществом векторных и связанных списков является локальность памяти.

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

Вектор гарантированно хранит все содержащиеся элементы непрерывно. (Предметы рядом друг с другом, без пробелов;)

Примечание: возможны чрезмерные упрощения...;)

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

1. отсутствует кеш

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

Пример:

64-байтовый блок (обычный размер строки кэша) соответствует шестнадцати 32-битным целым числам одновременно. Следовательно, пропадание кеша (данные еще не в кеше -> требуется загрузка из основной памяти) происходит в самое раннее время после обработки 16 элементов с момента, когда первый элемент был помещен в кеш. Если используется связанный список, первый элемент вполне может быть единственным в пределах 64-байтового блока. Теоретически может случиться так, что потеря кеша происходит для каждого элемента списка.

Конкретный пример:

std::vector<std::uint32_t> v;
// somehow fill 64 values into v
std::uint32_t s{};
for(std::size_t i{0}; i<v.size(); ++i)
{
  s += v[i];
}

Представьте себе содержание v пока не кэшируется.

Что происходит при обработке данных в цикле for?

1) Проверьте, находится ли элемент v[0] в кэше. -> Нет

2) Извлечь 64 байта, начиная с адреса v[0], из основной памяти в строку кеша

3) Загрузите v[0] из кеша и обработайте, добавив его значение в s

4) Элемент v 1 находится в кеше? -> Да загружено с предыдущей выборкой, потому что соседний v[0]

5) Загрузите v 1 из кеша и обработайте, добавив его значение в s

6) Элемент v[2] находится в кеше? -> Да...

7) Загрузите v[2] из кеша и обработайте, добавив его значение в s

... так далее...

34) Элемент v[16] находится в кеше? -> Нет

35) Извлечь 64 байта, начиная с адреса v[16], из основной памяти в строку кеша

36) Загрузите v[16] из кэша и обработайте, добавив его значение в s

37) Элемент v[17] находится в кеше? -> Да загружено с предыдущей выборкой, потому что соседний v[16]

так далее...

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

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

2. предварительная выборка

Вышеуказанный эффект усиливается функцией CPU, называемой "prefetcher".

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

Это, конечно, эффективно, если и только если вам действительно нужны данные из следующего подготовленного фрагмента.

Как обычно работают векторы (внутренне)?

Смотрите: C++ Vector, что происходит, когда он расширяет / перераспределяет в стеке?

Answer 2

Страуструп написал статью https://isocpp.org/blog/2014/06/stroustrup-lists , в которой говорится, что его неправильно поняли, и он не призывает избегать связанных списков.

Я не могу комментировать реализацию векторов и связанных списков на С++. Но вы говорите, что понимаете связанные списки, а не векторы. Могу сказать, что в Java люди понимали векторы, но не обязательно связные списки. C# имеет тип данных List, и большинство людей на самом деле не задумываются о том, реализован ли он как связанный список или как вектор. Вот хорошее обсуждение различий в условиях использования. https://www.reddit.com/r/learnprogramming/comments/15mxrt/what_are_the_real_world_applications_of_linked/ В одном комментарии говорится: «Данные, хранящиеся в связанном списке, после размещения в памяти останутся на том же месте. Это означает, что при изменении вашего связанного списка по размеру данные любых элементов не перемещаются (в памяти), поэтому на них можно смело указывать."

В статье Страуструпа говорится: «И, да, я рекомендую использовать std::vector по умолчанию. В более общем смысле используйте непрерывное представление, если нет веских причин не делать этого. Как и C, C++ предназначен для этого по умолчанию. Кроме того, пожалуйста, не делайте заявлений о производительности без измерений».

Я видел, как Страуструп в интервью сказал, что удаление элемента и перемещение их всех вверх выполняется очень быстро, и быстрее, чем удаление элемента из связанного списка. Но я полагаю, из этого не следует делать вывод, что он говорит, что связанные списки не имеют прецедентов.