Mysterious performance difference between close to identical programs

Hello!

I have a mysterious performance behaviour that has bothered me for some time. The situation is that I have two classes of programs, class A and class B. The only difference between A and B is that in A one function takes an extra parameter. I would expect programs in class A and B to be (close to) equally fast, and they are for the most part. But sometimes a B program is 20% faster than an A program, and sometimes it’s the other way around.

The following plot shows the peculiar behaviour for 100 randomised programs from classes A and B. The y-axis is the relative execution time (time(A) / time(B)). That is, a value 1.0 means equally fast, and a value 1.2 means that A was 20% slower than B. The x-axis is the sum of execution times for class A and B (time(A) + time(B)). What bothers me particularly is the weird distribution with the β€œjumps” to ~1.2 and ~0.82.

Some details about the programs and how they are generated:
Each program is a series of calls to a function map , which in class A looks like this:

let map n f s =
  if n == 1 then List.map f s
  else failwith "impossible"

And in class B looks like this:

let map f s =
  let n = 1 in
  if n == 1 then List.map f s
  else failwith "impossible"

That is, class A has an extra parameter n while B defines n locally in map.
The programs consist of a number of calls to map with randomised lists and randomised workloads (fibonacci function). In the experiment, I used 1-100 number of calls, with lists of lengths 1-100, and workloads of size 30-50.

Some details about the experiment:

  • I repeated them on on two different machines and got the same behaviour, although it differed slightly what programs gave the β€œjump” on the different machines.
  • I tried both with opam switches default and 4.12.0+domains, and 4.12.0+domains gives a larger difference than default.
  • Each program was run 10 times with 3 warmup runs. When I reversed the order of the programs (first running B before A instead of A before B) I got the same result.

My questions
I would be happy for ideas on the reason for the behaviour, or on how I can investigate it further. Some possible explanations are:

  • Some OCaml compiler optimization that kick in. But if so, how come one class is sometimes faster and sometimes slower?
  • Some machine-dependent explanation, such as cache alignment effects. If so, is it possible to explain why such a tiny code difference can affect e.g. caches?

Also, I’m curious about the reason for the difference between default and 4.12.0+domains.

Just to give an idea of what the programs look like, I attach a pair of programs that relative runtime 1.2 for me. For example:

$ ocamlbuild map-A-3.native map-B-3.native
$ hyperfine ./map-A-3.native ./map-B-3.native --warmup 1
Benchmark #1: ./map-A-3.native
  Time (mean Β± Οƒ):      2.447 s Β±  0.010 s    [User: 2.426 s, System: 0.008 s]
  Range (min … max):    2.428 s …  2.456 s    10 runs
 
Benchmark #2: ./map-B-3.native
  Time (mean Β± Οƒ):      2.980 s Β±  0.009 s    [User: 2.956 s, System: 0.010 s]
  Range (min … max):    2.964 s …  2.997 s    10 runs
 
Summary
  './map-A-3.native' ran
    1.22 Β± 0.01 times faster than './map-B-3.native'

Finally, if anyone is interested, here is a git repo with everything needed to repeat the experiments I did.

PS: The programs I used here are a reconstruction of a real application.

map-A-3.ml let map n f s = if n == 1 then List.map f s else failwith "impossible"

let rand_range min max =
min + Random.int (max - min)

let rec fibonacci n =
if n < 3 then 1
else (fibonacci (n-1)) + (fibonacci (n-2))

let _ = Random.init(3);

