Skip to content

Latest commit

 

History

History
114 lines (83 loc) · 3.57 KB

README.md

File metadata and controls

114 lines (83 loc) · 3.57 KB

dictionaries

Benchmarks for dictionary data structures: hash tables, maps, tries, etc.

Running

For all benchmarks:

$ stack bench :space

For just space:

$ stack bench :space

For just time:

$ stack bench :time

Insert Int keys

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

From List Int keys

Case Bytes GCs
Data.Map.Strict.fromList (1 million) 1,016,187,152 1,942
Data.Map.Lazy.fromList (1 million) 1,016,187,152 1,942
Data.IntMap.Strict.fromList (1 million) 776,852,648 1,489
Data.IntMap.Lazy.fromList (1 million) 776,852,648 1,489
Data.HashMap.Strict.fromList (1 million) 161,155,384 314
Data.HashMap.Lazy.fromList (1 million) 161,155,384 314

Intersection (Randomized)

Name 10 100 1000 10000
Data.Map.Lazy 1220 ns 13.50 μs 156.6 μs 1620 μs
Data.Map.Strict 1216 ns 13.62 μs 157.3 μs 1632 μs
Data.HashMap.Lazy 266.9 ns 2.306 μs 30.66 μs 366.2 μs
Data.HashMap.Strict 264.8 ns 2.322 μs 30.58 μs 366.5 μs
Data.IntMap.Lazy 117.2 ns 0.675 μs 7.665 μs 161.1 μs
Data.IntMap.Strict 116.7 ns 0.678 μs 7.747 μs 152.3 μs

Lookup Int (Randomized)

Name 10 100 1000 10000
Data.Map.Lazy 26.62 ns 34.21 ns 43.12 ns 55.55 ns
Data.Map.Strict 26.49 ns 34.15 ns 42.73 ns 56.03 ns
Data.HashMap.Lazy 22.03 ns 23.70 ns 17.96 ns 24.86 ns
Data.HashMap.Strict 21.05 ns 23.71 ns 17.80 ns 24.95 ns
Data.IntMap.Lazy 17.17 ns 25.39 ns 32.74 ns 43.08 ns
Data.IntMap.Strict 16.93 ns 25.42 ns 32.93 ns 42.92 ns

Insert Int (Randomized)

Name 10 100 1000 10000
Data.Map.Lazy 607.1 ns 11.91 μs 247.7 μs 4.226 ms
Data.Map.Strict 726.2 ns 13.69 μs 269.1 μs 4.575 ms
Data.HashMap.Lazy 534.0 ns 6.706 μs 104.1 μs 3.628 ms
Data.HashMap.Strict 525.9 ns 6.644 μs 103.6 μs 3.637 ms
Data.IntMap.Lazy 261.5 ns 3.796 μs 55.55 μs 1.788 ms
Data.IntMap.Strict 314.8 ns 4.558 μs 66.16 μs 1.943 ms

FromList ByteString (Monotonic)

Name 10000
Data.Map.Lazy 6.214 ms
Data.Map.Strict 6.425 ms
Data.HashMap.Lazy 3.198 ms
Data.HashMap.Strict 3.240 ms
Data.Trie 15.80 ms

FromList ByteString (Randomized)

Name 10 100 1000 10000
Data.Map.Lazy 802.2 ns 17.19 μs 361.8 μs 8.774 ms
Data.Map.Strict 866.4 ns 18.31 μs 370.9 μs 8.919 ms
Data.HashMap.Lazy 819.2 ns 10.54 μs 147.2 μs 3.784 ms
Data.HashMap.Strict 871.5 ns 10.70 μs 149.0 μs 3.801 ms
Data.Trie 1182 ns 24.94 μs 1174 μs 25.13 ms

IO Insert Int (Randomized)

Name 10 100 1000 10000
Data.HashTable.IO.BasicHashTable 1.010 μs 19.73 μs 199.5 μs 2.523 ms
Data.HashTable.IO.LinearHashTable 1.027 μs 21.54 μs 216.0 μs 3.840 ms
Data.HashTable.IO.CuckooHashTable 2.981 μs 45.46 μs 690.3 μs 10.75 ms
Data.Judy 1.460 μs 12.70 μs 135.3 μs 1.280 ms

IO Lookup Int (Randomized)

Name 10 100 1000 10000
Data.HashTable.IO.BasicHashTable 50.03 ns 51.00 ns 48.52 ns 46.16 ns
Data.HashTable.IO.LinearHashTable 139.2 ns 177.7 ns 161.9 ns 128.7 ns
Data.HashTable.IO.CuckooHashTable 203.2 ns 187.0 ns 187.4 ns 201.3 ns
Data.Judy 47.57 ns 55.74 ns 53.54 ns 52.33 ns