Re: Inefficiency of dynamic string/array initialization

Alf P. Steinbach wrote:
:: * Bo Persson:
::
::: On one modern compiler, using the Small String Optimization (no
::: dynamic allocation for small enough strings), you get this best
::: case machine code for an initialization and a copy construction:
:::
::: snip
:::
::: Is it worth trying to improve on this?
::
:: Is it worth having guaranteed constant time string assignments in
:: the /general/ case (except for conversions, of course)?

Yes, it is.

::
:: Yes, I think so: consider e.g. sorting, or just the general impact
:: on application performance of small string copy operations
:: peppered all over the code by indiscriminate use of std::string.

However, actual "small strings" also benefit a lot from the small
string optimization. On an x64 system, VC++'s special casing of strcpy
will copy eight (8) characters at a time.

Sorting might be improved by move semantics, where you don't really
need to copy the string.

:: It's possible that Copy On Write a.k.a. COW is a solution for
:: std::string as long as the strings aren't used in ways triggering
:: copy (that includes ordinary [] on non-const). But as I
:: understand it COW isn't generally used for std::string
:: implementations, because of some associated costs.

There are at least two problems here:

- COW works best for passing very long strings by value, and then
never modify them. Who does that?

- with the std::string semantics we actually get COpW - copy on
potential write. Like you say, having to do un-sharing in non-const
operator[] is a real killer!

::
:: With constant time copying in the general case, supporting
:: constant time for initialization by literal is trivial.
::
:: E.g. my own immutable string class (under development, just a hobby
:: project, see <url: http://preview.tinyurl.com/yu8z5w>) provides
:: constant time initialization from literal, as a matter of course;
:: a special case of the general constant time copying.
::
:: However, I haven't tested that non-optimized immutable string
:: class, compared to std::string; I just like fiddling with code, so
:: I'm eagerly waiting for someone to compare its performance to
:: std::string. :-)
::

I am in no way arguing against having an immutable string class, but
rather against the OP's idea of adding yet another special case to
std::string. Or replacing it with something "more efficient". We are
already in the backwards compatibilty swamp - despite its shortcomings
std::string is in wide use. Some of its perceived inefficiencies can
also be taken care of, perhaps with a little help from the compiler
optimizer team focusing on the infrastructure for the library.

Bo Persson

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]