let _ = map 1 fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 79 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 26 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 57 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 87 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 70 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 90 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 84 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 18 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 87 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 11 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 70 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 43 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 80 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 39 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 34 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 70 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 79 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 80 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 70 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 60 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 29 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 39 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 29 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 76 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 59 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 11 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 95 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 18 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 30 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 15 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 13 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 44 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 70 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 59 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 64 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 60 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 83 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 66 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 27 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 56 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 22 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 14 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 27 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 73 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 37 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 43 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 96 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 65 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 90 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 63 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 74 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 59 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 83 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 54 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 78 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 84 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 62 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 84 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 39 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 53 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 97 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 13 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 45 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 87 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 95 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 99 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 30 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 99 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 51 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 79 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 83 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 82 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 23 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 93 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 37 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 83 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 44 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 46 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 25 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 18 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 71 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 71 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 21 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 54 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 18 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 62 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 29 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 12 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 47 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 64 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 63 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 25 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 15 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 87 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 88 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 15 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 58 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 52 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 80 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 45 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 74 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 40 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 14 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 49 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 10 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 19 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 23 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 78 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 14 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 35 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 62 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 47 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 88 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 43 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 29 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 98 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 15 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 53 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 50 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 56 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 27 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 58 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 58 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 68 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 76 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 59 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 92 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 97 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 81 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 23 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 89 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 74 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 44 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 65 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 40 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 65 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 43 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 76 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 80 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 53 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 11 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 63 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 84 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 50 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 12 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 58 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 88 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 90 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 27 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 17 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 90 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 52 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 69 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 55 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 96 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 55 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 87 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 100 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 45 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 72 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 12 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 17 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 96 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 12 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 57 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 42 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 90 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 68 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 50 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 32 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 56 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 33 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 50 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 57 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 43 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 58 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 23 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 13 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 82 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 97 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 26 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 49 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 74 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 38 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 93 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 44 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 40 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 51 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 33 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 96 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 65 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 93 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 99 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 22 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 23 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 51 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 52 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 96 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 38 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 66 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 31 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 20 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 53 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 93 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 37 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 82 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 67 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 44 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 38 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 25 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 14 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 77 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 34 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 50 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 83 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 33 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 45 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 53 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 92 (fun _ β†’ rand_range 10 30)) in
let _ = map 1 fibonacci (List.init 20 (fun _ β†’ rand_range 10 30)) in

()

map-B-3.ml let map f s = let n = 1 in if n == 1 then List.map f s else failwith "impossible"

let rand_range min max =
min + Random.int (max - min)

let rec fibonacci n =
if n < 3 then 1
else (fibonacci (n-1)) + (fibonacci (n-2))

let _ = Random.init(3);

let _ = map fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 79 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 26 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 57 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 87 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 70 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 90 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 84 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 18 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 87 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 11 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 70 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 43 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 80 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 39 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 34 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 70 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 79 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 80 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 70 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 60 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 29 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 39 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 29 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 76 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 59 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 11 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 95 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 18 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 30 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 15 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 13 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 44 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 70 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 59 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 64 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 60 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 83 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 66 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 27 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 56 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 22 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 14 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 27 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 73 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 37 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 43 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 96 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 65 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 90 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 63 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 74 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 59 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 83 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 54 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 78 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 84 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 62 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 84 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 39 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 53 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 97 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 13 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 45 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 87 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 95 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 99 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 30 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 99 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 51 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 79 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 83 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 82 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 23 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 93 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 37 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 83 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 44 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 46 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 25 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 18 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 71 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 71 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 21 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 54 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 18 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 62 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 29 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 12 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 47 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 64 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 63 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 25 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 15 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 87 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 88 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 15 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 58 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 52 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 80 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 45 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 74 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 40 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 14 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 49 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 10 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 19 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 23 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 78 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 14 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 35 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 62 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 47 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 88 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 43 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 29 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 98 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 15 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 53 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 50 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 56 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 27 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 58 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 58 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 68 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 76 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 59 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 92 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 97 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 81 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 23 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 89 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 74 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 44 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 65 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 40 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 65 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 43 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 76 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 80 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 53 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 11 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 63 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 84 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 50 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 12 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 58 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 88 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 90 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 27 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 17 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 91 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 90 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 52 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 69 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 55 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 96 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 55 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 87 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 100 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 45 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 72 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 12 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 17 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 96 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 12 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 57 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 42 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 90 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 68 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 85 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 50 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 32 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 56 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 33 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 50 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 57 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 43 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 48 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 58 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 23 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 13 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 82 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 97 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 26 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 49 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 74 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 38 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 93 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 44 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 40 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 51 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 33 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 96 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 65 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 93 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 99 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 22 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 23 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 86 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 51 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 52 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 96 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 38 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 66 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 31 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 20 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 53 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 93 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 37 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 82 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 67 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 44 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 38 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 25 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 14 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 77 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 34 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 50 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 83 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 33 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 45 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 53 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 92 (fun _ β†’ rand_range 10 30)) in
let _ = map fibonacci (List.init 20 (fun _ β†’ rand_range 10 30)) in

()

1 Like

On my machine, ocaml (4.13.1, no -flambda) is able to reduce n == 1 to true in version B and eliminate the conditional altogether.

$ cat test.ml
let mapA n f s = if n == 1 then List.map f s else failwith "impossible"
let mapB f s = let n = 1 in if n == 1 then List.map f s else failwith "impossible"

$ ocamlopt -dcmm -c test.ml
[...]
(function{test.ml:1,9-71} camlTest__mapA_81 (n/83: val f/84: val s/85: val)
 (if (== n/83 3)
   (app{test.ml:1,32-44} "camlStdlib__List__map_236" f/84 s/85 val)
   (app{test.ml:1,50-71} "camlStdlib__failwith_6" "camlTest__1" val)))

