4 ms·

PRs to improve zstd's embarrassingly slow decoder require you to assign your firstborn to Zuck and new Microsoft is selling me a subscription to use my laundere

PRs to improve zstd's embarrassingly slow decoder require you to assign your firstborn to Zuck and new Microsoft is selling me a subscription to use my laundered open source code to generate autocomplete suggestions in their closed-source IDE that pegs 2 cores and needs 4 gigs of memory (on the remote machine only) to edit 50k text files over ssh

mappu 4y ago
Zstd's decoder is very very fast for what it does, what ideas do you have to improve it? It's unlikely to beat lzo family on decompression speed, but that's a different class of compressor entirely. And probably there are still some more tricks zstd can learn from closed-source Oodle leviathan, but i don't think much more can be learned.
- anonymoushn 4y ago
  I expect any "perform a conversion of some sort on a byte stream" implementation that uses 0 SIMD instructions and is not memory bound is leaving a lot of performance on the table, especially if one is permitted to mess with the design and layout of the input to make it more amenable to vectorized consumption. I cannot confidently claim that we're missing a a >2x speedup in this case though, it may be as low as ~1.3x or something.
  - mappu 4y ago
    I checked the zstd source and i'm surprised to see you're right - There's a little x86_64 assembly but I don't see a single SIMD instruction anywhere, and no intrinsics neither. Seems like brotli is the same. I assume zstd still gains something from SIMD autovectorization in the compiler, that might be interesting to benchmark with- and without- such a flag. Since the zstd bytestream got frozen in RFC8478, messing with the layout too much will require a zstd2 and moving the whole world again to use it (linux kernel compression, rpm binary format, etc)
bscphil 4y ago
Ah yes, the embarrassingly slow decoder that just happens to be on the Pareto frontier for decompression speed: http://www.mattmahoney.net/dc/text.html http://www.mattmahoney.net/dc/text.html
- anonymoushn 4y ago
  If you exclude oodle from your benchmarks?
josephg 4y ago
If microsoft's expensive software is bad, why are you using it? And you don't need anyone's permission to make zstd better. You just need their permission to merge your changes into their (upstream) branch. If you think you can maintain zstd better than facebook, fork their code and compete with them. Its BSD licensed after all! And if your zstd changes are sufficiently compelling, maybe everyone will start using your version instead. As a general rule, if I opensource some software I've written, I'm under no obligation to accept pull requests in any form. My time is my own. Facebook is free to run their zstd project however they like. They're already doing good in my books by sharing it with the world, for free, under a BSD license. They don't owe you anything more.

mappu 4y ago

Zstd's decoder is very very fast for what it does, what ideas do you have to improve it? It's unlikely to beat lzo family on decompression speed, but that's a different class of compressor entirely. And probably there are still some more tricks zstd can learn from closed-source Oodle leviathan, but i don't think much more can be learned.

anonymoushn 4y ago
I expect any "perform a conversion of some sort on a byte stream" implementation that uses 0 SIMD instructions and is not memory bound is leaving a lot of performance on the table, especially if one is permitted to mess with the design and layout of the input to make it more amenable to vectorized consumption. I cannot confidently claim that we're missing a a >2x speedup in this case though, it may be as low as ~1.3x or something.
- mappu 4y ago
  I checked the zstd source and i'm surprised to see you're right - There's a little x86_64 assembly but I don't see a single SIMD instruction anywhere, and no intrinsics neither. Seems like brotli is the same. I assume zstd still gains something from SIMD autovectorization in the compiler, that might be interesting to benchmark with- and without- such a flag. Since the zstd bytestream got frozen in RFC8478, messing with the layout too much will require a zstd2 and moving the whole world again to use it (linux kernel compression, rpm binary format, etc)

bscphil 4y ago

Ah yes, the embarrassingly slow decoder that just happens to be on the Pareto frontier for decompression speed: http://www.mattmahoney.net/dc/text.html http://www.mattmahoney.net/dc/text.html

anonymoushn 4y ago
If you exclude oodle from your benchmarks?

josephg 4y ago

If microsoft's expensive software is bad, why are you using it? And you don't need anyone's permission to make zstd better. You just need their permission to merge your changes into their (upstream) branch. If you think you can maintain zstd better than facebook, fork their code and compete with them. Its BSD licensed after all! And if your zstd changes are sufficiently compelling, maybe everyone will start using your version instead. As a general rule, if I opensource some software I've written, I'm under no obligation to accept pull requests in any form. My time is my own. Facebook is free to run their zstd project however they like. They're already doing good in my books by sharing it with the world, for free, under a BSD license. They don't owe you anything more.