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 11:46:44

Chad Nelson wrote:
> On Sun, 6 Mar 2011 17:43:15 -0800
> "Simonson, Lucanus J" <lucanus.j.simonson_at_[hidden]> wrote:

>> Whether you make one unneeded allocation or two is a less important
>> consideration than whether you make one or zero since 2/1 is a lot
>> smaller than 1/0.  If a temporary is generated by the user's code
>> they have already pessimized their code.  I am sorry, but you cannot
>> avoid allocation with a return by value semantic, only expression
>> templates allows you to reuse the storage on the left hand side of
>> the assignment operator. [...]
> 
> I'm not familiar with a use of expression templates that would allow
> that. Can you point me to something explaining it?

The operator+, for example, returns an expression template object that holds references to all the arguments of the orignal function and type information that it was operator+.  If any of the arguments are themselves expressions it holds references to their expression type, not their result.  An overloaded operator= on your data type allows you to accept an expression type instead of the result of the expression.  In the implementation of operator= you call a member function of the expression template and pass the left hand side of the assignment operator in by reference to use as the storage for the result.

vector<long long> x1;
vector<long long> y1;
initialize_with_values(x1, 1000000); //size of x1 is 1000000
initialize_with_values(y1, 1000000); //size of y1 is 1000000
integer_x result;
integer_x arg1;
integer_x arg2;
for(int i = 0; i < 1000000; ++i){
        arg1 = x1[i]; //allocates only in the first iteration
        arg2 = y1[i]; //allocates only in the first iteration
        result = arg1 * arg2; //allocates only in the first iteration, reuses storage in result thereafter
}

I can do O(N) big int operations with only O(1) allocations using a nice type safe operator syntax with a well designed expression template system.  Obviously, allocations would dominate the computation of 128 bit multiplication results, so this is a significant optimization.

If someone is just doing O(1) big int operations then they don't care about performance.  The common case isn't the one that is written the most times, it is the one that is executed the most times.

Regards,
Luke