Re: Patch: improving performance of basic_string modification functions

[Carlo Wood <carlo at alinoe dot com>]

On Thu, Aug 23, 2001 at 10:12:58PM -0700, Benjamin Kosnik wrote:
> 
> this is one way:
> 
> > I did a little analysis of 'basic' applications that are using strings heavily
> > with 3.0.1 (release) and found that only two functions of the API are important:
> [snip] 
> 
> this is another:
> 
> > Something like the stepanov abstraction penalty test would make sense, to
> > at least verify that we conform to the complexity requirements of the
> > standard; i.e. time adding one character to a string, then time adding a
> > lot of characters one at a time and make sure that we take no more than
> > linear time.
> 
> Of the two, the second seems easiest to do, off hand.

The first said which functions are important to test, the second says HOW
to test them.

You could use the second method to test the complexity requirements of
string::append().

However I think we also need a 'benchmark' test;  a patch that changes
the complexity from O(1) to O(1) won't fail, while it is possible that
all applications got twice as slow nevertheless.
The only way to integrate that in the testsuite is by demanding that
these tests run with a given _absolute_ speed - something that is
hard to achieve on all these different platforms.

Perhaps this test could be restricted to one platform (assuming the
speed is relatively platform independend) so that absolute values can
be added.  In order to get a PASS or FAILED, the benchmark needs to be
compared to this absolute value.  I have indeed no simple solution for
how to solve the problem of achieving that value.  One way would be
to look for an executable 'g++-3.0' and use that as a reference, then
the test itself only needs a relative value
(ie: benchmark_result * 0.8 <= 3.0_result  -->  PASS).
Once a patch succeeds and is added, this relative value then can be
decreased.

-- 
Carlo Wood <carlo@alinoe.com>