Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > std::string and refcounting

Reply
Thread Tools

std::string and refcounting

 
 
joe martin
Guest
Posts: n/a
 
      04-20-2004
In recent discussions relating to what to use for a new project which
integrated the work of two, previously seperate, teams we got to the
subject of our respective string implementations. One team rolled
their own strings while the other used the std::string. Reasons for
using the home-grown strings(and vectors) were mainly refcounting and
portabillity, but I thought that these days almost all STL
implementations used refcounted strings and that the STL was available
for most platforms.

When we got back to test things out with my compiler (MSVC++ 6 with
the latest patch-level) strings were refcounted but on the other team
lead's computer (.net) strings were not refcounted. Do any of you know
a webpage or site that consolidates information about the STL
implementations on various platforms or does anyone have specific
information about the state of the STL on Windows, WinCE, Symbian, Mac
or Linux?

Thanks for any help,

-joe
 
Reply With Quote
 
 
 
 
red floyd
Guest
Posts: n/a
 
      04-20-2004
joe martin wrote:

> In recent discussions relating to what to use for a new project which
> integrated the work of two, previously seperate, teams we got to the
> subject of our respective string implementations. One team rolled
> their own strings while the other used the std::string. Reasons for
> using the home-grown strings(and vectors) were mainly refcounting and
> portabillity, but I thought that these days almost all STL
> implementations used refcounted strings and that the STL was available
> for most platforms.
>
> When we got back to test things out with my compiler (MSVC++ 6 with
> the latest patch-level) strings were refcounted but on the other team
> lead's computer (.net) strings were not refcounted. Do any of you know
> a webpage or site that consolidates information about the STL
> implementations on various platforms or does anyone have specific
> information about the state of the STL on Windows, WinCE, Symbian, Mac
> or Linux?
>


std::string was changed in VC.NET because of threading issues. However,
that's kind of OT.
 
Reply With Quote
 
 
 
 
Dietmar Kuehl
Guest
Posts: n/a
 
      04-21-2004
joe martin wrote:
> When we got back to test things out with my compiler (MSVC++ 6 with
> the latest patch-level) strings were refcounted but on the other team
> lead's computer (.net) strings were not refcounted. Do any of you know
> a webpage or site that consolidates information about the STL
> implementations on various platforms or does anyone have specific
> information about the state of the STL on Windows, WinCE, Symbian, Mac
> or Linux?


I don't have specific information but my understanding from talking
to the other C++ library implementers is that everybody is moving
away from reference counted implementations of 'std::string'.
Essentially, the reason is that the interface is not really suitable
for this kind of implementation despite the fact that the specification
in the standard actually even mentions reference counting in a note
(if I remember correctly). This is somewhat related to the history of
the string class which was vamped up when everything became a template.
Things are further complicated in [potentially] multi-threaded
environments where the reference counting approach effectively requires
mutex locks in various places which significantly increases the costs.

I haven't verified the results but apparently the conclusion is that
copying strings is acceptable and the costs can be further reduced
by the "small string"-optimization (which simply embeds the string in
the string object directly if it is smaller than eg. 32 chars). For
really large strings you probably want to pass them around by reference
or through a shared pointer - at least when they are immutable.
--
<(E-Mail Removed)> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting
 
Reply With Quote
 
joe martin
Guest
Posts: n/a
 
      04-22-2004
On Wed, 21 Apr 2004 05:38:10 +0200, Dietmar Kuehl
<(E-Mail Removed)> wrote:

>joe martin wrote:
>> When we got back to test things out with my compiler (MSVC++ 6 with
>> the latest patch-level) strings were refcounted but on the other team
>> lead's computer (.net) strings were not refcounted. Do any of you know
>> a webpage or site that consolidates information about the STL
>> implementations on various platforms or does anyone have specific
>> information about the state of the STL on Windows, WinCE, Symbian, Mac
>> or Linux?

>
>I don't have specific information but my understanding from talking
>to the other C++ library implementers is that everybody is moving
>away from reference counted implementations of 'std::string'.
>Essentially, the reason is that the interface is not really suitable
>for this kind of implementation despite the fact that the specification
>in the standard actually even mentions reference counting in a note
>(if I remember correctly). This is somewhat related to the history of
>the string class which was vamped up when everything became a template.
>Things are further complicated in [potentially] multi-threaded
>environments where the reference counting approach effectively requires
>mutex locks in various places which significantly increases the costs.


