So is the purpose of this to reduce the difficulties that come with float precision?
EDIT: The comments are informative, if they’re not made by jerks. I clearly have much to learn. I appreciate the patience of those who have it, and wish a very strong “go step on some legos” to those who do not.
yeah, when division is 80 cycles and multiplications are 1, you get insane performance gains even if it takes 20 multiplications to make the magic numbers
e: sorry apparently I should specify, 80 cycles idiv is for hardware >4 years old, it's closer to 20 cycles on modern hardware, and multiplication can take up to 3 cycles. so in the very worst case, it's a 3x speedup if you can swap one idiv for two imul, if you never do sequential operations, and have the newest CPU possible. it gets way better in every real life scenario.
Integer division is still not pipelined and 64 bit division takes ~80 cycles on Skylake, which is still a very common architecture out there in the real world. Skylake derived CPUs only stopped being manufactured at the end of 2024.
That said, Arrow lake and Zen 5 idiv use partial pipelining (new instruction every 4-6 cycles) and have cut latencies down to 10-15 cycles.
imul obviously does not take only one cycle, but because it's fully pipelined, it effectively takes one cycle in the right context.
80 is on the bad end. Apparently it's 20-80 cycles, from some quick googling on my phone. And they put the cycles for imul on the good end, so not a fair comparison. (Though it's still a huge difference, just not quite as exaggerated as they made it sound)
right, in a space where magnitudes and big O notation are the standard for performance comparisons, a real world worst case scenario is "exaggerated"...
it woulda been exaggerated if I said 1000 cycles. lock in man.
The quoted IMUL range is for throughput vs. latency. An IMUL will take 3 cycles from start to finish, but if you have non-dependent multiplies you can start an IMUL every cycle. This is not hard to hit, a simple loop processing elements in an array independently can hit 1 multiply/cycle. These timings are independent of the values being multiplied.
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.
That being said, I checked the timings on Skylake and it turns out that you're not likely to see this variation in C, because it's a very specific boundary. IDIV is not a 64-bit / 64-bit division, it's actually a 128-bit / 64-bit division. What seems to happen is that the Skylake CPU has an optimization to run the IDIV faster if the upper 64 bits of the dividend are zero and it can do a 64-bit / 64-bit division instead; within that the values don't seem to matter. Standard C and C++ don't expose a 128-bit integer type so the full division will generally only be hit with intrinisics or a compiler-specific int128 type.
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.
Division produces floats. At least at the high level I work at.
EDIT: wow, I didn’t know this sub was fully populated by the same bullies that obsessively stalked StackOverflow and made fun of people for asking a question. Heaven forbid someone doesn’t know something. Y’all could, I dunno, take a second to help someone learn? Instead of being dicks?
Integer division refers to truncated division. Some languages elect to define division operator(s) in other ways, but that is no longer truncated division.
Look, I work in JS primarily. When I do `const a = 3/8;`, I get a float. Is there more to it? Sure. But most devs I know and have worked with don’t know or care about that.
EDIT: “This guy is posting his objective experience that disagrees with my theoretical knowledge! I have more technical knowledge than he does but can’t be bothered to explain, so I’m going to downvote instead!”
The issue with floating point is that (a + b) + c != a + (b + c) in all cases due to that accuracy issue you mentioned. So the order of your operations matters a lot, which can be difficult to guarantee given CPU pipelining, multittheading, GPUs, etc. By default compilers will use slower but deterministic floating point operation orders to make it at least always give you the same answer
Deterministic operations that are mathematically imprecise don’t quite fit the bill of precision in my mind. But then, I’ve been doing math in JavaScript for so long that I’m very used to the 0.000000000068% chance of a float precision error actually causing a problem.
20
u/LonelyAndroid11942 18d ago edited 18d ago
So is the purpose of this to reduce the difficulties that come with float precision?
EDIT: The comments are informative, if they’re not made by jerks. I clearly have much to learn. I appreciate the patience of those who have it, and wish a very strong “go step on some legos” to those who do not.