Efficient integer floor function in C++
Casting to int is notoriously slow.
Maybe you've been living under a rock since x86-64, or otherwise missed that this hasn't been true for a while on x86. :)
SSE/SSE2 have an instruction to convert with truncation (instead of the default rounding mode). The ISA supports this operation efficiently precisely because conversion with C semantics is not rare in actual codebases. x86-64 code uses SSE/SSE2 XMM registers for scalar FP math, not x87, because of this and other things that make it more efficient. Even modern 32-bit code uses XMM registers for scalar math.
When compiling for x87 (without SSE3 fisttp), compilers used to have to change the x87 rounding mode to truncation, FP store to memory, then change the rounding mode back again. (And then reload the integer from memory, typically from a local on the stack, if doing further stuff with it.) x87 was terrible for this.
Yes that was horribly slow, e.g. in 2006 when the link in @Kirjain's answer was written, if you still had a 32-bit CPU or were using an x86-64 CPU to run 32-bit code.
Converting with a rounding mode other than truncation or default (nearest) isn't directly supported, and until SSE4.1 roundps/roundpd your best bet was magic-number tricks like in the 2006 link from @Kirjain's answer.
Some nice tricks there, but only for double -> 32-bit integer. Unlikely to be worth expanding to double if you have float.
Or more usually, simply add a large-magnitude number to trigger rounding, then subtract it again to get back to the original range. This can work for float without expanding to double, but I'm not sure how easy it is to make floor work.
Anyway, the obvious solution here is _mm256_floor_ps() and _mm256_cvtps_epi32 (vroundps and vcvtps2dq). A non-AVX version of this can work with SSE4.1.
I'm not sure if we can do even better; If you had a huge array to process (and couldn't manage to interleave this work with other work), you could set the MXCSR rounding mode to "towards -Inf" (floor) and simply use vcvtps2dq (which uses the current rounding mode). Then set it back. But it's probably better to cache-block your conversion or do it on the fly as you generate the data, presumably from other FP calculations that need the FP rounding mode set to the default Nearest.
roundps/pd/ss/sd is 2 uops on Intel CPUs, but only 1 uop (per 128-bit lane) on AMD Ryzen. cvtps2dq is also 1 uop. packed double->int conversion also includes a shuffle. Scalar FP->int conversion (that copies to an integer register) usually also costs an extra uop for that.
So there's room for the possibility of magic-number tricks being a win in some cases; it maybe worth investigating if _mm256_floor_ps() + cvt are part of a critical bottleneck (or more likely if you have double and want int32).
@Cássio Renan's int foo = floorf(f) will actually auto-vectorize if compiled with gcc -O3 -fno-trapping-math (or -ffast-math), with -march= something that has SSE4.1 or AVX. https://godbolt.org/z/ae_KPv
That's maybe useful if you're using this with other scalar code that's not manually vectorized. Especially if you're hoping the compiler will auto-vectorize the whole thing.
Have a look at magic numbers. The algorithm proposed on the web page should be far more efficient than simple casting. I've never used it myself, but this is the performance comparison they offer on the site (xs_ToInt and xs_CRoundToInt are the proposed functions):
Performing 10000000 times:
simple cast 2819 ms i.e. i = (long)f;
xs_ToInt 1242 ms i.e. i = xs_ToInt(f); //numerically same as above
bit-twiddle(full) 1093 ms i.e. i = BitConvertToInt(f); //rounding from Fluid
fistp 676 ms i.e. i = FISTToInt(f); //Herf, et al x86 Assembly rounding
bit-twiddle(limited) 623 ms i.e. i = FloatTo23Bits(f); //Herf, rounding only in the range (0...1]
xs_CRoundToInt 609 ms i.e. i = xs_CRoundToInt(f); //rounding with "magic" numbers
Further, the xs_ToInt is apparently modified so that the performance improves:
Performing 10000000 times:
simple cast convert 3186 ms i.e. fi = (f*65536);
fistp convert 3031 ms i.e. fi = FISTToInt(f*65536);
xs_ToFix 622 ms i.e. fi = xs_Fix<16>::ToFix(f);
Brief explanation of how the 'magic numbers' method works:
"Basically, in order to add two floating point numbers, your processor "lines up" the decimal points of the numbers so that it can easily add the bits. It does this by "normalizing" the numbers such that the most significant bits are preserved, i.e. the smaller number "normalizes" to match the bigger one. So the principle of the "magic number" conversion that xs_CRoundToInt() uses is this: We add a big enough floating point number (a number that is so big that there are significant digits only UP TO the decimal point, and none after it) to the one you're converting such that: (a) the number gets normalized by the processor to its integer equivalent and (b) adding the two does not erase the integral significat bits in the number you were trying to convert (i.e. XX00 + 00YY = XXYY)."
The quote is taken from the same web page.
If you're doing this in batch, the compiler may autovectorize it, if you know what you're doing. For example, here is an small implementation that autovectorizes the conversion of floats to integers, on GCC:
#include <cmath>
// Compile with -O3 and -march=native to see autovectorization
__attribute__((optimize("-fno-trapping-math")))
void testFunction(float* input, int* output, int length) {
// Assume the input and output are aligned on a 32-bit boundary.
// Of course, you have to ensure this when calling testFunction, or else
// you will have problems.
input = static_cast<float*>(__builtin_assume_aligned(input, 32));
output = static_cast<int*>(__builtin_assume_aligned(output, 32));
// Also assume the length is a multiple of 32.
if (length & 31) __builtin_unreachable();
// Do the conversion
for (int i = 0; i < length; ++i) {
output[i] = floor(input[i]);
}
}
This is the generated assembly for x86-64 (With AVX512 instructions):
testFunction(float*, int*, int):
test edx, edx
jle .L5
lea ecx, [rdx-1]
xor eax, eax
.L3:
# you can see here that the conversion was vectorized
# to a vrndscaleps (that will round the float appropriately)
# and a vcvttps2dq (thal will perform the conversion)
vrndscaleps ymm0, YMMWORD PTR [rdi+rax], 1
vcvttps2dq ymm0, ymm0
vmovdqa64 YMMWORD PTR [rsi+rax], ymm0
add rax, 32
cmp rax, rdx
jne .L3
vzeroupper
.L5:
ret
If your target doesn't support AVX512, it will still autovectorize using SSE4.1 instructions, assuming you have those. This is the output with -O3 -msse4.1:
testFunction(float*, int*, int):
test edx, edx
jle .L1
shr edx, 2
xor eax, eax
sal rdx, 4
.L3:
roundps xmm0, XMMWORD PTR [rdi+rax], 1
cvttps2dq xmm0, xmm0
movaps XMMWORD PTR [rsi+rax], xmm0
add rax, 16
cmp rax, rdx
jne .L3
.L1:
ret