This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: on the speed of std::string::find


On 9/3/06, Paolo Carlini <pcarlini@suse.de> wrote:
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-.

After reading the man page, especially its reference to needles and haystacks, I was expecting it to use an algorithm similar to Boyer-Moore. Is there's any specifc reasons for it not doing this?

Rakshasa


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]