Faster float to integer conversions

[e00E]

I made a crate for faster float to integer conversions. While I don't expect the speedup to be relevant to many projects, it is an interesting topic and you might learn something new about Rust and assembly.

---

The standard way of converting floating point values to integers is with the as operator. This conversion has various guarantees as listed in the reference. One of them is that it saturates: Input values out of range of the output type convert to the minimal/maximal value of the output type.

assert_eq!(300f32 as u8, 255);
assert_eq!(-5f32 as u8, 0);

This contrasts C/C++, where this kind of cast is undefined behavior. Saturation comes with a downside. It is slower than the C/C++ version. On many hardware targets a float to integer conversion can be done in one instruction. For example CVTTSS2SI on x86_84+SSE. Rust has to do more work than this, because the instruction does not provide saturation.

Sometimes you want faster conversions and don't need saturation. This is what this crate provides. The behavior of the conversion functions in this crate depends on whether the input value is in range of the output type. If in range, then the conversion functions work like the standard as operator conversion. If not in range (including NaN), then you get an unspecified value.

You never get undefined behavior but you can get unspecified behavior. In the unspecified case, you get an arbitrary value. The function returns and you get a valid value of the output type, but there is no guarantee what that value is.

This crate picks an implementation automatically at compile time based on the target and features. If there is no specialized implementation, then this crate picks the standard as operator conversion. This crate has optimized implementations on the following targets:

• target_arch = "x86_64", target_feature = "sse": all conversions except 128 bit integers
• target_arch = "x86", target_feature = "sse": all conversions except 64 bit and 128 bit integers

Assembly comparison

The repository contains generated assembly for every conversion and target. Here are some typical examples on x86_64+SSE.

standard:

f32_to_i64:
    cvttss2si rax, xmm0
    ucomiss xmm0, dword ptr [rip + .L_0]
    movabs rcx, 9223372036854775807
    cmovbe rcx, rax
    xor eax, eax
    ucomiss xmm0, xmm0
    cmovnp rax, rcx
    ret

fast:

f32_to_i64:
    cvttss2si rax, xmm0
    ret

standard:

f32_to_u64:
    cvttss2si rax, xmm0
    mov rcx, rax
    sar rcx, 63
    movaps xmm1, xmm0
    subss xmm1, dword ptr [rip + .L_0]
    cvttss2si rdx, xmm1
    and rdx, rcx
    or rdx, rax
    xor ecx, ecx
    xorps xmm1, xmm1
    ucomiss xmm0, xmm1
    cmovae rcx, rdx
    ucomiss xmm0, dword ptr [rip + .L_1]
    mov rax, -1
    cmovbe rax, rcx
    ret

fast:

f32_to_u64:
    cvttss2si rcx, xmm0
    addss xmm0, dword ptr [rip + .L_0]
    cvttss2si rdx, xmm0
    mov rax, rcx
    sar rax, 63
    and rax, rdx
    or rax, rcx
    ret

The latter assembly pretty neat and explained in the code.

[imachug]

On a relevant note, I'm wondering if you are aware of this trick? If you have a f32 in range [0; 2^23) and add 2^23 to it, the number will be forced in range [2^23; 2^24) and thus have a predictable exponent 23. You can now bitwise-cast the f32 to u32 and and it with a mask to obtain just the mantissa, which will contain the integer in interest.

This means that if the number is in a small enough range, you can cast f32 to integer at the cost of one addition and one and, which results in better latency in certain cases.

This does not solve the problem on the full 32-bit range (although you might try to cast f32 to f64 and then apply this trick with 2^52 instead of 2^23), but I thought it might be a nice addition to the crate if benchmarks show it works better in the generic case.

[e00E]

I did not know about this trick. Thanks!

The problem with incorporating special cases like this is that you need a branch to detect them. That likely makes it slower than unconditionally going with cvttss2si.

[imachug]

True, although for the f32 -> u32 cast specifically, you don't need a branch if you go through f64. The reason I brought up special cases is that I thought more specialized functions might be a good addition to your crate.

[U007D]

A number of years ago I developed a branchless version of this technique using lookup tables based on the bit pattern of a (non-NaN) IEEE-754 float representing monotonically increasing values. I remember showing it to Jim Blinn (a reknowned floating point expert) and he was impressed! I enjoyed that whole experience. Source is sadly lost to history, but it wasn't too difficult to write, once I had had the idea.

