6 ms·

Iguana: fast SIMD-optimized decompression

162 points by l2dy 3y ago

aydyn 3y ago
Decompression speed looks good, but in my experience once you get past a certain point (~X000 MB/s) performance gains become pretty marginal in real world applications. I'd like to see compression speeds and performance on AVX if AVX-512 is not available.
- 2h 3y ago
  I don't agree with this. The whole point of tools like this, is that we don't live in age of dial up internet anymore, and haven't for a long time. 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.
  - scaramanga 3y ago
    Definitely there's a lot of workloads that are pure data-munging, where you don't want to store the whole bloated JSON (or protobuf) mess on eg. S3 where you're paying by the byte, but at the same time, you're looking at key parts of your infra which are spending double digit percentages of their CPU time just decompressing stuff. 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.
- gopalv 3y ago
  > in my experience once you get past a certain point (~X000 MB/s) performance gains become pretty marginal in real world applications 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/iguana/decompress_iguana_amd64.s#L34 https://github.com/SnellerInc/sneller/blob/master/ion/zion/i...
- marginalia_nu 3y ago
  Yeah, I think often these benchmarks don't capture the constant factor. The rate at which 4 Kb strings can be decompressed probably matter more than rate at which 400 Mb files can be decompressed. Benchmarks are hard though.
shoo 3y ago
technically this looks really impressive. great to see a new compression approach that supports extremely high performance decompression, with a high performance open source implementation. 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. [1] https://corecursive.com/data-compression-yann-collet/ https://corecursive.com/data-compression-yann-collet/
- pmh91 3y ago
  Hi! Sneller CTO here. 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.
  - adgjlsfhk1 3y ago
    this is very cool. thank you for releasing it! if you had to guess, how much of the performance depends on avx512 specifically? if this could run reasonably well on avx2, IMO this would be a really great general successor to LZ4
deleted 3y ago
[deleted]
Alifatisk 3y ago
What do people use these for?
- deleted 3y ago
  [deleted]
- hmottestad 3y ago
  Someone else brought up the recent podcast episode of CoRecursive. One benefit that was brought up was compression of the cache close to the user’s physical location. Facebook has a lot of machines around the world dedicated to this sort of cache. They need a balance between compression ratio and compression/decompression throughput. There’s no point using a great compression algorithm to achieve an amazing compression ratio if you end up being CPU-bound when you need to decompress it later on.
- bugboy73 3y ago
  DISCLAIMER: I'm one of the Sneller developers 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.
- marginalia_nu 3y ago
  I don't use Iguana in particular, but zstd and lz4 in Marginalia Search. 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.
powturbo 3y ago
As general purpose compressor iguana is decompressing a lot slower than advertised, when tested with a typical data compression corpus. 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-compressor?p=79634&viewfull=1#post79634 https://encode.su/threads/4041-Iguana-a-fast-vectorized-comp... - benchmark from the iguana developers here: https://github.com/SnellerInc/sneller/tree/master/cmd/iguanabench 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.
- thomasahle 3y ago
  > It requires: avx512-vbmi2, available only on skylake-X/Tiger-lake/AMD zen4 Isn't Avx 512 also available on Xeon which is most hosted servers, like aws.
  - powturbo 3y ago
    Not only AVX-512, but AVX-512 + VBMI2
  - Aardwolf 3y ago
    No modern intel consumer CPU has avx512 anymore, they only support at most the 10 year old avx2 vector instruction set, because they want to give every single consumer chip efficiency cores, those can't handle it, and even the performance cores have this feature removed due to it. The modern AMD Zen 4 CPU's for consumers do support avx512 (including avx512_vbmi2).
    - powturbo 3y ago
      > and even the performance cores have to be downgraded for it. Old rumours, it's no longer true.
pella 3y ago
Thank you, Promising work! 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/APKBUILD https://github.com/alpinelinux/aports/blob/master/main/zstd/...
zX41ZdbW 3y ago
It looks similar to LZSSE. We tried it in ClickHouse, but then removed it: https://github.com/ClickHouse/ClickHouse/pull/24424 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 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.
- xxpor 3y ago
  Looks like they switched from AGPL to Apache 2 last week? https://github.com/SnellerInc/sneller/commit/05410a85f900e02f1cf97cdb57c77feae0d695b4 https://github.com/SnellerInc/sneller/commit/05410a85f900e02...
  - zX41ZdbW 3y ago
    This is amazing news! 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#issuecomment-1454755111 https://github.com/ClickHouse/ClickHouse/issues/45130#issuec...
- Asm2D 3y ago
  A C version of the library with a portable implementation and AVX-512 optimizations is planned.
eigenrick 3y ago
Is this effected by Microsoft's patent on various rAns coding and decoding? If not, how does it avoid the (rather vague) claims? https://patents.google.com/patent/US11234023B2/en https://patents.google.com/patent/US11234023B2/en
powturbo 3y ago
Most time-series / analytical databases,... are already using or switching to integer-compression [1] where you can compress/decompress several times (>100GB/s see TurboBitByte in [2]) faster than general purpose compressors. [1] - https://github.com/powturbo/TurboPFor-Integer-Compression https://github.com/powturbo/TurboPFor-Integer-Compression [2] - https://github.com/powturbo/TurboPFor-Integer-Compression/issues/96 https://github.com/powturbo/TurboPFor-Integer-Compression/is...

