Re: [boost] [xint] Boost.Move vs Copy-on-Write timings

Subject: Re: [boost] [xint] Boost.Move vs Copy-on-Write timings
From: Jeffrey Lee Hellrung, Jr. (jhellrung_at_[hidden])
Date: 2010-05-04 02:38:13

On 5/3/2010 11:15 PM, Chad Nelson wrote:
> On 05/04/2010 01:32 AM, Jeffrey Lee Hellrung, Jr. wrote:
>> I've looked briefly through the code.  I'm not entirely sure where all
>> the "base" arithmetic functions are defined, but I do see that
>> primitives.cpp contains at least some of them.
>
> They're in the files that most logically support them. For example,
> detail::gcd and detail::lcm are in gcd.cpp.

Actually I was speaking more toward base_integer::_add, 
base_integer::_subtract, etc., which I don't see defined in 
base_integer.hpp or base_integer.cpp...

>> It seems like the general template you're using is
>>
>> void function(base_integer&  target, const base_integer&  argument0, const
>> base_integer&  argument1, ...)
>> {
>>      integer result;
>>      // ...populate result with the...well...result of the function...
>>      result._cleanup();
>>      target._attach(result);
>> }
>>
>> With only guesses as to the semantics of _cleanup and _attach (perhaps
>> you can help in that regard),
[...]
> _attach attaches the result to the target by adjusting the pointers
> where possible, and copying if necessary. Copying is usually only
> necessary for fixed_integer types, and only in some of the detail functions.
>
>> I suspect, in the absence of COW and regardless of movability of
>> integer and base_integer, you'd be making spurious and unneeded
>> copies of the result.
>
> I don't think so, but if you can show me otherwise, please do.

Well, _attach does have some allocation function calls, but I really 
have no idea how the logic branches when COW is turned off (and hence 
whether those allocations are actually invoked).  Perhaps you can 
convince me that those allocations are never called when COW is turned 
off...?

>> Can you please explain the rationale for the intermediate "result"
>> integer, when you have the "target" reference sitting right there
>> from the get-go?
>
> 'target' may refer to a fixed_integer that is not large enough to hold
> the entire result. For functions where this limitation might severely
> reduce the time it takes to come up with the answer (such as multiply),
> I've taken steps to limit the calculations, but for others (such as
> addition, where the result could be at most one extra digit_t) it is
> faster and cleaner to simply let the _attach function deal with
> truncating the result to the proper size.

I see.  I feel like a better design would give more abstraction to the 
arithmetic algorithms.  E.g., if I want to add 2 integers, the actual 
implementation of addition would take a couple of (pointer, length) 
pairs and a pointer for output (possibly with an optional maximal 
length), it being the callee's responsibility (of course) to ensure the 
output has enough space (up to the maximal length, if given).  This 
might seem too C-ish, but it is the common denominator among all your 
integer types (they all boil down to points to an array of digits), and 
it would make your arithmetic algorithms usable for a 
statically-allocated integer type as well (e.g., one built on a 
boost::array< digit_t, n >).  Carrying on this discussion might be more 
appropriate in a separate thread, however; one topic at a time.

- Jeff