Superoptimizing an FPU Emulator | Hacker News Reader

Superoptimizing an FPU Emulator

purplesyringa.moe

44 pointsdverlaeckt8014 comments

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:

    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.

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:

    let m = x.to_bits() & f32::MANTISSA_MASK;
    return f32::from_bits(x.to_bits() ^ (m & (m-1));

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.

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

I can assure you I'm very well aware about modern CPU microarchitecture.

Basic ALU operations like +, -, &, etc., run on the exact same ports, so timings are only affected by the shape of the expression. The number of operations is small enough that suboptimal uop-port allocation and register pressure shouldn't occur, so the externally observable outcome depends only on formal latency and throughput (i.e. the height of the tree and the number of nodes, since all the ops except for fp- have the same performance characteristics).

Cache is technically relevant on cold paths due to constant loads, but the number of constants is small enough to fit in a cache line regardless of whether there are two or three of them, so that point is kind of moot. Decreasing the number of constants is still worthwhile, but it's less of a priority than improving timings, and there aren't enough degrees of freedom for multiple algorithms with the same latency/throughput, but different number of constants, to exist.

No offense intended, just wanted to leave this here if someone is interested.

Reply on news.ycombinator.com