When are data structures copied
in [C++]
|
Prev: One question about table driven and function pointer
Next: Using (return val of) member function as default parameter of member function
From: Maxim Yegorushkin on 7 Nov 2009 07:23 On 07/11/09 02:04, tohava wrote: > On Nov 6, 1:21 am, ShaunJ<sjack...(a)gmail.com> wrote: >> avoided? Do any implementations of STL implement copy-on-write >> semantics for string or vector? > > I'm not 100% sure, but I think STLPort implements string with CoW. Current STLPort-5.2.1 and STLPort 4 bundled with the latest Sun C++ compilers do not not use CoW. One most disappointing feature of STLPort std::string is that the default constructor allocates storage, in other words, a memory allocation is performed even for empty strings. GNU std::string uses CoW. I hear that the standard interface of std::string can not be possibly satisfied by a CoW implementation of std::string, nevertheless I find CoW implementations of std::string the most practical. GNU C++ library also provides another string class __gnu_cxx::__versa_string, which does not do CoW and I've heard that there are plans to make it the default std::string implementation in the future, although the CoW std::string implementation will still be available under a different name. -- Max [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: yeroen on 8 Nov 2009 21:46 > copy-on-write doesn't work well with threads so nobody uses it much > anymore. It is perfectly possible to combine CoW and threads when the CoW classes use atomic-reference counting. This is precisely how the Qt framework provides fully reentrant implementations of string, container, and other implicitly shared classes. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Jeff Flinn on 9 Nov 2009 02:58 Do any implementations of STL implement copy-on-write > semantics for string or vector? MSVC(VC6)/Dinkumware used to do COW for std::string, but found that small string optimization provided better overall performance. Jeff -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: SG on 9 Nov 2009 03:27 On 7 Nov., 03:04, ShaunJ <sjack...(a)gmail.com> wrote: > On Nov 6, 2:27 pm, Seungbeom Kim <musip...(a)bawi.org> wrote: > > ShaunJ wrote: > > > > { > > > string s(100, 'x'); > > > vector<int> v(100); > > > map<string, vector<int>> m; > > > m.insert(make_pair(s, v)); > > > } > > > make_pair creates a new pair object and returns it by value, so "in > > principle" s and v will be copied. Of course, the compiler is allowed to > > perform any optimizations that doesn't change the observable behavior, > > so there's no "guarantee" that the copies will be made. Since s and v are lvalues they will be copied. Now, if that means that all the characters of that string object are duplicated is another questions and depends on whether the implementation uses CoW or not. Recent libstdc++ Versions still use CoW (in a thread-safe way) for std::string. I'm not sure about std::vector. Probably not. > > In C++0x you will be able to use make_pair(T1&&, T2&&) and "move" s and > > v, avoiding the copies. As far as I know, the syntax will probably be > > m.insert(make_pair(move(s), move(v))) (with all std:: omitted). > > "In principle" then, would m.insert(pair<string, vector<int>>(s, v)); > avoid making a copy? No. They have to be copied since s and v are lvalues. Bug again, that doesn't imply that the string's elements are copied (due to CoW). But CoW is not mandated, only a possibility. In C++0x you will be able to write m.emplace(move(s), move(v)); without having to worry about any copying. The pair object will be directly constructed "into the map" using its templated constructor that forwards the rvalues references of move(s) and move(v) to the constructors of std::string and std::vector. > I had been treating make_pair as a syntatic nicety, but completely > equivalent to the constructor of pair. I think it's safe to say that is is if your compiler supports RVO (return value optimization) and inlining. You can expect make_pair to be as efficient as a direct constructor call. If you're concerned about the performance you could do something like this: if (m.find(s)==m.end()) m[s].swap(v); This will create a pair with a copied string as key and a default- constructed vector. The new vector is immediately swapped with v. Cheers, SG -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Jeff Schwab on 9 Nov 2009 09:43
Jeff Flinn wrote: > Do any implementations of STL implement copy-on-write >> semantics for string or vector? > > MSVC(VC6)/Dinkumware used to do COW for std::string, but found that > small string optimization provided better overall performance. How does that preclude CoW for non-small strings? -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |