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-.
Paolo.
More information about the Libstdc++
mailing list