Massive slowdown in search_n in parallel mode

Johannes Singler singler@ira.uka.de
Fri Nov 23 18:34:00 GMT 2007


Hi Chris,

> 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?

Well, it is basically calling search() with a pseudo-sequence of n equal
elements. The Knuth-Morris-Pratt algorithm built into search() should be
able to analyze this and to advance in large steps, about n in this
case, leading to O(l/n) running time again. But maybe there is a bug in
there, or the overhead dominates. I will look into that. What are your
exact lengths, types, and comparators?
An explicit parallelization would improve the performance, of course...
but this routine was not in our major focus so far, so we tried to keep
the code size small. If you are really interested, we can add an
explicit parallelization.

-- Johannes



More information about the Libstdc++ mailing list