(function{test.ml:2,9-82} camlTest__mapB_150 (f/152: val s/153: val)
 (app{test.ml:2,43-55} "camlStdlib__List__map_236" f/152 s/153 val))
[...]

This being said, I would expect that there is absolutely no noticeable difference between the two programs, given that the cost should be dominated by fibonacci computations.

I cannot reproduce the results you mention on my machine. On my machine, according to hyperfine, version B is slightly (0-5%) faster than version A.

  • Some machine-dependent explanation, such as cache alignment effects. If so, is it possible to explain why such a tiny code difference can affect e.g. caches?

My understanding is that it suffices for something to cross the boundary between two cache lines for things to behave differently. This could be the code cache at play here, or cache effects on the call stack (the call stack will be shifted by one in A (or not, see below), and fibonacci is uses the call stack heavily), or maybe even possibly some return-address prediction machinery.

For scary stories about benchmarking, see Producing Wrong Data Without Doing Anything Obviously Wrong! by Mytkowicz, Diwan, Hauswirth and Sweeney, 2013.

Edit: I believe that my remark that the call stack will be shifted by one in A is incorrect: in both cases the call to List.map is a tail call, so its position in the stack will not depend on the stack frame size of the caller. The two versions should have exactly the same call-stack behavior once List.map is called. The only difference I can think of is the placement of fibonacci in the code cache.

2 Likes

First, let me point out that the OCaml compiler optimizes

let map f s = let n = 1 in if n == 1 then List.map f s else failwith "impossible"

into

let map = List.map

and then inlines the call.

That does not explain the speed difference though. (On the contrary, one might then expect the opposite result as a consequence.)

The issue just comes from the behavior of the micro-architecture of your processor. There is not much you can do about it. If you are on Linux, I suggest you experiment with the perf tool.

For example, on your two programs,

perf stat -e uops_issued.stall_cycles ./foo

gives 1 610 377 504 for the first program, and 2 120 863 180 for the second. In other words, it is just the processor being confused by the assembly code and being unable to produce micro-operations as fast as they are consumed by the execution units.

3 Likes

Look at the implementation of Random.int: the +domains variant has more code in it, it also does a β€˜Domain.DLS.get random_key’. And your benchmark calls Random.int a lot.

For me (with ocaml 4.12.0) I get the same assembly code for map-1-1.ml and map-2-1.ml’s hot code (apart from function names obviously), and the differences in execution time between the 2 are tiny.
Try to β€˜perf record’ the 2 runs of map-1-1.native vs map-2-1.native, and perf annotate the result, then compare it with diff --side-by-side.

There are some good tips here on how to make your machine more deterministic for benchmarking purposes: Benchmarking tips β€” LLVM 13 documentation.
Default settings like turbo have caused me a lot of confusion in the past (the heuristics on when it kicks in and for how long it stays on is CPU/firmware dependent, and sometimes the effect of a previous benchmark that caused turbo to kick in were reflected on the benchmark immediately following it, unless there was a long pause between running the 2 benchmark, when I got different results, etc. it is best to disable turbo for benchmarking).

When in doubt try to compare the runs of exactly the same executable against itself: can you get hyperfine to say they’re β€œthe same”. If not something on the system might interfere with the results.

3 Likes

You can try using this random generator instead of Random.int so that you’re not affected by changes to stdlib if you want to benchmark different compiler versions:

let rng = Bigarray.Array1.create Bigarray.int64 Bigarray.c_layout 1

let pcg () =
  let oldstate = Bigarray.Array1.unsafe_get rng 0 in
  Bigarray.Array1.unsafe_set rng 0
    Int64.(add 1L @@ mul oldstate 6364136223846793005L) ;
  let xorshifted =
    Int64.(
      shift_right_logical (logxor (shift_right_logical oldstate 18) oldstate) 27
      |> to_int)
  in
  let rot = Int64.(shift_right_logical oldstate 59 |> to_int) in
  (xorshifted lsr rot) lor (xorshifted lsl (-rot land 31))

(The idea to use a Bigarray is from grenier’s pcg.ml, but the code above also avoids allocation when compiled with OCaml 4.12. The PCG generator is based on the minimal implementation at Download the PCG Library | PCG, A Better Random Number Generator with a 0 seed and inc).
If you’re just using the output for benchmarking you probably don’t necessarily need seeding.

Comparing it with Random.int shows it is faster:

let rng = Bigarray.Array1.create Bigarray.int64 Bigarray.c_layout 1