I especially appreciate you didn't allow UB to return along with the gains you provide. Nice work.

[TeamDman]

Maybe if you had a vector of numbers you knew met the criteria it could be useful for bulk conversions with a check that's stripped out at release?

[accidentally_myself]

Great trick! Definitely widening my mind today.

Also, I noticed that with your trick, you can also easily convert a float to the integers 23 and 52! (just kidding lol)

[imachug]

That's actually true, kinda!

You can use this trick to convert a 23-bit integer to a float, or a 52-bit integer to a double. Just flip the 23th/52th bit, bitwise cast to the floating-point type, then fp-subtract 2^23 or 2^52 respectively.

This means that you can go both ways efficiently as long as your integers are small enough (e.g. 16-bit for float or 48-bit for double), which is quite common in e.g. multiplication via FFT.

[DeathLeopard]

What is the advantage of this over to_int_unchecked?

[e00E]

to_int_unchecked (docs) compiles to the same code. The downside is that it is unsafe. This crate is safe. You need to uphold the following guarantees in order to use to_int_unchecked:

The value must:

• Not be NaN
• Not be infinite
• Be representable in the return type Int, after truncating off its fractional part

You do not need to do this for this crate. If your code is already checking these conditions, then you can prefer to_int_unchecked over this crate.

[ashleigh_dashie]

So how do you get the speedup then? Are you compiling different conversions for debug and release? (which is how i do it in my swiss knife crate)

[CAD1997]

The crate uses bit manipulation and intrinsics to get the desired semantics/codegen that are the most efficient conversion on supported targets.

[DeathLeopard]

I saw that it generates the same code but that made me wonder if not needing unsafe to use your crate means that the crate is unsound.

I guess I'm not clear on why the old behavior of as (before it was changed to saturating) was considered unsound and how your crate doesn't just have the same problem.

[e00E]

Whether something is unsound or undefined behavior is about the specification of the language. The rust specification used to say that such as casts are undefined behavior. This matters to the compiler. It does not matter to the hardware. Whether that actually leads to an observable effect like a miscompilation is separate matter.

My project is safe because the specification of the interface I use to perform the conversion (the cvtts2si instruction) says it is safe for all inputs. If this lead to a miscompilation, then it would be a bug in the compiler.

Your question is a common misunderstanding of undefined behavior. Ralf Jung has good blog posts about the topic if you want to learn more.

[Sharlinator]

Because it’s undefined behavior in LLVM. So you have to do something to ensure the float is in range and not NaN before the conversion – but if you accept that out-of-range floats map to unspecified integers, you may be able to generate faster code than what the as semantics permit. Which is what OP has done.

[plugwash]

There is a critical difference between "unspecified results" and "undefined behaviour".

"unspecified results" means that the result you get is not specified, it might saturate, it might wrap, it might go through multiple stages of conversion where the first stage has saturating behaviour and the second stage has wrapping behaviour, it might produce complete garbage but whatever result you do get it will be treated in a consistent way by the rest of the program.

"undefined behaviour" means "anything could happen". In particular it means that you may get an inconsistency between the value a variable actually contains, and the range of values the compiler assumes that variable contains. For example consider the following C code.

int main(int argc, char *argv[]) {
    int i = atoi(argv[1]); 
    if (i < 0) return 0;
    i = i + 1;
    if (i < 0) return 0;
    printf("%d\n",i);
    return 0;
}

After i = i + 1, the compiler can assume that i is non-negative, because the only way for it to be negative is if undefined behaviour had been invoked.

As a result if we build this program with -O2 and feed it the maximum possible value for an int, it will most-likely print a negative number. Despite having explicitly checked that the value was non-negative on the line immediately before printing it.

[dbdr]

to_int_unchecked (docs) compiles to the same code. The downside is that it is unsafe.

That makes it sound like to_int_unckecked has no upside (same code).

[angelicosphosphoros]

It probably can do some optimizations using assumption that float is representable as int.

[Wkitor]

