Re: [boost] [accumulator][minmax_element] Perfomance comparsion different min max algorithm

Subject: Re: [boost] [accumulator][minmax_element] Perfomance comparsion different min max algorithm
From: John Bytheway (jbytheway+boost_at_[hidden])
Date: 2009-02-16 19:31:11

Hansi wrote:
> I have made today a few tests to compare the different possibilities to
> search min,max of a value. I had some really strange results which I
> don't have expected. As environment I use VS2008 Express edition,not
> managed, defines are SECURE_SCL=0 and NDEBUG=1.
> 
> In the comparsion I got the following timings:
> 
> <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
> min_element,max_element:73
> minVal=0,maxVal=9999999
> min_max: accumulator:2338
> minVal=0,maxVal=9999999
> min_max: minmax_element:86
> minVal=0,maxVal=9999999
> min/max handcoded:135
> minVal=0,maxVal=9999999
> <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
> 
> For me the strange things are:
> - that std::min_element and std::max_element is faster as
> boost::minmax_element
> - the accumulator library seems in this example really slow

I made some changes to your code.  I switched from chrono to
boost::timer because that measures CPU time, rather than wall-clock time
(at least, I think that's what your chrono-based code was measuring; it
seemed more variable).  I made it test an array with random contents as
well as one with numbers in order.  I increased your array size by a
factor of 10 to get more stable numbers.  Variation attached.  With
that, on i686 Linux, gcc -O3 I get:

sorted array:
min_element,max_element:1.89
minVal=0,maxVal=99999999
min_max: accumulator:0.45
minVal=0,maxVal=99999999
min_max: minmax_element:0.48
minVal=0,maxVal=99999999
min/max handcoded:0.79
minVal=0,maxVal=99999999
random array:
min_element,max_element:1.8
minVal=7,maxVal=2147483611
min_max: accumulator:0.36
minVal=7,maxVal=2147483611
min_max: minmax_element:0.6
minVal=7,maxVal=2147483611
min/max handcoded:0.71
minVal=7,maxVal=2147483611

And with icc -O3:

sorted array:
min_element,max_element:0.74
minVal=0,maxVal=99999999
min_max: accumulator:0.51
minVal=0,maxVal=99999999
min_max: minmax_element:0.48
minVal=0,maxVal=99999999
min/max handcoded:0.51
minVal=0,maxVal=99999999
random array:
min_element,max_element:0.75
minVal=7,maxVal=2147483611
min_max: accumulator:0.51
minVal=7,maxVal=2147483611
min_max: minmax_element:0.68
minVal=7,maxVal=2147483611
min/max handcoded:0.51
minVal=7,maxVal=2147483611

I'm quite surprised by these numbers, in that:
- gcc sometimes beats icc
- gcc's accumulator looks significantly faster on random data than
sorted data (indeed, on random it's the fastest thing of all).

I'd guess that minmax_element is faster on sorted data because branch
prediction works better there.

Nevertheless, it's clearly very different from your results, in that we
have opposite fastest and slowest methods.  I suspect you're missing
some crucial optimization (probably the inlining of a function somewhere
in accumulator).

John Bytheway