5 ms·

Intel flavors often do both with a single idiv instruction. Agner Fog has performance tables for many variants [1]. I’d guess a few pipeline to similar per loop

Intel flavors often do both with a single idiv instruction. Agner Fog has performance tables for many variants [1]. I’d guess a few pipeline to similar per loop cost of shift and add. I suppose if you’re writing a paper you’re aware of quite a bit of literature on exactly this problem. Recent papers have quite fast methods to do this. I’ve not looked at recent state of the art to see if 58 has a near zero cost divmod, but numbers of many forms do. I’d not be surprised if state of the art has it reduced to a few non-mem access branchless no division instructions on most architectures. Maybe later I’ll poke at 58 and see what I can design. I’ve made quite a few such algorithms over the years. [1] https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf

nkurz 8y ago
I feel comfortable with the x64 approaches, but am much less familiar with the efficiency of other architectures. The paper also benchmarks ARM (which is relatively faster) and Power 8 (which I don't understand well). I'd be particularly interested in knowing if any other architectures are much faster for division/modulus (which would weaken the paper) or much slower (which would strengthen it). I'm might be exposing my ignorance, but what's 58 in this context? Is this an ARM Cortex series, or something else?
- a1369209993 8y ago
  58 is the number we're trying to divide by. (It's a constant, so there's a bunch of clever optimizations we can do; I don't think anyone is claiming fully-general division is fast by any standards beyond "round trip to memory".)
  - nkurz 8y ago
    I feel silly, but thank you for the polite explanation of what is now obvious.
- BeeOnRope 8y ago
  FWIW I don't think other architectures are significantly faster than x86 for the div or divmod instruction. The GP said that "it can be reduced to a single assembly instruction" which is certainly true, but this one instruction is dog slow and produces 30+ uops[1]. Which is exactly why compilers choose to flip fixed divides to a multiplication and a series of corrections that often add up to ~10 instructions but even then it's still worth it. Divide is a hard problem and I'm not aware of any breakthroughs. It's been getting faster, but it's still 10 slower (at least) than multiplication as you point out. Intel has thrown hardware at it a few generations back, speeding it up (it used to be over 100 cycles), and AMD has a fairly fast divider in Ryzen as well (for many inputs faster than Intel). I expect POWER to be in the same range. ARM architectures are all over the power/performance map, obviously, but for the biggest/fastest, I would guess they are within a factor of 2, either way, of contemporary x86 implementations. --- [1] This point is important: it means you can't get as much work done while the division is happening. There are other slow instructions, such as floating point div, sqrt, transcendental and trig functions. However, these functions are only a single uop and then occupy only their respective execution unit for the duration, so you can use the rest of the EUs at full speed. So if you only need to do one every 50 cycles or so, and have work to do in the meantime, they can be also free. idiv is not like that: it spews out many uops which compete for the same EUs as the rest of your code.
  - ChrisLomont 8y ago
    IDIV on Skylake-X is 10 uops [1,p246], not 30+. Some other Intel chips are even lower (Goldmont is 3 uops, for example, but slower overall, Piledriver is 2 uops for r32, etc.). IMUL is often 2-3 uops on the same chips. 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 https://www.agner.org/optimize/instruction_tables.pdf

nkurz 8y ago

I feel comfortable with the x64 approaches, but am much less familiar with the efficiency of other architectures. The paper also benchmarks ARM (which is relatively faster) and Power 8 (which I don't understand well). I'd be particularly interested in knowing if any other architectures are much faster for division/modulus (which would weaken the paper) or much slower (which would strengthen it). I'm might be exposing my ignorance, but what's 58 in this context? Is this an ARM Cortex series, or something else?

a1369209993 8y ago
58 is the number we're trying to divide by. (It's a constant, so there's a bunch of clever optimizations we can do; I don't think anyone is claiming fully-general division is fast by any standards beyond "round trip to memory".)
- nkurz 8y ago
  I feel silly, but thank you for the polite explanation of what is now obvious.
BeeOnRope 8y ago
FWIW I don't think other architectures are significantly faster than x86 for the div or divmod instruction. The GP said that "it can be reduced to a single assembly instruction" which is certainly true, but this one instruction is dog slow and produces 30+ uops[1]. Which is exactly why compilers choose to flip fixed divides to a multiplication and a series of corrections that often add up to ~10 instructions but even then it's still worth it. Divide is a hard problem and I'm not aware of any breakthroughs. It's been getting faster, but it's still 10 slower (at least) than multiplication as you point out. Intel has thrown hardware at it a few generations back, speeding it up (it used to be over 100 cycles), and AMD has a fairly fast divider in Ryzen as well (for many inputs faster than Intel). I expect POWER to be in the same range. ARM architectures are all over the power/performance map, obviously, but for the biggest/fastest, I would guess they are within a factor of 2, either way, of contemporary x86 implementations. --- [1] This point is important: it means you can't get as much work done while the division is happening. There are other slow instructions, such as floating point div, sqrt, transcendental and trig functions. However, these functions are only a single uop and then occupy only their respective execution unit for the duration, so you can use the rest of the EUs at full speed. So if you only need to do one every 50 cycles or so, and have work to do in the meantime, they can be also free. idiv is not like that: it spews out many uops which compete for the same EUs as the rest of your code.
- ChrisLomont 8y ago
  IDIV on Skylake-X is 10 uops [1,p246], not 30+. Some other Intel chips are even lower (Goldmont is 3 uops, for example, but slower overall, Piledriver is 2 uops for r32, etc.). IMUL is often 2-3 uops on the same chips. 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 https://www.agner.org/optimize/instruction_tables.pdf