Binary data compression algorithms

[adminx01]

Hi, I deal with compression of compiled binary data and am always looking to get it better. (while keeping it streamable within dwarfs most of the time)

Recently I stumbled upon mcm compression algorithm specialized on compressing binary data.
https://github.com/mathieuchartier/mcm

Also a fork with improvements until last year https://github.com/eternaleye/mcm (that I couldn't compile unfortunately)

The agorithm is singlethreaded, but perhaps implementation into a format like dwarfs can make it multithread.

Even with mt support, this is not that fast. But it does make me curious about how well it can do or maybe taking it's context mixing techniques into modern algoritms. (I'm not a scientist)

Sharing some other algorithms that are great for this task would be great, I'm happy to learn what I'm not aware of.

Some benchmark: mcm compressed better by 50mib on 6gib binary data than lzma level 9 extreme.

[M-Gonzalo]

Hi! Sorry I'm replying so late. MCM is a great algorithm, with very a competitive compression ratio.
Having said that, it's a 6-year-old program, and it's also Context-Mixing based. Which means it's symmetric, decompressing at roughly the same speed it can compress, and using the same amount of resources (level 11 peaks at 5G of RAM per thread). So, in other words, not really a fit for a filesystem.

Which doesn't mean it can't be used if you treat dwarfs like an archiver. I saw in a thread about brotli that there is an abstraction in dwarfs to add new compression algorithms without too much trouble. I could get behind an MCM-backed dwarfs for some uses, definitely.

[M-Gonzalo]

Here's a quick and dirty comparison of some algorithms:

Text version:

Type	Size	Ratio	Gain over next one		Gain over baseline
Files in folder	221620734	100.00%
dwarfs-mcm	68355726	30.84%	3.82%	mcm over lzma exe	7.33%	mcm over zstd
dwarfs-lzma_exe	76825869	34.67%	0.75%	lzma exe over lzma plain	3.51%	lzma exe over zstd
dwarfs-lzma	78477320	35.41%	0.90%	lzma over brotli	2.76%	lzma plain over zstd
dwarfs-brotli	80474367	36.31%	1.86%	brotli over zstd	1.86%	brotli over zstd
dwarfs-defaults	84594532	38.17%	55.60%	zstd over nothing
dwarfs-none	207804775	93.77%

MCM option was done using mhx's script to extract all blocks and compress them individually

[M-Gonzalo]

Nothing wrong per se, but it's usually a good thing to be aware of any big multinational involved in one's project. Patents and suits and stuff...

[hackernoodle]

yeah, but dwarfs runs on folly and thrift, two products by Facebook. and also uses glog by google

[M-Gonzalo]

Yup. Didn´t think of that lol

[mhx]

Just to be sure, lzma_exe is lzma with something like a --x86 filter before the --lzma filter, right?

[M-Gonzalo]

Just to be sure, lzma_exe is lzma with something like a --x86 filter before the --lzma filter, right?

That's correct. --compression=lzma:level=9:binary=x86

[adminx01]

That is very cool!

Did the use of dwarfs make it be multithreaded though?

Also how is the speed on MT? comparable to LZMA?

[adminx01]

Oh, okay then. This sounds pretty good.

I'd like to try it myself but am not really good at configuring it so some examples on how to do it would be nice.

I understand this script needs to be used somehow? https://github.com/mhx/dwarfs/blob/main/scripts/extract_blocks.py

[M-Gonzalo]

Yes, I'll whip up an example script later today or tomorrow. It's not complicated

[M-Gonzalo]

Yes, I'll whip up an example script later today or tomorrow. It's not complicated

@adminx01:

This is what I do to recompress a dwarfs file using mcm. Note that it's only useful as a size comparison; the resulting file will be of course NOT a valid dwarfs file, but it'll be of a similar size to what it might be once implemented.

# 1. Undo compression of dwarfs file
mkdwarfs --recompress -l0 -i <file_name> -o <file_name-none>
# 2. Create temp dir for uncompressed blocks
mkdir <filename_tmp>
# 3. Extract uncompressed blocks to temp dir
python ~/Applications/extract_blocks.py <filename-none> <filename_tmp/filename>
# 4. Compress the blocks in parallel (one per CPU thread).
#    Once a block is compressed, concatenate its contents to a file
#    with the same name as the original and the 'mcm' extension,
#    and delete the temporarily compressed mcm block
find <filename_tmp> -type f | parallel --bar "mcm -x6 {} {}.mcm && pv {}.mcm >><filename.mcm> && rm {}.mcm"

