Как хранить элементы в стеке LIFO с возможностью кэширования?
РЕДАКТИРОВАТЬ / ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ:
Похоже, что мое понимание строк кэша было неправильным, что делает этот вопрос неактуальным и вводящим в заблуждение. Я думал, что всякий раз, когда процессор пытается получить память по определенному индексу, он также захватывает индексы сразу после первого, что НЕ верно. См. Как работают строки кэша? для справки.
Я собирался написать контейнер данных для хранения непрерывного блока памяти изменяемого размера, в котором к элементам можно было бы получить доступ только с одной стороны путем нажатия или извлечения - по сути, это стек LIFO. Я много читал о шаблонах доступа к кэшу ЦП и памяти и хотел, чтобы указанный контейнер был максимально дружественным к кэшу.
Итак, я взглянул на распространенные реализации стеков LIFO в Интернете. Большинство из них предлагают использовать динамический массив в качестве основы и получать доступ к данным путем добавления или удаления элементов из конца массива. В этом случае пустой пробел мощности сохраняется после данных следующим образом:
stack bottom stack top
array begin V array end
V V V
|V data V |V gap |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|8 |7 |6 |5 |4 |3 |2 |1 |0 | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| cache line |
Однако мне это кажется не очень удобным для кеша. Всякий раз, когда кто-то просматривает элемент на вершине стека, процессор извлекает память из пробела, содержащего мусор, или, по крайней мере, я так понимаю.
Будет ли более производительным подход, при котором пробел выглядит как начало блока памяти и данные в конце? В этом случае индексы элементов будут поменяны местами, как и в случае с низом и верхом. В этом случае строка кэша может содержать больше элементов, например:
stack top stack bottom
V V
| gap |V data V |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | |0 |1 |2 |3 |4 |5 |6 |7 |8 |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| cache line |
Правильно ли я понимаю здесь? Какой подход более производительный и дружественный к кэшу?
Я могу быть совершенно неправ в своих предположениях. Как я уже сказал, большинство реализаций, которые я видел, используют первый подход, поэтому в этом что-то должно быть.
Ваше здоровье!
Итак, короткий ответ: «Это зависит»?
Два вопроса. Это имеет значение? Вам нужна микрооптимизация? Если да - найдите другой подход
@0___________ Нет, не совсем. Мне просто интересно, будет ли это действительно иметь значение и иметь какое-то значение.
Я думаю, что более важным для производительности является то, что вы хотите использовать блок памяти изменяемого размера, что означает, что всякий раз, когда вы достигаете максимальной емкости, вам нужно скопировать весь массив в новый выделенный больший массив. Это будет стоить вам дорого (за исключением того, что вы можете избежать этого, ограничив максимальный размер и в первую очередь выделив этот объем памяти).
Ответы 1
Стеки LIFO, использующие массив, одинаково удобны для кэширования в любом направлении роста, если только у вас нет определенного шаблона размеров, который благоприятствует выделению нечетного размера и росту вниз.
API-интерфейсы для эффективного перераспределения (без копирования данных), такие как Linux mremap или C realloc, разработаны с учетом добавления нового пространства в конце выделения, а не в начале, так что это аргумент в пользу обычного способа, если ваш стек может выйти за пределы первоначального распределения. По крайней мере, если вы используете API распределения, который их поддерживает, а не как урезанный new/delete в C++, который по сути заставляет std::vector отстой.
В остальном они равны, если только ваша верхняя граница обычно не на 1 или 2 элемента больше кратного 64 байтам, как вы показали здесь, чтобы ваша другая версия выглядела хорошо. В этой версии первый помещенный элемент находится в отдельной строке кэша, но вершина стека еще не перешла в новую строку кэша.
Если вы вставите еще один элемент во вторую диаграмму, это будет единственный используемый элемент в строке кэша. Это выглядит хорошо только потому, что вы выбрали несколько элементов для текущего состояния стека, которые хорошо работают с несовпадением (относительно границ строки кэша), которое вы выбрали для первого элемента («дна» стека, на самом высоком уровне). адрес для вашего растущего стека).
При использовании вашего дизайна с растущим зазором спереди потенциально первый помещенный элемент (самый высокий адрес) находится в той же строке кэша, что и некоторые другие полезные данные, поэтому сохранение горячей строки кэша может быть полезно (если ваш стек часто становится пустым, поэтому вы действительно получаете доступ к этому элементу).
Распределители памяти часто округляют выделения до кратного большего размера, например 16 байт, но в одной строке кэша все равно могут быть и другие выделения.
Тем не менее, если вы не знаете чего-то особенного об ожидаемых размерах стека и/или о том, что будет дальше, обычно вам нужно выделить часть памяти, кратную размеру строки кэша.
Интересный факт: стек вызовов asm увеличивается на основных ISA (и соглашениях о вызовах для ISA, таких как MIPS, которые не поддерживают одно направление роста стека). например x86 push и call уменьшают регистр указателя стека (RSP). Причинами этого являются не эффективность кэша, а более историческая, возникшая еще до того, как у процессоров появились кэши. Однако для кэша процессора это не представляет особых проблем.
Стеки CPU/asm распределяются таким образом, что строка кэша с наивысшим адресом используется полностью, в отличие от вашего, где конец выделения не является концом строки кэша. (Обычно «стек» кратен размеру страницы, поэтому в той же строке рядом с ним в любом случае не будет других элементов.)
Спасибо за пояснения и ссылки. Вашей точки зрения на realloc достаточно, чтобы сделать 2-й подход не очень полезным. «Вы показали здесь, чтобы ваша другая версия выглядела хорошо» - это правда, я ошибался насчет того, как работают строки кэша (добавил РЕДАКТИРОВАНИЕ по этому поводу).
@ilikebananas: О, понятно; да, строки кэша естественным образом выровнены, поэтому границы фиксированы. Стеки, которые растут вниз, могут работать, если вы зарезервируете адресное пространство под ними для увеличения (путем сопоставления туда большего количества страниц), так что в этом нет ничего принципиально проблематичного, поэтому стеки вызовов asm на самом деле работают таким образом, не создавая проблем с производительностью. Но для того, чтобы сделать это для вашей собственной структуры данных на языке высокого уровня, потребуется много работы на низком уровне.
Верхняя часть стека время от времени меняется. Независимо от того, растет ли ваш стек в сторону более высоких или меньших адресов памяти, количество элементов в стеке в той же строке кэша, что и вершина стека, будет меняться, проходя через все возможные значения. Направление роста не влияет на это, если только конкретное место, где начинается или заканчивается ваш содержащий массив, и частотное распределение количества элементов в стеке не приводят к определенным закономерностям относительно кеша.