Как работает кэш?

@jambas92 · Регистрация: 18.11.2010

Здравствуйте! Хочу понять как работает кэш. Задание такое:

Нам надо нарисовать желтый квадрат на белом листе, для этого нам надо задать параметры CMYK (cyan, magenta, yellow, black).
У нас есть кэш на 2048 байта с блоком в 32 байта.

C++

struct point_color {
    int c;
    int m;
    int y;
    int k;
};
 
struct point_color square[16][16];
 
int i, j;

когда наш алгоритм выгледит вот так:

C++

for (i = 0; i < 16; i++) {
    for (j = 0; j < 16; j++) {
        square[i][j].c = 0;
        square[i][j].m = 0;
        square[i][j].y = 1;
        square[i][j].k = 0;
    }
}

количество записей в кэш будет 1024, а количество записей промахов в кэш будет 128.
А если мы будем забивать не построчно, а по столбцам:

C++

for (i = 0; i < 16; i++) {
    for (j = 0; j < 16; j++) {
        square[j][i].c = 0;
        square[j][i].m = 0;
        square[j][i].y = 1;
        square[j][i].k = 0;
    }
}

то количество записей в кэш будет 1024, а количество записей промахов в кэш будет 256.

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

@Nick Alte · 10.11.2012, 20:50

В кэш загружаются небольшие куски памяти определённого размера при первом обращении. Этот массив целиком не помещается, а помещаются кусочки по 2 записи, по 32 байта. В первом варианте мы двигаемся по адресам памяти последовательно, переходя от одного элемента строки к следующему, так что промахи происходят только когда мы переходим к новому кусочку. Это происходит потому, что массив устроен как последовательно уложенные строки, в каждой строке последовательно уложены элементы:
1 2 3
4 5 6
7 8 9
уложен в памяти как 1 2 3 4 5 6 7 8 9

Получается, что мы проходим по 128 кусочкам, отсюда соответствующее количество промахов. Во втором варианте мы двигаемся не последовательно, а с зазором и возвратами: 1 4 7 2 5 8 3 6 9.
Поскольку при обращении к каждому новому элементу мы уже вылезаем за пределы предыдущего кусочка, то каждое обращение к новому элементу вызывает промах и необходимость загрузки в кэш нового кусочка. Таким образом, промахи происходят столько же раз, сколько у нас элементов, 256 раз.

@jambas92 · 10.11.2012, 22:22 **[ТС]**

Nick Alte, благодарю за доходчивый ответ! все понял! спасибо!

@ZubSam · 13.11.2012, 11:50

Сообщение от Nick Alte

Во втором варианте мы двигаемся не последовательно, а с зазором и возвратами: 1 4 7 2 5 8 3 6 9.

а можно поподробнее расписать данный момент? просто как то не совсем понятно

@Nick Alte · 13.11.2012, 18:52

Ну вот возьмём, например, тот же пример: массив из 9 элементов. Как мы помним, в "кусочек" укладываются 2 соседних элемента, потому что каждый из них занимает 16 байтов, а размер "кусочка" - 32 байта.
1 2 3
4 5 6
7 8 9
Массив укладывается в памяти очень просто: все строчки укладываются друг рядом с другом, каждая строчка - последовательно уложенные элементы. И больше ничего, только сами элементы. Получается, что этот массив в памяти выглядит как непрерывная цепочка 1 2 3 4 5 6 7 8 9
То есть, мы получаем такие кусочки: (1 2) (3 4) (5 6) (7 8) (9 )
В первом варианте перебора мы идём по строчкам, и получается, что элементы перебираются в том же порядке 1 2 3 4 5 6 7 8 9. При этом мы получим 5 промахов, которые будут происходить каждый раз при заходе в новый кусочек.
А если мы идём по столбцам, то сначала мы лезем в 1 из кусочка (1 2), затем сразу переходим к 4 из (3 4), затем к 7 из (7 8), потом возвращаемся к 2 из (1 2) и так далее. Получается, что когда мы идём по столбцам, каждый раз, когда мы обращаемся к следующему элементу, мы переходим в другой кусочек. То есть, мы получим по промаху на каждый элемент, 9 штук.

@Nick Alte 1671 / 1043 / 174 Регистрация: 27.09.2009 Сообщений: 1,945
	10.11.2012, 20:50	2
	В кэш загружаются небольшие куски памяти определённого размера при первом обращении. Этот массив целиком не помещается, а помещаются кусочки по 2 записи, по 32 байта. В первом варианте мы двигаемся по адресам памяти последовательно, переходя от одного элемента строки к следующему, так что промахи происходят только когда мы переходим к новому кусочку. Это происходит потому, что массив устроен как последовательно уложенные строки, в каждой строке последовательно уложены элементы: 1 2 3 4 5 6 7 8 9 уложен в памяти как 1 2 3 4 5 6 7 8 9 Получается, что мы проходим по 128 кусочкам, отсюда соответствующее количество промахов. Во втором варианте мы двигаемся не последовательно, а с зазором и возвратами: 1 4 7 2 5 8 3 6 9. Поскольку при обращении к каждому новому элементу мы уже вылезаем за пределы предыдущего кусочка, то каждое обращение к новому элементу вызывает промах и необходимость загрузки в кэш нового кусочка. Таким образом, промахи происходят столько же раз, сколько у нас элементов, 256 раз. 1

@jambas92 59 / 58 / 16 Регистрация: 18.11.2010 Сообщений: 315
	10.11.2012, 22:22 [ТС]	3
	Nick Alte, благодарю за доходчивый ответ! все понял! спасибо! 0

@ZubSam 14 / 14 / 1 Регистрация: 24.03.2012 Сообщений: 238
	13.11.2012, 11:50	4
	Сообщение от Nick Alte Во втором варианте мы двигаемся не последовательно, а с зазором и возвратами: 1 4 7 2 5 8 3 6 9. а можно поподробнее расписать данный момент? просто как то не совсем понятно 0

@Nick Alte 1671 / 1043 / 174 Регистрация: 27.09.2009 Сообщений: 1,945
	13.11.2012, 18:52	5
	Ну вот возьмём, например, тот же пример: массив из 9 элементов. Как мы помним, в "кусочек" укладываются 2 соседних элемента, потому что каждый из них занимает 16 байтов, а размер "кусочка" - 32 байта. 1 2 3 4 5 6 7 8 9 Массив укладывается в памяти очень просто: все строчки укладываются друг рядом с другом, каждая строчка - последовательно уложенные элементы. И больше ничего, только сами элементы. Получается, что этот массив в памяти выглядит как непрерывная цепочка 1 2 3 4 5 6 7 8 9 То есть, мы получаем такие кусочки: (1 2) (3 4) (5 6) (7 8) (9 ) В первом варианте перебора мы идём по строчкам, и получается, что элементы перебираются в том же порядке 1 2 3 4 5 6 7 8 9. При этом мы получим 5 промахов, которые будут происходить каждый раз при заходе в новый кусочек. А если мы идём по столбцам, то сначала мы лезем в 1 из кусочка (1 2), затем сразу переходим к 4 из (3 4), затем к 7 из (7 8), потом возвращаемся к 2 из (1 2) и так далее. Получается, что когда мы идём по столбцам, каждый раз, когда мы обращаемся к следующему элементу, мы переходим в другой кусочек. То есть, мы получим по промаху на каждый элемент, 9 штук. 1

Опции темы