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!
purplesyringa 3 hours ago [-]
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:
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.
Joker_vD 2 hours ago [-]
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.
likoya 2 hours ago [-]
to optimize such small piece of code you need micro benchmarks, and running one micro benchmark for each combination is not realistic
perching_aix 3 hours ago [-]
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...
It was a really fun project!
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!
> 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.
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...