Skip to content

Latest commit

 

History

History
92 lines (64 loc) · 2.72 KB

README.md

File metadata and controls

92 lines (64 loc) · 2.72 KB
Raw

sets

Benchmarks for set data structures: hash maps, FSA's, etc.

There is also a comparison with bloom filters, but note that this is a probabilistic data structure – you will get a certain amount of false positives when testing for membership. The other data structures are all non-probabilistic.

Running

For all benchmarks:

$ stack bench :space :time

For just space:

$ stack bench :space

For just time:

$ stack bench :time

Insert Int (Randomized)

Name 10 100 1000 10000
Data.Set 557.3 ns 17.21 μs 329.0 μs 7.569 ms
Data.HashSet 1270 ns 14.56 μs 213.8 μs 7.279 ms
Data.IntSet 106.0 ns 1.170 μs 40.78 μs 0.491 ms

Intersection (Randomized)

Name 10 100 1000 10000 100000 1000000
Data.Set 1685 ns 18.46 μs 218.9 μs 3.357 ms 29.93 ms 241.3 ms
Data.HashSet 640.3 ns 6.534 μs 94.70 μs 0.854 ms 21.01 ms 267.1 ms
Data.IntSet 167.8 ns 0.947 μs 18.38 μs 0.256 ms 4.604 ms 42.46 ms

Member Int (Randomized)

Name 10 100 1000 10000 100000 1000000
Data.Set 40.38 ns 37.35 ns 47.81 ns 70.97 ns 90.09 ns 117.4 ns
Data.HashSet 124.5 ns 90.98 ns 49.75 ns 56.03 ns 106.6 ns 138.7 ns
Data.IntSet 45.48 ns 55.69 ns 67.94 ns 73.28 ns 88.82 ns 136.2 ns

Member Int (Randomized, false positive rate 0.1)

Name 10 100 1000 10000 100000 1000000
Data.Set 30.03 ns 54.31 ns 47.46 ns 74.55 ns 110.1 ns 93.38 ns
Data.HashSet 77.05 ns 73.74 ns 58.66 ns 52.13 ns 109.2 ns 104.3 ns
Data.IntSet 44.29 ns 57.61 ns 102.8 ns 85.83 ns 79.70 ns 100.9 ns
Data.BloomFilter 326.7 ns 214.6 ns 247.4 ns 183.4 ns 219.0 ns 224.8 ns

Member String (Randomized)

Name 10 100 1000 10000 100000 1000000
Data.Set 260.0 ns 336.3 ns 625.2 ns 674.7 ns 744.7 ns 1053 ns
Data.HashSet 280.0 ns 347.6 ns 420.2 ns 404.1 ns 457.4 ns 421.2 ns
Data.DAWG.Packed 1326 ns 1896 ns 1212 ns 1592 ns 1373 ns 76.12 ns

Member String (Randomized, false positive rate 0.1)

Name 10 100 1000 10000 100000 1000000
Data.Set 252.0 ns 404.0 ns 341.0 ns 670.3 ns 1079 ns 938.6 ns
Data.HashSet 530.4 ns 344.0 ns 352.6 ns 406.8 ns 409.9 ns 464.7 ns
Data.DAWG.Packed 1627 ns 1591 ns 1447 ns 1597 ns 1192 ns 75.21 ns
Data.BloomFilter 858.9 ns 911.3 ns 699.7 ns 1110 ns 821.2 ns 804.4 ns

FromList String (Monotonic)

Name 10000
Data.Set 14.40 ms
Data.HashSet 11.22 ms
Data.DAWG.Packed 7.570 ms

FromList String (Randomized)

Name 10 100 1000 10000
Data.Set 3.238 μs 49.43 μs 0.847 ms 21.40 ms
Data.HashSet 3.524 μs 44.44 μs 0.575 ms 17.99 ms
Data.DAWG.Packed 117.5 μs 2111 μs 31.65 ms 411.0 ms