Тянет ли доступ к одному элементу структуры всю структуру в Cache?

Question

Я читал Ульриха Дреппера, " Что каждый программист должен знать о памяти " и в разделе 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 байта и 4 тыс. Страниц. *

Простая итерация по связанному списку становится значительно медленнее по мере роста структуры, даже если на самом деле не осуществляется доступ к чему-либо кроме указателя.

Answer 1

Аппаратное обеспечение вообще не знает о структуре. Но это правда, что оборудование загружает в кеш несколько байтов вокруг байтов, к которым вы фактически обращаетесь. Это потому, что строка кэша имеет размер. Он работает не для байтового доступа, а, например, для Размер 16 байт за раз.

Вы должны быть осторожны при упорядочении членов структуры, чтобы часто используемые члены были близки друг к другу. Например, если у вас есть следующая структура:

struct S {
  int foo;
  char name[64];
  int bar;
};

Если переменные-члены foo и bar используются очень часто, аппаратное обеспечение будет загружать в кэш байты вокруг foo, а когда вы получите доступ к bar, ему придется загружать байты вокруг bar. Даже если эти байты вокруг foo и вокруг бара никогда не используются. Теперь перепишите вашу структуру следующим образом:

struct S {
  int foo;
  int bar;
  char name[64];
};

Когда вы будете использовать foo, оборудование будет загружать в кеш байты вокруг foo. Когда вы будете использовать bar, bar уже будет в кеше, потому что bar содержится в байтах вокруг foo. Процессору не придется ждать появления бара в кэше.

Ответ: : доступ к одному элементу структуры не вытягивает всю структуру в кеш, но вытягивает некоторый другой элемент структуры в кеш.

Answer 2

Аппаратное обеспечение не знает структуру структуры, а просто загружает несколько байтов вокруг элемента, к которому осуществляется доступ, в кэш. И да, замедление от более крупных структур связано с тем, что они будут распределены по большему количеству строк кэша.

Answer 3

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

Answer 4

"Простая итерация по связанному списку становится значительно медленнее по мере роста структуры, даже при том, что фактически ничего не происходит, кроме указателя."

При NPAD = 0 каждая строка кэша содержит 8 узлов списка, поэтому вы можете понять, почему это быстрее.

При NPAD = 7, 15, 31 необходимо загружать только одну строку кэша для каждого узла списка, и можно ожидать, что все они будут иметь одинаковую скорость - одна ошибка кэша на узел. Но современный менеджер памяти будет заниматься спекулятивным кэшированием. Если у него есть резервная емкость (что, вероятно, имеет место, потому что с современной памятью он может выполнять несколько операций чтения параллельно с основной памятью), тогда он начнет загружать память рядом с используемой памятью. Хотя это связанный список, если вы построили его любым из очевидных способов, есть хороший шанс, что вы обращаетесь к памяти последовательно. Таким образом, чем ближе друг к другу в памяти находятся узлы списков, тем успешнее будет кэш с точки зрения того, что у вас уже есть то, что вам нужно.

В худшем из возможных сценариев, когда ваша память извлекается из подкачки во время ее использования, ваша программа будет ограничена дисковым вводом / выводом. Вполне возможно, что скорость вашего прохождения по списку будет полностью зависеть от того, сколько узлов на странице, и вы можете увидеть, что затраченное время прямо пропорционально размеру узла, вплоть до 4k. Я не пробовал, однако, и операционная система будет умной со свопом так же, как MMU умна с основной памятью, так что это не обязательно так просто.

Answer 5

Несмотря на то, что ЦП может успешно справляться с нагрузками и хранит всего один байт, кэши имеют дело только с данными размера «кешлайн». В учебниках по компьютерной архитектуре это также называется «размер блока».

В большинстве систем это 32 или 64 байта. Он может отличаться от одного процессора к другому и даже иногда от одного уровня кэша к следующему.

Кроме того, некоторые процессоры выполняют умозрительную предварительную выборку; это означает, что при последовательном доступе к строкам кэша 5 и 6 он будет пытаться загрузить строку кэша 7 без вашего запроса.

Answer 6

Обычно кэш L1 использует виртуальные адреса , если вы обращаетесь к члену struct, в кэш попадает определенное количество байтов (одна строка кэша , размер обычно от 8 до 512 байт). Поскольку все элементы struct выровнены в памяти рядом друг с другом, вероятность того, что вся структура попадет в кэш, несколько велика (зависит от sizeof(struct your_struct)) ...