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

Subject: Re: [boost] [xint] Boost.Move vs Copy-on-Write timings
From: Chad Nelson (chad.thecomfychair_at_[hidden])
Date: 2010-05-04 02:15:20

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

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.

> 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),

Certainly. _cleanup reduces the length by skipping any zeros that are
now in the upper portion of the integer, ensures that zero values are
not marked negative, and (for fixed_integer types) ensures that the
topmost digit_t is limited to the proper number of bits by ANDing it
with a mask value. It's a very fast function. You can find the
definition in base_integer.cpp, if you want to confirm its efficiency.

_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.

> 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.

> Does this have to do with base_integer trying to account for both
> fixed-width and variable-width integers?

That's the primary reason for that design, yes. Since the detail
functions all take base_integer references, they can be shared by all
the integer types, and the _attach call at the end is often the only
piece that needs to worry about the differences.
- -- 
Chad Nelson
Oak Circle Software, Inc.
*
*
*
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkvfu3UACgkQp9x9jeZ9/wTclQCffHxg+943lbpu3Dta1C3sb0hu
1jwAoO5uHs3RUSfFWdI+zGkPSlBFunW1
=Bf4i
-----END PGP SIGNATURE-----