Talk About the Compression...

For a project I'm working on, I've had to add compression support, and so came the question of which algorithm to use. Now I didn't have to fully answer that one, because I did add support for more than one and thus ultimately it will come to to the user to make itw own decision.

Note that this wasn't a cop out move, but dependeing on whether you're more interested in speed or size, the answer won't be the same.

Still, which one is "better" ? Which is faster, which compresses more ? And by how much ? Let's find out...

Preface

Algorithms

So it comes down to three different algorithms :

1. zlib - using the miniz implementation,
2. lzma (xz) - using the fast-lzma2 implementation, and
3. zstd - using libzstd 1.3.7

Specificity

It might be important to note that I didn't do specific tests for those compression algorithms, instead I did add support for them and ran tests to see how each performed compared to the others.

What that means is, the specifity of the program matters here, and might have impacted the results. Most important of all being that whilst the tests were ran over a dataset of a few gigabytes, it wasn't compressed as a single stream of data.

The program I'm using here is actually splitting data in small blocks, and those are getting independently compressed.

bakelite

Indeed, some time back I was thinking about backup solutions, and came across what I found to be a very interresting little project called bakelite, by Rich Felker.

This is a backup program that aims to be secure & fast, and focuses on privacy of your data, meaning the backed up data can safely be stored online, they're encrypted and secure.

One of the way it does work, is by splitting each file into small data blocks, and - after deduplication of course - process those blocks.

In this case processing means compressing the data before encrypting it. And my tests were of bakelite to see how it performed with and without compression, and how a different algorithm behaved versus another.

Make sure to keep that in mind as you read the results. Specifically, the time values mentioned are of the whole process, including bakelite's own processing, notably the encrypting part, which isn't negligible.

Datasets

Every backup ran over the same datasets, obvisouly, and with similar options. Notably, the data blocks' sizes were up to 1 MiB at most

What I did was using complete system backups as sources. So every test will be made of 4 backups :

• The first backup is the so-called "complete" one, in that nothing was backed up before. So, bakelite went over the entire data, applied its own splitting into blocks algorithm, applied data deduplication, and went on to compress each and every blocks.

  That obvisouly took a long time, because we're talking about some 20 GiB of data (in over 300,000 files).

  Specifically, the source was 20,270,087,180 bytes over 319,746 files; and bakelite split that into 125,528 data blocks. That means an average blick size of about 143,361 bytes per block.

• The second backup is the first incremental backup. For a regular bakelite use, all backups except the very first one will be incremental.

  This had still about 20 GiB of data, the same data but with a bunch of changes made of course. Still a lot did not change, and data deduplication could take all that out. This is why those incremantal backups are much smaller, hence much faster too, than the "complete" one.

  The source for this one was 20,261,703,074 bytes over 319,622 files, resulting into 1,106 new blocks to be processed, that's about 243,908 bytes per block.

• The third backup had a source of now 20,274,086,577 bytes over 319,927 files, resulting into 1,089 new blocks, thus averaging 263,206 bytes per block.

• And finally the third and last incremental backup has its source at 20,253,360,439 bytes over 319,009 files, leading to 1,065 new blocks to be processed, averaging at 272,138 bytes per block.

Each test did consist of those four backups, with a different compression setting. The following tests were ran :

• no compression, to have a reference point
• zlib, at the default compression level (set at 5 in bakelite)
• zstd, at the default compression level (set at 8 in bakelite)
• zstd, at its maximum compression level of 22
• lzma, at the default compression level (set at 0 in bakelite)
• lzma, at compression level 4
• lzma, at compression level 6

First backup - the "complete" one

1
2
3
4

backupSpeed   : 6,070,705 bytes/s in 55m 39s
Backup  : 17,995,919,444 bytes    [88.78% of Source (deduplication)]
Extra   :     74,669,122 bytes    (metadata + overhead)
Written : 18,070,588,566 bytes    (Backup + Extra)

1
2

zlibSpeed   : 5,214,841 bytes/s in 1h 4m 47s
Written : 12,126,350,326 bytes    [67.38% of Backup + Extra (compression)]

1
2

zstd level 8Speed   : 6,065,256 bytes/s in 55m 42s
Written : 11,942,870,301 bytes    [66.36% of Backup + Extra (compression)]

1
2

zstd level 22Speed   : 3,008,324 bytes/s in 1h 52m 18s
Written : 11,774,609,528 bytes    [65.43% of Backup + Extra (compression)]

1
2

lzma level 0Speed   : 4,787,455 bytes/s in 1h 10m 34s
Written : 11,639,903,119 bytes    [64.68% of Backup + Extra (compression)]

1
2

lzma level 4Speed   : 4,828,510 bytes/s in 1h 9m 58s
Written : 11,662,361,887 bytes    [64.81% of Backup + Extra (compression)]

1
2

lzma level 6Speed   : 2,034,740 bytes/s in 2h 46m 2s
Written : 11,632,731,702 bytes    [64.64% of Backup + Extra (compression)]

As you can see, results are pretty much what you could expect : zlib takes some time to do its job, whereas zstd manages to be fast enough that it has basically no impact on the time it takes to complete the backup, all while providing better compression than zlib.

Meanwhile, lzma it slower than zstd but gets better compression; though when pushing zstd to its maximum level it gets slower than lzma yet still doesn't compress better.

Also worth noting that here, lzma level 0 seems a very good choice - not too slow and better compression than its competitor, even better than level 4 at almost the same speed.

Level 6 is clearly time hungry, only for a little gain in space. I didn't go above level 6 because that duration scared me I don't think there's much point anyways: as said earlier, we're only dealing with small data blocks here, with a maximum size of 1 MiB, and I believe level 7 and above are known not to be worthy for small files.

