Zigzag Decoding with AVX-512 • Hacker News Board

Re: Zigzag Decoding with AVX-512

#21

Post by tosh » Sun, Jun 21, 2026, 2:26 PM UTC

londons_explore wrote: post #3

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.

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

Re: Zigzag Decoding with AVX-512

#22

Post by mamcx » Sun, Jun 21, 2026, 3:01 PM UTC

londons_explore wrote: post #3

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.

> 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!

Re: Zigzag Decoding with AVX-512

#23

Post by keynha » Sun, Jun 21, 2026, 6:01 PM UTC

wood_spirit wrote: post #20

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

[dead]

Re: Zigzag Decoding with AVX-512

#24

Post by VonTum » Sun, Jun 21, 2026, 11:00 PM UTC

ignoreusernames wrote: post #19

cmovq wrote: post #5

Earlier quoted context omitted.

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.

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…

I believe the "Odin" language has this simd-awareness built-in.