Один из наиболее полезных случаев, которые я нахожу для связанных списков, работающих в критически важных для производительности областях, таких как сетка и обработка изображений, физические движки и трассировка лучей, заключается в том, что при использовании связанных списков фактически улучшается локальность ссылок и уменьшается выделение кучи, а иногда даже уменьшается память. использовать по сравнению с прямыми альтернативами.
Теперь это может показаться полным оксюмороном, что связанные списки могут делать все это, поскольку они печально известны тем, что часто делают обратное, но у них есть уникальное свойство в том, что каждый узел списка имеет фиксированный размер и требования выравнивания, которые мы можем использовать, чтобы их можно было хранить непрерывно и извлекать в постоянном времени так, как это невозможно.
В результате давайте возьмем случай, когда мы хотим сделать аналогичный эквивалент хранения последовательности переменной длины, которая содержит миллион вложенных подпоследовательностей переменной длины. Конкретным примером является индексированная сетка, хранящая миллион полигонов (некоторые треугольники, некоторые четырехугольники, некоторые пятиугольники, некоторые шестиугольники и т. Д.), И иногда многоугольники удаляются из любой точки сетки, а иногда многоугольники перестраиваются для вставки вершины в существующий многоугольник или удалить один. В этом случае, если мы сохраним миллион крошечных std::vectors, мы столкнемся с выделением кучи для каждого отдельного вектора, а также с потенциально взрывоопасным использованием памяти. Миллион крошечных SmallVectors может не так сильно страдать от этой проблемы в обычных случаях, но тогда их предварительно выделенный буфер, который не выделяется отдельно в куче, может все еще вызывать взрывное использование памяти.
Проблема здесь в том, что миллион std::vector экземпляров будет пытаться хранить миллион вещей переменной длины. Вещи переменной длины, как правило, нуждаются в распределении кучи, поскольку они не могут быть очень эффективно сохранены непрерывно и удалены в постоянном времени (по крайней мере, простым способом без очень сложного распределителя), если они не сохранили свое содержимое в другом месте в куче.
Если вместо этого мы сделаем это:
struct FaceVertex
{
// Points to next vertex in polygon or -1
// if we're at the end of the polygon.
int next;
...
};
struct Polygon
{
// Points to first vertex in polygon.
int first_vertex;
...
};
struct Mesh
{
// Stores all the face vertices for all polygons.
std::vector<FaceVertex> fvs;
// Stores all the polygons.
std::vector<Polygon> polys;
};
... тогда мы значительно сократили количество выделений кучи и количество кешей. Вместо того, чтобы требовать выделения кучи и потенциально обязательных пропусков кэша для каждого отдельного многоугольника, к которому мы обращаемся, мы теперь требуем, чтобы выделение кучи только тогда, когда один из двух векторов, сохраненных во всей сетке, превышает их емкость (амортизированная стоимость). И хотя шаг по переходу от одной вершины к другой может по-прежнему вызывать пропуск доли кеша, он все равно часто меньше, чем если бы каждый отдельный полигон хранил отдельный динамический массив, поскольку узлы хранятся смежно, и существует вероятность, что соседняя вершина может быть доступным до выселения (особенно учитывая, что многие полигоны будут добавлять свои вершины сразу, что делает львиную долю вершин многоугольника совершенно смежной).
Вот еще один пример:
... где ячейки сетки используются для ускорения столкновения частица-частица, скажем, для 16 миллионов частиц, движущихся в каждом отдельном кадре. В этом примере сетки частиц, используя связанные списки, мы можем переместить частицу из одной ячейки сетки в другую, просто изменив 3 индекса. Стирание из одного вектора и возвращение к другому может быть значительно более дорогостоящим и приводить к большему выделению кучи. Связанные списки также уменьшают объем памяти ячейки до 32 бит. Вектор, в зависимости от реализации, может предварительно выделить свой динамический массив так, что он может занять 32 байта для пустого вектора. Если у нас около миллиона ячеек сетки, это большая разница.
... и именно здесь я нахожу связанные списки наиболее полезными в наши дни, и я специально нахожу разнообразие «индексированных связанных списков» полезным, поскольку 32-разрядные индексы вдвое уменьшают требования к памяти для ссылок на 64-разрядных компьютерах, и они подразумевает, что узлы хранятся в массиве непрерывно.
Часто я также комбинирую их с индексированными свободными списками, чтобы разрешить постоянное удаление и вставку в любом месте:
В этом случае индекс next указывает либо на следующий свободный индекс, если узел был удален, либо на следующий использованный индекс, если узел не был удален.
И это пример использования номер один, который я нашел для связанных списков в эти дни. Когда мы хотим сохранить, скажем, миллион подпоследовательностей переменной длины, усредняя, скажем, по 4 элемента каждый (но иногда с элементами, которые удаляются и добавляются в одну из этих подпоследовательностей), связанный список позволяет нам хранить 4 миллиона узлы связанного списка непрерывно вместо 1 миллиона контейнеров, каждый из которых выделяется кучей по отдельности: один гигантский вектор, т.е. не миллион маленьких.