Broo lossless compression algorithm and delta encoding, compared with Xdelta3. Home project development

We are glad to welcome you. Almost a year has passed since the last article was published, and we are ready to tell you what happened with the algorithm itself and how delta coding is involved.

Introduction

After the release of the article on improvements to the Broo algorithm, we were faced with an obstacle in improving the level of compression and performance, namely it was impossible to improve the level of compression without degrading the speed of decompression and vice versa. I will immediately make a reservation, the improvements were made without prejudice to the other characteristics of the algorithm, but these changes are minor, then we will write about these changes. So, after, we thought about where we can apply the accumulated expertise and knowledge in a similar direction. And the choice fell on delta encoding .

What is delta coding?

Delta encoding ( English Delta encoding) - a way to present data as a difference ( delta ) between serial data instead of the data itself.

In practice, if the compression algorithms allow you to reduce the file size and store or send it without any dependencies on other files, then the delta encoding algorithms allow you to build a smaller patch (difference) based on two files (data set) and apply a patch to the file ( data set) 1 - get the file (data set) 2 .

The most common use for delta coding is to update applications on your phones and PCs. Instead of downloading the application completely and then replacing the files, a much smaller patch is built (depending on the number of changes), which makes it much faster to download the update, and the speed with which the patch is applied directly affects the update speed of the application itself.

If you know where else delta coding is applied, then write in the comments.

On changes in the Broo algorithm

As we said, they are few:

• Added support for 2 ^ 64 files for x64 and 2 ^ 32 for x32.
• Improved compression ratio.

These changes are still at the stage of experimentation and debugging. The main problem - after adding support for large files, the decompression speed dropped by 20%, which is unacceptable for us. So we are still searching for a solution.

Below we present only one table of comparisons of the old version of the algorithm, the experimental one and some levels of zstd. File "xml" from the previous article .

Processor: Intel i7-7700HQ

Memory: DDR4-2400

Like many algorithms, the speed depends on the processor, as we can see in the table, the decompression speed is more than 1.5 times faster than the first level zstd, on the Intel i7-7700HQ. While on the old Intel i3-550, the decompression speed was approximately equal to the zstd decompression speed, you can see the comparative tables here .

This suggests that you can perform tighter integration with individual processors. Depends on the specifics of the problem.

Delta Coding and Broo

As you might have guessed, we developed our own delta encoding algorithm and named it DBroo (Delta Broo).

Main characteristics and features:

• Support for files of size 2 ^ 64 for x64 and 2 ^ 32 for x32.
• Work with binary data.
• Partial change of the reference file to which the patch will be applied is allowed.

There are ready-made solutions, such as diff, bsdiff, xdelta and others. There was a goal to find the best (and also available) in this direction and to be with it. In a purely experimental way, Xdelta3 turned out to be the main competitor. It gives a good compression and a fairly fast speed of the patch. Also, Xdelta3 is used to update CyanogenMod (now LineageOS ).

Now look at the comparison table DBroo and Xdelta3. "Xml" is used as the reference file, and the same but changed randomly as the new file.

PS

Only those products that are in demand in the market receive development. Therefore, we welcome your comments. We also created a telegram channel .

Thank.