Re: SSO

From:

Juha Nieminen <nospam@thanks.invalid>

Newsgroups:

comp.lang.c++

Date:

Wed, 29 Jul 2009 09:03:56 GMT

Message-ID:

<0gUbm.30$TB5.25@read4.inet.fi>

tni wrote:

What advantages does a string class with SSO have over one which
always allocates the string dynamically and uses CoW?

Copying is much faster for small strings (at least on some important
platforms like x86).

  I don't see how that would be the case. With a regular CoW string a
copy entails assigning one pointer and updating one counter at the end
of that pointer. Copying a string which uses SSO entails a check whether
the string is small or dynamically allocated, and then (assuming it is
small) a copy of a member array (which is probably several times larger
than a pointer) and the size member variable.

  I could even believe that with optimal cache behavior and such you
could even achieve similar speeds, but much faster? I don't see that
happening.

  (And of course if the string was not small, but dynamically allocated,
the copying will be basically identical except that there will be the
additional check before copying.)

For COW, you generally need some form of reference counting with atomic
counters.

The STL, at least the implementation in gcc, has never bothered with
atomicity...

That's going to cost a few dozen clock cycles for a counter
access on x86 and causes the bus to be locked (which is a very bad thing
if you have lots of CPUs/cores). So, in a highly parallel environment,
you probably don't want COW.

OTOH always deep-copying can be detrimental for speed in many
situations, such as when sorting an array of large strings. I'd bet that
even using locking would be faster.

For some numbers (populating a vector with 8 char long strings via
push_back(), running on a Core i7 on Windows):

Small string optimization (as I posted, 8-char buffer): 780ms
Small string optimization (as I posted, 32-char buffer): 1550ms
Dynamic allocation: 15'000ms
Thread-safe COW String (Qt QByteArray): 3400ms
std::basic_string (Dinkumware, uses small string optimization): 3900ms

Naturally allocation will be significantly slower than simply
assigning to a member array. But only using 8 char long strings for such
a test feels a bit artificial.