Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Zigzag Decoding with AVX-512

zeux.io

Post reply on HN
Print view View original

11–20 of 24 posts

Re: Zigzag Decoding with AVX-512

#11

Post by londons_explore »

flohofwoe wrote: post #9
fulafel wrote: post #6

Earlier quoted context omitted.

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

Are there any programming languages which change the data layout beyond naively sorting struct members by alignment? (which at best helps with reducing padding bytes but can be either good or bad for performance, depending on the code which accesses the data).

One simple optimization is to change arrays of struts into struts of arrays. To my knowledge, nothing even makes those changes, despite them being safe and having a huge potential performance benefit.

Re: Zigzag Decoding with AVX-512

#12

Post by flohofwoe »

londons_explore wrote: post #11
flohofwoe wrote: post #9

Earlier quoted context omitted.

Are there any programming languages which change the data layout beyond naively sorting struct members by alignment? (which at best helps with reducing padding bytes but can be either good or bad for performance, depending on the code which accesses the data).

One simple optimization is to change arrays of struts into struts of arrays. To my knowledge, nothing even makes those changes, despite them being safe and having a huge potential performance benefit.

Now that you mention it... :)

Zig has MultiArrayList in the stdlib which does the SoA transform via comptime:

https://ziglang.org/documentation/master/std/#std.multi_arra...

Zig also sorts struct members by size/alignment, but has two escape hatches ('extern struct' which is for C compatibility, and 'packed struct' which offers an explicit bit-by-bit memory layout).

AFAIK Odin and Jai offer the SoA transform as specialized language features, e.g. in Odin:

https://odin-lang.org/docs/overview/#soa-data-types

I'd still always want such data layout transforms as an explicit language feature though, not the compiler making this decision for me.

Re: Zigzag Decoding with AVX-512

#13

Post by inigyou »

fulafel wrote: post #6
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.

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

FORTRAN is used for a lot of numerical algorithms - today! installed on your computer right now in some library! - because it optimizes better than C because it doesn't have pointers.

Re: Zigzag Decoding with AVX-512

#14

Post by fc417fc802 »

inigyou wrote: post #13
fulafel wrote: post #6

Earlier quoted context omitted.

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

FORTRAN is used for a lot of numerical algorithms - today! installed on your computer right now in some library! - because it optimizes better than C because it doesn't have pointers.

As I understand it most of the difference can be made up by adding the restrict qualifier to everything in C.

Re: Zigzag Decoding with AVX-512

#15

Post by fc417fc802 »

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.

Re: Zigzag Decoding with AVX-512

#16

Post by pillmillipedes »

flohofwoe wrote: post #9
fulafel wrote: post #6

Earlier quoted context omitted.

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

Are there any programming languages which change the data layout beyond naively sorting struct members by alignment? (which at best helps with reducing padding bytes but can be either good or bad for performance, depending on the code which accesses the data).

various SQLs and APLs come to mind :) the industry still has a lot to learn from them both

Re: Zigzag Decoding with AVX-512

#17

Post by motoboi »

cmovq wrote: post #5
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.

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.

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.

Re: Zigzag Decoding with AVX-512

#18

Post by fulafel »

flohofwoe wrote: post #9
fulafel wrote: post #6

Earlier quoted context omitted.

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

Are there any programming languages which change the data layout beyond naively sorting struct members by alignment? (which at best helps with reducing padding bytes but can be either good or bad for performance, depending on the code which accesses the data).

Halide comes to mind (though it a DSL and not a full independent language).

I wonder if Futhark does? Eg https://futhark-lang.org/student-projects/pedersen-nelin-msc...

Re: Zigzag Decoding with AVX-512

#19

Post by ignoreusernames »

cmovq wrote: post #5
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.

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

Re: Zigzag Decoding with AVX-512

#20

Post by wood_spirit »

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
Post reply on HN