Re: [boost] copy on write for std containers

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