Какая часть объекта (содержащего std :: vectors) загружена в кэш L1 / L2 / L3?
Пожалуйста, смотрите следующую ссылку, страница 22 и далее:
ссылка выше предлагает, если у меня есть объект, содержащий векторы / массивы, как это:
class MyClass{
public:
double a[1000];
double b[1000];
};
и код ниже перебирает вектор MyClass и выполняет некоторые математические операции над std :: vector b:
std::vector<MyClass> y;
y.populateVector();
for(auto x : y){
//Iterate though x.b and do some math;
for(int i=0; i<1000; i++){
std::cout << x.b[i] << std::endl;
}
}
когда мы получаем каждый объект MyClass, все данные из обоих массивов будут загружены в строку кэша. Это правда? Я не думал, что данные a будет загружен в строку кэша, потому что адрес для доступа b будет рассчитан и загружен.
Я пытаюсь понять, какая часть объекта MyClass загружена в кэш по сравнению с полезными данными, необходимыми для обработки?
Я могу понять, если самый первый b элемент разделяет ту же строку кэша, что и самый последний a элемент, но я не думал, что весь объект будет загружен в кэш L2 / L3 только для обработки одной части объекта?
Решение
Зависит от того, как организована память в вашей системе. Если так получилось, что резервные массивы для a а также b расположены очень близко в памяти (поскольку ЦП обычно выдает большие чтения для заполнения кэша в надежде, что вы его используете), возможно, они будут загружены. Если нет, я не вижу причин для чтения b будет означать что-нибудь делать с a кроме попыток прочитать некоторые указатели, откуда класс фактически находится в памяти.
Что он показывает, так это то, что использование классов в случайных манерах может привести к сбоям в кеше только потому, что они находятся в памяти.
Общее правило для того, что загружается в кеш, состоит в том, что, если ЦП выполняет чтение и пропускает кеш, он загружает выровненный кеш чанк из основной памяти (в примерах 128 байт).
Для вашего отредактированного примера: Да, это совмещенные фрагменты памяти и части a МОЖЕТ быть загружен, если читает b выдаются только из-за их расположения в памяти.
Для вашего примера каждый MyClass Объект состоит из смежной области 2000 * sizeof(double) байты (скорее всего выровненные). Эти объекты упакованы в непрерывную область памяти, на которую указывает вектор. Доступ к b член каждого объекта будет подвергаться отсутствию кэша (если он не кэширован). Содержимое выровненного кеша фрагмента памяти будет загружаться при каждом чтении, которое пропускает кеш. В зависимости от ограничений выравнивания памяти и размера кэша, возможно, что некоторые записи из a член будет загружен в память. Можно даже предположить, что из-за заполнения и выравнивания, это не будет иметь место, что любой из ваших MyClass a члены будут загружены в кеш (и нет причин, по которым они должны быть, поскольку к ним не было доступа).
Другие решения
Ваша декларация:
for(auto x : y) ...
объявляет x в качестве значения вместо ссылки. Вполне возможно, что компилятор может оптимизировать копирование каждого элемента y в локальную переменную x, но я бы на это не рассчитывал.
Если вы напишите:
for(auto &x : y) ...
Тогда цикл будет работать над ссылками на объекты в y, Я предполагаю, что это то, что вы хотели сделать.
Конкретно, игнорируя struct padding: компилятор преобразует
double temp = y[i].b[j];
в нечто эквивалентное
double temp = *(
y.data() + i * sizeof(MyClass) // start of y[i]
+ 1000 * sizeof(double) // skip over y[i].a
+ j * sizeof(double)); // get to the right place in y[i].b
и он загрузит блок размером с строку кэша, содержащий этот адрес, в строку кэша.
Затем, когда вы перебираете больше элементов y[i].bмногие из них уже будут в кеше.
Поскольку массивы содержат 1000 элементов каждый, они намного больше, чем строки кэша на типичном ЦП. 1000 double занимают 8000 байтов, тогда как строки кэша в архитектуре Sandy Bridge (например) занимают 64 байта. Перебор массивов будет эффективно насыщать кэш. Вы можете потратить часть строки кэша на первый и последний элементы x.a, но эффект должен быть небольшим. По мере увеличения размера ваших массивов значение этих потраченных впустую нагрузок приближается к 0.
В статье Playstation говорится об объектах, которые по размеру сопоставимы со строкой кэша. Эти оптимизации не будут иметь большого значения для таких больших объектов, как ваш.
В ссылке, на которую вы ссылаетесь, два массива a а также b 4×4 матрицы, что означает 16 элементов каждая. Поскольку речь идет о видеоиграх, они, вероятно, с плавающей точкой. 16 поплавков занимают 64 байта.
Строка кэша ЦП составляет 128 байт. Таким образом, существует значительная вероятность того, что большая часть a находится в той же строке кэша, чем b[0], По статистике, 50% a будет в той же строке кэша, чем b[0], чтение b[0] затем загрузит эту часть a в кеше.
Если вам удастся выровнять класс / структуру по 128 байтам, вам даже будет гарантировано, что a а также b поместиться полностью в одной строке кэша.
Теперь в вашем примере вы не используете 16 поплавков, но 1000 удваивает. Это 8000 байт, намного больше, чем обычная строка кэша. Несколько последних элементов a может быть в той же строке кэша, чем b[0] но эффект будет небольшим.