[Issue 4125] std.numeric.gcd can use a binary GCD

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=4125


Peter Alexander <peter.alexander.au at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |peter.alexander.au at gmail.co
                   |                            |m


--- Comment #2 from Peter Alexander <peter.alexander.au at gmail.com> 2013-01-05 11:15:04 PST ---
(In reply to comment #1)
> Replace uint with ulong for the longer version ;)
> I use this and it is notably faster than what I used before.

I implemented this (exactly as you have it) and it was slower than the
algorithm that is already there. I tested on all pairs of integers below
10,000, and also on the pairs (x^2, y) for all x,y < 10,000. At best it was 50%
slower, at worst 3x slower.

All tests used dmd -O -release -inline

I suspect the reason for the performance reduction is due to poor pipelining.
The binary version involves a lot more branching, and more loop iterations than
the standard algorithm. Also, the branches taken are highly unpredictable.

Maybe I'll look at this again in the future to try and make it faster, but it's
pretty low on my priority list.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------