Алгоритм сжатия без потерь Broo и дельта-кодирование, сравнение с Xdelta3. Развитие домашнего проекта
Прошел почти год с момента публикации последней статьи и мы готовы рассказать, что происходило с самим алгоритмом и как тут замешано дельта-кодирование. Рады Вас приветствовать.
Вступление
Сразу сделаю оговорку, улучшения были сделаны без ущерба для других характеристик алгоритма, но эти изменения незначительные, дальше мы напишем об этих изменениях. После выпуска статьи об улучшениях алгоритма Broo, мы столкнулись с преградой в улучшении уровня компрессии и производительности, а именно нельзя было улучшить уровень компрессии не ухудшив скорость распаковки и наоборот. И выбор пал на дельта-кодирование. Так вот, после, мы задумались, где мы можем применить накопленную экспертизу и знания в похожем направлении.
Что такое дельта-кодирование?
Delta encoding) — способ представления данных в виде разницы (дельты) между последовательными данными вместо самих данных. Дельта-кодирование (англ.
На практике, если алгоритмы сжатия позволяют уменьшить размер файла и хранить или пересылать его без каких либо зависимостей от других файлов, то алгоритмы дельта-кодирования позволяют построить патч(разницу) меньшего размера на основе двух файлов (набора данных) и применив патч для файла (набора данных) 1 — получить файл (набора данных) 2.
Вместо того, чтобы скачивать приложение полностью и потом заменять файлы, строится патч намного меньшего размера (зависит от кол-ва изменений), что позволяет намного быстрее скачать обновление, а скорость применения патча напрямую влияет на скорость обновления самого приложения. Самое распространенное применение для дельта-кодирования это обновление приложений на ваших телефонах и ПК.
Если Вы знаете где еще применяется дельта-кодирование, то напишите в комментариях.
Об изменениях в алгоритме Broo
Как мы и говорили, их немного:
- Добавлена поддержка файлов размером 2^64 для x64 и 2^32 для x32.
- Улучшен коэффициент сжатия.
Основная проблема — после добавления поддержки больших файлов, на 20% упала скорость распаковки, что для нас недопустимо. Эти изменения все еще находятся на стадии экспериментирования и отладки. Так что поиск решения нами все еще ведется.
Файл "xml" из предыдущей статьи. Ниже приведем только одну таблицу сравнений старой версии алгоритма, экспериментальной и некоторые уровни zstd.
Процессор: Intel i7-7700HQ
Память: DDR4-2400
Имя алгоритма
Скорость упаковки
Скорость распаковки
Размер сжатого файла, Байт
% оторигинала
memcpy
17460 MB/s
17194 MB/s
5345280
100.00
zstd 1.3.1 -6
141 MB/s
1311 MB/s
585810
10.96
broo 1.2
11 MB/s
1905 MB/s
606838
11.35
zstd 1.3.1 -5
196 MB/s
1207 MB/s
619510
11.59
zstd 1.3.1 -4
357 MB/s
1214 MB/s
637587
11.93
zstd 1.3.1 -3
366 MB/s
1220 MB/s
639073
11.96
broo 1.1
14 MB/s
2005 MB/s
643084
12.03
zstd 1.3.1 -2
394 MB/s
1108 MB/s
690508
12.92
zstd 1.3.1 -1
479 MB/s
1213 MB/s
703093
13.15
5 раза быстрее чем у zstd первого уровня, на процессоре Intel i7-7700HQ. Как и множество алгоритмов, скорость работы зависит от процессора, как мы можем видеть в таблице, скорость распаковки более чем в 1. В то время как на старом Intel i3-550 скорость распаковки была приблизительно равна скорости распаковки zstd, можно посмотреть сравнительные таблицы тут.
Зависит от специфики задачи. Это говорит о том, что можно выполнить более плотную интеграцию с отдельными процессорами.
Дельта-кодирование и Broo
Как вы уже могли догадаться, мы разработали свой алгоритм дельта-кодирования и дали ему название DBroo (Delta Broo).
Основные характеристики и особенности:
- Поддержка файлов размером 2^64 для x64 и 2^32 для x32.
- Работа с бинарными данными.
- Допускается частичное изменение опорного файла, к которому будет применяться патч.
Была цель найти лучшего (а также доступного) в этом направлении и тягаться с ним. Есть готовые решения, такие как diff, bsdiff, xdelta и другие. Выдает неплохое сжатие и достаточно быструю скорость применения патча. Чисто экспериментальным способом главным конкурентом оказался Xdelta3. Также Xdelta3 используется для обновлений CyanogenMod (ныне LineageOS).
В качестве опорного файла используется "xml", а в качестве нового файла тот же но измененный случайным образом. Теперь посмотрим на таблицу сравнения DBroo и Xdelta3.
Имя алгоритма
Скорость создания патча
Скорость применения патча
Размер патча, байт
% от оригинала
memcpy
18052 MB/s
18665 MB/s
5326823
100.00
Xdelta3 -9 + lzma
5.40 MB/s
306 MB/s
106542
2.00
Xdelta3 -6 + lzma
20 MB/s
310 MB/s
121916
2,28
DBroo 1.0
7.40 MB/s
1600.00 MB/s
123052
2.31
Xdelta3 -9
7.00 MB/s
688.24 MB/s
179732
3.37
Xdelta3 -6
36.71 MB/s
694.09 MB/s
201681
3.78
Xdelta3 -3
59.22 MB/s
637.43 MB/s
237218
4.45
Xdelta3 -2
72.73 MB/s
582.75 MB/s
279223
5.24
Xdelta3 -1
81.43 MB/s
540.53 MB/s
478824
8.9
P. S.
Поэтому, будем рады вашим комментариям. Развитие получают только те продукты, у которых есть спрос на рынке. Мы также создали телеграм-канал.
Спасибо.