[adminx01]

I just tried it and got better results than than your tests.

On a program that LZMA compressed to 4.3 gib I had mcm compress with -x6 to 4.1 so 5% gain. With -x9 (11 runs out of ram) I got it to 4.0 so 7% gain.

Very good results vs LZMA and does not take an absurd amount of time to compress. But I didnt test extraction speed yet.

[M-Gonzalo]

Yes, your mileage may vary, depending on the type of data you're compressing. As a rule of thumb, decompression will take about as much much time as compression with mcm, and use as much resources, so be careful if you plan to decompress on a different machine

[mhx]

Hey, just a quick note that I'm not ignoring this thread (or the precomp one). This is all really interesting, but I need to find time to write down some thoughts. While it would be incredibly cool to do all this, it's likely not straightforward. I'll get back.

[adminx01]

Would you consider adding this algorithm as level 10 of compression?

I would find it quite handy for software that is too hungry to run mounted.

[mhx]

I'm going to be quite honest, despite the impressive compression ratio, there isn't much about mcm that makes me want to include it. There's exactly one fork that builds (not even the original repo is in a buildable state), it hasn't really been maintained in 7 years. Last but definitely not least, the decompression speed is just unacceptable. On my (old-ish) Macbook, it takes almost half a minute to decompress a single 16M block. If my hard drive made me wait half a minute before starting up an application, I'd go mad for sure. :)

[mhx]

I've been pondering this (and a few other feature requests / ideas) for a bit now and here are some thoughts:

• It's unlikely I'll integrate a non-mainstream compression algorithm into DwarFS.
• One thing I'd definitely consider is adding "filters" (in the same sense that lzma/xz uses them), in particular, I'd like to make the BCJ filters that are part of lzma/xz available for use with all other compression algorithms.
• I'd like to introduce "categories" as a concept for input files to mkdwarfs. One such category will be, for example, "incompressible". Incompressible files can be clustered in blocks that will not be compressed (but can still exploit redundancy between files though segmentation). The advantage would be that no time is wasted trying to compress incompressible data. By separating data into compressible/incompressible, the blocks storing only compressible data would likely have a better compression ratio as well.
• Another category (or even multiple categories) could be "binary", or "binary-x86" / "binary-arm" / etc. These could easily be determined by parsing the ELF header for binaries / shared objects, for example. Again, these files would be clustered and the resulting blocks could be processed using a BCJ filter before being compressed.

