I was curious about whether one of the count bits instructions can help. Of course I'm lazy now and asked an llm to check... The llm noticed that the articles solution includes a floating point subtract in the end. This is fine since the target is wasm which has fsub/fadd, but was initially odd to see in a floating point emulator.
Apparently a ctz solution is a bit longer, but doesn't cross from the floating to integer domain at all, so might be better in the overall algorithm. There are hidden implicit floating to int convert instructions.
> This is fine since the target is wasm which has fsub/fadd, but was initially odd to see in a floating point emulator.
For more context, I'm emulating a full-feature FPU (with exceptions, rounding modes, etc.) over a basic FPU (just the five basic operations or so).
> Apparently a ctz solution is a bit longer, but doesn't cross from the floating to integer domain at all, so might be better in the overall algorithm.
That's what I tried originally, in fact I left this snippet in comments:
let exp = (x.abs().to_bits() >> 23).max(1) as i32 + 125; // max(1) for subnormals
let ctz = (x.to_bits() | (1 << 23)).trailing_zeros();
exp + ctz as i32 - 23
The problem with this approach is that you need quite a lot of wiring to handle subnormals and powers of two correctly. `max(1)` in particular requires `cmov`s or equivalently slow bit tricks. I quickly found out that using FP subtraction is significantly faster on modern hardware.
There is also another reason why I preferred the FP-based solution, and that's vectorization. The brute-forced algorithm can be easily vectorized on all major platforms, but `trailing_zeros` is only vectorizable with AVX-512 on x86, and even then it's not even available in WASM. So, in a twist of fate, I actually think emulating CTZ with floating-point is a more interesting avenue than the other way round. I don't want to self-promote, but you can find a recent relevant article on my blog.
Ah, the silly tradeoffs the ISAs expose us to. The CTZ/CLZ is fundamentally faster than floating point subtraction; but that doesn't mean that the CLZ/CTZ instruction will be faster than the FSUB. It could be but the vendors may as well decide to make it as slow as (or even slower than) FSUB.
That keeps the lowest bit in the mantissa, but it also keeps the hidden bit intact, so you get 2^e + 2^k as a result (where `e` is the initial exponent and `k` is the actual lowest bit). I wanted to retain just the lowest set bit, without the hidden bit. Reasonable attempt though.
is this the two types of tech posts that will exist moving forward?
1. look at this (maybe) new thing i made by prompting an LLM that i now (may or may not be able to) explain, ghostwritten by an LLM
2. look at this thing i artisanally handcrafted because i'm such a badass, owning Big LLM and its subhuman followers so hard with this, and i totally do not feel persistently paranoid about being intellectually cucked by LLMs whatsoever
superoptimizers existed long before LLMs were even a naughty thought, and an LLM would have written one for this problem without any issues, likely without even any specific steering that way. which matters exactly none whatsoever if exploring superoptimization oneself was earnestly the goal.
it's hard to genuinely blame the author for (possibly) feeling compelled to frame things this way, so i deleted a previous version of this comment that was even meaner about this. but that only helps so much in offsetting how incessant this type of blogpost is. now if this framing was more of an intentional choice however...
I respect your annoyances, but I think in this case they're overblown. I mention LLMs in two places. The first time is a neutral fact explaining why LLM swarms don't work as a solution, and the second time is one sentence at the very end of the post. I don't think it's reasonable to make inferences about the intended framing from one throw-away sentence.
At this scale, there simply aren't any interactions with hardware that you'd need benchmarking for. Each instruction takes a well-known amount of cycles, and for most instructions in question (+, -, &, |, ^), that's the exact same amount, because they execute on the same ALU.
I was curious about whether one of the count bits instructions can help. Of course I'm lazy now and asked an llm to check... The llm noticed that the articles solution includes a floating point subtract in the end. This is fine since the target is wasm which has fsub/fadd, but was initially odd to see in a floating point emulator.
Apparently a ctz solution is a bit longer, but doesn't cross from the floating to integer domain at all, so might be better in the overall algorithm. There are hidden implicit floating to int convert instructions.
This was a really cool little problem!
Thanks for the comment!
> This is fine since the target is wasm which has fsub/fadd, but was initially odd to see in a floating point emulator.
For more context, I'm emulating a full-feature FPU (with exceptions, rounding modes, etc.) over a basic FPU (just the five basic operations or so).
> Apparently a ctz solution is a bit longer, but doesn't cross from the floating to integer domain at all, so might be better in the overall algorithm.
That's what I tried originally, in fact I left this snippet in comments:
The problem with this approach is that you need quite a lot of wiring to handle subnormals and powers of two correctly. `max(1)` in particular requires `cmov`s or equivalently slow bit tricks. I quickly found out that using FP subtraction is significantly faster on modern hardware.There is also another reason why I preferred the FP-based solution, and that's vectorization. The brute-forced algorithm can be easily vectorized on all major platforms, but `trailing_zeros` is only vectorizable with AVX-512 on x86, and even then it's not even available in WASM. So, in a twist of fate, I actually think emulating CTZ with floating-point is a more interesting avenue than the other way round. I don't want to self-promote, but you can find a recent relevant article on my blog.
Ah, the silly tradeoffs the ISAs expose us to. The CTZ/CLZ is fundamentally faster than floating point subtraction; but that doesn't mean that the CLZ/CTZ instruction will be faster than the FSUB. It could be but the vendors may as well decide to make it as slow as (or even slower than) FSUB.
I shared a toy superoptimizer I made a few years ago: https://news.ycombinator.com/item?id=36117950
It was a really fun project!
That looks really cool! The discussion also contains a ton of useful pointers. Thanks!
Possibly better solution:
Isolate mantissa, clear lowest bit in it, return bit difference as new float. Any problems with this?That keeps the lowest bit in the mantissa, but it also keeps the hidden bit intact, so you get 2^e + 2^k as a result (where `e` is the initial exponent and `k` is the actual lowest bit). I wanted to retain just the lowest set bit, without the hidden bit. Reasonable attempt though.
Well, it would work in the x87 extended precision format, which has no hidden bit...
But you're right, for normal float/double it doesn't.
is this the two types of tech posts that will exist moving forward?
1. look at this (maybe) new thing i made by prompting an LLM that i now (may or may not be able to) explain, ghostwritten by an LLM
2. look at this thing i artisanally handcrafted because i'm such a badass, owning Big LLM and its subhuman followers so hard with this, and i totally do not feel persistently paranoid about being intellectually cucked by LLMs whatsoever
superoptimizers existed long before LLMs were even a naughty thought, and an LLM would have written one for this problem without any issues, likely without even any specific steering that way. which matters exactly none whatsoever if exploring superoptimization oneself was earnestly the goal.
it's hard to genuinely blame the author for (possibly) feeling compelled to frame things this way, so i deleted a previous version of this comment that was even meaner about this. but that only helps so much in offsetting how incessant this type of blogpost is. now if this framing was more of an intentional choice however...
I respect your annoyances, but I think in this case they're overblown. I mention LLMs in two places. The first time is a neutral fact explaining why LLM swarms don't work as a solution, and the second time is one sentence at the very end of the post. I don't think it's reasonable to make inferences about the intended framing from one throw-away sentence.
to optimize such small piece of code you need micro benchmarks, and running one micro benchmark for each combination is not realistic
At this scale, there simply aren't any interactions with hardware that you'd need benchmarking for. Each instruction takes a well-known amount of cycles, and for most instructions in question (+, -, &, |, ^), that's the exact same amount, because they execute on the same ALU.