std::string and refcounting

Discussion in 'C++' started by joe martin, Apr 20, 2004.

  1. joe martin

    joe martin Guest

    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
     
    joe martin, Apr 20, 2004
    #1
    1. Advertising

  2. joe martin

    red floyd Guest

    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.
     
    red floyd, Apr 20, 2004
    #2
    1. Advertising

  3. 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.
    --
    <mailto:> <http://www.dietmar-kuehl.de/>
    <http://www.contendix.com> - Software Development & Consulting
     
    Dietmar Kuehl, Apr 21, 2004
    #3
  4. joe martin

    joe martin Guest

    On Wed, 21 Apr 2004 05:38:10 +0200, Dietmar Kuehl
    <> 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
     
    joe martin, Apr 22, 2004
    #4
  5. joe martin

    Siemel Naran Guest

    "joe martin" <> wrote in message
    > <> 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.
     
    Siemel Naran, Apr 22, 2004
    #5
  6. joe martin <> 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.
    --
    <mailto:> <http://www.dietmar-kuehl.de/>
    <http://www.contendix.com> - Software Development & Consulting
     
    Dietmar Kuehl, Apr 22, 2004
    #6
  7. > 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
     
    Peter van Merkerk, Apr 22, 2004
    #7
  8. joe martin <> wrote in message news:<>...
    > 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
     
    Michiel Salters, Apr 22, 2004
    #8
  9. 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?threadm=

    regards,
    alexander.
     
    Alexander Terekhov, Apr 22, 2004
    #9
  10. "Siemel Naran" <> wrote in message news:<k5Hhc.18351$>...
    > "joe martin" <> wrote in message
    > > <> 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.
    --
    <mailto:> <http://www.dietmar-kuehl.de/>
    <http://www.contendix.com> - Software Development & Consulting
     
    Dietmar Kuehl, Apr 22, 2004
    #10
  11. Alexander Terekhov <> wrote in message news:<>...
    > 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.


    I think we're talking about two things. You probably interpreted it
    as "too hard to implement correctly" while I meant "too hard to
    implement correctly and still faster than comparable non-refcounted".

    > 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.


    True. COW obviously shines in the absence of W. Of course, the common
    CHAR_T& STRING::eek:perator[](pos_type) might very well be a write, which
    causes branches and possibly copies in COW-types.

    > #43-#45 is rather interesting reading but don't believe
    > everything (especially conclusions) that it says.


    Indeed. The best string class can only be found by profiling.
    Until that time, stick with std::string. It is universally available,
    and in general recent versions are pretty good for common cases.
    It also has the added advantage of being able to use
    platform-specific tricks in the implementation without sacrificing
    portability, something your code can never achieve ;)

    Regards,
    Michiel Salters
     
    Michiel Salters, Apr 22, 2004
    #11
  12. Michiel Salters wrote:
    [...]
    > True. COW obviously shines in the absence of W. Of course, the common
    > CHAR_T& STRING::eek:perator[](pos_type) might very well be a write, which
    > causes branches and possibly copies in COW-types.


    Use "const CHAR_T& STRING::eek:perator[](pos_type) const" for reads.

    regards,
    alexander.
     
    Alexander Terekhov, Apr 22, 2004
    #12
  13. > > #43-#45 is rather interesting reading but don't believe
    > > everything (especially conclusions) that it says.

    >
    > Indeed. The best string class can only be found by profiling.


    For a given case and a given platform. It is not realistic to expect for a
    string implementation to produce optimal results in every case, a trade off
    has to be made somewhere.

    --
    Peter van Merkerk
    peter.van.merkerk(at)dse.nl
     
    Peter van Merkerk, Apr 22, 2004
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Pierre Phaneuf
    Replies:
    1
    Views:
    367
    Leor Zolman
    Apr 4, 2004
  2. Peter Jansson
    Replies:
    5
    Views:
    6,441
    Ivan Vecerina
    Mar 17, 2005
  3. Simon Dahlbacka

    refcounting

    Simon Dahlbacka, Apr 13, 2004, in forum: Python
    Replies:
    2
    Views:
    327
    Simon Dahlbacka
    Apr 14, 2004
  4. refcounting errors???

    , Nov 2, 2006, in forum: Python
    Replies:
    2
    Views:
    291
  5. Replies:
    4
    Views:
    417
    Neil Cerutti
    Nov 15, 2005
Loading...

Share This Page