Re: Search algorithms in __gnu_cxx::

["Dhruv Matani" <dhruvbird at gmail dot com>]

On 11/14/06, Paolo Carlini <pcarlini@suse.de> wrote:
> Dhruv Matani wrote:
>
> > I've patched on gcc-4.2[gcc version 4.2.0 20061107 (prerelease)]
>
> ... no way to convince you that we always patch *mainline* first...

I mailed Benjamin explaining to him that I can't seem to be able to
get mainline from svn, and current 4.3 snapshot. He said that it's
fine if I am able to test against any 4.2 snapshot.


> > Please let me know if you have any other specific requirements in mind.
>
> ... also no way to convince you that we are in a 64-bits era: I can tell
> you immediately that many of your types are wrong, today ints are often
> 32-bits, you can't assign the difference of two iterators to an int, you
> need a difference_type; similarly you cannot assign a size_t to an int,
> because a size_t today is often 64-bits...

Sorry, my bad. Have made the necessary changes.

> While you are at it, please consistently uglify *everything*; don't use
> curly braces for single statement blocks; follow the conventions about
> names of iterator types (from the name must be *obvious* the iterator
> category); index excess *128* because the smallest signed (8-bit) char
> value is -128. There are many additional minor things, but we have time,

Taken care of all these issues.

> I'd like to see first performance numbers vs current string::find...

Here are the numbers. Attached is the file used.

+-------------------+---------+
| algo              | time    |
+-------------------+---------+
| Boyer Moore       | 9.475s  |
| std::search       | 12.283s |
| strstr            | 13.184s |
| std::string::find | 20.166s |
+-------------------+---------+

Regards,
-Dhruv.

ps. I seem to have forgotten how to run the libstdc++-v3 tests. All I
remember is to go to: x86_64-suse-linux/libstdc++-v3 and type 'make
check'. Is that it?
Also, how do I check the output? In particular, the performance test
cases and their numbers?



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

"Be sure brain is in gear before engaging mouth"
     -- Anonymous

Attachment: boyer_moore.cpp
Description: Text document