let pcg () =
  let oldstate = Bigarray.Array1.unsafe_get rng 0 in
  Bigarray.Array1.unsafe_set rng 0
    Int64.(add 1L @@ mul oldstate 6364136223846793005L) ;
  let xorshifted =
    Int64.(
      shift_right_logical (logxor (shift_right_logical oldstate 18) oldstate) 27
      |> to_int)
  in
  let rot = Int64.(shift_right_logical oldstate 59 |> to_int) in
  (xorshifted lsr rot) lor (xorshifted lsl (-rot land 31))

let random_int () = Random.int (1 lsl 29)

let use_pcg = ref false

let spec =
  [ ( "-pcg"
    , Arg.Bool (fun use -> use_pcg := use)
    , "Use PCG generator when true, or Random.int when false" ) ]

let () =
  Arg.parse spec (fun _ -> exit 1) "pcgtest -pcg <true|false>" ;
  let f = if !use_pcg then pcg else random_int in
  let x = ref 0 in
  for _ = 1 to 5000_000 do
    x := !x + Sys.opaque_identity (f ())
  done ;
  ignore (Sys.opaque_identity x)
$ ocamlopt pcgtest.ml -o pcgtest
$ hyperfine './pcgtest -pcg true' './pcgtest -pcg false'
Benchmark #1: ./pcgtest -pcg true
  Time (mean Β± Οƒ):      15.1 ms Β±   0.4 ms    [User: 14.6 ms, System: 0.6 ms]
  Range (min … max):    14.6 ms …  17.5 ms    195 runs
 
Benchmark #2: ./pcgtest -pcg false
  Time (mean Β± Οƒ):      36.6 ms Β±   0.4 ms    [User: 36.0 ms, System: 0.5 ms]
  Range (min … max):    35.9 ms …  37.9 ms    81 runs
 
Summary
  './pcgtest -pcg true' ran
    2.42 Β± 0.08 times faster than './pcgtest -pcg false'

Another way to avoid the extra overhead from +domains is to use Random.State (and explicitly preserving the state yourself) instead of using Random.int (which needs to retrieve the domain local state), and since you’re not using multicore here, a global Random.State should restore pre-multicore behaviour:

let state = Random.State.make_self_init ()
let random_int n = Random.State.int state n

(and then use random_int wherever you’d use Random.int)

5 Likes

My guess (I haven’t benchmarked) is that most of the time in your programs is spent in the fibonacci function, so almost all the difference is linked to that.
The usual culprit (as mentioned above) is code alignment differences, which for small functions can introduce noticeable performance differences. I’d suggest to move the fibonacci function to the top of the file, and see if you still observe a difference (the compiler usually tries to output functions in the order of their definition).
Regarding Multicore, I suspect that the difference is that the fibonacci function contains an extra poll pseudo-instruction on this branch, that is not present on 4.12. This could end up making the function big enough that alignment issues become less noticeable. The feature was merged upstream for 4.13, so you might want to check which behaviour you get on this version (if I’m correct, you should get similar results to 4.12+domains).

1 Like

Thank you for the responses! As several pointed out, code alignment seems to play a big role. I tried moving fibonacci to the top of the file, as @vlaviron suggested, and this is the result on the same randomised 100 programs as before (on 4.12.0+domains):

As you can see, the difference is now around +/-8% instead of around +/-20% as before. This result is very similar to what I get on 4.12.0 and 4.13.1 (regardless of the placement of fibonacci, 4.12.0 and 4.13.1 give around +/-8% difference at most).

Furthermore, after inspecting the generated assembly, I believe the reason why 4.12.0+domains gave a larger difference (when fibonacci was at the bottom) is that rand_range includes more code (as also pointed out by @edwin). This means that the code alignment made a larger difference on 4.12.0+domains.

Next I will try to find an explanation for the remaining +/-8% of difference, as this is still a bit more than I would expect.

Again I would recommend having a look at Producing Wrong Data Without Doing Anything Obviously Wrong! by Mytkowicz, Diwan, Hauswirth and Sweeney, 2013.

They observed measurement bias due to linking order or environment variables (!), both well above 8% on some benchmarks, and there are of course other sources of bias. An 8% difference due to code placement does not seem so surprising in this light. (And yes, it means that drawing conclusions from benchmarks is very difficult! One recommendation could be to avoid micro-benchmarks that can magnify these effects, and focus on more integrated macro-benchmarks.)

On the same subject, I can also recommend watching 2016 LLVM Developers’ Meeting: Z. Ansari "Causes of Performance Instability due to Code ..." - YouTube and "Performance Matters" by Emery Berger - YouTube