Re: [boost] [xint] Performance of fixed-size large integers

Subject: Re: [boost] [xint] Performance of fixed-size large integers
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-03-04 11:35:14

Hi Chad,

Chad Nelson wrote:
> "Phil Endecott" <spam_from_boost_dev_at_[hidden]> wrote:
>> Also I noted that the conventions here don't match the built-in
>> (u)intN_t types, i.e. int64_t vs. int63_t and the "wrap-around"
>> behaviour.  Perhaps there is some rationale for this, but I would be
>> happier to see it consistent with the built-in types. [...]
>
> Sorry, but the library doesn't use two's complement representation
> (there's no high-bit on arbitrary-length integers, so it can't), so
> that would only be possible with code specifically written for
> fixed-length integers.

Is it not possible to use the most significant bit of the current most 
significant word as the sign bit?  (What do other implementations do?)  
Surely this would be much more efficient - unless there is some 
disadvantage that I've not spotted...

>> [...] It seems to me that that is several hundred times faster than
>> the Xint code (on my 1.2 GHz ARM test system). [...] This is about
>> half the speed of the assembler, but still hundreds of times faster
>> than the Xint code. [...]
>
> I'll be happy to accept patches.

> Fixed-size integers are definitely second-class citizens right now,
> simply due to time and manpower constraints. As the library matures, I
> think you'll see serious efficiency improvements.

Well, is the current design of the library one that is suited to 
patching to make this sort of improvement?  Specifically, say I want to 
add this as a specialisation for fixed-size storage (PSEUDO-CODE):

template <int N>
class integer< fixedlength<N> > {
   uint32_t data [ N/4 ];
};

If your implementation had a generic algorithm for addition, i.e. (PSEUDO-CODE):

template <typenmame INT_ITER>
void add(INT_ITER a_begin, INT_ITER a_end, INT_ITER b_begin, INT_ITER b_end)
{
   int carry = 0;
   for (INT_ITER i = a_begin, j = b_begin; i != a_end; ++i, ++j) {
     (carry, *i) = add_with_carry( *i, *j, carry);
   }
}

then that could work with this new storage, with some extra glue to 
enable operator-overloading etc. (maybe using Boost.Operators).  
Similarly, the add_with_carry function in there could also be something 
that I could overload with my asm version.  Based mainly on other 
peoples' reviews, I get the impression that it would not be so easy to 
make these changes - and certainly, they could not be applied by a user 
from the outside using the public API of the library.

Regards,  Phil.