1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
module Bench = Core_bench.Bench
module Command = Core.Command
let run tests =
let tests =
List.map (fun (name, test) -> Bench.Test.create ~name test) tests
in
Command.run (Bench.make_command tests)
type expr =
| EConst of (int[@opaque])
| EAdd of expr * expr
| EList of expr list
[@@deriving visitors { variety = "iter"; concrete = true },
visitors { variety = "map"; concrete = true },
visitors { variety = "reduce"; ancestors = ["VisitorsRuntime.addition_monoid"]; concrete = true }]
let iter : expr -> unit =
new iter # visit_expr ()
let rec native_iter env e =
match e with
| EConst _ ->
()
| EAdd (e1, e2) ->
native_iter env e1;
native_iter env e2
| EList es ->
List.iter (native_iter env) es
class size = object
inherit [_] reduce as super
method! visit_expr () e =
1 + super # visit_expr () e
end
let size : expr -> int =
new size # visit_expr ()
let rec native_size env e =
match e with
| EConst _ ->
1
| EAdd (e1, e2) ->
native_size env e1 +
native_size env e2
| EList es ->
List.fold_left (fun accu e -> accu + native_size env e) 0 es
let rec native_size_noenv e =
match e with
| EConst _ ->
1
| EAdd (e1, e2) ->
native_size_noenv e1 +
native_size_noenv e2
| EList es ->
List.fold_left (fun accu e -> accu + native_size_noenv e) 0 es
let rec native_size_noenv_accu accu e =
match e with
| EConst _ ->
accu + 1
| EAdd (e1, e2) ->
let accu = native_size_noenv_accu accu e1 in
native_size_noenv_accu accu e2
| EList es ->
List.fold_left native_size_noenv_accu accu es
let split n =
assert (n >= 0);
let n1 = Random.int (n + 1) in
let n2 = n - n1 in
assert (0 <= n1 && n1 <= n);
assert (0 <= n2 && n2 <= n);
n1, n2
let rec generate n =
assert (n >= 0);
if n = 0 then
EConst (Random.int 100)
else
match Random.int 2 with
| 0 ->
let n1, n2 = split (n - 1) in
EAdd (generate n1, generate n2)
| 1 ->
let n1, n2 = split (n - 1) in
EList [ generate n1; generate n2 ]
| _ ->
assert false
let rec list_init i n f =
if i = n then
[]
else
let x = f i in
x :: list_init (i + 1) n f
let list_init n f =
list_init 0 n f
let samples =
list_init 100 (fun _ -> generate 100)
let test f () =
List.iter (fun e -> ignore (f e)) samples
let () =
run [
"iter", test iter;
"native_iter", test (native_iter ());
]
let () =
run [
"size", test size;
"native_size", test (native_size ());
(*
"native_size_noenv", test native_size_noenv;
"native_size_noenv_accu", test (native_size_noenv_accu 0);
*)
]
(* with hoisting, applied to self#visit_expr:
iter allocates no memory, and is 46% slower than native_iter (which allocates).
without hoisting:
iter allocates memory and is 65% slower than native_iter
So, in this case, hoisting helps a little.
with hoisting, applied to self#visit_expr:
size allocates no memory, and is 105% slower than native_size (which allocates).
without hoisting:
size allocates memory (same amount as native_size) and is 86% slower than native_size
So, in this case, hoisting seems counter-productive.
*)
|
