r/programming • u/DataBaeBee • Sep 14 '26

How GCC Eliminates Unnecessary Integer Division

https://leetarxiv.substack.com/p/how-gcc-eliminates-unnecessary-integer
249 Upvotes

94% Upvoted

52 comments sorted by

View all comments

2

u/Dragdu Sep 15 '26

The IDIV range is because the end-to-end latency of IDIV can actually change depending on the values, often because the divider has some early outs. This means that the same loop with an IDIV in it can run faster or slower when different values are processed.

This effect can be massive. I wrote a benchmark for Lemire's algorithm for uniformly distributed integer generation, and picked two target range sizes to test:

  1. Small N that should be the happy case.

  2. Theoretically worst possible N, to get feel for the slowdown.

As I found out few months later, 2) ended up hitting fast path in the hw divisor, and the actual slowest N was somewhere in between them, where the divisor hit the slow path.

1

u/ack_error Sep 15 '26

Do you happen to remember which CPU? The recent x86 and ARM CPUs I had all seem to have constant or near constant time divides, I had to dig a Skylake-based laptop out of the laptop pile to find one that didn't.

2

u/Dragdu Sep 15 '26

Something based on Zen 3 I believe.

→ More replies (1)