The BCJ filtering would definitely help ZSTD compression as much as it does XZ. MCM is still better, but as far as I can tell it only currently implements x86 filtering (which is why it's only marginally better for ARM binaries):

-rw-r--r-- 1 mhx mhx 4581903 May 27 22:08 sbin_block0.zstd
-rw-r--r-- 1 mhx mhx 4276530 May 27 22:08 sbin_block0-bcj.zstd
-rw-r--r-- 1 mhx mhx 4218348 May 27 19:17 sbin_block0-9ec.xz
-rw-r--r-- 1 mhx mhx 3929040 May 27 19:20 sbin_block0-9ec-x86.xz
-rw-r--r-- 1 mhx mhx 3929040 May 27 22:08 sbin_block0-bcj.xz
-rw-r--r-- 1 mhx mhx 3351660 May 27 20:27 sbin_block0.mcm

-rw-r--r-- 1 mhx mhx 5358249 May 27 22:08 bin-arm_block0.zstd
-rw-r--r-- 1 mhx mhx 5117590 May 27 22:08 bin-arm_block0-bcj.zstd
-rw-r--r-- 1 mhx mhx 4665120 May 27 19:31 bin-arm_block0-9ec.xz
-rw-r--r-- 1 mhx mhx 4453004 May 27 19:34 bin-arm_block0-9ec-arm.xz
-rw-r--r-- 1 mhx mhx 4453004 May 27 22:08 bin-arm_block0-bcj.xz
-rw-r--r-- 1 mhx mhx 4323938 May 27 20:29 bin-arm_block0.mcm

[mhx]

I tried on a 4.3 GiB test case. dwarfs image with -B26 -S26 -l7 is 1,722,719 KiB.

Tar compressed with --ultra -22 is 1,525,709 KiB. No clue why its so much smaller when l7 is supposed to be the same settings? Maybe zstd defaults to higher equivalent of -B and -S values?

A .tar.zstd is not a file system, so random access is not really a priority. In order to extract a single file from a .tar.zstd, you need to decompress everything. With DwarFS, you only need to decompress one or more individual blocks. If you want the best possible compression and don't care about the compressed artifact to be usable as a file system, you'll likely always find a way to achieve a (much) better compression ratio than with DwarFS. From the overall compression ratio (4.3 GiB to ~1.7 GiB), I would assume there's not really much redundancy to be exploited between individual files. So I'd hazard a guess that if you drop from -B26 to -B1, it wouldn't make that much of a difference. OTOH, using zstd on the tar archive can exploit redundancy on a much smaller scale than DwarFS' segmenter. By default at -l7, the segmenter will only be able to exploit redundancy if it finds a match of 4 KiB or more. zstd will be able to make use of matches much smaller. So I'm not too surprised by the difference.

Also, -B and -S are completely different things: -S 26 means DwarFS will use a block size of 2^26 bytes (64 MiB). -B 26 means the segmenter will try to find matching segments in up to 26 blocks.

Anyway, the Tar filtered with BCJ and compressed with --ultra -22 ended up being 1,528,785 KiB. So just a bit worse I guess. It looks like this filter is not very good.

I think the problem may be that the BCJ filter isn't intended to be used on a tar archive. When parsing the input, it needs to keep track of the instructions it sees to ensure it'll only change branch/call/jump instructions. If there is tar metadata mixed with binary data, it may completely lose context and change the wrong bytes, which could definitely cause a worse compression ratio.

This is a problem that I'm not entirely sure how to address. Blindly applying the filter does seem to work okay in a lot of cases, but providing context to the filter might help at the expense of complicating things and making everything (potentially much) slower.

[adminx01]

I think the problem may be that the BCJ filter isn't intended to be used on a tar archive.

That seems to be it. I tried on 2 exe files with the following results:

Original: 48,458 KiB. Zstd: 12,548 KiB. Zstd + BCJ: 11,629 KiB.

Original: 90,107 KiB. Zstd: 26,648 KiB. Zstd + BCJ: 25,639 KiB.

So it does a pretty decent job. But I was hoping this filter would extend to compiled assets that are not very compressible (for example the test case I tried on, zstd could at best get a 96% compression ratio). And it didn't at all. Perhaps there is another filter out there for this type of data. M-Gonzalo mentioned some stuff too below worth looking at.

As for adopting any of them, I think its best to have these as optional.

[mhx]

When you say "assets that are not very compressible", maybe those are already compressed binaries (using upx for example)?

[adminx01]

They probably are, I just don't have the further knowledge due their proprietary nature. In any case, if better results can be achieved then it is fun for me to try to reach them. If they don't have big side-effects.

[mhx]

If they are indeed already compressed, I don't think you'll be able to gain much. Definitely not by the use of a filter that is aimed at dealing with uncompressed binary data.

[adminx01]

Sounds great. Especially the filters in combination with zstd. I dont really care about extreme algorithms anymore since I want to use the format with it's mounting feature. So helping zstd be better is the way!

[M-Gonzalo]

There are the codecs from Bulat Ziganshin's FreeArc. One of them is called dispack (actually an adaptation of the original one). It's what I use on my scripts to filter executable data, and it works great on exes of all origin. rep is an extremely fast deduper which can speed up and help compress better the data blocks. They can be separated from FA, of course

Then there's also this with lots of transforms, including for exe

[M-Gonzalo]

That's the right use for MCM, in my opinion... It's that good because it makes good use of filters, actually...

[adminx01]

One of the algorithms/filters is DELTA. Looks interesting but couldn't find much info about it in terms of independent use. It's supposed to improve compression of tables in binary data.