Massive slowdown in search_n in parallel mode

Chris Jefferson
Fri Nov 23 17:37:00 GMT 2007

I decided to try compiling my code in 'parallel mode', hoping to make
use of my 2 core machine. I was somewhat suprised to see my code slow
down about 50 times or so.

I'm not an expert on parallel things, so I could be abusing something
stupidly, but it seems to me that search_n is just being delegated to
a non-optimised search, which has two problems.

1) It has abandoned the recent optimisation to make the code about
O(l/n) where l is the length of the string to be searched and n is the
number of occurrences when the there are few occurrences of the string
being searched for.

2) Even a trivial search_n is O(l), whereas a trivial search (as there
seems to be in search.h) is O(n*l).

Is this right, or am I badly misunderstanding what is going on?

More information about the Libstdc++ mailing list