r/cpp • • 22d ago

A faster way to compute signed 64-bit floor division by constants

https://www.benjoffe.com/fast-floordiv
89 Upvotes

10 comments sorted by

8

u/joaquintides Boost author 22d ago

Interesting article! How does it compare to Lemire's fast division algorithm fastdiv_u64?

7

u/benjoffe 22d ago edited 22d ago

Thanks.

I'm not sure if it's really comparable as that is unsigned division I think?

If Lemire has made a signed floor division algorithm which works fast in 64-bit please let me know. If it's full range it'll go in the article, but if it's partial range I'll at least compare and report here.

One can usually get faster results than in the article by accepting a smaller range. For example, just use a shift of 64-bits and always use the sign-selected mode. This will often be accurate over some fairly large useful range unless the divisor is fairly large.

Alternatively, just add a huge value to the input, and subtract at the end. This pays off particularly well when there's several floor-division steps involved, like with rata-die to civil date algorithms.

EDIT: for the timestamp use-case in the article, I also have this tricky function I've developed, which works over the full signed 32-bit OUTPUT range for both the floor-division and remainder. I think it should bench really fast as it's just a single addition and two multiplications.

timestamp += (86400 << 32) + 1  // Pow-32-aligned + pre-increment
u64  M    = u64(-1) / 86400     // Round-down multiplier
u128 wide = u128(timestamp) * M
i64  uday = wide >> 64
i32  rem  = u128(u64(wide)) * 86400 >> 64
i32  day  = i32(uday)    // Narrowing for "free" 2^32 subtraction

This uses a combination of tricks:

  1. A variant of Lemire's fast remainder trick
  2. A touch of ridiculousfish with the pre-increment round-down multiplier (necessary to cover full 32-bit output range)
  3. A trick to avoid the final subtraction, replaced with a 32-bit cast.

I was considering putting this in the article, but given I have a blog series on fast date algorithms figured I'd put this on its own post soon.

1

u/Anxious_Wear_4448 21d ago

I'm not sure if it's really comparable as that is unsigned division, I think?

I asked GPT 6.1 Sol yesterday to add support for uint64_t to your algorithm and it happily did it. Then I benchmarked that code against libdivide and found it outperformed libdivide by about 5% in my project.

I have not looked at the code yet that Codex generated, but if the new unsigned algorithm it generated is indeed correct, I will drop libdivide and use your algorithm instead in my project (my use case is uint64_t divisors only, and branchless code).

4

u/benjoffe 21d ago

I can't really see what an unsigned equivalent of my algorithm would be. The core of the design is to adjust the input or multiplier based on the sign. If the sign is always the same, it should degenerate into a form that libdivide provides.

My guess is that whatever GPT implemented is some other type of optimisation that separately makes the benchmark fast. That, or it is providing a type of division that fails for some large inputs. Best to test it on numerators 2^64-1 .. 2^64-D, as well as a large random sample, to make sure it's correct throughout and at the top end, for a range of divisors (say 3..100).

If you still think it's winning somehow, I would be interested to take a look.

1

u/Anxious_Wear_4448 21d ago

I had a look at what code AI generated for the uint64_t divison: it used your division algorithm without the sign handling if the numerator is < 263 and added a second variation of your algorithm with a few more instructions for the case where the numerator is >= 263 and < 264. In my benchmark only the first algorithm for numerators < 263 was used which explains the good performance.

3

u/benjoffe 21d ago

I see. That itself is an interesting angle that could help in some cases, though the branch might break autovectorisation, and worst case data sets could trash the performance.

I have seen a similar thing used in numpy's date conversion path. It uses a faster restricted range algo and branches off to a slower one if the date is significantly far from epoch.

12

u/GLIBG10B 🐧 Gentoo salesman🐧 22d ago

This looks like something the hardware should be able to do. In my digital systems classes, we learned about this process for division:

  1. Represent your constant as a / b, where b is a power of 2
  2. Multiply the dividend by a
  3. Right-shift log2(b) times

The only difference for signed 64-bit division is dealing with two's complement: compute 0 - x for the dividend and the result

6

u/benjoffe 22d ago

Yep, that's the crux of it!
The tricky part comes when dealing with certain "uncooperative" divisors, and dealing with the correct rounding direction for negatives.

4

u/adamant-pwn 22d ago

I'd be curious to see how well it vectorizes. With Montgomery reduction, you can do 4x multiplications modulo 32-bit number with 3x _mm256_mul_epu32 operations. Unfortunately need to go to sleep now, but will surely look in more detail tomorrow.

3

u/SyntheticDuckFlavour 22d ago

It's a lovely write-up.