I thought though that the use of atomic incrementors and decrementors
could be used in place of a mutex and that they were available on most
processors. I asked on the Windows newsgroup about what their reasons
might have been to not just use the provided Interlocked functions but
havn't really gotten a response. Maybe I am wrong that atomic fcns are
all that are really needed for refcounted objects? That would be
unfortunate as I think this is our internal solution.

>
>I haven't verified the results but apparently the conclusion is that
>copying strings is acceptable and the costs can be further reduced
>by the "small string"-optimization (which simply embeds the string in
>the string object directly if it is smaller than eg. 32 chars). For
>really large strings you probably want to pass them around by reference
>or through a shared pointer - at least when they are immutable.


This makes sense I guess although refcounting seems so much more
efficient. My hope is that Smarter Brains Than Mine have considered
the necessary issues in most STL implementations and acted
accordingly. Anyway, thanks for your response.

-joe

 
Reply With Quote
 
Siemel Naran
Guest
Posts: n/a
 
      04-22-2004
"joe martin" <(E-Mail Removed)> wrote in message
> <(E-Mail Removed)> wrote:


> >I don't have specific information but my understanding from talking
> >to the other C++ library implementers is that everybody is moving
> >away from reference counted implementations of 'std::string'.
> >Essentially, the reason is that the interface is not really suitable
> >for this kind of implementation despite the fact that the specification
> >in the standard actually even mentions reference counting in a note
> >(if I remember correctly). This is somewhat related to the history of
> >the string class which was vamped up when everything became a template.


What is it about the interface turns implementors away from reference
counting?

> >Things are further complicated in [potentially] multi-threaded
> >environments where the reference counting approach effectively requires
> >mutex locks in various places which significantly increases the costs.


This is only a problem when we share writable strings between threads. How
often does this happen anyway? For that matter, isn't boost::shared_ptr a
problem?


> This makes sense I guess although refcounting seems so much more
> efficient. My hope is that Smarter Brains Than Mine have considered
> the necessary issues in most STL implementations and acted
> accordingly. Anyway, thanks for your response.


Why would refcounted strings be faster? Sure, it's fast when you pass and
return strings by value. But then when you change the reference copied
string you have to make a deep copy anyway. Also, there is the return value
optimization, but I don't know how many compilers implement this.


 
Reply With Quote
 
Dietmar Kuehl
Guest
Posts: n/a
 
      04-22-2004
joe martin <(E-Mail Removed)> wrote:
> I thought though that the use of atomic incrementors and decrementors
> could be used in place of a mutex and that they were available on most
> processors. I asked on the Windows newsgroup about what their reasons
> might have been to not just use the provided Interlocked functions but
> havn't really gotten a response. Maybe I am wrong that atomic fcns are
> all that are really needed for refcounted objects? That would be
> unfortunate as I think this is our internal solution.


My understanding is that atomic increments and decrements (combined at
least in one direction with a test) are sufficient for single processor
machines but not for multi processor machines. However, I'm not really
sure about this.

> This makes sense I guess although refcounting seems so much more
> efficient.


Is this a conclusion from measuring or from deduction? I can see that
reference counting huge strings will probably be more efficient but
for the typical small strings I'm using in my programs I doubt that a
reference counted approach is really faster. On the other hand, I
haven't measured it either.

> My hope is that Smarter Brains Than Mine have considered
> the necessary issues in most STL implementations and acted
> accordingly. Anyway, thanks for your response.


The problem with the standard string class is that the specification
effectively requires copying the string in many, often unexpected,
places. For example, when obtaining and dereferecing and iterator for
a non-const object, a copy becomes necessary. The necessary additional
logic will almost certain dwarf any gains obtained from omitting
copies except when handling mostly fairly large strings. A string
class avoiding problems like this could use reference counting more
effectively but I would still expect it to pay off only for bigger
strings. A good analysis of this would probably be quite interesting.
--
<(E-Mail Removed)> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting
 
Reply With Quote
 
Peter van Merkerk
Guest
Posts: n/a
 
      04-22-2004
> What is it about the interface turns implementors away from reference
> counting?


This (old, possibly outdated) article sheds some light on the problem with
reference counted string implementations:
http://www.sgi.com/tech/stl/string_discussion.html

--
Peter van Merkerk
peter.van.merkerk(at)dse.nl


 
Reply With Quote
 
Michiel Salters
Guest
Posts: n/a
 
      04-22-2004
