Промахи кэша
Квадратная матрица n × n из чисел по s байт лежит в памяти по строкам, начиная с адреса 0: элемент (i, j) занимает байты с (i·n + j)·s. Её обходят, читая каждый элемент один раз, — по строкам, по столбцам или блоками. Посчитайте, сколько раз нужных данных не окажется в кэше.
Кэш устроен так. Память поделена на строки по L байт: элемент попадает в строку номер ⌊адрес / L⌋, а его байты в строке не пересекают её границу. В кэше C байт, то есть C/L мест для строк, разбитых на наборы по w мест. Строка с номером x может лежать только в наборе x mod (C/(L·w)). При чтении элемента, если его строки нет в своём наборе, это промах: строка загружается, а если набор полон, из него выбрасывается та, к которой дольше всего не обращались. Если строка уже есть, она становится самой свежей в наборе.
Порядки обхода: row — по строкам матрицы, слева направо; col — по столбцам, сверху вниз; block B — матрица разбита на квадраты B × B (у краёв — меньше), квадраты идут по строкам, внутри квадрата — тоже по строкам.
Вход
В первой строке q (1 ≤ q ≤ 6). В каждой из следующих q строк: n, s, C, L, w и порядок обхода (для block — ещё B). 1 ≤ n ≤ 512, s делит L, L·w делит C, все размеры — степени двойки, кроме n, w и B.
Выход
Для каждой строки — число промахов.
Примеры
Пример 1
3 4 4 64 16 1 row 4 4 64 16 1 col 4 4 64 16 2 block 2
4 4 4
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Здесь не нужен хитрый алгоритм — нужна точная модель. Заведите для каждого набора список строк в порядке последнего обращения и аккуратно повторите правила условия.
2Идея
Для каждого чтения считаем адрес, номер строки памяти и номер набора. Набор — короткий список длиной не больше w: если строка в нём есть, переносим её в конец (самая свежая); если нет — промах, выбрасываем первую (самую давнюю), если набор полон, и кладём новую в конец.
3Разбор
Обход по столбцам на матрице, у которой строка занимает степень двойки байт, — худший случай для такого кэша: элементы одного столбца отстоят друг от друга ровно на длину строки матрицы, их строки памяти попадают в один и тот же набор, и w мест в нём не хватает. Каждое чтение становится промахом. Обход по строкам, наоборот, читает строку памяти целиком: один промах на L/s чтений.
Обход блоками — приём, которым ускоряют умножение и транспонирование матриц (подробнее — в статье «Данные, удобные кэшу»): если блок помещается в кэш, каждая его строка памяти загружается один раз, и промахов почти столько, сколько строк памяти вообще занимает матрица. В пятом тесте это 11 250 при блоках 4 и 8; с ростом блока он перестаёт помещаться в кэш, и промахов становится больше — 11 804 при блоке 64.
Посмотрите и на четвёртый тест: матрица 500 × 500 по столбцам даёт 16 000 промахов, а 512 × 512 — все 262 144. Строка матрицы в 2000 байт — не степень двойки, и элементы одного столбца расходятся по разным наборам, а не толпятся в одном. Поэтому в высокопроизводительном коде строки больших матриц иногда нарочно удлиняют на несколько элементов.
Ускорение для моделирования: если строка та же, что при прошлом чтении, это попадание, и она уже самая свежая — можно сразу переходить к следующему чтению.
3+Решение
4Сложность
O(n²·w) на один обход: n² чтений, на каждое — поиск в наборе из w строк.
5Типичные ошибки
- Кэш без наборов. Если строка может лечь куда угодно, промахов меньше, чем в настоящем кэше: столбец на 512 строк уже не выталкивает сам себя из восьми мест набора.
- Выбрасывать не ту строку. Нужна та, к которой дольше всего не обращались, а не та, что раньше всех загружена: попадание делает строку самой свежей.
- Блоки у края. Если n не делится на B, крайние блоки меньше — пятый тест на это.
Алгоритмы задачи
O-большое то же
1 задача
TEC
Приём
Числа, которые стоит знать
Кэш, память, диск и сеть отличаются в сотни раз — прикидка по этим числам показывает, что ускорять.
прикидка — минута на салфетке
1 задача