162 points by l2dy 3y ago

Decompression speed looks good, but in my experience once you get past a certain point (~X000 MB/s) performance gains become pretty marginal in real world applications. I'd like to see compression speeds and performance on AVX if AVX-512 is not available.

2h 3y ago
I don't agree with this. The whole point of tools like this, is that we don't live in age of dial up internet anymore, and haven't for a long time. 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.
- scaramanga 3y ago
  Definitely there's a lot of workloads that are pure data-munging, where you don't want to store the whole bloated JSON (or protobuf) mess on eg. S3 where you're paying by the byte, but at the same time, you're looking at key parts of your infra which are spending double digit percentages of their CPU time just decompressing stuff. 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.
gopalv 3y ago
> in my experience once you get past a certain point (~X000 MB/s) performance gains become pretty marginal in real world applications 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/iguana/decompress_iguana_amd64.s#L34 https://github.com/SnellerInc/sneller/blob/master/ion/zion/i...
marginalia_nu 3y ago
Yeah, I think often these benchmarks don't capture the constant factor. The rate at which 4 Kb strings can be decompressed probably matter more than rate at which 400 Mb files can be decompressed. Benchmarks are hard though.

shoo 3y ago

technically this looks really impressive. great to see a new compression approach that supports extremely high performance decompression, with a high performance open source implementation. 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. [1] https://corecursive.com/data-compression-yann-collet/ https://corecursive.com/data-compression-yann-collet/

pmh91 3y ago
Hi! Sneller CTO here. 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.
- adgjlsfhk1 3y ago
  this is very cool. thank you for releasing it! if you had to guess, how much of the performance depends on avx512 specifically? if this could run reasonably well on avx2, IMO this would be a really great general successor to LZ4

deleted 3y ago

[deleted]

Alifatisk 3y ago

What do people use these for?

deleted 3y ago
[deleted]
hmottestad 3y ago
Someone else brought up the recent podcast episode of CoRecursive. One benefit that was brought up was compression of the cache close to the user’s physical location. Facebook has a lot of machines around the world dedicated to this sort of cache. They need a balance between compression ratio and compression/decompression throughput. There’s no point using a great compression algorithm to achieve an amazing compression ratio if you end up being CPU-bound when you need to decompress it later on.
bugboy73 3y ago
DISCLAIMER: I'm one of the Sneller developers 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.
marginalia_nu 3y ago
I don't use Iguana in particular, but zstd and lz4 in Marginalia Search. 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.

powturbo 3y ago

As general purpose compressor iguana is decompressing a lot slower than advertised, when tested with a typical data compression corpus. 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-compressor?p=79634&viewfull=1#post79634 https://encode.su/threads/4041-Iguana-a-fast-vectorized-comp... - benchmark from the iguana developers here: https://github.com/SnellerInc/sneller/tree/master/cmd/iguanabench 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.

thomasahle 3y ago
> It requires: avx512-vbmi2, available only on skylake-X/Tiger-lake/AMD zen4 Isn't Avx 512 also available on Xeon which is most hosted servers, like aws.
- powturbo 3y ago
  Not only AVX-512, but AVX-512 + VBMI2
- Aardwolf 3y ago
  No modern intel consumer CPU has avx512 anymore, they only support at most the 10 year old avx2 vector instruction set, because they want to give every single consumer chip efficiency cores, those can't handle it, and even the performance cores have this feature removed due to it. The modern AMD Zen 4 CPU's for consumers do support avx512 (including avx512_vbmi2).
  - powturbo 3y ago
    > and even the performance cores have to be downgraded for it. Old rumours, it's no longer true.

pella 3y ago

Thank you, Promising work! 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/APKBUILD https://github.com/alpinelinux/aports/blob/master/main/zstd/...

zX41ZdbW 3y ago

It looks similar to LZSSE. We tried it in ClickHouse, but then removed it: https://github.com/ClickHouse/ClickHouse/pull/24424 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 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.

xxpor 3y ago
Looks like they switched from AGPL to Apache 2 last week? https://github.com/SnellerInc/sneller/commit/05410a85f900e02f1cf97cdb57c77feae0d695b4 https://github.com/SnellerInc/sneller/commit/05410a85f900e02...
- zX41ZdbW 3y ago
  This is amazing news! 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#issuecomment-1454755111 https://github.com/ClickHouse/ClickHouse/issues/45130#issuec...
Asm2D 3y ago
A C version of the library with a portable implementation and AVX-512 optimizations is planned.

eigenrick 3y ago

Is this effected by Microsoft's patent on various rAns coding and decoding? If not, how does it avoid the (rather vague) claims? https://patents.google.com/patent/US11234023B2/en https://patents.google.com/patent/US11234023B2/en

powturbo 3y ago

Most time-series / analytical databases,... are already using or switching to integer-compression [1] where you can compress/decompress several times (>100GB/s see TurboBitByte in [2]) faster than general purpose compressors. [1] - https://github.com/powturbo/TurboPFor-Integer-Compression https://github.com/powturbo/TurboPFor-Integer-Compression [2] - https://github.com/powturbo/TurboPFor-Integer-Compression/issues/96 https://github.com/powturbo/TurboPFor-Integer-Compression/is...