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
and4.12.0+domains
, and4.12.0+domains
gives a larger difference thandefault
. - 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
()