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
137
138
139
140
141
142
143
144
145
146
147
148
|
[@@@ocaml.warning "-5"]
module MList = struct
type 'a t = {
content: 'a array; (* elements of the node *)
mutable len: int; (* number of elements in content *)
mutable tl: 'a t; (* tail *)
}
(** A list that contains some elements, and may point to another list *)
(** Empty list, for the tl field *)
let _empty () : 'a t = Obj.magic 0
let make n =
assert (n > 0);
{ content = Array.make n (Obj.magic 0); len = 0; tl = _empty () }
let rec is_empty l = l.len = 0 && (l.tl == _empty () || is_empty l.tl)
let rec iter f l =
for i = 0 to l.len - 1 do
f l.content.(i)
done;
if l.tl != _empty () then iter f l.tl
let iteri f l =
let rec iteri i f l =
for j = 0 to l.len - 1 do
f (i + j) l.content.(j)
done;
if l.tl != _empty () then iteri (i + l.len) f l.tl
in
iteri 0 f l
let rec iter_rev f l =
if l.tl != _empty () then iter_rev f l.tl;
for i = l.len - 1 downto 0 do
f l.content.(i)
done
let length l =
let rec len acc l =
if l.tl == _empty () then
acc + l.len
else
len (acc + l.len) l.tl
in
len 0 l
(** Get element by index *)
let rec get l i =
if i < l.len then
l.content.(i)
else if i >= l.len && l.tl == _empty () then
raise (Invalid_argument "MList.get")
else
get l.tl (i - l.len)
(** Push [x] at the end of the list. It returns the block in which the
element is inserted. *)
let rec push x l =
if l.len = Array.length l.content then (
(* insert in the next block *)
if l.tl == _empty () then (
let n = Array.length l.content in
l.tl <- make (n + (n lsr 1))
);
push x l.tl
) else (
(* insert in l *)
l.content.(l.len) <- x;
l.len <- l.len + 1;
l
)
(** Reverse list (in place), and returns the new head *)
let rev l =
let rec rev prev l =
(* reverse array *)
for i = 0 to (l.len - 1) / 2 do
let x = l.content.(i) in
l.content.(i) <- l.content.(l.len - i - 1);
l.content.(l.len - i - 1) <- x
done;
(* reverse next block *)
let l' = l.tl in
l.tl <- prev;
if l' == _empty () then
l
else
rev l l'
in
rev (_empty ()) l
(** Build a MList of elements of the Seq. The optional argument indicates
the size of the blocks *)
let of_seq ?(size = 8) seq =
(* read iterator into a MList.t *)
let start = make size in
let l = ref start in
seq (fun x -> l := push x !l);
start
let to_seq l k = iter k l
end
(** Store content of the seqerator in an enum *)
let persistent_mlist seq =
let l = MList.of_seq seq in
MList.to_seq l
let bench_mlist n =
for _i = 0 to 100 do
let _ = persistent_mlist Iter.(1 -- n) in
()
done
let bench_naive n =
for _i = 0 to 100 do
let l = Iter.to_rev_list Iter.(1 -- n) in
let _ = Iter.of_list (List.rev l) in
()
done
let bench_current n =
for _i = 0 to 100 do
let _ = Iter.persistent Iter.(1 -- n) in
()
done
let () =
let bench_n n =
Printf.printf "BENCH for %d\n" n;
let res =
Benchmark.throughputN 5
[
"mlist", bench_mlist, n;
"naive", bench_naive, n;
"current", bench_current, n;
]
in
Benchmark.tabulate res
in
bench_n 100;
bench_n 100_000;
()
(* vim:Use benchmark: *)
|
