COW (copy-on-write) strings & multithreading
Artem Livshits
and I happened to be on the side of COW string. The main argument against
COW strings was that they have poor performance in multithreaded environment
and I was pointed to the article "Optimizations That Aren't (In a
Multithreaded World)" by Herb Sutter
http://www.gotw.ca/publications/optimizations.htm. The problem presented in
the article is that if we have a COW string var shared between several
threads it may share its representation under the covers so even if we
synchronize the access to the var we still may end up with a shared
representation accessable from several threads. The solution presented in
the article is to embed synchronization into a COW string so it could
synchronize the access into shared representaion from several threads.
I agree with the problem but I don't quite agree with the solution. In my
opinion the solution for COW strings should be similar in principle to the
solution for plain (non-COW) strings. The alternatives for plain string look
like (quoted from the article):
1. [WRONG] Do locking within String member functions.
2. [RIGHT] Do locking in the code that owns/manipulates a String object.
3. [PROBLEMATIC] Do both.
And the solution is the alternative #2. Indeed, we need specical care only
in the code where an object can be accessed from several threads as in the
other code (i.e. where an object can be accessed only from a single thread)
the usual signle-threaded logic works just fine. Rephrasing the alternatives
from the article can get an acceptable solution for COW string:
1. [WRONG] Take spectial care about multithreading within String member
functions.
2. [RIGHT] Take spectial care about multithreading in the code that
owns/manipulates a String object.
3. [PROBLEMATIC] Do both.
In the case of plain (non-COW) strings the special care is locking; in the
case of COW strings the special care is locking plus always doing a deep
copy (instead of sharing the representation). So for COW string objects
accessable from several threads we do deep copies always and for COW string
objects accessable from a single thread the representaion can be shared
wherever it's safe for a single-threaded COW string.
Let's take now the example from the article and modify it so it forces a
deep copy when a shared object is accessed (let's assume that string in this
example is std::string)
string err;
int count = 0;
CriticalSection cs; // to protect the err and count values
string GetError()
{
cs.Lock(); // --enter mutual exclusion block------
string ret = err.c_str(); // XXX <-- HERE!
cs.Unlock(); // --exit mutual exclusion block-------
return ret;
}
string SetError( const string& msg )
{
cs.Lock(); // --enter mutual exclusion block------
err = AsString( ++count ) + ": ";
err += msg;
err += " (" + TimeAsString() + ")";
string ret = err.c_str(); // XXX <-- AND HERE!
cs.Unlock(); // --exit mutual exclusion block-------
return ret;
}
This works both with COW and plain implementations of string and doesn't
require a COW implementaion to do any kind of locking inside the string
itself.
Actually it would be nice to mark the shared string somehow that it
shouldn't use the COW "optimization" so we don't need to use c_str() every
time we copy from/to the shared string. One way is to have a plain (non-COW)
string counterpart class and use plain strings for string objects accessable
from several threads; another way is to modify a COW string class so we
could use 'volatile' keyword on the objects to show that we don't want
"optimizations".
The modified COW string class's interface could look like this:
class string
{
public:
string(const string &rhs) { /* do shared copy */ }
string(const volatile string &rhs) { /* do deep copy */ }
// other consructors and destructor
string &operator=(const string &rhs) { /* do shared copy */; return
*this; }
string &operator=(const volatile string &rhs) { /* do deep copy */;
return *this; }
volatile string &operator=(const volatile string &rhs) volatile { /* do
deep copy */; return *this; }
char operator[](size_t i) const volatile;
char &operator[](size_t i) volatile;
// other methods with added "volatile" keyword
};
So given this interface the example transforms into:
volatile string err; // XXX <-- don't try to make 'err' smarter than
the programmer
int count = 0;
CriticalSection cs; // to protect the err and count values
string GetError()
{
cs.Lock(); // --enter mutual exclusion block------
string ret = err; // calls string(const volatile string &rhs)
cs.Unlock(); // --exit mutual exclusion block-------
return ret;
}
string SetError( const String& msg )
{
cs.Lock(); // --enter mutual exclusion block------
err = AsString( ++count ) + ": ";
err += msg;
err += " (" + TimeAsString() + ")";
string ret = err; // calls string(const volatile string &rhs)
cs.Unlock(); // --exit mutual exclusion block-------
return ret;
}
Note that again the code doesn't depend on whether the implementation of
string is COW or plain (provided that it conforms to the same interface).
The 'volatile' variant, however, have some problems that can't be solved
automatically at compile time (at least I don't see how), the most serious,
IMHO, is that the copy constructor doesn't recongnize if it's called for a
volatile object or not. So
static string s1;
static volatile string s2(s1);
would still share the representation that can bring about race conditions
(the second line should be "static volatile string s2(s1.c_str());" instead,
but the compiler can't advise us about it).
This can be checked at run time, though. To check this, different volatile
and non-volatile versions of modifying methods can be provided. E.g.:
class string
{
public:
// other methods
char &operator[](size_t i) volatile
AssumeUnique();
return const_cast<string &>(*this)[i];
}
char &operator[](size_t i);
private:
inline void AssumeUnique() const volatile
{
if (data_->refs > 1)
throw StringError("logic error: volatile string is shared!");
}
string_rep *data_;
};
This way a volatile string never modifies a ref counter; non-volatile
strings are supposed to be used by a single thread so they are intrinsically
synchronized with each other; if a string doesn't use the string_rep after
it decremented its ref counter there should be no race condition possible as
far as I can see.
Another probem is that the compiler can't "unshare", of course, the
representation every time we "add" 'volatile' keyword to the string:
void f(volatile string &s)
{
s = "Hello!";
}
void h()
{
string s1 = "One";
string s2 = s1;
f(s2);
}
The exception will be thrown showing that a volatile string has to meet
certain conditions and it doesn't; this is the correct behaviour, but it
would be better if the situation could be prevented at compile time.
The solution does mean that the COW string implementation doesn't "just
work" in multithreaded environment (but in fact the plain string doesn't
"just work" too as it at least requires locking and may require more if the
fast allocator uses per-thread heaps). But I believe this solution (in any
variant: using 'volatile', using a special class or using just .c_str())
looks consistent with STL's (and C++ in general) position about
multithreading: it's possible to make STL (and the language in general) to
be more thread safe (so they "just work" without special care) but in most
(all?) cases it inevitably means a performance hit for code that is
single-threaded, i.e. we have to pay for what we don't use. Note, that it
often happens that even if a program can have several threads most of the
code is single-threaded in the sense that most objects are created and
accessed only within a single thread.
Sincerely,
Artem Livshits
Brainbench MVP for C++
http://www.brainbench.com
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Francis Glassborow
<a_e_li...@yahoo.com> writes
>Some time ago I had a discussion with a fellow programmer about COW strings
>and I happened to be on the side of COW string. The main argument against
>COW strings was that they have poor performance in multithreaded environment
>and I was pointed to the article "Optimizations That Aren't (In a
>Multithreaded World)" by Herb Sutter
>http://www.gotw.ca/publications/optimizations.htm. The problem presented in
>the article is that if we have a COW string var shared between several
>threads it may share its representation under the covers so even if we
>synchronize the access to the var we still may end up with a shared
>representation accessable from several threads. The solution presented in
>the article is to embed synchronization into a COW string so it could
>synchronize the access into shared representaion from several threads.
>
>I agree with the problem but I don't quite agree with the solution. In my
>opinion the solution for COW strings should be similar in principle to the
>solution for plain (non-COW) strings. The alternatives for plain string look
>like (quoted from the article):
>
>1. [WRONG] Do locking within String member functions.
>2. [RIGHT] Do locking in the code that owns/manipulates a String object.
>3. [PROBLEMATIC] Do both.
There is one overwhelming assumption when discussing COW, and that is
that the representation will be held in dynamic storage. This is one of
the main motivations for the idiom.
An alternative for strings is to use internal storage for short strings
(say, up to 16 bytes, or perhaps 32 bytes) and only move to dynamic
storage for longer strings. Now most of the problems go away. We no
longer have to worry about shared representations being visible in
different threads.
The problem with COW versions is that the programmer must either always
lock when working in an MT environment or be fully aware of all the
potential sharers of the representation. We have had enough problem in
the past with manual memory management for single objects, the idea that
we trust programmers do manage memory (representations) across multiple
objects is a serious threat to my health.
I seriously do not believe that COW and MT can ever be both safe and
efficient.
As COW even in a single threaded environment often delivers less than it
promises, we should be seeking other idioms, even if a language
extension might be needed for some of them.
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
Dietmar Kuehl
"Artem Livshits" <a_e_li...@yahoo.com> wrote:
> Some time ago I had a discussion with a fellow programmer about COW strings
> and I happened to be on the side of COW string.
For string classes with an interface specifically designed to support COW, COW
strings may be reasonable. Just a note, however, that the precondition of
being specifically designed for COW does not apply to the string classes in
the standard C++, ie. the class template 'std::basic_string': Using COW (and
correctly implementing the string class, of course) will in most cases yield
inferior behavior to a good non-COW implementation. Only when taking
considerable care about string operations, a COW string might be more
efficient. The problem with the standard string class is that there are too
many operations which are causing a potential copy. Apart from the obvious
mutators, any access to returning a reference to the string, even those using
an iterator, have to check whether a copy has to be made (there was a lengthy
discussion on this topic in this forum before and I explained in detail why
it is pretty unreasable to use a COW implementation for 'std::basic_string',
even in a single threaded environment).
This is not even taking multi-threading into account! If every check has to
lock even an extremely fast synchronization object (whatever that may be),
the performance will be reduced to a crawl. The advantage of COW will only
show up for careful accesses to huge strings. Although this may be one usage
scenario, I don't think that it makes sense to optimize for this and to
leave other usage scenarios with mediocre performance.
The current standard library does not really provide a reasonable string
class (or string class template) for many typical applications: Often strings
are immutable and when a variation of the string is necessary, making a copy
is reasonable. The current specification basically dictates making copies in
many situations. It would be beneficial if the standard library had an
immutable string whose representation could be shared between instances with
a simple reference counting mechanism (there is still a cost but it is
probably sufficient low, even in multi-threaded environments where a
synchronization object has to be locked). Since the current string class
requires its character type to be assignable, we might just use the
specialization
template <typename cT, typename traits, typename alloc>
class basic_string<cT const, traits, alloc> { ... };
(note the 'const' character type). This specialization would just provide
the subset of the 'basic_string' interface which includes the immutable
string operations or, at least, it does not provide any possibility to get
at a mutable character reference: Removing the functions providing access
to a non-const character reference is probably sufficient to make a COW
implementation viable, although I would favour a really immutable string.
--
<mailto:dietma...@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
Artem Livshits
news:p6+$iQBgkJ...@ntlworld.com...
> In article <9nhir3$ai8$1...@newsreader.mailgate.org>, Artem Livshits
> <a_e_li...@yahoo.com> writes
> >
> >opinion the solution for COW strings should be similar in principle to
the
> >solution for plain (non-COW) strings. The alternatives for plain string
look
> >like (quoted from the article):
> >
> >1. [WRONG] Do locking within String member functions.
> >2. [RIGHT] Do locking in the code that owns/manipulates a String object.
> >3. [PROBLEMATIC] Do both.
>
> There is one overwhelming assumption when discussing COW, and that is
> that the representation will be held in dynamic storage. This is one of
> the main motivations for the idiom.
>
> An alternative for strings is to use internal storage for short strings
> (say, up to 16 bytes, or perhaps 32 bytes) and only move to dynamic
> storage for longer strings. Now most of the problems go away. We no
> longer have to worry about shared representations being visible in
> different threads.
>
You are probably right about strings. Sorry, I forgot to mention that as the
original article the discussion is not exactly about implementation of a
string class, but rather about one specific problem of a
shared-representation optimization. A string class is just a well-known and
wide spread application of it (and it was used in the article anyway). So I
didn't consider what can be done for strings in particular or what other
problems COW strings can have; I tried to show that the particular problem
presented in the article can be solved in a different (and IMHO more
efficient) way.
> The problem with COW versions is that the programmer must either always
> lock when working in an MT environment
> or be fully aware of all the
> potential sharers of the representation.
Well, kind of. Except the solution is to find all the "100%" non-sharers:
it's usually a relatively small subset and the elements of the subset are
usually already distinguished somehow (as special care like locking is
needed for them anyway). After the non-sharers are located the sharers are
automatically splited into safe-intersharing subsets and the problem of
"being fully aware of all the potential sharers of the representation" is
solved. (It's like someone may say that a Circle object must use a lot of
memory as a circle is an infinite number of points located on the same
distance from the center; in practice we don't have to store all the points
of a circle indeed).
> We have had enough problem in
> the past with manual memory management for single objects, the idea that
> we trust programmers do manage memory (representations) across multiple
> objects is a serious threat to my health.
Ok.
> I seriously do not believe that COW and MT can ever be both safe and
> efficient.
That's basically what the solution implements -- separates COW and MT. As I
said if an object is accessed by a single thread there is no difference for
the object if there are other threads in the system or there is only one
thread in the whole world, i.e. in fact the object lives in a
single-threaded evironment and is allowed to share representation with any
other object in the same single-threaded environment. But the objects that
may be accessed from several threads aren't allowed to share representation,
i.e. in fact they are not COW. E.g. (provided that the string is the class
from my solution)
volatile string mt_obj; // lives in MT env; acts as non-COW
CritSec cs;
string someFunc(string st_obj, bool f)
{
if (f)
return st_obj;
else
return st_obj + ", world!";
}
void threadBody()
{
string st_obj1 = "Hello";
string st_obj2 = someFunc(st_obj1, false);
// all the st_* live in single-threaded env and can
// share representation wherever possible
// now we "enter" into MT env
cs.lock();
string st_old = mt_obj; // no COW
mt_obj = st_obj2; // no COW
cs.unlock(); // I know, this is not exeption safe
// "return" to single-threaded env
sd_obj2 = st_old; // can share representaion
}
int main()
{
somehowStartThread(&threadBody);
somehowStartThread(&threadBody);
somehowStartThread(&threadBody);
somehowWaitForThreads();
}
This example illustrates that despite that the program executes multiple
threads the MT code is only what touches the mt_obj; all the other code is
single-threaded indeed. And the code that touches mt_obj doesn't do COW. So
the solution very precisely limits COW to single-threaded code (vs just
saying "don't use COW strings if there might be more than one thread in a
program ever").
> As COW even in a single threaded environment often delivers less than it
> promises, we should be seeking other idioms, even if a language
> extension might be needed for some of them.
Ok.
Artem Livshits
Brainbench MVP for C++
http://www.brainbench.com
Andrei Alexandrescu
news:5b15f8fd.01091...@posting.google.com...
[snip]
> It would be beneficial if the standard library had an
> immutable string whose representation could be shared between instances
with
> a simple reference counting mechanism (there is still a cost but it is
> probably sufficient low, even in multi-threaded environments where a
> synchronization object has to be locked). Since the current string class
> requires its character type to be assignable, we might just use the
> specialization
>
> template <typename cT, typename traits, typename alloc>
> class basic_string<cT const, traits, alloc> { ... };
>
> (note the 'const' character type). This specialization would just provide
> the subset of the 'basic_string' interface which includes the immutable
> string operations or, at least, it does not provide any possibility to get
> at a mutable character reference: Removing the functions providing access
> to a non-const character reference is probably sufficient to make a COW
> implementation viable, although I would favour a really immutable string.
Sounds good, but that would not really improve performance a lot. The
problem is converting between mutable and immutable strings. People would
have functions take string<const char>, but when initializing a string<const
char> with a string<char>, a copy must be made :o/.
Andrei
Dietmar Kuehl
"Andrei Alexandrescu" <andre...@hotmail.com> wrote:
> Sounds good, but that would not really improve performance a lot.
This is nothing which helps to improve performance "under the hood". It is
a deliberate decision to use 'std::basic_string<cT const>' instead of
'std::basic_string<cT>'. To aid in converting programs or to aid
programs needing both version of the class, appropriate conversion
constructors (ie. in both directions) could be supplied. However, using
the right string class consistently could avoid unnecessary copies where
the current situation does not support this at all.
--
<mailto:dietma...@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Dave Harris
> Sounds good, but that would not really improve performance a lot. The
> problem is converting between mutable and immutable strings. People
> would have functions take string<const char>, but when initializing a
> string<const char> with a string<char>, a copy must be made :o/.
Can't that copy be avoided if string<char> cooperates? If string<const
char> and string<char> share the same storage, I would have thought the
copy could be deferred until the next attempt to write to the
string<char>. If the next attempt is resize(0), or there is no attempt,
then the copy can be avoided altogether.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
Dietmar Kuehl
Dave Harris wrote:
> Can't that copy be avoided if string<char> cooperates? If string<const
> char> and string<char> share the same storage, I would have thought the
> copy could be deferred until the next attempt to write to the
> string<char>. If the next attempt is resize(0), or there is no attempt,
> then the copy can be avoided altogether.
This doesn't make sense: The mutable version of string should not use
copy on write. If it uses this approach in one place, it would have the
whole machinery and it should then be used consistently. ... but copy
on write is no good for a class not specifically and completely designed
for this.
My idea is to provide an immutable, COW string class which can be
choosen deliberately where appropriate, eg. for a key in map.
--
<mailto:dietma...@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
Bill Wade
"Francis Glassborow" <francis.g...@ntlworld.com> wrote
> There is one overwhelming assumption when discussing COW, and that is
> that the representation will be held in dynamic storage. This is one of
> the main motivations for the idiom.
Actually the overwhelming assumption for promoting COW is that copying
pointers/references is much less expensive then performing deep copies.
Dynamic storage is often a major contributor to this expense, but it is not
the only source.
Note that passing an object (not necessarily a string) by const-reference
rather than by value is a COW optimization. Like string COW,
const-reference has certain dangers, primarily associated with aliasing.
Nevertheless, most authors, even those who argue against premature
optimization, promote pass-by-const-reference as an almost automatic
optimization.
Certainly if most of your objects are small enough (small==cheap deep
copies) then you won't spend much time writing reference-counted smart
pointers, and you may decide to pass all in-arguments by value.
The utility of allowing COW in std::string is certainly debatable. If I
need COW in portable code, then I have to write my own string class, because
the standard doesn't guarantee it will be there. On the other hand,
std::string is more dangerous than it would have been had COW been
forbidden.
Probably the greatest argument for allowing a good COW string was that it
was bait for C programmers in the early nineties (single threaded
environments, slow allocators, no convenient string) to get them to
seriously consider C++. By the time the standard was actually passed, much
of that motivation was obsolete (MT, fast allocators, most C programmers
already migrated to C++).
Francis Glassborow
Wade <wrw...@swbell.net> writes
>
>"Francis Glassborow" <francis.g...@ntlworld.com> wrote
>
>> There is one overwhelming assumption when discussing COW, and that is
>> that the representation will be held in dynamic storage. This is one of
>> the main motivations for the idiom.
>
>Actually the overwhelming assumption for promoting COW is that copying
>pointers/references is much less expensive then performing deep copies.
>Dynamic storage is often a major contributor to this expense, but it is not
>the only source.
cases other than dynamic memory.
>
>Note that passing an object (not necessarily a string) by const-reference
>rather than by value is a COW optimization. Like string COW,
>const-reference has certain dangers, primarily associated with aliasing.
>Nevertheless, most authors, even those who argue against premature
>optimization, promote pass-by-const-reference as an almost automatic
>optimization.
Yes, I once (more than five years ago) wrote an article whose burden was
that even pass by const ref disallowed many optimisations, precisely
because of the aliasing problem (which includes such problems as the
function call passing a const ref to a global variable, those two things
do not mix well)
>
>Certainly if most of your objects are small enough (small==cheap deep
>copies) then you won't spend much time writing reference-counted smart
>pointers, and you may decide to pass all in-arguments by value.
And that is something that programmers should always consider. However
there is a problem if you try to write portable code because something
that can be passed cheaply (in a register for example) on one system may
be much more expensive on another (e.g. causing a cache update or a page
fault)
>
>The utility of allowing COW in std::string is certainly debatable. If I
>need COW in portable code, then I have to write my own string class, because
>the standard doesn't guarantee it will be there. On the other hand,
>std::string is more dangerous than it would have been had COW been
>forbidden.
Indeed, and I am happy to see libraries moving away from this, but as
long as the standard allows it, portable code (portable between library
implementations) has to assume that COW will be used and that is a bad
hit.
>
>Probably the greatest argument for allowing a good COW string was that it
>was bait for C programmers in the early nineties (single threaded
>environments, slow allocators, no convenient string) to get them to
>seriously consider C++. By the time the standard was actually passed, much
>of that motivation was obsolete (MT, fast allocators, most C programmers
>already migrated to C++).
Well the only point that I would refine is that 'most programmers who
might move to C++ from C have done so.' There are many who do not
perceive C++ as being useful in their problem domains.
Francis Glassborow
I offer my sympathy and prayers to all those who are suffering
as a result of the events of September 11 2001.
Herb Sutter
quibble about two small details of the way he said it.
"Bill Wade" <wrw...@swbell.net> writes:
>Nevertheless, most authors, even those who argue against premature
>optimization, promote pass-by-const-reference as an almost automatic
>optimization.
^^^^^^^^^^^^
That last word isn't really accurate. I for one strenuously argue against
premature optimization -- but when in the same talk/article/book I also say
that passing by const&, writing ++i, and such idioms should just
automatically flow out your fingers up front, I try to make the point that
this is not up-front optimization. Rather, it is the avoidance of obvious
pessimization.
Premature optimization is when you worry about performance up front absent
evidence that any problem actually exists, and particularly when it costs
you up front because you end up writing more complex code or even just
spending more time on the code in a probably-vain striving after a needless
performance boost.
Avoidance of pessimization is just sound coding that isn't any harder up
front and doesn't make your code more complicated. Alternatively, it can be
spelled "just don't do obviously boneheaded things" like pass a
million-element list by value to a search function. :-)
>Probably the greatest argument for allowing a good COW string was that it
>was bait for C programmers in the early nineties (single threaded
>environments, slow allocators, no convenient string) to get them to
>seriously consider C++.
That may be a good argument, but was it really the historical reason? If so,
I would appreciate the historical insight. COW has been popularly and widely
used long before C++, back to the 1960s, and particularly for strings. As I
have understood it to date, the idea was just that it seemed natural to
support it in C++ strings too because that's what everyone else had been
doing for years.
> By the time the standard was actually passed, much
>of that motivation was obsolete (MT, fast allocators, most C programmers
>already migrated to C++).
Herb
---
Herb Sutter (http://www.gotw.ca)
Secretary, ISO WG21 / ANSI J16 (C++) standards committee
Contributing Editor, C/C++ Users Journal (http://www.cuj.com)
* Check out THE C++ Seminar: http://www.gotw.ca/cpp_seminar
Herb Sutter
>I would be interested in an example of where deep copying costs for
>cases other than dynamic memory.
In my articles on this topic (also in More Exceptional C++ Items 13-16 and
both appendices), one of the interesting results was this one, as originally
written in GotW #45 (http://www.gotw.ca/gotw/045.htm):
"3. It is a myth that COW's principal advantage lies in avoiding
memory allocations. Especially for longer strings, COW's principal
advantage is that it avoids copying the characters in the string."
Surprised me too, but that was before I saw how fast modern memory
allocators have become.
Herb
---
Herb Sutter (http://www.gotw.ca)
Secretary, ISO WG21 / ANSI J16 (C++) standards committee
Contributing Editor, C/C++ Users Journal (http://www.cuj.com)
* Check out THE C++ Seminar: http://www.gotw.ca/cpp_seminar
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Dave Harris
> > [unwanted copies converting mutable to immutable strings]
> > If string<const char> and string<char> share the same storage,
> > I would have thought the copy could be deferred until the next
> > attempt to write to the string<char>
>
> copy on write.
Ok; sorry. In that case we would need a destructive "copy", which passes
the memory to the immutable string and leaves the mutable one in an empty
state. This would deal with the common case where the contents of the
mutable string are not used after it has been converted into the immutable
one.
As with auto_ptr, destructive copy would need to be explicit, perhaps done
with a function rather than a destructor. Perhaps "pilfer" would be a
reasonable name for the function.
std::basic_string<char> source;
// Build up a string in source. Source is mutable and without
// reference counting, optimised for editing.
std::basic_string<const char> result = source.pilfer();
// Result is immutable and cheap to copy. Source is
// now empty. pilfer() can be implemented not to copy
// the characters of the string.
Basically I agree that a separate immutable string class would be a good
thing.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
David Abrahams
"Dave Harris" <bran...@cix.co.uk> wrote in message
news:memo.20010915...@brangdon.madasafish.com...
> dietma...@yahoo.com (Dietmar Kuehl) wrote (abridged):
> > > [unwanted copies converting mutable to immutable strings]
> > > If string<const char> and string<char> share the same storage,
> > > I would have thought the copy could be deferred until the next
> > > attempt to write to the string<char>
<snip>
> Basically I agree that a separate immutable string class would be a good
> thing.
I think it might be a good idea at this point to clarify what we're talking
about. When we say "immutable" I don't think we really mean it. For example,
I see no reason to prevent ordinary assignment, or the use of += (or even
*=, but that's another discussion). I think the key features of the string
we're discussing are something like this:
1. It is only /atomically/ mutable, meaning that operations which change the
string operate on the whole thing at once. Assignment is such an operation,
but we could easily imagine others, e.g. to_lower() or reverse().
2. pointers/references/iterators are always constant, and are invalidated by
any operations which modify the string.
[please speak up if you've been imagining something different ;-)]
Interestingly, this rules out the use of any algorithm which would modify
the string through an iterator, and seems to argue for "algorithms which
take container arguments". Although that's something I've often heard
requested, it isn't clear that it's something people actually need, and I
wonder if it would be worth doing just to support COW.
-Dave
Dietmar Kuehl
Dave Harris wrote:
[Comment on uselessness of sharing the internal representation between a
mutable and an immutable string when converting between the string
classes removed]
> Ok; sorry. In that case we would need a destructive "copy", which passes
> the memory to the immutable string and leaves the mutable one in an empty
> state.
Apparently I haven't expressed myself very well about the goals of
'std::basic_string<cT const>': This class is intended to allow a
representation shared between multiple instances of the class. It is
actually not a "COW" class but just an immutable string (ie. there is
no write) with a possibly reference counted representation. It is a
very different class than 'std::basic_string<cT>'. The only relations
between 'std::basic_string<cT const>' and 'std::basic_string<char>'
is that there are implicit conversions (ie. suitable constructors)
defined to convert between the two strings. In particular, converting
a 'std::basic_string<cT const>' from a 'std::basic_string<cT>' or vice
versa *does* copy the internal representation. Copying or assigning a
'std::basic_string<cT const>' may result in two instances sharing the
internal representation, eg. by using a reference counted pointer to
the internal representation.
The point here is that when dealing with immutable strings (the
immutability applies to the character sequence represented, not to the
string object itself, ie. you can assign a new value to the string
but that's it; there are some possible operations which might be
reasonable like eg. 'operator+=()' because such operations would not
touch the original internal representation but create a new one anyay)
is that the strings are never changed and dealing with sharing the
internal representation is localized in a few methods (eg. the copy
ctor, copy assignment, and dtor plus, possibly, a few "convenience"
operations like 'operator+=()'). A COW for 'std::basic_string<cT>'
isn't viable because there are too many situations where it is necessary
to check whether the string is actually shared before the operations can
be applied.
Of course, an explicit method doing a destructive conversion between
'std::basic_string<cT>' and 'std::basic_string<cT char>' might also be
reasonable. I'm actually not sure whether I should take your comments
sarcastic or honest and I at least partially assumed them to be
sarcastic (sorry if this wasn't your intention...).--
<mailto:dietma...@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
Dave Harris
> 'std::basic_string<cT const>': This class is intended to allow a
> representation shared between multiple instances of the class. It is
> actually not a "COW" class but just an immutable string (ie. there is
> no write) with a possibly reference counted representation.
Yes, I understood that.
> [...] In particular, converting a 'std::basic_string<cT const>' from
> a 'std::basic_string<cT>' or vice versa *does* copy the internal
> representation.
Yes, I understood that too. Certainly a copying conversion is needed and
should probably be the default. I was addressing a comment by Andrei
Alexandrescu about the cost of that conversion. I am pointing out that we
can do the conversion in O(1) time if we don't mind zapping the source in
the process.
> Of course, an explicit method doing a destructive conversion between
> 'std::basic_string<cT>' and 'std::basic_string<cT char>' might also be
> reasonable.
Exactly.
> I'm actually not sure whether I should take your comments
> sarcastic or honest and I at least partially assumed them to be
> sarcastic (sorry if this wasn't your intention...).--
I wasn't being sarcastic.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
James Kanze
news:<9o0v1t$2du$1...@bob.news.rcn.net>...
> "Dave Harris" <bran...@cix.co.uk> wrote in message
> news:memo.20010915...@brangdon.madasafish.com...
> > dietma...@yahoo.com (Dietmar Kuehl) wrote (abridged):
> > > > [unwanted copies converting mutable to immutable strings]
> > > > If string<const char> and string<char> share the same storage,
> > > > I would have thought the copy could be deferred until the next
> > > > attempt to write to the string<char>
> <snip>
> > Basically I agree that a separate immutable string class would be
> > a good thing.
> I think it might be a good idea at this point to clarify what we're
> talking about. When we say "immutable" I don't think we really mean
> it. For example, I see no reason to prevent ordinary assignment, or
> the use of += (or even *=, but that's another discussion). I think
> the key features of the string we're discussing are something like
> this:
Agreed. Initially, the only way to modify my pre-standard string
class was by using an assignment operator (=, += and *=). I still
find this the clearest.
Note that the semantics of += and *= (and most other non-const
functions, for that matter) can be specified in terms of assignment,
so supporting assignment is sufficient for them as well. What you
can't support is a non-const operator[] (at least not efficiently) or
non-const iterators.
> 1. It is only /atomically/ mutable, meaning that operations which
> change the string operate on the whole thing at once. Assignment is
> such an operation, but we could easily imagine others,
> e.g. to_lower() or reverse().
You can imagine anything whose semantics can be expressed in terms of
assignment; i.e. create a new string and assign it to the existing
one.
> 2. pointers/references/iterators are always constant, and are
> invalidated by any operations which modify the string.
> [please speak up if you've been imagining something different ;-)]
> Interestingly, this rules out the use of any algorithm which would
> modify the string through an iterator, and seems to argue for
> "algorithms which take container arguments". Although that's
> something I've often heard requested, it isn't clear that it's
> something people actually need, and I wonder if it would be worth
> doing just to support COW.
It's not completely clear to me why you need the algorithms taking a
container. The "unmodifiable" string only has const iterators; you
can't modify the string through them regardless of the algorithm you
invoke. (If the algorithm tries to modify the string, you will get
the usual incomprehesible error message from the compiler.)
--
James Kanze mailto:ka...@gabi-soft.de
Beratung in objektorientierer Datenverarbeitung --
-- Conseils en informatique orientée objet
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany, Tél.: +49 (0)69 19 86 27
Matthew Austern
> "Francis Glassborow" <francis.g...@ntlworld.com> wrote
>
> > There is one overwhelming assumption when discussing COW, and that is
> > that the representation will be held in dynamic storage. This is one of
> > the main motivations for the idiom.
>
> Actually the overwhelming assumption for promoting COW is that copying
> pointers/references is much less expensive then performing deep copies.
The other assumption is that the time saved by avoiding deep copies is
greater than the time lost by making character access more expensive.
(Because reference-counting in general adds one level of pointer
indirection to read access, and because COW adds a test to write
access.)
If we were more energetic, we could make this assumption quantitative:
it depends on the number of character references compared to the
number of string copies, the cost of adding an extra pointer
indirection to character read access, and the relative cost of a
string copy compared to a pointer copy and refcount update. The
latter number depends on the length distribution of strings in your
particular application, of course.
David Abrahams
"Matthew Austern" <aus...@research.att.com> wrote in message
news:dilofo9...@isolde.research.att.com...
> The other assumption is that the time saved by avoiding deep copies is
> greater than the time lost by making character access more expensive.
> (Because reference-counting in general adds one level of pointer
> indirection to read access,
Where does that extra indirection come from? Even if you don't use an
intrusive count, you don't need to indirect twice to get at the characters.
I don't see what you could be referring to, unless you are assuming an
implementation of reference counting that will, in general, be relatively
costly compared to other easily-implemented schemes.
-Dave
David Abrahams
"James Kanze" <ka...@gabi-soft.de> wrote in message
news:d6651fb6.01091...@posting.google.com...
> > 1. It is only /atomically/ mutable, meaning that operations which
> > change the string operate on the whole thing at once. Assignment is
> > such an operation, but we could easily imagine others,
> > e.g. to_lower() or reverse().
>
> You can imagine anything whose semantics can be expressed in terms of
> assignment; i.e. create a new string and assign it to the existing
> one.
Certainly, but if all you have is assignment, you can't take advantage of
in-place modification for strings whose storage is "uniquely referenced"
(refcount == 1).
> > 2. pointers/references/iterators are always constant, and are
> > invalidated by any operations which modify the string.
>
> > [please speak up if you've been imagining something different ;-)]
>
> > Interestingly, this rules out the use of any algorithm which would
> > modify the string through an iterator, and seems to argue for
> > "algorithms which take container arguments". Although that's
> > something I've often heard requested, it isn't clear that it's
> > something people actually need, and I wonder if it would be worth
> > doing just to support COW.
>
> It's not completely clear to me why you need the algorithms taking a
> container. The "unmodifiable" string only has const iterators; you
> can't modify the string through them regardless of the algorithm you
> invoke. (If the algorithm tries to modify the string, you will get
> the usual incomprehesible error message from the compiler.)
The point is that if you regularly have to use the same mutating algorithm
(e.g. case conversion), this can be made much more efficient if there's an
exposed make_unique() (or about_to_modify()) function and the mutating
"whole container" algorithms always call that before making modifications.
-Dave
James Kanze
> > > 1. It is only /atomically/ mutable, meaning that operations
> > > which change the string operate on the whole thing at
> > > once. Assignment is such an operation, but we could easily
> > > imagine others, e.g. to_lower() or reverse().
> > You can imagine anything whose semantics can be expressed in terms
> > of assignment; i.e. create a new string and assign it to the
> > existing one.
> Certainly, but if all you have is assignment, you can't take
> advantage of in-place modification for strings whose storage is
> "uniquely referenced" (refcount == 1).
What are the advantages of in-place modification?
Generally, my own pre-standard string class corresponded more or less
to what Dietmar is describing. Initially, the only non-const
functions were = and +=; most string operations returned a new
string. I never had any problem with this. I later added a non-const
operator[], because people seemed to want it, but I doubt that it has
ever been used.
> > > 2. pointers/references/iterators are always constant, and are
> > > invalidated by any operations which modify the string.
> > > [please speak up if you've been imagining something different ;-)]
> > > Interestingly, this rules out the use of any algorithm which
> > > would modify the string through an iterator, and seems to argue
> > > for "algorithms which take container arguments". Although that's
> > > something I've often heard requested, it isn't clear that it's
> > > something people actually need, and I wonder if it would be
> > > worth doing just to support COW.
> > It's not completely clear to me why you need the algorithms taking
> > a container. The "unmodifiable" string only has const iterators;
> > you can't modify the string through them regardless of the
> > algorithm you invoke. (If the algorithm tries to modify the
> > string, you will get the usual incomprehesible error message from
> > the compiler.)
> The point is that if you regularly have to use the same mutating
> algorithm (e.g. case conversion), this can be made much more
> efficient if there's an exposed make_unique() (or about_to_modify())
> function and the mutating "whole container" algorithms always call
> that before making modifications.
But that sounds like a false economy. You will save a little CPU time
in a few rare occasions, but you will loose a lot of programmer time
tracking down subtle and hard to find errors.
--
James Kanze mailto:ka...@gabi-soft.de
Beratung in objektorientierer Datenverarbeitung --
-- Conseils en informatique oriente objet
Ziegelhttenweg 17a, 60598 Frankfurt, Germany, Tl.: +49 (0)69 19 86 27
David Abrahams
> "David Abrahams" <david.a...@rcn.com> wrote in message
> news:<9o64bv$58l$1...@bob.news.rcn.net>...
> > "James Kanze" <ka...@gabi-soft.de> wrote in message
> > news:d6651fb6.01091...@posting.google.com...
> > > of assignment; i.e. create a new string and assign it to the
> > > existing one.
>
> > Certainly, but if all you have is assignment, you can't take
> > advantage of in-place modification for strings whose storage is
> > "uniquely referenced" (refcount == 1).
>
> What are the advantages of in-place modification?
The same as COW: Copies are avoided.
> > > It's not completely clear to me why you need the algorithms taking
> > > a container. The "unmodifiable" string only has const iterators;
> > > you can't modify the string through them regardless of the
> > > algorithm you invoke. (If the algorithm tries to modify the
> > > string, you will get the usual incomprehesible error message from
> > > the compiler.)
>
> > The point is that if you regularly have to use the same mutating
> > algorithm (e.g. case conversion), this can be made much more
> > efficient if there's an exposed make_unique() (or about_to_modify())
> > function and the mutating "whole container" algorithms always call
> > that before making modifications.
>
> But that sounds like a false economy. You will save a little CPU time
> in a few rare occasions, but you will loose a lot of programmer time
> tracking down subtle and hard to find errors.
If the algorithms are supplied by the library, there's no problem. If you
don't trust programmers who write "whole string" algorithms to call
make_unique() at the beginning, I agree that there will be problems. I think
we might disagree about whether these programmers can be trusted ;-)
-Dave
P.S. I would probably not give a programmer a non-const iterator to a string
except as a return value from make_unique(). I think that would cut down on
mistakes dramatically.