Re: [Patch] Use std::search in string::find

[Dhruv Matani <dhruvbird at gmx dot net>]

On Sun, 2004-06-13 at 14:00, Paolo Carlini wrote:
> Dhruv Matani wrote:
> 
> >Here is a version that takes a const char*, size_type, and size_type, it
> >can be adopted easily if you feel it's fine.
> >  
> >
> Don't we agree with Matt that the first step is definitely make use of 
> algorithms
> in string? Afterwards, in case, we can conceive improving -slowly- the 
> former...

Ok, I have done some hunting, and from the code for find_end(), it seems
that the function has 2 dispatch functions:

1. For forward iterators.
2. For Bi-directional iterators.

However, there is no dispatch function for random access iterators, and
my code relies on random-access iterators, and the operator[] being
defined for that iterator. So, I can see 2 options:

1. Create a new dispatch function for find_end.
2. Do not use find_end(), and just code the function directly for
std::basic_string<>.

However, I have noticed these things:

1. The dispatch on bi-directional iterators functions in a way that is
not exactly good for modern processor caches. What it does is that it
compares each element starting from the last one, instead of jumping to
the most probable one, and then applying std::search from then on.

2. (1) Means that a lot of redundant comparisons are preformed in case
of a search string (first2, last2] pair that is large in size.

3. The use of reverse_iterators further degrades performance because of
the abstraction penalty.


-- 
        -Dhruv Matani.
http://www.geocities.com/dhruvbird/

Proud to be a Vegetarian.
http://www.vegetarianstarterkit.com/
http://www.vegkids.com/vegkids/index.html