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

Subject: Re: [boost] [accumulator][minmax_element] Perfomance comparsion different min max algorithm
From: Hansi (hansipet_at_[hidden])
Date: 2009-02-17 02:17:59

<snip>
 > 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).
> 

Your results are really different from my one, but normally I would say 
more expected. I can't find any wrong settings at the moment in my project.

May be it helps when I post the command line parameters:
Compiler settings:
/GL /D "WIN32" /D "_CONSOLE" /D "_SECURE_SCL=0" /D "NDEBUG=1" /D 
"_UNICODE" /D "UNICODE" /FD /EHsc /MD /Yu"stdafx.h" 
/Fp"Release\Statistic.pch" /Fo"Release\\" /Fd"Release\vc90.pdb" /W3 
/nologo /c /Zi /TP /errorReport:prompt

Linker settings
/OUT:"D:\projects\sandbox\BoostTests\Release\Statistic.exe" 
/INCREMENTAL:NO /NOLOGO /MANIFEST 
/MANIFESTFILE:"Release\Statistic.exe.intermediate.manifest" 
/MANIFESTUAC:"level='asInvoker' uiAccess='false'" /DEBUG 
/PDB:"d:\projects\sandbox\BoostTests\release\Statistic.pdb" 
/SUBSYSTEM:CONSOLE /OPT:REF /OPT:ICF /LTCG /DYNAMICBASE:NO /MACHINE:X86 
/ERRORREPORT:PROMPT kernel32.lib user32.lib gdi32.lib winspool.lib 
comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib 
odbc32.lib odbccp32.lib

BTW if I compile your program with debug I get an compile error :

error C2664: 'std::_Vector_iterator<_Ty,_Alloc>::_Vector_iterator(const 
std::_Vector_iterator<_Ty,_Alloc> &)': can't convert from 'int *const ' 
to 'const std::_Vector_iterator<_Ty,_Alloc> &'

in the line

std::pair< std::vector<int>::iterator, std::vector<int>::iterator > 
result = boost::minmax_element(data.begin(), data.end());

Any ideas?

Thanks
Hansjörg