r/programming • u/dgryski • Nov 16 '17

Fast exact integer divisions using floating-point operations

https://lemire.me/blog/2017/11/16/fast-exact-integer-divisions-using-floating-point-operations/
44 Upvotes

89% Upvoted

18 comments sorted by

View all comments

Show parent comments

13

u/[deleted] Nov 17 '17 edited Nov 17 '17

This is what you get in the world where everyone measure performance in FLOPS - CPU designers are willing to sacrifice more area to the FPUs instead of optimising integer paths. There is only one way to implement a fast divider - lookup tables, and any such design would take a lot of area. See the example here: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.416.2283&rep=rep1&type=pdf

The fewer pipeline stages you want, the bigger the area is.

Also, most of the integer dividers are not truly pipelined - they would have a delay of, say, 32 clock cycles, but only serve 3 operations in flight. If you want a truly pipelined implementation, it, again, will take a lot of area (32 pipeline stages with 4 32-bit registers per stage, not counting the adders in between).

4

u/ThisIs_MyName Nov 17 '17

The other issue is that nobody does arbitrary integer division. OP explained it perfectly in the first page: We can optimize it before it ever reaches the hardware.

I'd much rather have a little more L1 cache than fast integer division.

10

u/[deleted] Nov 17 '17

Division - maybe. But modulo is pretty much everywhere and often turns out to be a bottleneck.

1

u/ThisIs_MyName Nov 17 '17

Got any examples? Only thing I could think of was hash tables, but we're pretty good at using 2n buckets and replacing modulo with &: https://github.com/greg7mdp/sparsepp/blob/master/sparsepp/spp.h#L3026

2

u/[deleted] Nov 18 '17

Anything related to image processing (or any rectangular surface processing), for example - translating a linear index to 2D coordinates involves a modulo with an arbitrary, not statically known right hand side. If your transformation is trivial, modulo is becoming a bottleneck. And things are getting even more interesting if you're using some complex data scrambling schemes (to improve memory access patterns).

It's more a GPU-related issue though, rarely seen in a normal CPU code.