on the speed of std::string::find

Paolo Carlini pcarlini@suse.de
Sun Sep 3 18:21:00 GMT 2006

Hi again,

>Attached is a small test that I hacked together. Its not very accurate
>and clean etc. but it should show that memmem is ~1.5 times faster in
>this case.
Thanks. In the meanwhile I checked a few things, I cannot do much more 
right now, maybe you can before I return to this issue (in a few days). 
An interesting one is that apparently glibc does *not* provide any 
special hand written assembly implementation of memmem: as a matter of 
fact, the generic, pure C, implementation, is very simple, similar to 
what we used to have in libstdc++: it uses memcmp in a loop, only adds 
to it the small optimization of comparing the first pair of characters 
before calling it. So, was it a mistake changing to std::search? Or is 
the underlying memcmp now better / better optimized? Or we should only 
add the first char comparison? Or it all depends on the data and the 
more sophisticated algorithm in std::search is more robust wrt many 
different kinds of data (string lenghts, partial matches, etc.)? In case 
you have got some more spare time, you may want to have a look to our 
performance test for string::find, which you will find in 
testsuite/performance/21_strings/string_find.cc, and check what's 
happening now, with the current compiler, when you run on it: 1- The old 
string::find; 2- The current string::find; 3- The version forwarding to 
memmem; + double check that 1- added of the first char optimization 
becomes equivalent to 3-.


More information about the Libstdc++ mailing list