-
Notifications
You must be signed in to change notification settings - Fork 0
/
notes.txt
100 lines (74 loc) · 2.89 KB
/
notes.txt
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
Queue:
(time (count (reduce #(-> % (conjr %2) rest) (reduce consl (EmptyTree. nil) (range 1e4)) (range 1e6))))
letfn: "Elapsed time: 5043.853495 msecs"
digit macro: "Elapsed time: 3411.159957 msecs"
32% better
Split:
(time (let [n 1e4, t (to-tree {:size [(constantly 1) + 0]} (range n))] (dotimes [i n] (split-tree t #(< i (:size %))))))
"Elapsed time: 4408.469664 msecs"
loopless split digit: "Elapsed time: 4102.303245 msecs"
later got this for the same code: "Elapsed time: 3976.687969 msecs"
Concat:
(time (let [t (to-tree nil (range 1e5))] (dotimes [_ 3e4] (ft-concat t t))))
"Elapsed time: 2402.644912 msecs"
nodes without apply: "Elapsed time: 2004.185324 msecs"
Using digit for node and always using a delayed measure cache:
queue: 3302.095682 (3% better)
split: 3096.94213 (22% better)
concat: 1680.462405 (16% better)
...it's also less code.
Removing the assert in 'deep' helps a bit too:
queue: 2934.046655
split: 3086.496488
concat: 1631.712977
Delay deep's measure:
queue: 2156.064809
split: 2471.035156
concat: 1510.606604
Slightly better 'split' only calling measure/reduce on middle tree when needed.
split: 2347.711168
Reify:
queue: 2151.073871
split: 2351.481345
concat: 1699.367853
defprotocol:
queue: 6234.505356
split: 3824.236948
concat: 1958.039438
protocol call site caching:
queue: 5380.091688
split: 3552.108167
concat: 1679.4733
protocol methods inside deftype:
queue: 6115.087433
split: 2851.264586
concat: 1532.471135
Note PersistentQueue does queue test in 363.281297 msecs
(defn t [] (count (reduce #(-> % (conj %2) pop) (reduce conj clojure.lang.PersistentQueue/EMPTY (range 1e4)) (range 1e6))))
with Clojure 1.2.0:
queue: 2645.928817
split: 2374.810216
concat: 1530.395627
with record-based meters (+ some performance tweaks):
queue: (time (count (reduce #(-> % (conjr %2) rest) (reduce consl (EmptyTree. nil) (range 1e4)) (range 1e6))))
split: (time (let [n 1e4, t (to-tree len-meter (range n))] (dotimes [i n] (split-tree t #(< i %)))))
concat: (time (let [t (to-tree nil (range 1e5))] (dotimes [_ 3e4] (ft-concat t t))))
queue: 3334.090979
split: 313.484652
concat: 1763.906721
Len-Meter instead of Integer:
queue: (time (count (reduce #(-> % (conjr %2) rest) (reduce consl (EmptyTree. nil) (range 1e4)) (range 1e6))))
split: (time (let [n 1e4, t (to-tree len-meter (range n))] (dotimes [i n] (split-tree t #(< i (:len %))))))
concat: (time (let [t (to-tree nil (range 1e5))] (dotimes [_ 3e4] (ft-concat t t))))
split: 331.637379
Test for nil op:
queue: 2346.357413
split: 352.238152
concat 1518.418893
split with len-string-meter: 40264.907112
--- sorted set slowness:
(do (def rands (let [r (java.util.Random. 42)] (take 10000 (repeatedly #(.nextInt r))))) nil)
(defn s1 [] (first (reduce (fn [t i] (insert-where t #(when-let [r (:right %)] (< i r)) i)) (finger-tree right-meter) rands)))
; 914.896926
(defn s2 [] (first (reduce conj (sorted-set) rands)))
; 55.687814