string::find complexity.

[Dhruv Matani]

Hi,
	Well, I have implemented a rough version of the KMP algorithm and it's
given in the attached file. You can run it to compare timings between:
1. The traditional n^2 algo. (re-implemented).
2. string::find -> very slow, because it uses traits::compare.
3. KMP -> probably final version.

(3) Is not copy-book KMP, but a modified version, which I have conjured
up to make a speed up.

A few hours ago, when I tested on g++3.4, (3) was giving better timings,
but that tree has become corrupted because of my allocator testing, and
on 3.2, (1) is giving the best timings.

I would like to know the performance on different machines. I've tested
on an AMD Duron-1GHz -> Uni-processor, DDR RAM. x86-Linux.

Currently, string::find is implemented using traits::compare, which does
a 3-way compare, using 2-comparisonsas does memcmp, so that is a
wasteful operation. find could be modified to be like (1) to have a
speedup.

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

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: str_find.cpp
Type: text/x-c++
Size: 2597 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040610/a9b47338/attachment.bin>