Доступ к единственному участнику структуры вытягивают всю структуру в Кэш?
Я читал Ulrich Drepper, "Что каждый программист должен знать о памяти" и в разделе 3.3.2 Измерения Эффектов Кэша (на полпути ниже на страницу) это производит мне впечатление, что доступ к любому члену структуры заставляет целую структуру быть вытянутой в кэш ЦП.
Это корректно? Если так, как аппаратные средства знают о расположении этих структур? Или код, сгенерированный компилятором так или иначе, вынуждают всю структуру быть загруженной?
Или является, прежде всего, должно замедление от использования больших структур к TLB промахи, вызванные структурами, распространяемыми через большее количество страниц памяти?
Структура в качестве примера, используемая Drepper:
struct l {
struct l *n;
long int pad[NPAD];
};
Где sizeof(l) определяется NPAD равняется 0, 7, 15 или 31 получающийся в структурах, которые являются 0, 56, 120, и на расстоянии в 248 байтов и принимающие строки кэша, которые составляют 64 байта и 4k страницы.
Просто итерация через связанный список становится значительно медленнее, когда структура растет, даже при том, что ни к чему кроме указателя на самом деле не получают доступ.
6 ответов
Аппаратное обеспечение вообще ничего не знает о структуре. Но это правда, что оборудование загружает в кеш несколько байтов вокруг байтов, к которым вы действительно обращаетесь. Это потому, что строка кэша имеет размер. Он работает не с побайтовым доступом, а с размером, например, 16 байтов за раз.
Вы должны быть осторожны при упорядочивании элементов структуры, чтобы часто используемые элементы располагались близко друг к другу. Например, если у вас есть следующая структура:
struct S {
int foo;
char name[64];
int bar;
};
Если переменные-члены foo и bar используются очень часто, оборудование будет загружать в кеш байты вокруг foo, и когда вы получите доступ к bar, ему придется загрузить байты вокруг бара. Даже если эти байты вокруг foo и around bar никогда не используются. Теперь перепишите структуру следующим образом:
struct S {
int foo;
int bar;
char name[64];
};
Когда вы будете использовать foo, оборудование загрузит в кеш байты вокруг foo. Когда вы будете использовать bar, bar уже будет в кеше, потому что bar содержится в байтах вокруг foo. ЦП не будет ждать, пока панель окажется в кеше.
Ответ : доступ к одному члену структуры не извлекает всю структуру из кеша, а втягивает какой-либо другой член структуры в кэш.
Доступ к члену структуры не вызывает большего снижения производительности, чем доступ к любой другой области памяти. Фактически, может произойти улучшение производительности, если вы обращаетесь к нескольким членам структуры в одной и той же области, поскольку другие члены могут быть кэшированы при первом доступе.
Обычно кэш L1 использует виртуальных адресов , если вы обращаетесь к члену структуры , определенное количество байтов попадает в кеш ( одна строка кэша , размер обычно от 8 до 512 байт). Поскольку все члены struct выровнены бок о бок в памяти, вероятность того, что вся структура попадет в кеш, несколько велика (зависит от sizeof (struct your_struct) ) ...
Аппаратное обеспечение не знает макета структуры, а просто загружает несколько байтов вокруг элемента, к которому осуществляется доступ, в кеш. И да, замедление из-за больших структур происходит потому, что они затем будут распределены по большему количеству строк кэша.
В то время как ЦП может успешно справляться с нагрузками и хранить до одного байта, кеши имеют дело только с данными размером "кэш-строка". В учебниках по компьютерной архитектуре это также известно как «размер блока»
. В большинстве систем это 32 или 64 байта. Он может отличаться от одного процессора к другому и даже иногда от одного уровня кэша к другому.
Кроме того, некоторые процессоры выполняют спекулятивную предварительную выборку; это означает, что если вы последовательно обращаетесь к строкам кэша 5 и 6, он попытается загрузить строку кэша 7 без вашего запроса.
«Просто итерация по связанному списку становится значительно медленнее по мере роста структуры, даже если фактически осуществляется доступ только к указателю.»
При NPAD = 0 каждая строка кэша содержит 8 узлов списка, так что вы можете понять, почему это самый быстрый.
При NPAD = 7, 15, 31 необходимо загрузить только одну строку кеша для каждого узла списка, и вы можете ожидать, что все они будут иметь одинаковую скорость - одну промах в кэше на узел. Но современный диспетчер памяти будет делать спекулятивное кэширование. Если у него есть свободная емкость (что, вероятно, есть, потому что с современной памятью он может выполнять несколько операций чтения параллельно с основной памятью), он начнет загружать память, близкую к памяти, которую вы используете. Несмотря на то, что это связанный список, если вы составили его любым из очевидных способов, есть большая вероятность, что вы повторный доступ к памяти по очереди. Таким образом, чем ближе друг к другу в памяти узлы ваших списков, тем успешнее будет кэш с точки зрения того, что вам уже нужно.
В худшем из возможных сценариев, когда ваша память извлекается из подкачки, когда вы используете это ваша программа будет ограничена дисковым вводом-выводом. Возможно, ваша скорость прохождения по списку будет полностью определяться количеством узлов на странице, и вы можете увидеть, что затраченное время прямо пропорционально размеру узла, вплоть до 4k. Однако я не пробовал, и ОС будет умна с подкачкой, так же как MMU умна с основной памятью, так что это не обязательно так просто.
тем более успешным будет кэш с точки зрения того, что у вас уже есть то, что вам нужно.В наихудшем возможном сценарии, когда ваша память извлекается из подкачки, когда вы ее используете, ваша программа будет ограничена дисковым I / О. Возможно, ваша скорость прохождения по списку будет полностью определяться количеством узлов на странице, и вы можете увидеть, что затраченное время прямо пропорционально размеру узла, вплоть до 4k. Однако я не пробовал, и ОС будет умна с подкачкой, так же как MMU умна с основной памятью, так что это не обязательно так просто.
тем более успешным будет кэш с точки зрения того, что у вас уже есть то, что вам нужно.В наихудшем возможном сценарии, когда ваша память извлекается из подкачки, когда вы ее используете, ваша программа будет ограничена дисковым I / О. Возможно, ваша скорость прохождения по списку будет полностью определяться количеством узлов на странице, и вы можете увидеть, что затраченное время прямо пропорционально размеру узла, вплоть до 4k. Однако я не пробовал, и ОС будет умна с подкачкой так же, как MMU умна с основной памятью, так что это не обязательно так просто.
Возможно, ваша скорость прохождения по списку будет полностью определяться количеством узлов на странице, и вы можете увидеть, что затраченное время прямо пропорционально размеру узла, вплоть до 4k. Однако я не пробовал, и ОС будет умна с подкачкой так же, как MMU умна с основной памятью, так что это не обязательно так просто. Возможно, ваша скорость прохождения по списку будет полностью определяться количеством узлов на странице, и вы можете увидеть, что затраченное время прямо пропорционально размеру узла, вплоть до 4k. Однако я не пробовал, и ОС будет умна с подкачкой, так же как MMU умна с основной памятью, так что это не обязательно так просто.