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".
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.
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?
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.
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.
> 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.
11 comments
[ 0.26 ms ] story [ 11.9 ms ] threadIn 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.
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.
[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.
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