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-02 21:42:02

On 05/02/2010 06:30 PM, Chad Nelson wrote:
> On 05/02/2010 07:17 PM, Jeffrey Lee Hellrung, Jr. wrote:
>> I don't think so, unless your arithmetic operators use by-value
>> parameters (allowing copies to be elided).  Assuming you're not using
>> expression templates, I would expect an implementation with no move
>> semantics to translate "w = x * y + z" to be, effectively,
>>
>> T t0 = x * y;
>> w = t0 + z;
>>
>> which requires 2 allocations minimum (one to store the result of x * y,
>> another to store the result of t0 + z).
>
> Hm... looking at it more closely, I think you're right. There's no way
> for the copy code to know that t0 isn't going to be used again, so it
> would still allocate a temporary for the addition.
>
>> But, again, if operator+ takes its parameters by-value, you can
>> probably get some copies elided in practice and detect that the first
>> argument to operator+ has unique ownership, hence is modifiable.
>
> I'm not sure that's right, because if I set it to take its parameters by
> value, it would either have to deep-copy those parameters or use
> copy-on-write, making the reference count for copy-on-write two, and
> preventing it from detecting that either parameter is unique (and thus
> temporary). The variables used for the parameters could be used again
> later on, so it's still not safe to modify them.

If the compiler does a decent job at copy elision (and most recent ones 
do, as I understand), then your reference count will be just 1.  E.g., 
if you have

T f();

void g(T);

and you call g(f()), any decent compiler will elide the copy from the 
result of f to the argument of g (MSVC even does this in debug mode, 
last time I investigated it).

It's far from guaranteed, but that's why I said "in practice".

>> Note that move semantics, on the other hand, can directly detect that t0
>> is just a temporary (by overloading operator+ on both a
>> reference-to-const and an (emulated) rvalue reference), hence the t0 + z
>> can be safely replaced with t0 += z (which will possibly avoid a
>> reallocation), and the then the new t0 would be moved into w.
>
> I must be missing a trick then, because operator+ just takes constant
> references. The library would do those same allocations for the move
> stuff too, at present.

Precisely; you're not taking full advantage of (emulated) rvalue 
references and moving from / modifying temporaries.  There's no rule 
that says you can't have 4 overloads of operator+:

T operator+(const T&, const T&);
T operator+(const T&, T&&);
T operator+(T&&, const T&); // this would be called for x * y + z
T operator+(T&&, T&&);

Would be even better when we can overload member functions on 
rvalue-ness ;)  But I have no idea how mature that proposal is... :/

> operator+ and operator- would be the only ones that could use that
> trick, if I'm seeing things right. And it seems to me that I could

All the free operators / functions could be overloaded on 
lvalue-/rvalue-ness, not just operator+ and operator-.  Any operation 
where you can potentially save reallocations by modifying the arguments 
directly qualifies for consideration.

> emulate move semantics with my current design too, without going through
> Boost.Move... I was thinking about that before, when I thought I
> shouldn't use Boost.Move because it wasn't yet official. It might be
> worth reviving the thought.

That's certainly an option, though it sounds like Ion is prepping 
Boost.Move for final submission, so the review for it shouldn't be *too* 
far down the line...

- Jeff