Massive slowdown in search_n in parallel mode
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++