First incremental backup

1
2
3
4

backupSpeed   : 159,540,969 bytes/s in 2m 7s
Backup  :    269,763,111 bytes    [1.33% of Source (deduplication)]
Extra   :     27,961,347 bytes    (metadata + overhead)
Written :    297,724,458 bytes    (Backup + Extra)

1
2

zlibSpeed   : 142,688,049 bytes/s in 2m 22s
Written :    118,927,108 bytes    [44.09% of Backup + Extra (compression)]

1
2

zstd level 8Speed   : 158,294,555 bytes/s in 2m 8s
Written :    107,105,601 bytes    [39.70% of Backup + Extra (compression)]

1
2

zstd level 22Speed   : 84,423,762 bytes/s in 4m 0s
Written :    104,160,735 bytes    [38.61% of Backup + Extra (compression)]

1
2

lzma level 0Speed   : 140,706,271 bytes/s in 2m 24s
Written :     99,282,242 bytes    [36.80% of Backup + Extra (compression)]

1
2

lzma level 4Speed   : 140,706,271 bytes/s in 2m 24s
Written :     99,749,436 bytes    [36.98% of Backup + Extra (compression)]

1
2

lzma level 6Speed   : 35,115,603 bytes/s in 9m 37s
Written :     99,021,470 bytes    [36.71% of Backup + Extra (compression)]

The trends observed earlier do continue : zlib slows down things a bit whilst providing some nice compression, but zstd is fast enough not to have any impact on duration yet providing better compression than zlib.

lzma on the other hand is slower, though again not much slower than zlib, yet provides better compression - even than zstd can pull of at its maximum level.

I'll also note than no, I didn't make a copy/paste error (as I also first thought), levels 0 and 4 did get the exact same speeds, but the former managed to compress things a little more during that time.

Another incremental backup

1
2
3
4

backupSpeed   : 127,509,978 bytes/s in 2m 39s
Backup  :    286,631,666 bytes    [1.41% of Source (deduplication)]
Extra   :     27,973,723 bytes    (metadata + overhead)
Written :    314,605,389 bytes    (Backup + Extra)

1
2

zlibSpeed   : 119,965,009 bytes/s in 2m 49s
Written :    136,857,330 bytes    [47.75% of Backup + Extra (compression)]

1
2

zstd level 8Speed   : 131,649,912 bytes/s in 2m 34s
Written :    124,795,410 bytes    [43.54% of Backup + Extra (compression)]

1
2

zstd level 22Speed   : 74,812,127 bytes/s in 4m 31s
Written :    121,821,393 bytes    [42.50% of Backup + Extra (compression)]

1
2

lzma level 0Speed   : 113,263,053 bytes/s in 2m 59s
Written :    116,446,359 bytes    [40.63% of Backup + Extra (compression)]

1
2

lzma level 4Speed   : 115,193,673 bytes/s in 2m 56s
Written :    116,927,621 bytes    [40.79% of Backup + Extra (compression)]

1
2

lzma level 6Speed   : 26,193,910 bytes/s in 12m 54s
Written :    116,188,958 bytes    [40.54% of Backup + Extra (compression)]

Exactly what we expected by now, zstd even manages to get the duration of the backup process to be less than that without compression ! Noting that this is something you'd have probably gotten every time by lowering to level 7 or below, but obvisously at some compression cost.

One final increment to go, then we're done, we can go home

1
2
3
4

backupSpeed   : 141,631,891 bytes/s in 2m 23s
Backup  :    289,827,318 bytes    [1.43% of Source (deduplication)]  
Extra   :     27,831,427 bytes    (metadata + overhead)
Written :    317,658,745 bytes    (Backup + Extra)

1
2

zlibSpeed   : 131,515,327 bytes/s in 2m 34s
Written :    129,262,919 bytes    [44.60% of Backup + Extra (compression)]

1
2

zstd level 8Speed   : 142,629,298 bytes/s in 2m 22s
Written :    116,527,054 bytes    [40.21% of Backup + Extra (compression)]

1
2

zstd level 22Speed   : 78,501,397 bytes/s in 4m 18s
Written :    113,475,627 bytes    [39.15% of Backup + Extra (compression)]

1
2

lzma level 0Speed   : 126,583,502 bytes/s in 2m 40s
Written :    108,323,330 bytes    [37.38% of Backup + Extra (compression)]

1
2

lzma level 4Speed   : 125,797,269 bytes/s in 2m 41s
Written :    108,825,556 bytes    [37.55% of Backup + Extra (compression)]

1
2

lzma level 6Speed   : 32,353,610 bytes/s in 10m 26s
Written :    108,058,931 bytes    [37.28% of Backup + Extra (compression)]

And thus our journey into compression statistics ends. Before running those tests, I had set the default level for lzma to 6, and was wondering whether that was optimal or maybe lowering to 5 (or even 4) wouldn't be a better option.

In the end, as announced earlier, I've set it to level 0, which is a far superior choice indeed.

Now for speed-minded users, zstd is the recommended option : you get no impact on backup duration and a much smaller output. One could even lower the level to speed things up, but that will cost you. I can't say how much, I haven't actually ran those tests.

As for size-oriented users, lzma (with its default level 0) is the better option : for only a small impact on duration, you get much better compression than you'd otherwise get. Except for a higher lzma level, but for that to really become worthy you'd suffer some serious slow down.

More on compression

If somehow you haven't had enough on the topics, or are intereste in more general comparisons between those algorithms (and some bzip2 too), I'll lead you to this nice post on Clear Linux that even features some graphs ! :)