Один из наиболее полезных случаев, который я нахожу для связанных списков, работающих в критических по производительности областях, таких как обработка сетки и изображений, физические движки и трассировка лучей, при использовании связанных списков actua lly улучшает локальность ссылок и уменьшает распределение кучи, а иногда даже уменьшает использование памяти по сравнению с прямыми альтернативами.
Теперь это может показаться полным оксюмороном, что связанные списки могут делать все это, потому что они часто печатаются в обратном порядке, но имеют уникальное свойство, поскольку каждый узел списка имеет фиксированный размер и требования к выравниванию, которые мы могут использовать их, чтобы они сохранялись смежно и удалялись в постоянное время способами, которые не могут иметь переменные величины.
В результате получим случай, когда мы хотим сделать аналогичный эквивалент хранения последовательности переменной длины, которая содержит миллион вложенных подпоследовательностей переменной длины. Конкретным примером является индексированная сетка, в которой хранится миллион многоугольников (некоторые треугольники, некоторые квадратики, некоторые пятиугольники, некоторые шестиугольники и т. Д.), А иногда полигоны удаляются из любой точки сетки, а иногда многоугольники перестраиваются, чтобы вставить вершину в существующий многоугольник или удалите один. В этом случае, если мы храним миллион крошечных 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 миллион контейнеров, каждый из которых распределен по отдельности: один гигантский вектор, т. е. не миллион маленьких.
Ответ на ваш второй абзац занимает около семестра. –
По моему мнению, см. Http://punchlet.wordpress.com/2009/12/27/letter-the-fourth. И поскольку это похоже на опрос, вероятно, это должен быть CW. – 2010-03-11 22:35:50
@ Нил, милый, хотя я сомневаюсь, что С.С. Льюис одобрит. – Tom