Форум программистов, компьютерный форум CyberForum.ru

Как работает кэш? - C++

Восстановить пароль Регистрация
 
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
10.11.2012, 19:36     Как работает кэш? #1
Здравствуйте! Хочу понять как работает кэш. Задание такое:

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

C++
1
2
3
4
5
6
7
8
9
10
struct point_color {
    int c;
    int m;
    int y;
    int k;
};
 
struct point_color square[16][16];
 
int i, j;
когда наш алгоритм выгледит вот так:

C++
1
2
3
4
5
6
7
8
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++
1
2
3
4
5
6
7
8
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
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
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 раз.
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
10.11.2012, 22:22  [ТС]     Как работает кэш? #3
Nick Alte, благодарю за доходчивый ответ! все понял! спасибо!
ZubSam
12 / 12 / 1
Регистрация: 24.03.2012
Сообщений: 238
13.11.2012, 11:50     Как работает кэш? #4
Цитата Сообщение от Nick Alte Посмотреть сообщение
Во втором варианте мы двигаемся не последовательно, а с зазором и возвратами: 1 4 7 2 5 8 3 6 9.
а можно поподробнее расписать данный момент? просто как то не совсем понятно
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
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 штук.
Yandex
Объявления
13.11.2012, 18:52     Как работает кэш?
Ответ Создать тему
Опции темы

Текущее время: 04:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru