Re: Inefficiency of dynamic string/array initialization
* Bo Persson:
hovik wrote:
:: To the best of my knowledge there is no way for a C++ program to
:: optimize initialization of dynamic strings so that a string literal
:: isn't copied, e.g.:
::
:: std::string s = "abc";
::
:: At the same time languages that support dynamic structures (strings
:: and arrays) internally may easily solve the problem by allocating
:: proper data structures in the constant segment so that no data is
:: copied when instantiating new variables.
::
The question is: how much are you prepared to invest in all other
operations, to check for which variant is active in any given string?
As far as I know (having implemented a class like the OP requests) there
is generally no negative impact on other operations, just the opposite,
and there is no checking of which variant is stored. So the question is
really, if hypothetically we didn't have std::string and were now at the
point of choosing a standard string class for C++, /how much/ would we
be prepared to invest to have the full functionality of std::string?
And what is that, compared to an immutable string?
Where std::string shines, so to speak, is seemingly only in the ability
to modify the string value's characters.
And where per-character modification is necessary, it's usually a
sequential iteration over characters, and can then be performed in
amortized constant time per character using append operations on an
immutable string. Alternatively, it can be performed in constant time
per character on a mutable string buffer which then can be transferred
to an immutable string in constant time. So as I see it there's really
no advantage whatsoever to the mutability of std::string, only
disadvantages, including a performance cost.
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:
; 753 : std::string s = "abcd";
00815 a1 00 00 00 00 mov eax, DWORD PTR
??_C@_04EHKALCEN@abcd?$AA@
0081a 89 84 24 dc 02
00 00 mov DWORD PTR _s$[esp+1792], eax
00821 88 9c 24 f7 02
00 00 mov BYTE PTR _s$[esp+1819], bl
00828 89 ac 24 f8 02
00 00 mov DWORD PTR _s$[esp+1820], ebp
0082f 88 9c 24 e0 02
00 00 mov BYTE PTR _s$[esp+1796], bl
; 754 :
; 755 : std::string s2 = s;
00836 89 84 24 5c 03
00 00 mov DWORD PTR _s2$[esp+1792], eax
0083d 88 9c 24 77 03
00 00 mov BYTE PTR _s2$[esp+1819], bl
00844 89 ac 24 78 03
00 00 mov DWORD PTR _s2$[esp+1820], ebp
0084b 88 9c 24 60 03
00 00 mov BYTE PTR _s2$[esp+1796], bl
That's four machine instructions a piece. We are talking nano seconds!
This is an amazing special case optimization, and it would be
interesting to know the compiler, and not the least, the C++ source code
(string constructor) that got optimized down to four assignments.
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, 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. 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.
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. :-)
Cheers,
- Alf
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]