Боря программирует

Cache misses

На контестах полезно уметь оценивать, сколько будет работать какое-то решение. Не только помнить константы "10^6 операций с сетом работают меньше 1с, а 10^7 больше", но и понимать почему.

Типичная проблема — обращения к памяти. Как оценить насколько они дорогие? Зависит от количества используемой памяти. Если у нас массив на 1000 элементов, то он легко поместится в L1 кеш и все будет очень быстро. А если массив занимает 100мб, то не хватит и L3 кеша, и все будет тормозить. Давайте научимся определять размеры кешей и насколько дорого к ним обращаться.

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

let n = 500_000;
let p = gen_perm(n);
let mut a = vec![0; n];
for i in 0..n {
a[p[i]] = p[(i + 1) % n];
}
let mut pos = 0;
for _ in 0..100_000_000 {
pos = a[pos];
}

Можно измерить, сколько выполняется каждая итерация цикла, и это будет хорошим приближением того, сколько стоит обращение к кешу. Но к какому именно? Посчитаем количество реальных кеш промахов:

$ perf stat -e mem_load_retired.l1_miss,mem_load_retired.l2_miss,mem_load_retired.l3_miss ./a

99,569,765 mem_load_retired.l1_miss
71,453,658 mem_load_retired.l2_miss
22,025 mem_load_retired.l3_miss

Количество L3 промахов маленькое, так что можно считать, что вся память помещается в L3. А вот количество L2 промахов говорит о том, что 71.4% массива не поместилось в L2 кеш (а 28.6% поместилось). Целиком массив занимает 500_000 * 8 = 4мб, значит размер L2 кеша 4мб * 0.286 = 1.14мб.

Учитывая реальный размер L2 кеша, оценка довольно хорошая:

$ getconf -a | grep LEVEL2_CACHE_SIZE
LEVEL2_CACHE_SIZE 1310720

Можно провести такой же эксперимент для разных значений n и узнать параметры всех уровней кешей, но в телеграмме есть ограничение на длину постов :(

👍20🔥7🥰1🤯1

www.tgoop.com/bminaiev_blog/34

2.08K viewsedited  Feb 18, 2023 at 10:01

Cache misses

На контестах полезно уметь оценивать, сколько будет работать какое-то решение. Не только помнить константы "10^6 операций с сетом работают меньше 1с, а 10^7 больше", но и понимать почему.

Типичная проблема — обращения к памяти. Как оценить насколько они дорогие? Зависит от количества используемой памяти. Если у нас массив на 1000 элементов, то он легко поместится в L1 кеш и все будет очень быстро. А если массив занимает 100мб, то не хватит и L3 кеша, и все будет тормозить. Давайте научимся определять размеры кешей и насколько дорого к ним обращаться.

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

let n = 500_000;
let p = gen_perm(n);
let mut a = vec![0; n];
for i in 0..n {
a[p[i]] = p[(i + 1) % n];
}
let mut pos = 0;
for _ in 0..100_000_000 {
pos = a[pos];
}

Можно измерить, сколько выполняется каждая итерация цикла, и это будет хорошим приближением того, сколько стоит обращение к кешу. Но к какому именно? Посчитаем количество реальных кеш промахов:

$ perf stat -e mem_load_retired.l1_miss,mem_load_retired.l2_miss,mem_load_retired.l3_miss ./a

99,569,765 mem_load_retired.l1_miss
71,453,658 mem_load_retired.l2_miss
22,025 mem_load_retired.l3_miss

Количество L3 промахов маленькое, так что можно считать, что вся память помещается в L3. А вот количество L2 промахов говорит о том, что 71.4% массива не поместилось в L2 кеш (а 28.6% поместилось). Целиком массив занимает 500_000 * 8 = 4мб, значит размер L2 кеша 4мб * 0.286 = 1.14мб.

Учитывая реальный размер L2 кеша, оценка довольно хорошая:

$ getconf -a | grep LEVEL2_CACHE_SIZE
LEVEL2_CACHE_SIZE 1310720

Можно провести такой же эксперимент для разных значений n и узнать параметры всех уровней кешей, но в телеграмме есть ограничение на длину постов :(

BY Боря программирует