Re: [boost] [xint] Boost.XInt formal review (concrete complaint)

Subject: Re: [boost] [xint] Boost.XInt formal review (concrete complaint)
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2011-03-07 13:08:33

Peter Dimov wrote:
> Joel Falcou wrote:
>> x just have a operator= taking a interge_expression<X> type whcich
>> contains the whole a+b abstract syntax tree. From there, there is
>> countless techniques to iterate over the AST, transform it or
>> evaluate it as code.
> 
> There surely are, but a large integer library doesn't seem like a
> trivial application. Even simple things like
> 
> x = a*b + c;
> x += a*b*c;
> 
> don't seem entirely straightforward when the goal is to eliminate all
> temporaries. So rewriting everything to use expression templates
> (properly) could be quite an amount of work.

How about not so simple?

 x_num = (x11 * dy1 * dx2 - x21 * dy2 * dx1 + y21 * dx1 * dx2 - y11 * dx1 * dx2); 
 x_den = (dy1 * dx2 - dy2 * dx1);
 x = x_num / x_den;

I originally wrote it as one line.  This is a real use case for big int from my library.

The problem we are faced with is we can only eliminate allocation for one temporary in an expression by reusing the lhs of the assignment.

A compound expression, like the ones above, requires several temporaries.  

It is sort of unreasonable to ask the user to rewrite their expressions as one line per operation to avoid temporaries.  It defeats the purpose of operator syntax.

I suggest that when the expression is evaluated at runtime storage for temporaries be allocated on the stack.  You will want a threshold of say 4K on the size of the temporary in the stack (otherwise allocate on the heap).  This optimization would be much easier to implement *if* the algorithms were generic and agnostic to whether the buffer holding the big int value were a member of some integer_x object.

Now, taking things just a little futher, what if there were a point of customization for each algorithm so that the user could override the algorithms at compile time with their own implementation.  That could give us the option to override with gmp's C interface at the low level but get our clever expression templates with stack allocation optimization on top instead of gmp's C++ interface which allocates for temporaries in compound expressions.  (Assuming gmp's C interface would let us manage the memory ourselves, I haven't looked that closely at it since I use the C++ interface.)

It is pretty important to me that a boost big int library be better than GMP in at least one way.  Better expression templates and usage of C++ to define the C++ interface is the *only* area where a boost library can deliver on that, and that is exactly the area boost excels.  For the algorithms it is fine to provide a default boost licensed implementation, but also provide hooks to override it with GMP or something else that is SSE accelerated and asymptotically optimal and actively maintained to be up to date with hardware changes.  Also, it is just plain better design to decouple the interface from the implementation of the algorithms.

Eventually we could standardize such an interface and let compiler authors implement the algorithms.  For the gnu stl they could just plug in gmp.  Standardization is a good reason not to use proto, since the expression template system would need to be rewritten or proto itself would need to become standardized.  Personally, I don't see why this library should have any dependencies at all.

Regards,
Luke