Re: basic_string patch

[Paolo Carlini <pcarlini at unitus dot it>]

"Martin v. Loewis" wrote:

> > eventually I have re-diffed the patch vs today's mainline. I'm still
> > convinced that the original one, that on libstdc++, is perfectly
> > correct, it's just that sometimes I use tabs instead of plain spaces
> > and viceversa and...
>
> The main problem is that the patch has seen HTML markup in the
> archives. Undoing this is not trivial, especially as line breaks were
> inserted in the wrong spots.

I see.

> > Anyway, please let us know your opinion. As you may see from the
> > benchmarks I have posted the effect of the exponential allocation
> > (vs the improvements already in mainline) should be particularly
> > noticeable when out-of-cache and/or for long concateaned strings.
>
> The improvements in the mainline are indeed significant. Your patch
> adds a slight speed-up on top of the mainline.

Well, it depends on the testcase! When a truly large amount of memory is
necessary, the improvement is not *slight* at all, on a general
*theoretical* basis, not because we have implemented the exponential
growth particularly well or what else!
Try you original testcase, but with concatenations ten chars long!

> It still doesn't
> achieve the 2.95 performance; for my test case, gcc 3.1 takes twice as
> much time as 2.95 (on Pentium III).

Well, may be. However we should carefully distinguish two different
problems: the overall O() complexity of the algorithm and the actual
constants. *Only* adding the exponential allocation required by the
standard O(n) complexity is achieved. Compare (on my PII)
http://gcc.gnu.org/ml/libstdc++/2001-07/msg00030.html) :

mainline
-------
Execution time of 10000 string::append(char) calls: 0 sec.
Execution time of 10000 string::append(const string&) calls: 0 sec.
Execution time of 100000 string::append(char) calls: 0.06 sec.
Execution time of 100000 string::append(const string&) calls: 0.1 sec.
Execution time of 1000000 string::append(char) calls: 1.48 sec.
Execution time of 1000000 string::append(const string&) calls: 1.91 sec.
Execution time of 10000000 string::append(char) calls: 116.83 sec.
Execution time of 10000000 string::append(const string&) calls: 120.71
sec.

mainline + expon
-------------
Execution time of 10000 string::append(char) calls: 0 sec.
Execution time of 10000 string::append(const string&) calls: 0 sec.
Execution time of 100000 string::append(char) calls: 0.06 sec.
Execution time of 100000 string::append(const string&) calls: 0.09 sec.
Execution time of 1000000 string::append(char) calls: 0.43 sec.
Execution time of 1000000 string::append(const string&) calls: 0.87 sec.
Execution time of 10000000 string::append(char) calls: 4.2 sec.
Execution time of 10000000 string::append(const string&) calls: 8.83 sec.

You can see that going from 1.000.000 to 10.000.000 only with the
additional expon alloc patch we have a *perfectly linear* trend (0.42 ->
4.2), (0.87 -> 8.83), whereas that is not true in the first case, where
the timings are not only higher (this is not my point here) but *grow
much faster* than linearly with the number of appended chars.

Coming to the constants, my feeling is that, yes, currently those are a
little bit higher for v3 vs v2, but that this is mostly noticeable for
const string append (vs char append).

Cheers,
Paolo.