Rendered at 22:53:07 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
sjrd 1 days ago [-]
There is a paper by Vincent Lefèvre that indeed proves that floating point division and a floor implement the euclidean division, with a careful analysis of when. [1] A corollary of the main theorem in the paper is that, with round to nearest, if x and y fit in 53 bits unsigned then it works out.
> Integer division q=(x/y) and remainder (of Euclidean division) r=(x%y) hardware operations are very sad on current hardware. Typically very long latency and poor throughput. In contrast floating-point division is pretty happy: shorter latency, higher throughput and often more execution units to perform the operation.
oh wow I missed when this started to happen
ted_dunning 40 minutes ago [-]
IT started in the 60s with the CDC6400, actually. It's no wonder you missed it.
Panzerschrek 17 hours ago [-]
> Typically very long latency and poor throughput.
Recently I have been investigating what operations modern compilers for modern CPUs can optimize. I fond, that for floating-point types there are vector division instructions (which compilers use if they can vectorize), but for integers there are still only scalar instructions. It's unclear for me why no vector instructions exist for such basic arithmetic.
juancn 1 days ago [-]
I would love to have some benchmarks for this on some reasonably practical scenario.
In many common cases shift and masking can replace integer division (i.e. hash tables) and you avoid division altogether, and that probably has about the cost of converting an int to a float.
taeric 1 days ago [-]
I'm curious that the latency of these is actually worse than the latency of floating operations. Yes, they are worse than many integer instructions, but they seem to be on basically the same order as the equivalent float operations?
mtklein 1 days ago [-]
My rule of thumb is that integer ops cost 1 cycle except divides, floats 3 but maybe divide is a bit more, then integer divides are like infinity at 20+ cycles that cannot be amortized by vectorization.
When you code simd it's best to assume the integer divide instruction does not exist. Just an impossibility, if you need to divide ints, rethink your whole program.
dzaima 1 days ago [-]
Float divides are still pretty expensive; 8-10 cycles of latency on modern hardware, integer divides being 8-20 cycles. (on Apple M1 both are 8-10 cycles; int div is much worse on older x86 hw)
Integer multiply is also pretty universally 3 cycles of latency, i.e. basically the same as float multiply (or even add!).
What float div definitely has over int div is throughput, as float div comes in vectorized versions on x86 & ARM, and it usually is actually parallelized.
On top of generally fp div generally having higher throughput (M1 gets down to 1 instr/cycle! though int div isn't bad either at 0.5 instrs/cycle; x86 numbers are messy but even 32-bit int div is never better than f64 div, though they're close; also an annoying aspect is that x86 division instrs actually always take a 128-bit divisor, though hopefully a sign-/zero-extended 64-bit value skips the extra work)
brianpaul 1 days ago [-]
Though, if you happen to be dividing by constants, compilers can do a good job of optimizing for that, simd too probably.
jcranmer 1 days ago [-]
Floating-point division requires 53 bits instead of 64 bits for integers. A lot of the increased latency comes from the wider datatypes.
5 days ago [-]
RossBencina 1 days ago [-]
x and y are integers represented as floating point
> d = trunc(x/y); // floor works for unsigned
>
> // NOTE: if only want 'd' and it's being converted to an
> // integer then the truncate or floor operation is
> // free in the float to integer conversion.
Please show me how to portably truncate or floor a floating point value to an int in C for "free".
mtklein 1 days ago [-]
They're typically like a 3-cycle op, right? Obviously that's not zero, but as far as floating point ops get it's a cheap as it gets, like an add, mul, fma, that sorta thing.
1 days ago [-]
NooneAtAll3 1 days ago [-]
I think you misread?
{within float-to-integer conversion} trunc or floor is free
that is, if you are converting, you already get it by default
ranger_danger 1 days ago [-]
Perhaps they meant implicit instead of free, since the comment also explains that `d` is an integer and the intent is to truncate, so the trunc() call is not even necessary when the assigning type is an int.
amelius 1 days ago [-]
Why is floating point faster?
ted_dunning 45 minutes ago [-]
As the article says, some processors only have an instruction that produces 1 bit of quotient per cycle. This gives a variable time for integer division which can be longer than the time it takes to do a floating point operation.
This sort of limitation has a long pedigree and is surprisingly common. For instance, the CDC 6000 series had no general purpose integer arithmetic unit. The DEC Alpha had no integer divide and the standard RISC-5 spec also omits it. Same for low-end ARM chips.
tverbeure 23 hours ago [-]
It’s a more important use case, so CPU vendors throw more resources at it.
ithkuil 16 hours ago [-]
The mantissa has also less bits, so the actual operation is cheaper, which affects latency.
Genbox 5 hours ago [-]
Agner's table[1] for Intel IceLake/TigerLake shows FDIV to have higher latency, but slightly better throughput.
[1] https://hal.univ-lorraine.fr/inria-00070403v1
oh wow I missed when this started to happen
Recently I have been investigating what operations modern compilers for modern CPUs can optimize. I fond, that for floating-point types there are vector division instructions (which compilers use if they can vectorize), but for integers there are still only scalar instructions. It's unclear for me why no vector instructions exist for such basic arithmetic.
In many common cases shift and masking can replace integer division (i.e. hash tables) and you avoid division altogether, and that probably has about the cost of converting an int to a float.
When you code simd it's best to assume the integer divide instruction does not exist. Just an impossibility, if you need to divide ints, rethink your whole program.
Integer multiply is also pretty universally 3 cycles of latency, i.e. basically the same as float multiply (or even add!).
What float div definitely has over int div is throughput, as float div comes in vectorized versions on x86 & ARM, and it usually is actually parallelized.
On top of generally fp div generally having higher throughput (M1 gets down to 1 instr/cycle! though int div isn't bad either at 0.5 instrs/cycle; x86 numbers are messy but even 32-bit int div is never better than f64 div, though they're close; also an annoying aspect is that x86 division instrs actually always take a 128-bit divisor, though hopefully a sign-/zero-extended 64-bit value skips the extra work)
{within float-to-integer conversion} trunc or floor is free
that is, if you are converting, you already get it by default
This sort of limitation has a long pedigree and is surprisingly common. For instance, the CDC 6000 series had no general purpose integer arithmetic unit. The DEC Alpha had no integer divide and the standard RISC-5 spec also omits it. Same for low-end ARM chips.
For latency:
- DIV/IDIV r32: 12 cycles
- DIV/IDIV r64: 15 cycles
- FDIV: 14–16 cycles
Throughput:
- DIV/IDIV r32: 6 cycles
- DIV/IDIV r64: 10 cycles
- FDIV: 4–5 cycles
I didn't check for a more recent CPU.
[1] https://www.agner.org/optimize/instruction_tables.pdf page 366 & 369
Use this instead of x87’s FDIV