Оптимальный размер блока для развернутых связанных списков
Я изучаю основные структуры данных и до сих пор попал в развернутые связанные списки. У меня есть книга, в которой говорится, что, если я сделаю так, чтобы количество элементов в каждом блоке было не больше размера одной строки кэша, я получу лучшую производительность кэша из улучшенной области памяти. У меня есть два вопроса по этому поводу.
Во-первых, оптимально ли сделать его точно таким же, как размер строки кэша, или любой меньший размер, который неделим, хорош?
Во-вторых, я обнаружил в этом посте, что размеры строк для кэша L1/2/3 составляют 64 байта. Я просто хотел убедиться, что это для всех моделей i7? У меня MBP середины 2014 года, и я пытаюсь создать развернутый связанный список, который будет оптимальным для моей системы. Есть ли терминальная команда для проверки размера строки кэша?
1 ответ
Доступ к элементу узла в развернутом связанном списке очень быстрый1.
Все байты в кэшированной строке доступны очень быстро.
Здесь мы видим аналогию: развернутые связанные списки предназначены для того, чтобы сжимать элементы в непрерывную область памяти, чтобы они были более дружественными к кешу.
Чтобы понять, почему проблема может иметь размер узла больше, чем строка кэша, рассмотрим архитектуру с кэшем (любой ассоциативности), имеющую только одну строку размера S.
Рассмотрим также развернутый связанный список с размером узла 2S.
Наконец, давайте проанализируем ошибки кэша алгоритма
For each node N
Let avg = ArithmeticMean(N.items)
For i = 0 To N.numerOfItems - 1
N.items[i] = avg
Это устанавливает значение каждого элемента (предположим, полный узел) в узле к среднему арифметическому узла.
Чтобы вычислить среднее значение, все элементы должны быть суммированы, доступ к первому элементу запускает загрузку кеша (+1). В первой половине элементы считываются из только что загруженной строки кэша.
Как только к первому элементу во второй половине обращаются, требуется другая загрузка кеша, и старая строка очищается (+2). До конца узла эта вторая загрузка выполняет все будущие обращения.
Как только мы получим среднее значение, к первой половине снова обращаются с последующей загрузкой кеша (+3), высвобождая строку со второй половиной, которая вскоре будет перезагружена позже (+4).
Алгоритм запускает 4 загрузки кеша для узла. Если мы сделаем размер узла S и повторим анализ, мы увидим, что требуется только загрузка кеша.
Делая узел меньше, чем строки кеша, это тоже подойдет, некоторые узлы могут в итоге разделить одну и ту же строку, но в целом это не повредит. Однако при этом будет использоваться больше строк по сравнению с общим количеством элементов в списке, поскольку каждый из них находится по своему адресу, и они не обязательно расположены близко друг к другу. В пределе, если S=1, у нас есть обычный связанный список.
Пока что все не очень старые процессоры Intel имеют 64-байтовую строку кэша.
Это может очень хорошо измениться, хотя.
Чтобы увидеть информацию о вашем кэше процессора, вы можете обратиться к этому вопросу: найти размер кэша L2 в Linux2.
Сводится к использованию sudo dmidecode -t cache,
1 Спасибо за то, что для хранения элементов используется массив, обеспечивающий произвольный доступ.
2 Для всех уровней кэша Infact.