Anything in the review queue?

[Don]

dsimcha wrote:
> On 3/22/2011 1:25 AM, Don wrote:
>>> There are a few approaches we can take from here. One is to define
>>> certain traits that differentiate BigInt from other integrals (e.g.
>>> preferAdditionToMultiplication or whatnot), and then design Rational to
>>> use those traits. Another is of course to specialize the entire
>>> Rational on BigInt. Third would be to specialize certain core routines
>>> (gcd and friends) for BigInt and keep Rational agnostic.
>>
>> You're missing something important here. Rational big integers are a
>> very well defined area of research, with its own set of algorithms.
>> Although you can pretend a BigInt behaves as an int, and make a rational
>> type, the performance will be pathetic, and everyone will laugh at you.
> 
> I fully understand this based on your previous posts.  I therefore agree 
> that Rational doesn't belong in Phobos exactly as-is.  I'm trying to 
> understand which of the following scenarios is true, though:
> 
> Scenario A:  Making BigInt efficient would require changes only in a few 
> small places, like GCD.  If we provide hooks for arbitrary precision 
> types to specialize these, and provide specializations for 
> std.bigint.BigInt, all will be well.
> 
> Scenario B:  Making BigInt efficient would have ripple effects all over 
> the implementation, require rethinking of every operation, etc., but in 
> a way that wouldn't bleed out into the interface.  It might make sense 
> to get the interface and a generic implementation right first, then 
> specialize it to improve performance later.
> 
> Scenario C:  Making BigInt efficient would have ripple effects for both 
> the interface and the implementation.  In this case, we probably 
> shouldn't provide a generic implementation because the arbitrary 
> precision one is much more generally useful and the fixed width one 
> would mostly add clutter.

 From the BigInt side, the only real change is the addition of gcd and 
gcdExtended.
(gcdExtended returns x, y such that a*x + b*y = gcd(a, b) ).

I believe that is the only low-level algorithm which is missing; pretty 
much everything else remains unchanged.

However, the other case which is interesting is when BigInt is replaced 
with FixedInt!n (maybe someone can come up with a better name for this?) 
-- an integer with a length of a fixed number of ints.
Unlike BigInt, this has basically the same semantics as built-in integer 
types. In fact, FixedInt!1 == int, FixedInt!2 == long, FixedInt!4 == cent.
This is possibly even more relevant for Rational. I haven't thought much 
about the implications though.

> BTW, does BigInt over-allocate initially to allow certain operations 
> (like +=) to be done in-place more frequently?

No, it doesn't. As long as it uses copy-on-write, there's no benefit to 
doing so.
Reference counting would clearly be superior for FixedInt, but I'm not 
at all sure that it would be a win for BigInt. But of course FixedInt 
wouldn't need to over-allocate.

Using TempAlloc would have a far greater effect on performance.