Significantly worse compression than ZLIB on DWARF debug info

[resistor]

Describe the bug
ELF executables are able to store DWARF debug info in a compressed format, using ZLIB. I have been experimenting with using ZSTD as a replacement for it, and am generally seeing good results. However, on the ".debug_str_offsets" section, I am seeing significantly worse compression ratios with ZSTD than with ZLIB, even at max compression levels (176KB vs 138KB, from 290KB uncompressed).

To Reproduce
I have attached uncompressed.bin.gz, which is an extracted .debug_str_offsets section from a debug build of the LLVM compiler. It has been compressed with gzip -9. You can reproduce my results above by extracting it to obtain uncompressed.bin, and recompressing that with zstd -19.

Expected behavior
I would generally expect ZSTD's compression ratio to be no worse than that of ZLIB.

Desktop (please complete the following information):
zstd command line interface 64-bits v1.5.0
gzip 1.11

[Cyan4973]

I'm getting good compression ratio on this file at level 18 specifically (<130KB).
Then it gets worse at levels 19 and beyond.

This is uncommon, though it does unfortunately happen from time to time. The explanation is something like a "trapped into local minima" scenario, which prevents the algorithm to "find" the globally shortest path, due to minuscule evaluation differences at the beginning of the file. This is a known problem for all these algorithms, and finding a way to not miss the "better" opportunity is non-trivial, often involving compromises.

Anyway, your file is proving a great training ground to analyze this situation. This could prove useful in finding a solution.

[resistor]

Thanks for the analysis. Unfortunately for this example, it's also the case that ZLIB outperforms ZSTD at the default compression level as well. (138KB vs 234KB)

It also appears that there's something specific about the data patterns in these .debug_str_offset sections that is causing ZSTD pain. I consistently see them compressing significantly better with ZLIB than with ZSTD across a range of object files. I can source some more examples if it would be helpful.

[Cyan4973]

The files seem to generate a ton of short matches of length 3, following a regular 4-bytes pattern.
It's not too surprising, every time we've seen ratio problems at high settings, it has involved such kind of pattern.
Length 3 matches are "relatively difficult" for zstd. They can be found, but then, it's more difficult to determine if they are worthwhile or not. Worse, depending on selecting one match or the other, it can influence the selection for the rest of the block, because evaluation is really very close, so it's easy to lean one way or the other, and then continuously reinforce the selected way.

For files > 256 KB, only levels 18+ can hope to handle that properly. Even then, it's difficult, and while generally "okay", there are cases where the algorithm leans on the wrong side.

I presume we have enough data to learn from the provided sample already. Once it gets improved, it will be interesting to see if the tentative update survives more examples.

[resistor]

I would expect most of the data in this file to be LEB128 variable-width integers. I haven't checked, but it's plausible that they're sorted in some way that would cause the 3-byte ones to come first.

[dwblaikie]

ah, no, they aren't LEB128 encoded in .debug_str_offsets - they're regular sized for faster lookup (by index): https://dwarfstd.org/doc/DWARF5.pdf bottom of page 240: "This header is followed by a series of string table offsets that have the same representation as DW_FORM_strp. For the 32-bit DWARF format, each offset is 4 bytes long; for the 64-bit DWARF format, each offset is 8 bytes long."

[resistor]

Thanks for that clarification.

Looking at the specification and the raw bytes, the data consists of a 12-byte header followed by a sequence of 4-byte little-endian unsigned integers, sorted in increasing order. In this particular file, the high byte of the values is always zero. I'm not sure where specifically 3-byte matches would be coming from, though there's plenty of redundancy in general.

[resistor]

I am attaching two more examples of other debug info sections that compress worse with ZSTD than with ZLIB at default compression levels.

debug_loclists.bin.gz - ZSTD 6.4MB vs ZLIB 5.9MB
debug_rnglists.bin.gz - ZSTD 6.7MB vs ZLIB 5.2MB

Both of these examples are prefixes of the actual section (due to GitHub attachment limits).
One interesting observation: The smaller the prefix I use, the better ZSTD performs relative to ZLIB, i.e. the ratio difference grows super-linearly with input size.

[DemiMarie]

This is uncommon, though it does unfortunately happen from time to time. The explanation is something like a "trapped into local minima" scenario, which prevents the algorithm to "find" the globally shortest path, due to minuscule evaluation differences at the beginning of the file. This is a known problem for all these algorithms, and finding a way to not miss the "better" opportunity is non-trivial, often involving compromises.

For applications in which compression speed is basically irrelevant, would it be possible to try expensive options, such as trying many different paths and picking the best one? I would not at all be surprised if optimum compression is NP-hard or worse, but I imagine there are options if one has compute power to spare.

[Cyan4973]

For applications in which compression speed is basically irrelevant, would it be possible to try expensive options, such as trying many different paths and picking the best one? I would not at all be surprised if optimum compression is NP-hard or worse, but I imagine there are options if one has compute power to spare.

Yes.
But the computing requirement increases very steeply as nb of analyzed options increases too.

[DemiMarie]

Would using a dictionary help? What about preprocessing?

[Cyan4973]

All these options are possible.
They cost a lot of investigation time though.

[ishitatsuyuki]

FYI, I just found some benchmark on debuginfo done by MaskRay:
https://maskray.me/blog/2022-09-09-zstd-compressed-debug-sections

Looking at the number the gist seems that using a level around -9 yields speed comparable to gzip while almost always outperforming its ratio.