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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

Answer 3

Посмотрите следующую ветку stackoverflow .

Answer 4

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

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) ... }

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