# конспект · шаг 7 из 7
Конспект: память, замер и точка пересечения
Понятия
Строка кеша - 64 байта, единица переезда данных между уровнями памяти. Предвыборка - заказ следующих строк заранее, когда адреса идут подряд или с постоянным шагом.
Прогрев - первые прогоны, которые платят за холодные кеши и первое выделение памяти.
Квартили q1, q3 - числа, не больше которых четверть и три четверти отсортированных замеров;
[q1, q3] - средняя половина.
Опыт с удвоением - замеры на размерах n, 2n, 4n…; показатель роста b ≈ log₂(T(2n) / T(n)).
Точка пересечения - размер, с которого асимптотически лучший алгоритм обгоняет простой.
Что унести
ЛЕСТНИЦА ПАМЯТИ (порядки; машина сайта: i5-3350P)
L1 32 КБ ~1 нс | L2 256 КБ ~3-4 нс | L3 6 МБ ~10-20 нс
оперативная память ~60-100 нс
sum подряд - 8 нс на элемент при любом размере (предвыборка)
sum вразброс: 31 КБ ×1,0 | 312 КБ ×1,1 | 3 МБ ×2 | 31 МБ ×5 | 125 МБ ×6
модель кеша: ступенька там же, но отношение 1,7 вместо 5-6
ЧЕСТНЫЙ ЗАМЕР
прогрев отбросить: первые прогоны дороже на 15-20%
повторов 7-30, варианты A и B поочерёдно
минимум - «без помех»; медиана + [q1, q3] - «обычно и насколько дрожит»
[q1, q3] перекрываются -> «не различить»
одинаковые варианты: 15 пар - 11 : 3 и ничья; 3 серии по 40 - 20, 22, 19
timeit.repeat: number раз в каждом из repeat замеров, сборщик выключен
ОПЫТ С УДВОЕНИЕМ
b ≈ log₂(T(2n) / T(n)): константа сокращается
n log n -> ~1,1 (1,07 на миллионе), n² -> 2
искажения: накладные расходы занижают на малых n,
кеш завышает на больших (словарь O(n): 1,1-1,6)
прогноз на рост данных в k раз - в kᵇ раз дольше
ТОЧКА ПЕРЕСЕЧЕНИЯ
a·n² против b·n·log₂ n: первый быстрее, пока n / log₂ n < b / a
вставки против слияния: модель - между 32 и 64, Python - между 64 и 128
на 8 элементах: модель 44 против 79, машина 1,8 мкс против 8,6
пороги гибридов (16 в libstdc++, minrun 32-64) находят замером
Ловушки джокера
Бенчмарк на данных, которые помещаются в кеш. Разбросанная структура выглядит не хуже компактной.
Один прогон или средние. Выбросы и прогрев решают за тебя; пятнадцать пар тоже могут соврать.
«На 4% быстрее» при перекрытых квартилях. Это шум, а не оптимизация.
Подготовка данных внутри засечки. Меряется import и создание входа, а не алгоритм.
Экстраполяция времени, а не показателя. «0,2 с на тысяче - 200 с на миллионе» при квадрате - это 55 часов.
Показатель на одной паре удвоений. Ступень кеша выглядит как квадрат; смотреть на устойчивую часть ряда.
Порог из статьи про другой язык. Константы зависят от машины и интерпретатора.
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий