Сравнение двух больших бинарных файлов

Всем доброго времени суток.
Сегодня я расскажу о двух стандартных подходах для сравнения двух файлов и о тонкостях реализации одного из них.
Внимание, пост немаленький!

#0 Постановка задачи.

На работе мне поставили такую задачу: сделать патчер.
На вход прилетают два файла. Надо выдать файлик

Дополнительно уточнялось, что файлы бинарные, и, что превращает задачу из тривиальной(и всем известной) в интересную, файлы большие, порядка нескольких гигабайт.
Ну и конечно, все дожно работать быстро.
По памяти требований не было.
В качестве бонуса надо было написать программу, которая по диффу будет осуществлять накат изменений на клиентской стороне.

#1 Стандартные методы решения

Существует два основных подхода — на LCS(longest common sequence) и так или иначе использующих хэши.
Начнем по порядку.

LCS

Объясню, почему LCS. Ищем LCS от двух файлов, все, что в нее не попало, считаем разницей, дальше пишем в дифф список блоков на удаление и на добавление.
Все просто, осталось найти LCS.
На хабре много статей, описывающих разные алгоритмы.
Предыдущий передо мной автор патчера, видимо, ничего не слышал о том, что у алгоритмов есть сложность, и написал поиск LCS через димамической программирование. Это простой алгоритм, пишется быстро и отлично работает на маленьких файлах. Но вот сложность у него

. И по памяти тоже O(n*m). Ладно, по памяти от нас ничего не требовали, а считает все равно сервер, у него памяти много. Но вот квадратичная сложность по времени убивала все. Сервер обсчитывал 600 Мб файл за 6 часов. Плохо, но это будет отправным временем сравнения эффективности тех или иных идей. Так как я был вторым, я решил свои тесты проводить не на сервере, а на обычном ноуте, чтобы все было честно.
LCS в той или иной мере используется юниксовой утилитой diff(с существенными доработками, конечно).
Какие же есть алгоритмы?
Есть ДП — время квадрат, память квадрат.
Есть алгоритм Хиршберга — время квадрат, память линейна. Это лучше, но мы соревнуемся по секундомеру.
Есть алгоритм с nlogn и по времени и по памяти, но хочется быстрее.
И, наконец, есть алгоритм с линейной памятью и временем O(n*(n-sizeof(LCS)). Здорово! Учитывая, что разница между разными версиями файлов маленькая, порядка 1% для файлов в 300Мб и дальше уменьшается(объем изменений постоянен, относительный объем уменьшается), то это почти линия! Но, константы этого алгоритма слишком большие. И выигрывает он лишь в далеком огромном необозримом размере файла.
Так что нет, не LCS.
p.s. описания этих алгоритмов легко гуглятся, так что не буду увеличивать и без того большой пост лишними словами.

Хэши

Самая популярная утилита, реализующая эту парадигму, называется Rsync. Я даже слышал о ней до того, как занялся этой задачей.
Алгоритм Rsync описывался на хабре, и очень неплохо, так что снова гугл вам в помощь.
Основная идея в том, что один из файлов бьется на блоки, для них считаются слабые и сильные хэши, потом идем по второму файлу, считаем слабый хэш, если он совпал, то проверяем, точно ли блоки одинаковы, сильным хэшем. Слабый хэш считается быстро, сильный обеспечивает наименьшее возможное число коллизий. Криптоустойчивость тут ни к чему, так что берется обычно MD5.(про криптоустойчивость MD5 — им рекомендовали не пользоваться в шифровании, снова гугл в помощь).
Так что принимаем волевое решение — сегодня мы любим хэши, а не LCS.

#3 Выбранный алгоритм и реализация.

Первоначально алгоритм был такой. Считываем файлы, для старого файла считаем кольцевые хэши для каждого байтового сдвига.

Полученные хэши мы кидаем в map, где ключ — хэш, а значение — адрес блока в сдвигах от начала файла.
Потом разбиваем новый файл на блоки, для каждого считаем хэш и ищем в мэпе старого файла. Нашли — проверяем сильным хэшем, или просто в лоб сравнением.
Почему для старого нужны кольцевые хэши для старого файла? Потому что, например, могло ничего в файлах не измениться, только в начало поставили один байт. И все, если бы блоки были статичными, мы бы подумали, что все блоки разные.
Сначала мне казалось, что все здорово. Написав, я получил порядка 3 минут для 300Мб, но вот на 600Мб я получал runtime error. Не хватало памяти, ведь файлы я считывал сразу и полностью, это 1.2 Гб, плюс мэп для каждого кольцевого сдвига… А на ноуте 4Гб. Компилил я, конечно, под x64. Выигрывать, поменяв ввод файла или что-то в этом духе, не хотелось, и я решил оставить такие мелочи на потом, когда будет готов алгоритм. А выиграть надо алгоритмом. Я поигрался на 300Мб с размерами блока и увидел, что чем меньше блок, тем быстрее работа. Остановился на 8 байтах.
И да, конечно, не стоит забывать о коллизиях. При маленьком размере блока есть шанс на нее натолкнуться, а у нас мэп, которые принимает только уникальные ключи… А значит, потеря каких-то блоков и больший чем есть на самом деле дифф.
Следующей идеей был мультимэп. Разумеется, памяти уходило еще больше.
На следующей итерации проблема с потерянными и неучтенными блоками была решена. В качестве значения я передавал дек, в который писались адреса и вернулся к мэпу.
Почему дек? Потому что мне не нужен произвольный доступ и поиск, ведь блоки, идущие в старом файле по порядку, скорее всего не перепутаны в новом файле(если они там остались), возможны только в ставки между ними, но порядок сохраняется. Так что просто идем по деку по порядку и все.
Дальше. Почему дек, а не лист? Потому что макс. размер дека больше размера листа. Проверяется вызовом list::max_size и deque::max_size в С++.
Это вскрыло большую проблему. Написанный мной на коленке хэш не справлялся со своей задачей. Было слишком много попаданий блоков под один хэш. Разумеется, маленький размер блока тоже играл роль. Для блока в 8 байт максимальный размер дека среди всех значений хэшей был 5.2% от всех блоков. Я стал увеличивать размер. Падала скорость почти линейно, а вот коллизии сначала падали до 2% от всех блоков на одном хэше и на этом остановились. Видимо, внутри моей хэш-функции была бага, которую я никак не могу отследить.
И тут я вспомнил про замечательный С++11 и std::unordered_map. Это ни в коем случае не красно-черное деерво, которым является мэп. Это просто хэш таблица. В этой хэш таблице ключом становится блок, а значением — дек адресов идентичных блоков.
Эта идея взлетела. Я поднялся до 90 секунд на 600Мб, и никаких плаваний по памяти уже не было.
Но я хотел быстрее, выше, сильнее.
Следующей итерацией была такая идея.
Зачем нам сначала хэшировать старый файл и хранить кучу хэшей?
Ведь лучше посчитать хэши для фиксированных блоков нового файла, которых всего число_байт_в_файле/размер_блока.
Банальное изменение параметров у принимающей функций(она принимала название файла и стратегию обработки), позволило подойти к 45 секундам.
Я не стал увеличивать размер блока. Я оставил это на потом. Когда будет закончено все, я просто передефайню константу и наслажусь очередным ускорением.
Дальше стоило написать вывод диффа, а не просто подсчет числа несовподающих/ндобавленных/удаленных блоков. Причем с агрегацией одинаковых. Ведь не стоит писать, что надо удалить блок 1,2,3,4,5, если можно написать что удали все с самого начала до байта номер 5*размер_блока. Просто добавил несколько условий в цикл поиска соответствий и все.

Время было 49 секунд.
Я увеличил размер блока до 32. 26 секунд.
Блок 64. 18 секунд.
Я решил остановиться. 18 секунд против 6 часов. 1200 раз.
Дальше увеличивать нет смысла — различие в 1 байт, даже в 1 бит повлечет за собой изменение 128 байт. Слишком дорого.
Почему размер блока — степень двойки? Потому что я часто умножаю номер блока на размер, чтобы получить байтовый адрес.
Конечно, лучше делать это битовым сдвигом.

#4 Результаты.

Построив график времени работы от размера файла, я получил чистую линию. Потому что хэш-таблица. Поиск и добавление за О(1).
Памяти тоже линия. С константой ~<4. На два файла по 600 Мб у моего ноута хватает оперативы. Хотя ее всего 4Гб.
Время — 18 секунд для 600Мб. Это с вводом(написанным лишь бы был), хэширование+поиск, и вывод(тоже лишь бы был).
Нормальный ввод/вывод даст еще пару секунд максимум. Размер патча неплох — с изменениями в 1,5% дифф весит 600Kb. Рядом лежит 15мб файл с блоками, которые надо вставить или записать вместо каких-то.
Код прост, как душа комсомолки, практически чистый STL и ничего более.
Ну только аллокаторы сам написал, чтоб не было переаллокаций, а сразу выделял столько, сколько в конце концов нужно будет.

Вывод — С++11 хорош, а сложности надо знать и понимать =)

p.s. к сожалению весь код — коммерческая тайна, но вам не составит труда написать подобное)

Автор: demist

Источник ^[1]