Предподсчёт и таблицы
Также: Precomputation and lookup tables · таблица заранее · lookup table · память против времени · space–time tradeoff · табличный CRC · CRC-32
Если функция с небольшим числом возможных входов вызывается миллионы раз, её ответы можно посчитать заранее и брать из таблицы. Так считают контрольную сумму CRC-32 у каждого zip-архива: восемь шагов на байт превращаются в один, и «Война и мир» проверяется в десять раз быстрее. На замере видно и другое: таблица побольше — не всегда быстрее.
У каждого файла в zip-архиве записана контрольная сумма CRC-32: распаковщик пересчитывает её и так узнаёт, что файл не испорчен. По определению CRC обрабатывает данные по биту: восемь шагов «сдвинуть и, может быть, вычесть» на каждый байт. «Война и мир» — пять мегабайт, сорок миллионов шагов. Но каждые восемь шагов зависят только от одного байта, а разных байтов 256. Посчитаем все 256 ответов заранее — и байт будет обрабатываться одним шагом. Наберите любой текст и пройдите его по байтам.
На каждом шаге из состояния и байта получается номер — число от 0 до 255, — и он выбирает одну клетку таблицы. Включите «восемь шагов по битам»: те же восемь сдвигов, которые таблица заменила, — и их результат совпадает с числом в клетке. Таблица — килобайт памяти. На сервере сайта CRC-32 всего романа по таблице на Go считается в одиннадцать раз быстрее, чем по битам.
Идея
Если функцию вызывают много раз, а разных входов у неё мало, посчитаем её для всех входов один раз и сложим ответы в массив. Каждый следующий вызов — одно обращение к памяти. Это обмен памяти на время: таблица занимает место, зато работа превращается в чтение. Выгодно, когда вычисление дороже чтения из памяти, а таблица помещается в кэш.
Это родственник запоминания: там ответы складываются по мере того, как их спрашивают, здесь — все сразу, ещё до первого вопроса. И родственник префиксных сумм: там заранее считаются ответы на все вопросы «сумма от начала до i», и любой отрезок получается вычитанием.
Почему таблица даёт то же самое
CRC — остаток от деления многочлена, записанного битами данных, на фиксированный многочлен P, и «вычесть» здесь значит XOR. Байт по определению — восемь шагов: если младший бит состояния единица, сдвинуть и сделать XOR с P, иначе просто сдвинуть.
Пусть c — 32-битное состояние, b — байт данных, а T[i] — результат восьми шагов, начатых с числа i. Тогда восемь шагов, начатых с c XOR b, дают (c >> 8) XOR T[(c XOR b) & 255].
Один шаг — это сдвиг вправо и, может быть, XOR с P. И сдвиг, и XOR с постоянным числом перестановочны с XOR: сдвиг (x XOR y) — это XOR сдвигов. Поэтому восемь шагов над числом x = c XOR b — это x, сдвинутое на 8, XOR какое-то число Q — сумма тех копий P, которые вычитались. Какие копии вычитать, решает только младший бит на каждом шаге, а он в первых восьми шагах берётся из младшего байта x: XOR с P на шаге j меняет и биты, которые проверяются позже, но только в зависимости от уже прочитанных младших. Значит, Q зависит лишь от x & 255. Для числа i = x & 255 те же восемь шагов дают i >> 8 XOR Q = 0 XOR Q, то есть T[i] = Q. Остаётся заметить, что x >> 8 = c >> 8: байт b сидит только в младших восьми битах и уходит при сдвиге.
Ничего специфичного для CRC здесь нет: предподсчёт работает для любой функции, которой важны только несколько бит входа. Так же устроены таблица единиц в байте — подсчёт единиц в 64-битном числе тогда стоит восемь чтений, — и таблица синусов в старых играх: в исходниках Doom 1993 года синус берётся из массива finesine, а не вычисляется.
Таблица побольше — быстрее?
Если таблица на 8 бит заменяет восемь шагов одним, таблица на 16 бит — 65 536 записей — должна обрабатывать два байта за шаг и быть вдвое быстрее. Замер — CRC-32 «Войны и мира» по биту и таблицами на 4, 8 и 16 бит, а рядом стандартные функции.
От битов к таблице на 4 бита и дальше к 8 время падает в разы. А таблица на 16 бит — медленнее, чем на 8, и в Go, и в Python. Таблица на 8 бит — килобайт, она живёт в кэше первого уровня, и каждое обращение почти бесплатно. Таблица на 16 бит — 256 КБ: в кэш первого уровня она не помещается, и обращение к ней стоит в разы дороже, чем сэкономленные шаги. В Python к этому добавляется цена самого шага: собрать два байта в одно число — несколько лишних операций интерпретатора. Подробно об этой стене — в статье «Данные, удобные кэшу».
Стандартные функции в десятки и сотни раз быстрее любой нашей таблицы. Они используют приёмы следующего уровня: несколько маленьких таблиц сразу, чтобы обрабатывать четыре или восемь байт за шаг, а там, где процессор умеет считать CRC сам, — его особые команды. Вывод для практики простой: CRC, хеши и подсчёт единиц берут из стандартной библиотеки, а предподсчёт пишут сами для своих функций.
Код
CRC-32 по битам и по таблице, сверка со стандартной функцией и то, ради чего CRC вообще считают: она ловит любую ошибку в одном бите и любую порчу отрезка подряд идущих бит длиной до 32.
Обе функции и библиотечная дают одно и то же. Строки «War and Peace» и «War and peace» отличаются одной буквой, а их суммы — почти всеми цифрами. Все 128 перевёрнутых битов и все 2720 испорченных отрезков длиной до 32 бит замечены. Это не случайность, а свойство: CRC с многочленом степени 32 гарантированно замечает любую порчу отрезка не длиннее 32 бит — поэтому её и ставят в сети и файловые системы, где ошибки чаще всего приходят пачками.
Сколько это стоит
Построение таблицы — O(число записей × цена одного вычисления), один раз. Каждый запрос — O(1), одно чтение памяти. Предподсчёт окупается, когда запросов больше, чем записей в таблице, а вычисление дороже чтения.
Крайний случай — таблицы, которые считают годами. В шахматах для всех позиций с семью фигурами на доске посчитано, выигрышна ли позиция и за сколько ходов: такие таблицы эндшпиля занимают десятки терабайт, и программа, дойдя до семи фигур, больше не думает, а читает ответ. Обратный крайний случай — таблица, которая дороже вычисления: если ответ считается за пару тактов, обращение к таблице за пределами кэша только замедлит программу, как таблица на 16 бит в замере.
Задачи
Задача — посчитать CRC каждой строки «Войны и мира» для двух разных многочленов. Без таблицы решение не укладывается в ограничение по времени.
CRC по строкам