4 ms·

I'm left with a feeling something else must be going on here in addition to the 'fast mod' optimization. It looks like the optimization would only be used on th

by mbell 12y ago

I'm left with a feeling something else must be going on here in addition to the 'fast mod' optimization. It looks like the optimization would only be used on the first 2 or 4 calls to isEvenlyDistributed() which doesn't strike me as enough to cut runtime in half, nor does it seem to make sense that you'd see roughly the same performance difference for all values of lim (I'd expect the performance to get closer as lim grows). Am I missing something?

Perseids 12y ago
Maybe you underestimate how many numbers are weeded out just by checking divisibility by 3, 4 and 5? The first check regarding 2 will always return true, as `val` is incremented by 2. The check for divisibility by 3 will cause an abort for two out of three calls. The check for divisibility by 4 will cause an abort of half of the remaining calls (as `val` is incremented). And I guess the check for 5 will weed out an additional segment of 4 out 5. Thus just after checking 3, 4 and 5 only 1/3 * 1/2 * 1/5 of the `val`s will continue down the recursion call. So the majority of calls terminate in the highly optimized static division code. Now you can still argue that the remaining calls that go deep into the recursion could account for a lot of time. I don't believe this is the case though, as in each recursion call you should terminate a constant fraction of each calls, so the drop down should be exponential. An other interesting observation of this phenomenon is that running the recursion backwards (beginning with the large divisors) might greatly decrease the runtime as a more significant fraction of the `val`s are falsified by larger divisors in the first calls of the recursion.
- mbell 12y ago
  I see what your saying and that was the type of thing I was getting at. If i understood the article correctly, the claim was that it was faster because the first 2-4 checks could be optimized by avoiding the idiv. But even if you optimize those check to zero time, that is a small number of checks in comparison the number of checks needed as lim increases (even at lim = 20, only 10%-20% of the checks would be optimized). It doesn't follow that the run time would be cut in half based on the article's conclusions alone.
dbenhur 12y ago
With 64bit operands, IMUL+SAR is between 10 and 25 times faster than IDIV on current x86 hardware. (div speed is very dependant on the values being divided. eg: on Sandy Bridge arch, latency is between 40 and 103 cycles.) With these deltas, the first few checks are essentially free. A large number of the numbers to check will be eliminated early and never try the expensive idiv tests.

by mbell 12y ago

Perseids 12y ago

Maybe you underestimate how many numbers are weeded out just by checking divisibility by 3, 4 and 5? The first check regarding 2 will always return true, as `val` is incremented by 2. The check for divisibility by 3 will cause an abort for two out of three calls. The check for divisibility by 4 will cause an abort of half of the remaining calls (as `val` is incremented). And I guess the check for 5 will weed out an additional segment of 4 out 5. Thus just after checking 3, 4 and 5 only 1/3 * 1/2 * 1/5 of the `val`s will continue down the recursion call. So the majority of calls terminate in the highly optimized static division code. Now you can still argue that the remaining calls that go deep into the recursion could account for a lot of time. I don't believe this is the case though, as in each recursion call you should terminate a constant fraction of each calls, so the drop down should be exponential. An other interesting observation of this phenomenon is that running the recursion backwards (beginning with the large divisors) might greatly decrease the runtime as a more significant fraction of the `val`s are falsified by larger divisors in the first calls of the recursion.

mbell 12y ago
I see what your saying and that was the type of thing I was getting at. If i understood the article correctly, the claim was that it was faster because the first 2-4 checks could be optimized by avoiding the idiv. But even if you optimize those check to zero time, that is a small number of checks in comparison the number of checks needed as lim increases (even at lim = 20, only 10%-20% of the checks would be optimized). It doesn't follow that the run time would be cut in half based on the article's conclusions alone.

dbenhur 12y ago

With 64bit operands, IMUL+SAR is between 10 and 25 times faster than IDIV on current x86 hardware. (div speed is very dependant on the values being divided. eg: on Sandy Bridge arch, latency is between 40 and 103 cycles.) With these deltas, the first few checks are essentially free. A large number of the numbers to check will be eliminated early and never try the expensive idiv tests.