Iguana: fast SIMD-optimized decompression
sneller.io
sneller.io
It requires: avx512-vbmi2, available only on ice-lake/Tiger-lake/AMD zen4
- Benchmark from encode.su experts: https://encode.su/threads/4041-Iguana-a-fast-vectorized-comp...
- benchmark from the iguana developers here: https://github.com/SnellerInc/sneller/tree/master/cmd/iguana...
Silesia corpus / cpu Xeon Gold 5320
zstd -b3 3.186 943.9 MB/s
zstd -b9 3.574 1015.8 MB/s
zstd -b18 3.967 910.6 MB/s
lz4 -b1 2.101 3493.8 MB/s
lz4 -b5 2.687 3323.5 MB/s
lz4 -b9 2.721 3381.5 MB/s
iguana -t=0 2.58 4450 MB/s
iguana -t=1 3.11 2260 MB/s
As you can see, iguana with entropy coding enabled (-t 1) has a similar compression ratio to zstd -3, but it decompresses more than twice as quickly. With entropy coding disabled (-t 0), iguana has a compression ratio roughly equivalent to lz4 -5 and decompresses about 33% faster.
Isn't Avx 512 also available on Xeon which is most hosted servers, like aws.
The modern AMD Zen 4 CPU's for consumers do support avx512 (including avx512_vbmi2).
(1) https://releases.llvm.org/7.0.0/tools/clang/docs/AttributeRe...
Old rumours, it's no longer true.
And they chose to give you efficiency cores + performance cores without avx512 on all consumer CPU's, rather than, what would be my preference, sell some with only performance cores with avx512 like their previous gen CPUs. I'd be ok with efficiency cores on a laptop, sure, but not on a desktop machine.
But AMD already gives plenty fast cores with avx512 now so I'm satisfied, I'm simply not an intel user anymore. Of course intel's choice still affects me anyway since the less consumers have avx512, the less software will make use of it.
DISCLAIMER: I work for Sneller
https://github.com/ClickHouse/ClickHouse/pull/24424
Reasons: - the decompression speed is slightly better than for lz4, but the compression speed is low; - the code was non-perfect, and the fuzzer has found issues.
LZSSE library was abandoned five years ago, but they have great blog posts to read: https://github.com/ConorStokes/LZSSE
Iguana looks promising, but AVX-512 requirement is too restrictive. We need something to work both on x86 and ARM. Also, integrating Go assembly into other software is not easy. And A-GPL license makes it incompatible.
https://github.com/SnellerInc/sneller/commit/05410a85f900e02...
PS. Interesting if someone has experience integrating Go Asm dialect into C or C++ build system? We needed it for another experiment https://github.com/ClickHouse/ClickHouse/issues/45130#issuec...
re: winning adoption of new compression approaches, there's an interesting podcast interview [1] with Yann Collet (of lz4 / zstd):
Some factors Yann discussed that helped lz4 & zstd gain traction were: permissive licensing (BSD) ; implementation in C -- widest support for including it into other software ecosystems ; open development & paying attention to issues raised by users of the software ; the new compression approach able beat an existing popular approach in some use cases with no downside: e.g. if a hypothetical new compression approach has 200% faster decompression but offers 10% worse compression ratios, then there's friction for introducing it into an existing system, as the new approach might first require purchase and deployment of additional storage. Whereas a new approach that is 50% faster and has exactly the same or slightly better compression ratios can be adopted with much less friction.
It looks like the Iguana code has recently been relicensed with Apache instead of AGPL (which used for the rest of the sneller repo), which could lower the barrier for other projects to consider adopting Iguana, although there are still dependencies from the Iguana code to code in AGPL licensed files elsewhere in the sneller repo.
Thanks for pointing out the dependency on the AGPL bits -- I'm going to fix that ASAP. (There's just a small utility library we've got to re-license as Apache-2 as well.)
Once we're comfortable committing to the format for the long haul, we're planning on publishing a C implementation as well. There are still a few tweaks we've been evaluating to try to make the compression ratio a tiny bit more competitive.
For the pure-LZ77 Iguana variant (no rANS encoding), most of the decoding time is spent moving memory around rather than decoding the match+length tuples from the input stream, which suggests the performance difference wouldn't be that great if we were only on AVX2, but AVX-512 has a bunch of instructions that are super helpful for parsing our base254 integers quickly. If I had to take a wild guess I'd say it would cost an additional 15%.
One sacrifice we made in the design is that the minimum match offset distance is always 32 bytes, which means we can always perform a literal or match copy by starting with a ymm register load + store. This hurts the compression ratio a bit but it helps performance immensely, and for that reason alone I suspect we'd still come out ahead of lz4 even without AVX-512.
Have you done any testing with running multiple decompression tasks in parallel, or just running a single decompression task while at the same time running other tasks like maybe a web server?
Our typical workload at Sneller uses most of the computational power of the machine: we typically execute heavy AVX-512 workloads on all available cores and we compare our processing performance at GB/s per core. This is generally why we needed a faster decompression, because before Iguana almost 50% of the computational power was spent in a zstd decompressor, which is scalar. The rest of the code is written in Go, but it's insignificant compared to how much time we spend executing AVX-512 now.
(I work for Sneller)
Unless they provide a certified proof of QA assurance memory corruption free code, with respective data fuzzing tests.
OS ABI compliant, by all means, as implementation language, better not.
Thankfully the ongoing cybersecurity bills will improve on this.
Question: How was zstd built in the tests?
In other words, was the possibility of 2-stage pgo+lto optimization taken into account?
(the alpine zstd claim ~ "+30% faster on x86_64 than the default makefile" [1] )
[1] ""
# 2-stage pgo+lto build (non-bootstrap), standard meson usage.
# note that with clang,
# llvm-profdata merge --output=output/somefilename(?) output/.profraw
# is needed.
# believe it or not, this is +30% faster on x86_64 than the default makefile build (same params)..
# maybe needs more testing
# shellcheck disable=2046
""*
https://github.com/alpinelinux/aports/blob/master/main/zstd/...
[1] - https://github.com/powturbo/TurboPFor-Integer-Compression
[2] - https://github.com/powturbo/TurboPFor-Integer-Compression/is...
If not, how does it avoid the (rather vague) claims?
Back then you wanted maximum compression like XZ, because the slowest part of the process was the download. Now especially with XZ awful decompress rate, the slowest part is extract. In many cases it's better to have 9% larger size, for 500% increase in extract, like you get with ZST.
Sure, you can say the problem is JSON, protobuf, whatever. But in a huge organization with hundreds or thousands of types of documents, it's a needless friction to require custom optimized formats for each one.
So a faster decompressor is often a no-brainer of a win and can have substantial dollar values attached.
There might be no latency benefits to that, but there's always a throughput gain from using fewer cpu cycles over all - the cpu cycles you would have spent decompressing can be used for other things.
For that reason single-core performance would still be nice to have and always great to have open source code which is performance centric so that we all get to find out "How the hell did they do it?" (it is very readable assembly [1])
> I'd like to see compression speeds and performance on AVX if AVX-512 is not available.
The ARM is probably more interesting in the elastic compute world right now, the AVX world is unlikely to get cheaper.
And unlike before, I don't need to wait for a vendor to sell me an SoC, Gravitons are already here.
[1] - https://github.com/SnellerInc/sneller/blob/master/ion/zion/i...
Benchmarks are hard though.
Compression is required to make more efficient use of the available bandwidth and RAM. Although AWS provides up to 100Gb/s networking, we improve the net throughput using compression. Also we cache data on the computing nodes, so storing it in compressed form allows us to store more data on the node.
Our query engine is often limited by memory bandwidth when using uncompressed data. So it needs a lot of data and it needs it fast. Because we cache data in compressed form, decompression is always needed, so it should be as fast as possible. That's the primary reason why we developed Iguana, because a faster decompression results in a faster query engine.
First, I use it to store and retrieve crawl data faster. Mechanical hard drives are much slower than these decompression algorithms. So for sequential access, you can make a cheap mechanical drive faster and bigger as big as long as you've got some CPU cycles to spare to decode the data. (This is also true for network, basically anything outside of RAM, as long as it's nice and sequential, there's probably an argument for compressing it)
I also use them to keep more stuff in RAM than what should be possible. I do transparent compression/decompression of some large strings e.g. document HTML that typically compresses with a factor 10x. These algorithms are so fast the performance hit of decompressing the strings as they're used is like a 10% pessimization of the run time for significantly slashing the RAM usage.