Re: [Caml-list] ackermann microbenchmark strange results

[Xavier Leroy <Xavier.Leroy@inria.fr>]

On 24/04/13 12:35, ygrek wrote:

> Running `make bench` here consistently gives the following (ack1,
  ack3 - tuples, ack2, ack4 - curried) : [...]
> Moreover, the generated assembly code for the main loop is the same,
> afaics. The only difference is the initialization of structure
> fields and the initial call to ack. Please can anybody explain the
> performance difference?

As others said, probably code placement.  A good tool to explore these
issues under Linux is "perf", in particular "perf stats", which lets
you count various hardware events.  Running it on your 4 programs,
you'll see that the number of instructions executed is almost exactly
the same, but the branch mispredictions (for instance) vary
significantly, in a way correlated with the overall execution time.

(Note that this doesn't have anything to do with OCaml: you'd observe
crazy variations like these with any compiled language.)

> I understand that microbenchmarks are no way the basis to draw
> performance conclusions upon, but I cannot explain these results to
> myself in any meaninful way.

Nobody can except perhaps a few engineers at Intel or AMD who have the
whole microarchitecture of their processors imprinted in their heads.
(And then they will not tell you.)  See, modern microarchitectures
contain so many clever heuristics that performance is generally very
good but essentially unpredictable...

rixed@happyleptic.org adds:

> Remember me of a paper I read some years ago that was measuring the
> effect of the various optimisation levels of gcc against the effect
> of addresses choices (randomised using environment strings of
> various lengths!), and which conclusion was that the effect of -O3
> compared to -O2 was less than the effect of "choosing" a good
> environment string :-) Couldn't find it again using Google ; maybe
> someone remember this paper?

It's probably "Producing Wrong Data Without Doing Anything Obviously
Wrong!" by Diwan et al, ASPLOS 2009,
http://www-plan.cs.colorado.edu/diwan/asplos09.pdf
This paper made quite a splash in the compiler community...

- Xavier Leroy