joe martin <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>. ..
> In recent discussions relating to what to use for a new project which
> integrated the work of two, previously seperate, teams we got to the
> subject of our respective string implementations. One team rolled
> their own strings while the other used the std::string. Reasons for
> using the home-grown strings(and vectors) were mainly refcounting and
> portabillity, but I thought that these days almost all STL
> implementations used refcounted strings and that the STL was available
> for most platforms.
>
> When we got back to test things out with my compiler (MSVC++ 6 with
> the latest patch-level) strings were refcounted but on the other team
> lead's computer (.net) strings were not refcounted. Do any of you know
> a webpage or site that consolidates information about the STL
> implementations on various platforms or does anyone have specific
> information about the state of the STL on Windows, WinCE, Symbian, Mac
> or Linux?


A site that addresses the basics is www.gotw.ca, especially GOTW
articles #43-#45. The executive summary: refcounting is too hard in
threaded environments, and even in single-threaded environments
typically provides little if any advantage.

Regards,
Michiel Salters
 
Reply With Quote
 
Alexander Terekhov
Guest
Posts: n/a
 
      04-22-2004

Michiel Salters wrote:
[...]
> A site that addresses the basics is www.gotw.ca, especially GOTW
> articles #43-#45. The executive summary: refcounting is too hard in
> threaded environments, and even in single-threaded environments
> typically provides little if any advantage.


First off, it isn't really too hard. As for advantage... if deep
copying needs to allocate memory (small string optimisations
aside for amoment), it simply means that you'll incur "some"
synchronisation overheard in the allocator instead of one single
"naked" atomic increment without any membars on refcount. #43-#45
is rather interesting reading but don't believe everything
(especially conclusions) that it says.

http://groups.google.com/groups?thre...CBD4B%40web.de

regards,
alexander.
 
Reply With Quote
 
Dietmar Kuehl
Guest
Posts: n/a
 
      04-22-2004
"Siemel Naran" <(E-Mail Removed)> wrote in message news:<k5Hhc.18351$(E-Mail Removed)>...
> "joe martin" <(E-Mail Removed)> wrote in message
> > <(E-Mail Removed)> wrote:

>
> > >I don't have specific information but my understanding from talking
> > >to the other C++ library implementers is that everybody is moving
> > >away from reference counted implementations of 'std::string'.
> > >Essentially, the reason is that the interface is not really suitable
> > >for this kind of implementation despite the fact that the specification
> > >in the standard actually even mentions reference counting in a note
> > >(if I remember correctly). This is somewhat related to the history of
> > >the string class which was vamped up when everything became a template.

>
> What is it about the interface turns implementors away from reference
> counting?


Effectively, the string has to be unshared in many situations often
unexpected situation. In particular, the string has to be [potentially]
unshared for each character access. This means that you get a conditional
dealing with the reference count in each iterator dereference, each array
access operation (on non-const strings, of course). This costs cycles
even for the considerate people which normally pass strings by reference.
Also, implementers use small string optimizations which don't need an
allocation for strings up to a certain size, eg. 32 chars: this is big
enough to contain many strings (IDs, tpyical data base values, etc.) and
only incurs a memory allocation for really big strings. With all this it
turns out that reference counting is actually more expensive than copying
strings in some cases.

> > >Things are further complicated in [potentially] multi-threaded
> > >environments where the reference counting approach effectively requires
> > >mutex locks in various places which significantly increases the costs.

>
> This is only a problem when we share writable strings between threads.


Yes and no: the problem with reference counting inside a string is that
it is an implementation detail. As such, the implementer of a strings
class for a multi-threaded environment has to make sure that it works
correctly if the string representation is really shared between threads
(well, strictly speaking the standard makes no such requirement but the
users will do anyway): after all, to the user the strings are separate
things and there is no need to protect them in any form from concurrent
accesses. As a consequence, the string has to do protections internally.
That is, it is a problem even if the strings are read-only and not even
shared at all...

> How
> often does this happen anyway? For that matter, isn't boost::shared_ptr a
> problem?


'shared_ptr' does not have this problem because they do no internal
sharing magic: if the 'shared_ptr' is used from different threads, the
user is responsible for the protection against concurrent accesses.
--
<(E-Mail Removed)> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
if and and vs if and,and titi VHDL 4 03-11-2007 05:23 AM
refcounting errors??? hannibal.holm@gmail.com Python 2 11-03-2006 03:23 PM
Advanced topics... optimising / C++ / OOP / RefCounting / type-safety st_ev_fe@hotmail.com C++ 4 11-15-2005 12:35 PM
refcounting Simon Dahlbacka Python 2 04-14-2004 06:09 AM
refcounting and protecting against delete Pierre Phaneuf C++ 1 04-04-2004 02:28 AM



Advertisments