Влияет ли расстояние между областями чтения и записи на производительность кэша?

Question

У меня есть буфер размером n, который заполнен, и буфер-преемник размера n, который пуст. Я хочу вставить значение в первый буфер в позиции i, но для этого мне нужно переместить диапазон памяти вперед, поскольку буфер заполнен (т. Е. Последовательная вставка). У меня есть два варианта здесь:

Предпочитают писать близко к чтению (смежно):

1. Вставить последнее значение первого буфера во второй.
2. Перемещение между i и n - 1 в первом буфере на один шаг вперед.
3. Вставить на i.

Предпочитают меньше шагов:

1. Скопируйте диапазон от i до n - 1 из первого во второй буфер.
2. Вставить в i.

Большая часть того, что я могу найти, говорит только о локальности в контексте read , и мне интересно, следует ли учитывать расстояние между памятью чтения и записи.

Answer 1

это компонент, находящийся глубоко в структуре данных на самом низком уровне, где n равно small , а константа

по маленьким, я предполагаю, что вы имеете в виду меньше, чем L1 CPUразмер кеша где-то меньше 1 МБ или кэш-память второго уровня до 10-20 МБ, в зависимости от вашего процессора, то нет,

Мне интересно, следует ли учитывать расстояние между чтением и памятью записи.

иногда;если все данные могут поместиться в кэш CPU L1, L2, L3, на котором выполняется процесс, то, как вы думаете, произвольный доступ означает, что при применении все это будет иметь одинаковую задержку.Вы можете получить мельчайшие детали и углубиться в различия между кэшем L1, L2, L3, но ради краткости (и я просто принимаю это как должное) в любом месте в пределах памяти граница это все та же задержка для доступа.Так что в вашем случае, когда N мало, и если все это помещается в кэш процессора (первое из многих границ), то это будет способ и эффективность, в которой вы решили перемещать / изменять значения, и сколько раз вы в конечном итоге это делаетекоторый влияет на производительность (время для завершения).

Теперь, если N были большими, например, в системе с 2 или более сокетами (через intel QPI или UPI) и эти данные находились в оперативной памяти DDRкоторый расположен через путь QPI или UPI к памяти, затемняет контроллер памяти другого ЦП, тогда определенно да большой удар по производительности (условно говоря), потому что теперь граница была пересечена, и это было бы то, чтоНЕ мог поместиться в кэш ЦП, на котором выполнялся процесс (который был изначально извлечен из DIMMS LOCAL в этот контроллер памяти ЦП), теперь влечет за собой накладные расходы на общение с другим ЦП по пути QPI или UPI (хотя все еще очень быстро по сравнению спредыдущая архитектура) и этот другой процессор затем извлекает данные из набора памяти DIMMS и отправляет его обратно через QPI или UPI в процессор, на котором выполняется ваш процесс.

Таким образом, когда вы превышаете ограничение кэша L1 в L2, происходит снижение производительности, также как и в кэше L3, все в одном ЦП.когда процесс должен многократно извлекать из своего локального набора диммов больше данных, которые он не может вписать в кэш, то это влияет на производительность.И когда эти данные не находятся на локальных по отношению к диммерам, то процессор = медленнее.И когда эти данные не находятся на одной материнской плате и проходят через какое-то высокоскоростное волокно RDMA = медленнее.Когда через Ethernet еще медленнее ... и т. Д.

Answer 2

Влияет ли расстояние между точками чтения и записи на производительность кэша?

Да. Обычно (за исключением редких ситуаций, когда ЦП может записать всю строку кеша с новыми данными), ЦП должен извлечь самую последнюю версию строки кеша в свой кеш перед выполнением записи. Если строка кэша уже находится в кэше (например, из-за предыдущего чтения некоторых других данных, которые оказались в той же строке кэша), то ЦПУ не нужно будет извлекать строку кэша перед выполнением записи.

Обратите внимание, что есть и другие причуды (псевдоним кеша, пропуски TLB и т. Д.); и все это зависит от конкретной ситуации и от того, какой ЦП (например, если все данные процесса помещаются в кэш ЦП, нет задействованной общей памяти и нет переключателей задач или других процессов, использующих ЦП; тогда можно предположить, что все равно всегда будет в кеше).

Я хочу вставить значение в первый буфер в позиции i, но для этого нужно переместить диапазон памяти вперед, поскольку буфер заполнен (т. Е. Последовательная вставка).

Без дополнительной информации (как часто это происходит, сколько данных задействовано и т. Д.) Я не могу сделать никаких предложений. Однако (на первый взгляд, без особой информации) сама идея кажется плохой. В частности, звучит так, будто вы добавляете кучу хлопот, чтобы заставить два меньших массива вести себя точно так же, как если бы у одного большего массива (а затем беспокоиться о стоимости вставки, потому что массивы вообще не годятся для вставки).