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 this includes a floating point subtract in the end. This is fine since the target is wasm which has fsub/fadd.
Apparently ctz is a bit longer, but doesn't cross from the floating to integer domain at all, so might be better in the overall algorithm.
> 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.
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 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.
That's wrong due to out of order execution, speculative prediction, the existence of multiple ports for each of those operations, cache and stack management, register pressure, and other quirks of modern cpu
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.
14 comments
[ 22.2 ms ] story [ 173 ms ] threadApparently ctz is a bit longer, but doesn't cross from the floating to integer domain at all, so might be better in the overall algorithm.
This was a really cool little problem!
> 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.
It was a really fun project!