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 03:24:05

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

On 05/04/2010 02:38 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...

They're not defined there because they don't exist. :-) base_integer is
mostly concerned with small shared member functions (like _log2 and
_get_length) and memory handling, it doesn't have any mathematical
operations code in it, other than _increment and _decrement. That's all
handled by free functions in namespace detail, like detail::add (in
primitives.cpp).

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

They aren't supposed to be, but tracing through the code, I don't see
any way they won't be. :-( The problem is that the 'adopt' variable, at
the top, isn't being set to true because the data that it's supposed to
adopt never has a copy-count of zero... after getting distracted by
other things, I never finished the move-emulation code that I wrote that
for.

Well, that explains at least part of why the copy-on-write code measures
faster.

I'll fix that tomorrow and re-measure everything.

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

That might indeed be a better design. And if I do adopt the CRTP design,
it might be the only way, since if I understand it correctly, there
won't be a non-template base class that's shared by all of the integer
types anymore.

> Carrying on this discussion might be more appropriate in a separate
> thread, however; one topic at a time.

Feel free to start one if you like. I don't think there's any need
though, I know exactly what you're describing. I'll finish this one by
reporting the new timings, hopefully tomorrow.
- -- 
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/

iEYEARECAAYFAkvfy5EACgkQp9x9jeZ9/wSQ8gCfdhLP0LCjbZHj/6d01Ibh8aYC
XC4An1mk+vtxc9trsjzZ4+Xl3KQIVPMR
=I+FP
-----END PGP SIGNATURE-----