Boost logo

Boost :

Subject: Re: [boost] copy on write for std containers
From: Jeffrey Lee Hellrung, Jr. (jhellrung_at_[hidden])
Date: 2010-12-04 18:16:20

On 12/4/2010 2:53 PM, Simonson, Lucanus J wrote:
> Peter Foelsche wrote:
>> I wrote a couple of lines and replaced std::set and std::map with some
>> copy-on-write-wrappers
>> and I got a dramatic speed improvement with the last gcc 4.5. I think.
>> My code was using recursive functions iterating over a tree returning
>> and setting such objects.
>> I looked and it seems there is nothing like this in boost!
>> Ideally this should be an template argument for the std containers.
> No. The problem you have solved is not general and furthermore it is not the right solution. Rather than pass containers by value and return by value it is standard practice to pass by const reference and make a copy when you are aware that you want to modify a copy. To return a container pass it by non-const reference and populate it, which avoids copy on return. Finally there is iterator semantics which also allow efficient usage of the STL. The solution to this performance problem is to use the STL correctly in the first place. Your code would be faster still without the extra level of indirection and extra memory allocations of the wrapper.

One should also be cognizant of the optimization opportunities afforded
you by the presence of Return Value Optimization (RVO) and move
semantics (if available). These generally give one the same interface
choices that copy-on-write would allow but without the overhead. For
example, if your function does an unconditional copy-modify-return, you
should pass by value and return by value; contemporary compilers elide
the spurious copies.

To specifically address returning a container: If I wanted to return a
container, I think you want to prefer returning by value and relying on
RVO and/or move assignment and/or swap. This simplifies the interface
and makes the program's reasoning easier to parse. I would only modify
an existing container in-place (i.e., take a reference to a
to-be-modified container) if the semantics are explicitly to "add" to
the container.

Of course, rvalue references aren't available on every compiler yet.
For those C++03 compilers, one could use the (proposed) Boost.Move
library or, if that isn't an option, swap can sometimes be used as poor
man's move assignment.

- Jeff

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