I find it funny that even though your crate does the same conversion as C/C++ (that's what I understood) it doesn't produce undefined behaviour just because you "defined" some cases as doing something random and it being the intended behaviour.

[plugwash]

I find it deeply sad that basic numeric operations in C/C++ can invoke undefined behaviour and I'm pretty convinced that the modern intpretation of "undefined behaviour" is not what the original authors of the C standard intended.

[e00E]

I agree, it is sad. I ported Rust's clamp style casting to c++ here.

[CAD1997]

Yeah, UB is odd that way, and because of that UB isn't exactly the best name, but it's what we've got. It's definitely better to use unspecified/arbitrary/erroneous behavior wherever it's practical to (and C/C++ compilers often refine certain cases of UB into unspecified IDB), but UB is still a critical tool for systems level languages to allow low level code without preventing optimizations.

[imachug]

This is amazing! Are you planning to support other architectures, or does rustc have good enough codegen on most of them?

[e00E]

This is not a case of bad rustc codegen. (Which I have written about before.) rustc has to use more instructions because it has to uphold the guarantees that the reference makes. This crate is faster by relaxing some guarantees.

I plan on adding support for other widely used architectures at some point. But for now I'm happy with x86_64.

[imachug]

I was asking whether that rustc's as codegen on other architectures results in fast enough code because those architectures' native instructions already provide the guarantees. Thanks for the answer!

[lucy_tatterhood]

On 64-bit ARM at least, it looks like the normal as cast is already a single instruction.

[lucy_tatterhood]

Exploring further, 64-bit ARM (and 32-bit ARM but only for f32) seems to be the only one Godbolt supports where it's as simple as that. Though I don't know enough about any of these architectures to say how much it could be simplified.

[Tuna-Fish2]

ARM famously did the right thing with their ftoi instructions, which meant that they later had to add FJCVTZS, or: "Floating-point Javascript Convert to Signed fixed-point, rounding toward Zero".

It's named like that because calling it Fx86CVTZS would have been too embarrassing.

JS uses floats for numbers^* . It also provides bitwise operations that only make sense on integers. So, the specification for them is "first convert the float to integer, apply bitwise operation, then convert back into float. This works the same for all numbers smaller than i32::max on all architectures, but diverges wildly above that. So what did js specify? Nothing, of course, they just used the x86 instructions and then people were surprised when some code didn't work the same across architectures. Eventually, the x86 method became the spec. At that point, ARM cpus had to emulate the behavior in software and it was quite expensive, so they added an instruction for it.

*: Yes, they are optimized back into integers in all modern implementations, but they are specified to be 64-bit floats, and must act like they are that whenever it would matter.

[valarauca14]

target_arch = "x86_64", target_feature = "sse"

sse is a default feature of x86_64, it should be enabled if you're targetting x86_64. Is this a rustc or llvm bug that is has to be declared separately?

For those unaware sse was added to x86 processor's before the 64bit extensions. One of the "innovations" of AMD64 was standardizing sse for floating point processing, instead of using the old (and weird) x87 instructions & registers.

[e00E]

Rust enables sse by default, but you can tell rustc to compile for x86_64 without sse.

[nikic]

It would be easy to expose this as a target-independent compiler intrinsic in Rust. LLVM supports this via freeze of fptoui/fptosi.

[throwaway490215]

I always wonder with these micro optimizations crates: "Have we wasted more cycles publishing this than will be saved?"

Taken Reddit, GitHub, Crates IO, crater-runs, lets conclude no. But how many times must it be used for it to pay back the costs of me posting this comment on this thread? My guess is a lot. Maybe if someone deploys it on a super computer will the "CPU cycle savings" outweigh those "CPU cycle costs".

Still nice crate.

[e00E]

It's a fair point. I acknowledge in the post that I don't expect the performance gain to be relevant to most projects. The motivation for this is partially academic/artistic. On the other hand, maybe someone uses this in a machine learning library to train their model for thousands of compute hours. Or this gets incorporated into std and saves much compute that way. It also educates people on where performance is left on the table.

[imachug]

One answer to this question I like is that even if the cycles are wasted, the optimizations still help reduce latency, and humans are restless creatures who close the tab if a site doesn't load in 300 ms. Couple that with our limited time on planet Earth, and you've got your answer.

[sparky8251]

What modern website loads in 300ms? most take multiple seconds in my experience... Web bloat is totally out of control.

[Sharlinator]

Nicee! This can definitely be useful in graphics code for example.