[treffer]

There is one thing you can't with most algorithms: prallelize decompression. That's because most compression algorithms use sliding windows to remove repetitive sections.

And decompression speed also drops as compression ratio increases.

If you transfer over say a 1GBit link then transfer speed is likely the bottleneck as zstd decompression can reach >200MB/s. However if you have a 10GBit link then you are CPU bound on decompression. See e.g. decompression speed at [1].

Bzip2 is not window but block based (level 1 == 100kb blocks, 9 == 900kb blocks iirc). This means that, given enough cores, both compression and decompression can parallelize. At something like 10-20MB/s per core. So somwhere >10 cores you will start to outperform zstd.

Granted, that's a very very corner case. But one you might hit with servers. That's how I learned about it. But so far I've converged on zstd for everything. It is usually not worth the hassle to squeeze these last performance bits out.

[1] https://gregoryszorc.com/blog/2017/03/07/better-compression-...

[dralley]

That's possible with pzstd in any case. zstd upstream has a plan to eventually support parallel decompression natively but hasn't prioritized it given the complexity and lack of immediate need.

https://github.com/facebook/zstd/issues/2499#issuecomment-78...

[treffer]

The issue talks about one vs. multiple frames. That's exactly the issue. It's not a matter of complexity, it's a matter of bad compromises.

The issue can be easily played through. The most simplistic encoding where the issue happens is RLE (run length encoding).

Say we have 1MB of repeated 'a'. Originally 'aaa....a'. We now encode it as '(length,byte)', so the stream turns into (1048576,'a').

Now we would want to parallelize it over 16 cores. So we split the 1MB into 16 64k chunks and compress each chunk independently. This works but is ~16x larger.

Similar things happen for window based algorithms. We encode repeated content as (offset,length), referencing older occurrences. Now imagine 64k of random data, repeated 16 times. The parallel version can't compress anything (16x random data), the non-parallel version will compress it roughly 16:1.

There is a trick to avoid this downside. The lookup is not unlimited, there is a maximum window size to limit memory usage. For compatibility it's 8MB for zstd (at level 19), but you can go all the way to 2GB (ultra, 22, long=31). As you make chunks significantly larger than the window you are only loosing out on the new ramp up. E.g. if you use 80MB chunks then you have a bit less than 10% of the file encoded worse. You could still double your encoded size with a well crafted file. If you don't care about parallel decompression then you are able to only parallelize parts like the lookup search. This gives good speedup, but only on compression. That's the current parallel compression approach in most cases (iirc) leading to a single frame, just faster. The problem is that back-references can only be resolved backwards.

The whole problem is not implementation complexity. It's something you algorithmically can't do with current window based approaches without significant tradeoffs on memory consumption, compression ratio and parallel execution.

For bzip2 the file is always chunked at 900kb boundaries at most. Each block is encoded independently and can be decoded independently. It avoids this whole tradeoff issue altogether.

I would also disagree with "no need". Zstd easily outperforms tar, but even my laptop SSD is faster than the zstd speed limits. I just don't have the _external_ connectivity to get something onto my disk fast enough. I've also worked with servers 10 years ago where the PCIe bus to the RAID card was the limiting factor. Again easily exceeding the speed limits.

Anyway, as mentioned a few times it's an odd corner case. And one can't go wrong by choosing zstd for compression. But it is real fun to dig into these issues and look at them, I hope this sparks some interest in it!

[dralley]

My point is, it's already possible to use multiple independently compressed (and decompressable) frames with zstd if you really want to.

It's even in the zstd repo, under a "contrib" implementation

https://github.com/facebook/zstd/blob/87af5fb2df7c68cc70c090...

That does, of course, require that you compress it into multiple frames to begin with, which could be a problem if you don't control the source of the compressed files, because the default is a single frame. In theory if everyone used pzstd to compress their files, it would be strictly superior to BZ2 in nearly every circumstance. As it is, you do have to go out of your way to do that.

But I don't think that necessarily means the single-frame choice by default is a bad tradeoff. It's better in most circumstances. And if they do eventually figure out a reasonably efficient way to handle intra-frame parallel decompression, then it's just gravy.