Почему это так медленно перебирает большой список std :: list?

Question

Как следует из заголовка, у меня были проблемы с моей программой, в которой я использовал std :: list в качестве стека, а также для перебора всех элементов списка. Программа заняла слишком много времени, когда списки стали очень большими.

У кого-нибудь есть хорошее объяснение этому? Это поведение стека / кэша?

(Решил проблему, изменив списки на std :: vector и std :: deque (кстати, удивительная структура данных), и все вдруг стало намного быстрее)

РЕДАКТИРОВАТЬ: я не дурак, и я не доступ к элементам в середине списков. Единственное, что я сделал со списками, это удалил / добавил элементы в конце / начале и перебрал все элементы списка. И я всегда использовал итераторы для перебора списка.

Answer 1

Списки имеют ужасную (несуществующую) локальность кэша. Каждый узел имеет новое распределение памяти и может быть где угодно . Таким образом, каждый каждый раз, когда вы следуете указателем от одного узла к другому, вы переходите на новое, не связанное с этим место в памяти. И да, это немного ухудшает производительность. Промах в кеше может быть на два порядка медленнее, чем в кеше. В векторе или в deque, почти каждый доступ будет попаданием в кеш. Вектор - это один непрерывный блок памяти, поэтому итерации по нему выполняются настолько быстро, насколько это возможно. Deque - это несколько меньших блоков памяти, поэтому он вызывает случайную потерю кеша, но они все еще будут редкими, и итерация будет очень быстрой, поскольку вы получаете в основном попадания в кеш.

В списке будут почти все ошибки кеша. И производительность будет отстой.

На практике связанный список вряд ли является правильным выбором с точки зрения производительности.

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

Если вы перебираете вектор, это не проблема. Вы можете вычислить следующий адрес для чтения на лету, даже не проверяя память. Если вы сейчас читаете по адресу x, то следующий элемент будет расположен по адресу x + sizeof(T), где T - тип элемента. Таким образом, там нет никаких зависимостей, и ЦП может начать загрузку следующего элемента или следующего за ним сразу же, продолжая обрабатывать более ранний элемент. Таким образом, данные будут готовы для нас, когда они нам понадобятся, и это также поможет скрыть стоимость доступа к данным в ОЗУ.

В списке нам нужно следовать указателю с узла i на узел i+1, и пока i+1 не будет загружен, мы даже не знаем, где искать i+2. У нас есть зависимость от данных, поэтому процессор вынужден читать узлы по одному, и он не может начать читать будущие узлы раньше времени, потому что он еще не знает, где они находятся.

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

Answer 2

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

Answer 3

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

Answer 4

Посмотрите на следующую нить stackoverflow .

Answer 5

Простой ответ заключается в том, что итерации по вектору вообще не итерируются, а просто начинаются с основания массива и читают элементы один за другим.

Я вижу, что это помечено C ++, а не C, но, поскольку они делают то же самое под крышками, стоит указать, что вы можете добавлять элементы в начало и конец массива, выделяя его как угодно большой, и realloc () ing и memmove () между 2-мя массивами-компаньонами, если и когда вы выходите из комнаты. Очень быстро.

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

Точно так же C может поддерживать отрицательные подписки.

C ++ делает все это для вас с векторным классом STL, но все же стоит помнить, что происходит под одеялом.

Answer 6

[Правка: Я исправлен. std :: list не имеет оператора []. К сожалению.]

Трудно сказать по вашему описанию, но я подозреваю, что вы пытались получить доступ к элементам случайным образом (т.е. по индексу):

for(int i = 0; i < mylist.size(); ++i) { ... mylist[i] ... }

Вместо использования итераторов:

for(list::iterator i = mylist.begin(); i != mylist.end(); ++i) { ... (*i) ... }

Оба "вектора" и "deque" хороши при произвольном доступе, поэтому любой из них будет работать адекватно для этих типов --- O (1) в обоих случаях. Но «список» не хорош при произвольном доступе. Доступ к списку по индексу занял бы O (n ^ 2) времени по сравнению с O (1) при использовании итераторов.