Zigzag Decoding with AVX-512

https://zeux.io/2026/06/17/zigzag-decoding-avx512/

by luu • 1 month ago

129 22 1 month ago

MaskRay• 1 month ago

While we could utilize zigzag encoding (i>>31) ^ (i<<1) to convert SLEB128-encoded type/addend to use ULEB128 instead, the generate code is inferior to or on par with SLEB128 for one-byte encodings on x86, AArch64, and RISC-V. Haven't tried wider values - but zigzag encoding is likely slower as well

// One-byte case for SLEB128 int64_t from_signext(uint64_t v) { return v < 64 ? v - 128 : v; }

// One-byte case for ULEB128 with zig-zag encoding int64_t from_zigzag(uint64_t z) { return (z >> 1) ^ -(z & 1); }

londons_explore2• 1 month ago

This sort of analysis is great.

Now why can't compilers do this sort of thing automatically?

Almost any problem seems to be possible to speed up 1000x in AVX512+days of thought compared to the naive version written in a python loop. If we could automate that whole process for big codebases the performance gains could be huge.

diamondlovesyou• 1 month ago

Now why can't compilers do this sort of thing automatically?

They do - they just can't assume GFNI instructions are present unless you explicitly say so: https://godbolt.org/z/eYasbKsse

cmovq• 1 month ago

Compilers can’t really, in a meaningful way, change the layout of your data in memory. And you do need to think about your memory layout to get any benefit from SIMD. You’ll notice a lot of compiler auto vectorization insert many instructions just to shuffle data around to get to a usable layout, which negates much of the benefit.

fulafel2• 1 month ago

Depends on the programming language. A good question is why we don't have more optimizable languages in mainstream use.

motoboi• 1 month ago

This is actually a very nice question and the answer is that interpreted languages with a JIT benefit from this.

One example is Java, which will happily vectorize your code into AVX or SSE where possible.

Python just got a JIT compiler and we’ll start seeing the same thing soon.

But as someone else said here, some constructs don’t translate well and adding transformations to show vectorization would negate the perfomance gains.

Sad that the compiler (even Java) can’t explain you this and warn about it, but now with LLM, maybe they’ll start doing things like that soon.

ignoreusernames• 1 month ago

Even when the layout is friendly to simd, auto vectorization can be finicky. As a programmer, it’s really annoying to be constantly inspecting compiler output to see if the code was properly vectorized. Even if it was, slight changes or compiler updates can throw the whole thing off. Auto vectorization is nice when you get performance improvements for “free”, but I find it fragile for the really critical parts where you absolutely need it to be vectorized.

I often wonder about a macro-like thing where we could write a function using a subset of the language that’s simd aware. A bit higher level than using intrinsics or those simd libs

flohofwoe4• 1 month ago

1000x in AVX512+days of thought compared to the naive version written in a python loop

Out of this 1000x speedup you get 100x by just not using python though ;)

Also IIRC the main problem specifically with AVX512 was that mainstream CPUs simply didn't have it, so a smart compiler won't be of much use when the output code only runs on a handful devices.

lifthrasiir• 1 month ago

Intents matter. Compilers can't see through your skull to infer your intents and thus behave very conservatively unless you override that behavior somehow. This inference, alas, also takes (much) time, so compilers have to balance the compilation time with quality of intents guessed as well. (This is why we can't exactly use LLMs in mainstream compilers, by the way.) So go and make a programming language that preserves your intents by every means; but making it practical would be very difficult.

tosh• 1 month ago

it is not easy for a compiler to vectorize

a pragmatic approach: write in a high level interpreted language that rhymes with modern CPUs, vector extensions, memory bandwidth

e.g. apl [0], bqn [1], k [2], kiwi [3]

  - vectors are dense (not boxed)
  - optimized internal representation (e.g. bitpacked bool vectors)
  - primitives act on vectors + use avx, neon if possible

[0] https://www.dyalog.com [1] https://mlochbaum.github.io/BQN/ [2] https://kx.com [3] https://kiwilang.com

great article by marshall on BQN performance compared to C and how to think about it

https://mlochbaum.github.io/BQN/implementation/versusc.html

  - columnar databases: kdb, duckdb, clickhouse
  - machine learning frameworks: pytorch, keras, jax, mlx

mamcx• 1 month ago

Now why can't compilers do this sort of thing automatically?

Because they are not query compilers, ie: They don't know the data.

For example a query compiler could swap index to full scan because it "see" (by runtime statistics) the data not benefit for it.

In the other hand, an optimization here can pessimism there. So optimizers in general should be very conservative because butterfly effects!

flohofwoe4• 1 month ago

Worth mentioning that MeshOptimizer (https://github.com/zeux/meshoptimizer) has become one of a handful 'hidden champion' pillar libraries that probably carries half of the gaming industry.

Basically the curl of asset pipelines ;)

https://github.com/zeux/meshoptimizer/discussions/986

fc417fc8022• 1 month ago

Is the matrix for bit shifting upside down or am I momentarily making a really dumb mistake here? Edit: nvm I missed the footnote which clarifies that for whatever reason the instruction populates the matrix from bottom to top.

wood_spirit• 1 month ago

Zigzag encodings are a common compression scheme used in the Parquet format. It is fun to speculate that these kind of tricks could be applied there in something so commonly under the hood of a lot of data processing and analytics

Zigzag Decoding with AVX-512

Related Stories