Кэширование связанного списка — возможно ли это?
Я знаю, что массивы могут полностью использовать механизмы кэширования в архитектуре x86_64, встраиваясь в строки кэша и из-за их последовательной природы. Связанный список — это набор структур / объектов, связанных между собой указателями. Можно ли воспользоваться системой кэширования с такой структурой? Объекты связанного списка могут быть размещены в любом месте памяти
Решение
Это правда, что связанный список записей Можно быть где угодно, но они не иметь быть «просто где угодно». Например, вы можете выделить их из «зоны». Выделите кучу смежных записей одновременно, объедините их в список «свободных записей, которые являются смежными», а затем разложите их. Выделите другую зону, полную по мере необходимости. С некоторыми не очень чистыми приемами вы можете в конечном итоге перераспределить освобожденные записи и так далее.
Однако в большинстве случаев не стоит идти на все эти усилия.
Другие решения
Вы можете иметь несколько записей на один связанный элемент списка, то есть небольшой массив записей в каждом элементе. Это позволяет кэшировать несколько записей, сохраняя динамический характер списка.
Это развернутый список и вроде дает вам то, что вы после.
Возможно, вы можете иметь один элемент связанного списка, который будет содержать более 1 записи данных.
например рассмотрим ниже структуру.
struct myll{
int data[16];
char valid[16/8];
struct myll* next;
}
Таким образом, вы делаете гранулярность в виде 16 записей на узел. Тем не менее, у вас все еще есть возможность добавить больше записей, чем 16, используя другой узел & удалить, используя флаг «valid». Это немного болезненно для реализации, но зависит от ваших требований.
Похоже, несколько похоже Механизм используется для некоторых файловых систем.