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

Subject: Re: [boost] [xint] Performance of fixed-size large integers
From: Chad Nelson (chad.thecomfychair_at_[hidden])
Date: 2011-03-05 13:37:43

On Fri, 04 Mar 2011 16:35:14 +0000
"Phil Endecott" <spam_from_boost_dev_at_[hidden]> wrote:

> Chad Nelson wrote:
>> 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's certainly possible, I tried it in early iterations of the library.
But almost all operations other than addition and subtraction are more
naturally broken down into magnitude and sign, and to get a magnitude
from that representation requires extra steps to remove the sign bit
and add it back later. Or, if using two's complement, to change
negative numbers to positive ones and back.

>>> [...] 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? 

Sorry, but no. There are a number of improvements on the to-do list
from the review. But as soon as those are done, it should be stable
enough to accept patches.

> Specifically, say I want to add this as a specialisation for
> fixed-size storage (PSEUDO-CODE): [...] 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.

No, they couldn't. It's not part of the library's design parameters,
and I don't think it should be at present, for the reasons I've
outlined in other messages. A future iteration, after the internals are
stable, is another story.
-- 
Chad Nelson
Oak Circle Software, Inc.
*
*
*