Benchmarks for dictionary data structures: hash tables, maps, tries,
etc.
The judy
package was removed from this test suite for instability;
it segfaults the program.
For all benchmarks:
For just space:
For just time:
Insert Int keys space use
Case |
Bytes |
GCs |
Data.Map.Strict.insert mempty |
64 |
0 |
Data.Map.Lazy.insert mempty |
64 |
0 |
Data.HashMap.Strict.insert mempty |
64 |
0 |
Data.HashMap.Lazy.insert mempty |
48 |
0 |
Pure maps fromList space use
Case |
Total bytes |
Max residency |
Final live |
GCs |
Data.Map.Strict.fromList (1 million) |
1,016,187,152 |
55,394,296 |
31,864 |
1,942 |
Data.Map.Lazy.fromList (1 million) |
1,016,187,152 |
55,394,296 |
31,864 |
1,942 |
Data.IntMap.Strict.fromList (1 million) |
776,852,648 |
55,207,424 |
31,864 |
1,489 |
Data.IntMap.Lazy.fromList (1 million) |
776,852,648 |
55,207,424 |
31,864 |
1,489 |
Data.HashMap.Strict.fromList (1 million) |
161,155,384 |
40,358,064 |
0 |
314 |
Data.HashMap.Lazy.fromList (1 million) |
161,155,384 |
40,358,064 |
0 |
314 |
IO maps fromList space use
Case |
Total bytes |
Max residency |
Final live |
GCs |
Data.HashTable.IO.BasicHashTable (1 million) |
424,214,184 |
47,254,400 |
1,120 |
672 |
Data.HashTable.IO.CuckooHashTable (1 million) |
173,581,848 |
1,328 |
1,328 |
244 |
Data.HashTable.IO.LinearHashTable (1 million) |
281,294,784 |
22,373,256 |
0 |
545 |
Name |
10 |
100 |
1000 |
10000 |
Data.Map.Lazy |
406.3 ns |
7.695 μs |
137.3 μs |
2.349 ms |
Data.Map.Strict |
473.1 ns |
9.485 μs |
165.3 μs |
2.769 ms |
Data.HashMap.Lazy |
287.2 ns |
3.949 μs |
53.47 μs |
1.741 ms |
Data.HashMap.Strict |
291.8 ns |
3.948 μs |
53.25 μs |
1.711 ms |
Data.IntMap.Lazy |
136.4 ns |
2.119 μs |
30.13 μs |
0.878 ms |
Data.IntMap.Strict |
161.3 ns |
2.878 μs |
39.46 μs |
0.985 ms |
IO Insert Int (Randomized)
Name |
10 |
100 |
1000 |
10000 |
Data.HashTable.IO.BasicHashTable |
356.1 ns |
3.308 μs |
33.70 μs |
466.2 μs |
Data.HashTable.IO.LinearHashTable |
684.2 ns |
7.321 μs |
76.05 μs |
660.1 μs |
Data.HashTable.IO.CuckooHashTable |
875.3 ns |
8.493 μs |
85.69 μs |
943.4 μs |
Intersection (Randomized)
Name |
10 |
100 |
1000 |
10000 |
100000 |
1000000 |
Data.Map.Lazy |
422.4 ns |
5.036 μs |
63.85 μs |
742.4 μs |
10.38 ms |
154.1 ms |
Data.Map.Strict |
437.6 ns |
5.028 μs |
65.15 μs |
742.6 μs |
9.070 ms |
97.95 ms |
Data.HashMap.Lazy |
118.3 ns |
1.332 μs |
17.81 μs |
225.2 μs |
2.760 ms |
37.95 ms |
Data.HashMap.Strict |
114.4 ns |
1.315 μs |
17.94 μs |
225.5 μs |
2.884 ms |
38.64 ms |
Data.IntMap.Lazy |
66.73 ns |
0.454 μs |
5.146 μs |
121.1 μs |
1.533 ms |
23.48 ms |
Data.IntMap.Strict |
66.86 ns |
0.456 μs |
5.115 μs |
120.2 μs |
1.524 ms |
24.30 ms |
IO Intersection (Randomized)
Name |
10 |
100 |
1000 |
10000 |
100000 |
Data.HashTable.IO.BasicHashTable |
212.9 ns |
1.286 μs |
17.44 μs |
368.9 μs |
9.504 ms |
Data.HashTable.IO.LinearHashTable |
262.8 ns |
2.503 μs |
25.17 μs |
309.6 μs |
14.84 ms |
Data.HashTable.IO.CuckooHashTable |
1010 ns |
8.765 μs |
84.19 μs |
901.9 μs |
19.21 ms |
Intersection ByteString (Randomized)
Name |
10 |
100 |
1000 |
10000 |
100000 |
1000000 |
Data.Map.Lazy |
947.2 ns |
11.61 μs |
197.5 μs |
3.059 ms |
46.70 ms |
607.7 ms |
Data.Map.Strict |
1152 ns |
15.69 μs |
209.6 μs |
3.149 ms |
41.23 ms |
500.9 ms |
Data.HashMap.Lazy |
533.9 ns |
6.898 μs |
81.07 μs |
1.514 ms |
24.18 ms |
375.1 ms |
Data.HashMap.Strict |
648.7 ns |
8.636 μs |
80.14 μs |
1.166 ms |
24.13 ms |
314.8 ms |
Data.Trie |
439.6 ns |
6.474 μs |
73.46 μs |
1.755 ms |
24.13 ms |
245.4 ms |
Name |
10 |
100 |
1000 |
10000 |
100000 |
1000000 |
Data.Map.Lazy |
97.96 ns |
1.634 μs |
52.42 μs |
1023 μs |
20.27 ms |
697.9 ms |
Data.Map.Strict |
101.1 ns |
1.632 μs |
52.25 μs |
970.9 μs |
17.87 ms |
583.0 ms |
Data.HashMap.Lazy |
133.6 ns |
1.705 μs |
22.95 μs |
408.9 μs |
8.338 ms |
453.7 ms |
Data.HashMap.Strict |
132.9 ns |
1.728 μs |
22.42 μs |
411.9 μs |
8.540 ms |
460.5 ms |
Data.IntMap.Lazy |
105.7 ns |
1.756 μs |
53.45 μs |
895.8 μs |
14.88 ms |
710.6 ms |
Data.IntMap.Strict |
103.6 ns |
1.688 μs |
53.62 μs |
883.4 μs |
15.25 ms |
700.8 ms |
IO Lookup Int (Randomized)
Name |
10 |
100 |
1000 |
10000 |
100000 |
1000000 |
Data.HashTable.IO.BasicHashTable |
15.24 ns |
23.19 ns |
14.62 ns |
14.43 ns |
14.34 ns |
14.28 ns |
Data.HashTable.IO.LinearHashTable |
53.83 ns |
58.41 ns |
57.73 ns |
53.36 ns |
57.63 ns |
145.0 ns |
Data.HashTable.IO.CuckooHashTable |
59.15 ns |
57.50 ns |
57.13 ns |
58.15 ns |
57.69 ns |
56.47 ns |
FromList ByteString (Monotonic)
Name |
10000 |
Data.Map.Lazy |
3.584 ms |
Data.Map.Strict |
4.161 ms |
Data.HashMap.Lazy |
2.040 ms |
Data.HashMap.Strict |
2.075 ms |
Data.Trie |
8.717 ms |
FromList ByteString (Randomized)
Name |
10 |
100 |
1000 |
10000 |
Data.Map.Lazy |
559.3 ns |
11.60 μs |
236.3 μs |
4.496 ms |
Data.Map.Strict |
631.5 ns |
13.54 μs |
246.4 μs |
5.082 ms |
Data.HashMap.Lazy |
547.8 ns |
7.100 μs |
96.10 μs |
2.741 ms |
Data.HashMap.Strict |
557.0 ns |
7.214 μs |
98.62 μs |
2.710 ms |
Data.Trie |
910.6 ns |
15.71 μs |
373.8 μs |
14.93 ms |
Lookup ByteString Monotonic
Name |
10000 |
Data.Map.Lazy |
91.88 ns |
Data.Map.Strict |
91.35 ns |
Data.HashMap.Lazy |
27.23 ns |
Data.HashMap.Strict |
27.41 ns |
Data.Trie |
150.7 ns |
Lookup ByteString Randomized
Name |
10000 |
Data.Map.Lazy |
2.031 ms |
Data.Map.Strict |
1.915 ms |
Data.HashMap.Lazy |
0.678 ms |
Data.HashMap.Strict |
0.670 ms |
Data.Trie |
2.515 ms |