copy on write for std containers
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. Peter
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. Regards, Luke
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
Hi Luke, lucanus.j.simonson@intel.com wrote:
"To return a container pass it by non-const reference and populate it, which avoids copy on return."
Certainly, but shouldn't we promote a little more copy elision instead ? This is supposed to avoid copy on return too, or did I misunderstood it? http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/ Best regards, Pierre PS: grats for the polygon lib!
Pierre Morcello wrote:
Hi Luke,
lucanus.j.simonson@intel.com wrote:
"To return a container pass it by non-const reference and populate it, which avoids copy on return."
Certainly, but shouldn't we promote a little more copy elision instead ? This is supposed to avoid copy on return too, or did I misunderstood it? http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/
Best regards,
Pierre
PS: grats for the polygon lib!
Thanks.
Peter Foelsche wrote: 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.
Peter and Pierre have some points about the direction C++ is taking from the old standard usage and the new. I actually like to have an accumulate semantic on containers I pass by reference most of the time. I know I should use an output iterator instead, mea-culpa. The other thing I like about pass by reference is it places memory management responsibility on the caller (which output iterators also do, of course). If the caller wants to allocate a std container on the heap or make it a data member of a class and pass it to a function by reference to populate it they can do so at no extra cost. Yes r-value references, NRVO, RVO and copy ellison/move semantics all help make those things zero-cost, but I take some comfort in writing code that I know for sure will compile to an efficient executable in every C++ compiler. Also, I don't find passing by const reference to be much of a cognitive overhead and I admit passing by reference to populate a container gets in the way of equational reasoning and forces multi-line syntax where a single expression might be more natural, but I like accumulate semantics and I like pushing ownership of containers down the call stack as far as possible and not trasfering that ownership around. Generally when passing containers around I like to make them template parameters. A return value type can't be an implicit template parameter, while calls to a template function with pass by reference can usually be made bare without supplying a template parameter list, which makes using them more intuitive. We can never infer the return type of a template function by what comes on the left hand side of the assignment operator. Well, I guess I do use expression templates with generic assignment operators to get my equational reasoning, infer the right hand side and still use pass by reference under the hood. It's a lot of work, but we have proto to help with that. Getting the ownership of an object right in the first place seems to me to be 95% of the problem and a lot of these things like RVO and copy-ellison is there to address the 5%. I'd rather people learn how to manage the lifetime of their objects properly than learn the new language features. Once you have the 95% covered see how the new langauge features can help you with the remaining 5%. Build the pyramid from the bottom up. Regards, Luke
"Simonson, Lucanus J" <lucanus.j.simonson@intel.com> wrote in message news:26E9B811E137AB4B95200FD4C950886BB6A15442@orsmsx507.amr.corp.intel.com...
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
Peter Foelsche wrote: 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.
The container returned was in fact a container containing other containers. Thus I might have saved making a copy of the outer container by passing the object by address (are you actually using non-constant references to obfuscate your code?) the inner containers still would need to be copied. Anybody know in which cases the compiler optimizes away or does not optimize away the call to the copy-constructor when returning an object by value? I still think that something like this should be available in some library for people, which cannot write such a wrapper in a few minutes by themselves.
On 12/4/2010 4:11 PM, Peter Foelsche wrote: [...]
Anybody know in which cases the compiler optimizes away or does not optimize away the call to the copy-constructor when returning an object by value?
http://en.wikipedia.org/wiki/Return_value_optimization
I still think that something like this should be available in some library for people, which cannot write such a wrapper in a few minutes by themselves.
I think the point is that copy-on-write is rarely optimal, often suboptimal, and increases complexity; hence it should not be encouraged. - Jeff
"Jeffrey Lee Hellrung, Jr." <jhellrung@ucla.edu> wrote in message news:4CFADA65.40708@ucla.edu...
I think the point is that copy-on-write is rarely optimal, often suboptimal, and increases complexity; hence it should not be encouraged.
increases complexity -- wrong -- I only replaced the matching types -- the using code was not modified. The number of lines for the wrapper are minimal -- I only implemented the methods I'm using. I don't care about complexity the compiler has to manage. I care about the complexity I have to manage. I could introduce some filtering to avoid storing identical instances which would even more decrease the memory foot print.
Peter Foelsche wrote:
"Jeffrey Lee Hellrung, Jr." <jhellrung@ucla.edu> wrote in message news:4CFADA65.40708@ucla.edu...
I think the point is that copy-on-write is rarely optimal, often suboptimal, and increases complexity; hence it should not be encouraged.
increases complexity -- wrong -- I only replaced the matching types -- the using code was not modified. The number of lines for the wrapper are minimal -- I only implemented the methods I'm using. I don't care about complexity the compiler has to manage. I care about the complexity I have to manage. I could introduce some filtering to avoid storing identical instances which would even more decrease the memory foot print.
No, no, no. Design an efficient algorithm with proper analysis of data flow that doesn't make any copies that aren't needed even when compiled in debug mode and your code will be simpler, more maintainable and faster. Why are you investing engineering effort into solving a problem that is entirely of your own making? Do by not doing. Don't dig holes just so that you can fill them in. Regards, Luke
On 12/4/2010 4:33 PM, Peter Foelsche wrote:
"Jeffrey Lee Hellrung, Jr." <jhellrung@ucla.edu> wrote in message news:4CFADA65.40708@ucla.edu...
I think the point is that copy-on-write is rarely optimal, often suboptimal, and increases complexity; hence it should not be encouraged.
increases complexity -- wrong -- I only replaced the matching types -- the using code was not modified. The number of lines for the wrapper are minimal -- I only implemented the methods I'm using. I don't care about complexity the compiler has to manage. I care about the complexity I have to manage. I could introduce some filtering to avoid storing identical instances which would even more decrease the memory foot print.
Rather than address these points directly, I will simply refer to Herb Sutter's discussions [1,2,3,4] on copy-on-write. I'm not claiming that copy-on-write is never a good solution, only that it should not be one's knee-jerk reaction (to say the least) to reducing unnecessary copies. There are solutions that, much more often than not, are superior that one should explore first, especially now with emulated move semantics or true move semantics. [1] http://www.gotw.ca/gotw/043.htm [2] http://www.gotw.ca/gotw/044.htm [3] http://www.gotw.ca/gotw/045.htm [4] http://www.gotw.ca/publications/optimizations.htm - Jeff
On 05/12/2010 01:11, Peter Foelsche wrote:
Anybody know in which cases the compiler optimizes away or does not optimize away the call to the copy-constructor when returning an object by value?
Whenever the object returned is a temporary or local variable, and the result of the function is used to initialize a new object. You can also benefit from this optimization in assignments by writing your assignment operator as type& operator(type other) { swap(other); return *this; } since the return of the function is then used to directly initialize 'other' without any copy.
I still think that something like this should be available in some library for people, which cannot write such a wrapper in a few minutes by themselves.
To make such a solution generic, you would have to be able to make a good "smart reference" first, which isn't possible due to lack of operator. overloading.
On Saturday 04 December 2010 20:46:49 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!
Automatic COW is often generating too much overhead. Using objects you only explicitly clone when you need a modifyable copy can be beneficial though, and there is a very simple way to achieve both: Use a shared_ptr<T const> for the shared, immutable object and an auto_ptr<T> for the unshared, mutable one. Uli
participants (6)
-
Jeffrey Lee Hellrung, Jr. -
Mathias Gaunard -
Peter Foelsche -
Pierre Morcello -
Simonson, Lucanus J -
Ulrich Eckhardt