Re: For Loops and Lambda in "Lies, Damned Lies, and Microbenchmarks"
On Mon, 15 Oct 2007 03:53:09 -0600, Damien Kick wrote:
skaller wrote:
At "-O3", the std::accumulate is the fastest, std::for_each 2nd, and the
for loop is the slowest. I'm still a little surprised that for these
three different ways to write such a simple iteration, that the versions
which use lambda seem to be consistently out performing the "simple" for
loop.
I'm not quite so surprised. I need to explain that: this generated
C++ code for calculating Ackermann's function:
int FLX_REGPARM ack( int x, int y){
start_5719:;
ifnot(x == 0 ==1) goto _5714;
return y + 1 ;
_5714:;
ifnot(y == 0 ==1) goto _5715;
y = 1;
x = x - 1 ;
goto start_5719;
_5715:;
y = ack(x, y - 1 );
x = x - 1 ;
goto start_5719;
}
is TWICE as fast as this C code:
int Ack(int M, int N) {
if (M==0) return N +1;
else if(N==0) return Ack(M-1,1);
else return Ack(M-1, Ack(M,N-1));
}
Do you know why? I have no idea! Both compiled with gcc 4.1 with -O3
on amd64.
I also had C++ code generated by Felix for Shootout nbody where
small differences in array indexing in what appeared to be a
floating point performance test made my code FOUR times slower
than C. (It isn't now .. now it is faster!).
I will be looking at loops vs STL algorithms shortly, mainly with
the effect of using OpenMP with gcc 4.2, since libstdc++ has
a number of parallelised STL algorithms in it. I'm curious to
know how effective that is.
However I think there is a need to go back and examine the issues: from
my viewpoint the performance is secondary because the library and/or
compiler should be able to generate fast stuff from clean source.
Foreigner: How to I get to FooBarKhan from here? Local: Oh, I wouldn't
start from here.
Point taken, but see above: microbenchmarks are notoriously sensitive
to trivial details. It's particularly counter-intuitive to find a
template solution is faster than the plain loop it undoubtedly reduces
to anyhow.
I am still personally quite persuaded by Scott Meyers item on preferring
algorithms to hand written loops, for exmaple. However, They have read
it, too, but They are not convinced.
IMHO, it isn't really a matter of preferring one or the other,
but on making a choice based on tradeoffs.
For example if you have an applicative object ready prepared,
OR the calculation is complex and can be reused, the algorithm
appears a better choice, otherwise localisation issues suggest
the loop is a better choice.
something being "too complicated", the easiest way to convince Them that
what They perceive to be complication is worthwhile is to be able to
point out that it is faster.
I agree it certainly helps to point at a performance advantage .. but ..
Now, admittedly, the difference in run-time
performance between these three are small enough that I would easily
imagine that They will simply wave it away.
... the point is that the 'more complicated' way isn't necessarily
slower. Indeed you show here it can be faster.
Not to mention that
microbenchmarks generally tend to be sorta fubar from the word go.
Yes, indeed, but they serve a good purpose here, if only to
show more research and experiment is needed.
And again you should note it is not the STL algorithms that are
the problem. They actually provide 'stock standard' functional
programming stuff like maps (called copy in STL) and folds
(called accumulate in STL). Such combinatorial programming is
generally good, and often faster than hand written code --
the problem here is simply that C++ doesn't have the core language
capability to service the library.
I'm sure Boost::Lambda helps, but you'd never write a complex
algorithm that way. Compare with Felix
int k = 2;
int sum = accumulate
(fun (acc:int) (x:int) : int => acc + k* x)
0
lst
;
to really understand the difference. That 'fun' thing in the middle
GENERATES a C++ applicative object like:
struct X {
int k;
X(int k_) : k(k_) {}
int operator()const(int acc, int x) {
return acc + k * x;
}
};
for you and passes it to the accumulate. Templates cannot
compete with this kind of code generator, where the 'functional'
value is more or less arbitrary. In theory "Lambda" (with recursion
it doesn't have) could do this, but the notation is unreadable.
In effect Felix translates a sane notation, namely the main
language, into the right form (i.e. applicative object here).
FYI, in the 'old days' I was asked to write a book on STL.
After some months of work setting it up, I wanted to show
how to rewrite a triple loop using STL algorithms.
Pages of code and days later I quit the book .. AND C++.
There's no way a triple loop with a 1 line body should be
so complicated. STL algorithms just aren't useful enough in C++
to bother given the real power comes from higher order
functions which in C++ are very hard to construct.
The amount of work is VERY considerable: I can easily
prove that .. take a look at the ~200,000 lines of Ocaml
code in the Felix compiler, which tries to build minimal
and optimal applicative objects to ensure good performance
whilst preserving locality. In general this cannot be done
with C++ templates, no matter how complex you make them,
due to the lack of type recursion**. Felix originally did
generate templates but I soon gave them up in favour of
doing my own instantiation.
** Gabriel del Rois showed a way to solve this in general
using open recursion and a specialisation to fixate it.
However the code to generate this solution is much more
complicated even in a high level language like Ocaml,
than instantiating polymorphic entities directly.
For the same reason, hand written specialised C++ code such
as loop bodies have a significant advantage over templates
because templates simply don't have the right combinators
in a convenient form.
The effect is you'd probably use STL for sorting, since sorting
is a complex algorithm, but the simpler accumulate and copy
just aren't worth using from application top level code.
They're useful to use from inside other templates though.
--
John Skaller <skaller at users dot sf dot net>
Try Felix, the successor to C++ http://felix.sf.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]