back

by raphlinus·3y ago·view on hn ↗
I love these kinds of things and use them in GPU programming, among other things. Things have changed in a variety of ways: population count and count-trailing-zeros are generally available as fast instructions now. Multiply is also now just as fast as other operations, so is not to be avoided.

A couple examples. [1] computes the sum of the number of bytes used of four consecutive segments of a bezier path - each segment can be lineto, quadto, or curveto, can be the end of a path or not, and be i16 or f32. 4 tag bytes are packed into a 32 bit word, it computes all these, then sums them together.

[2] linearizes a recursive subdivision into an iterative loop. The stack depth is represented as the number of zeros in a word, so pushing the stack is a left shift, and popping is a right shift. It turns out you want to pop multiple levels at once, and the number of levels is computed by countTrailingZeros. ([2] is experimental Rust code, but I will adapt this into a compute shader)

[1]: https://github.com/linebender/piet-gpu/blob/main/piet-wgsl/s...

[2]: https://github.com/linebender/kurbo/blob/euler/src/euler.rs#...

1 comments
Multiply is not as cheap as other arithmetic operations such as addition yet, though it has certainly gotten a lot cheaper (and many of these older bithack guides target CPUs that may not have a multiply at all).

As an example, contemporary Intel CPUs can do an addition in a single cycle (latency) but multiplies take 3. They can do 4 independent additions every cycle, but only one multiply.

That's true on CPUs, but I think the parent was talking about GPUs. AFAIK (I have not been able to get very much detailed information on GPU performance characteristics), GPUs tend to do better at such things, in part due to the great width and lower clocks (eg trig functions in just a few clock cycles).

AVX512 may not have killed the GPU market, but consider SIMD on CPUs for flavour: float FMA and add have identical throughput on intel.