Простой пример алгоритма кеширования?

Question

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

Answer 1

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

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

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

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

Answer 2

Я думаю, что один из самых простых примеров алгоритма, поддерживающего кэш, - это доступ к двумерному массиву мажор строки по сравнению с мажором столбца. Поскольку двумерный массив обычно хранится в памяти так же, как конкатенация всех строк массива, доступ к нему строка за строкой помещает соответствующие данные в кэш в нужное время. Однако при доступе к массиву в главном порядке столбцов много скачков в памяти и кэш-памяти могут привести к значительному замедлению.

Чтобы привести пример, этот код C ++:

for (int i = 0; i < MAX_N; ++i) {
  for (int j = 0; j < MAX_N; ++j) {
   a[i][j] = 10;
  }
}

на моей машине работает в 3-4 раза быстрее, чем если бы я поменял местами индексы доступной ячейки (то есть вместо доступа a[j][i]).