Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at