Base58

However, uops are not the bottleneck, pipelined throughput is what matters for performance. Multiple IDIV can be in flight at once on different register sets (real or virtual). Register renaming gives even more room.

A compiler can unroll the loop, use different registers (or the CPU can use renaming), and pipeline them, getting better throughput. r16 IMUL has a relative throughput of 2, r16 IDIV then has a relative throughput of 6. This is 3 times slower, not 10. Pretty much any other 10 instructions are going to be slower, not faster as you claim.

Compared to the overhead of looping and memory access, these are not the bottleneck. These represent a small amount of the time to do the computation.

Do some timing and check. IDIV is not what it once was.

[1] https://www.agner.org/optimize/instruction_tables.pdf

For Skylake, we have 36 uops and 35-88 cycles of latency for a 64-bit div, and for idiv it is even worse: 57 uops and 42 to 95 cycles of latency. These can execute one every 20 to 80 cycles, so the throughput is fully twenty to eighty times worse than 64-bit multiplication.

> IMUL is often 2-3 uops on the same chips.

On Intel chips multiplication is almost always 1 uop if you need a 64-bit result (this is what a multiply in C will compile to), and 2 uops if you need the full 128 result. In in either case it can sustain one every cycle.

> However, uops are not the bottleneck, pipelined throughput is what matters for performance. Multiple IDIV can be in flight at once on different register sets (real or virtual). Register renaming gives even more room.

How do you know uops are not the bottleneck? They often are: it depends on the surrounding code.

More importantly, div is slow in every way that could matter: if latency is the bottleneck, div sucks (20 to 80 cycles, vs 3 for multiply). If uop throughput is the bottleneck, div sucks. If pure div throughput is the bottleneck (as you are suggesting), div still sucks: the inverse throughput for 64-bit div is 21 to 83 cycles: almost the same as the latency, so it is barely pipelined at all, and fully 21 to 83 times slower than multiplication.

Now one might say that you are mostly interested in 32-bit values, as these are common even in 64-bit code, and Intel has good support for them.

In this case div is quite a bit faster, but still dramatically slower than multiplication. In latency terms it is 26 cycles on Skylake, versus 3 for multiplication, so about 9 times slower. In "pipelined throughput" terms, it is 6 cycles per division, versus 1 per multiplication, so 6 times slower.

As a summary, we can say that on the most recent Intel, which probably have the fastest dividers around (and which have seen recent improvements), 64-bit division is anywhere from 11 to 90 times slower than multiplication, depending on how you measure it (and the input values), and 32-bit division is between 6 and 9 times slower, depending on how you measure it. I think my "10 times slower" which actually falls towards the faster end of that range is actually quite conservative!

On chips older than Skylake (which is the vast majority of chips you'll still find in datacenters and in the cloud, since SKX is quite recent), the situation is worse for div, since mul had the same 1/3 latency/tput performance, but div was slower.

> Do some timing and check. IDIV is not what it once was.

Here, I agree.

It has gotten much faster! In other words, it has gone from shockingly slow to merely very slow. It is still way slower than multiplication in every respect (which itself has gotten faster to the point where it has 1-cycle throughput now), and almost all of the tricks to avoid actual div instructions still apply.