vector-hashtables

Efficient vector-based mutable hashtables implementation.

https://github.com/klapaucius/vector-hashtables#readme

LTS Haskell 22.39:0.1.2.0
Stackage Nightly 2024-10-31:0.1.2.0
Latest on Hackage:0.1.2.0

See all snapshots vector-hashtables appears in

BSD-3-Clause licensed by klapaucius
Maintained by klapaucius, swamp_agr, ArtemPelenitsyn
This version can be pinned in stack with:vector-hashtables-0.1.2.0@sha256:a3293e9961c68b4ae48ec2a09ac3a23f1d78122aa33f87b1545b34c211e78f3c,2728

Module documentation for 0.1.2.0

Used by 1 package in lts-22.39(full list with versions):
Agda

vector-hashtables

Hackage Stackage Nightly Version Stackage LTS Version Build Status

A brief history of this library is given in this blog post.

Benchmarks vs hashtables

(and vector where relevant)

Benchmarks below are produced under GHC 9.4.8, and can be reproduced locally with

cabal bench --benchmark-options="--csv results.csv"
bench-show report results.csv

(You will need the bench-show tool, which is available from Hackage.)

Benchmark v.0.1.1.4 (ns) current (ns)
Comparison/1000/insert/hashtables basic 36083.57 36907.68
Comparison/1000/insert/vector-hashtables boxed 25735.13 17055.86
Comparison/1000/insert/vector-hashtables unboxed keys 23601.08 15333.05
Comparison/1000/insert/vector-hashtables 25298.67 13881.72
Comparison/1000/insert/mutable vector boxed 6458.14 3658.16
Comparison/1000/insert/mutable vector 2526.35 1282.13
Comparison/1000/insert (resize)/hashtables basic 318207.51 159834.87
Comparison/1000/insert (resize)/vector-hashtables boxed 106490.84 25900.28
Comparison/1000/insert (resize)/vector-hashtables unboxed keys 66848.40 25382.56
Comparison/1000/insert (resize)/vector-hashtables 65694.66 21393.31
Comparison/1000/insert, delete/hashtables basic 96776.41 72615.51
Comparison/1000/insert, delete/vector-hashtables 79701.44 20920.26
Comparison/1000/find/hashtables basic 22841.85 23678.93
Comparison/1000/find/vector-hashtables 16398.19 5586.93
Comparison/1000/find/vector-hashtables (frozen) 11967.63 3128.18
Comparison/1000/lookupIndex/hashtables basic 19744.27 19209.79
Comparison/1000/lookupIndex/vector-hashtables 13624.09 4978.75
Comparison/1000/fromList/hashtables basic 167277.66 162920.75
Comparison/1000/fromList/vector-hashtables 48670.75 25283.17
Comparison/1000/toList/hashtables basic 9296.91 9286.65
Comparison/1000/toList/vector-hashtables 9753.58 10022.51
Comparison/10000/insert/hashtables basic 384031.02 373885.01
Comparison/10000/insert/vector-hashtables boxed 246923.90 175892.73
Comparison/10000/insert/vector-hashtables unboxed keys 229812.05 147689.46
Comparison/10000/insert/vector-hashtables 216924.38 128417.71
Comparison/10000/insert/mutable vector boxed 43104.20 42712.36
Comparison/10000/insert/mutable vector 12298.81 12193.85
Comparison/10000/insert (resize)/hashtables basic 1342541.64 1378595.70
Comparison/10000/insert (resize)/vector-hashtables boxed 487188.49 273187.43
Comparison/10000/insert (resize)/vector-hashtables unboxed keys 441635.60 242659.06
Comparison/10000/insert (resize)/vector-hashtables 412651.12 188011.22
Comparison/10000/insert, delete/hashtables basic 722883.16 736250.66
Comparison/10000/insert, delete/vector-hashtables 407113.19 200643.92
Comparison/10000/find/hashtables basic 228154.09 232874.24
Comparison/10000/find/vector-hashtables 164343.06 55693.39
Comparison/10000/find/vector-hashtables (frozen) 119669.00 31291.02
Comparison/10000/lookupIndex/hashtables basic 197212.48 191707.57
Comparison/10000/lookupIndex/vector-hashtables 136205.70 49762.50
Comparison/10000/fromList/hashtables basic 1391968.88 1562065.86
Comparison/10000/fromList/vector-hashtables 430590.93 233128.12
Comparison/10000/toList/hashtables basic 112894.13 114543.83
Comparison/10000/toList/vector-hashtables 152214.13 154034.89
Comparison/100000/insert/hashtables basic 4492224.86 4546924.57
Comparison/100000/insert/vector-hashtables boxed 2414664.98 1767261.44
Comparison/100000/insert/vector-hashtables unboxed keys 2243027.45 1476174.02
Comparison/100000/insert/vector-hashtables 2144269.70 1272101.52
Comparison/100000/insert/mutable vector boxed 667945.33 666673.13
Comparison/100000/insert/mutable vector 121264.87 123138.53
Comparison/100000/insert (resize)/hashtables basic 18217163.16 18777839.68
Comparison/100000/insert (resize)/vector-hashtables boxed 9452674.69 7287443.14
Comparison/100000/insert (resize)/vector-hashtables unboxed keys 7721635.33 5698107.38
Comparison/100000/insert (resize)/vector-hashtables 4722092.98 2574932.04
Comparison/100000/insert, delete/hashtables basic 8699786.66 8790937.73
Comparison/100000/insert, delete/vector-hashtables 4073127.47 2010559.30
Comparison/100000/find/hashtables basic 2283995.01 2346364.66
Comparison/100000/find/vector-hashtables 1676135.49 588427.30
Comparison/100000/find/vector-hashtables (frozen) 1201572.29 319639.97
Comparison/100000/lookupIndex/hashtables basic 1963727.73 1931036.13
Comparison/100000/lookupIndex/vector-hashtables 1363501.76 499992.98
Comparison/100000/fromList/hashtables basic 20681183.31 30059346.94
Comparison/100000/fromList/vector-hashtables 5262183.79 3945839.47
Comparison/100000/toList/hashtables basic 2675794.96 2702739.12
Comparison/100000/toList/vector-hashtables 5155629.15 5118781.70
Comparison/1000000/insert/hashtables basic 86723317.72 85752701.43
Comparison/1000000/insert/vector-hashtables boxed 68162021.23 75667649.90
Comparison/1000000/insert/vector-hashtables unboxed keys 50777620.44 46615543.58
Comparison/1000000/insert/vector-hashtables 23334885.43 16025927.63
Comparison/1000000/insert/mutable vector boxed 30281652.62 32068295.04
Comparison/1000000/insert/mutable vector 1283399.43 1393859.51
Comparison/1000000/insert (resize)/hashtables basic 228726522.46 282346897.14
Comparison/1000000/insert (resize)/vector-hashtables boxed 104556190.01 84385042.40
Comparison/1000000/insert (resize)/vector-hashtables unboxed keys 79183320.30 62413398.66
Comparison/1000000/insert (resize)/vector-hashtables 45925222.08 28777902.04
Comparison/1000000/insert, delete/hashtables basic 130189177.30 134399640.44
Comparison/1000000/insert, delete/vector-hashtables 42722592.04 23648387.28
Comparison/1000000/find/hashtables basic 23094297.73 24583079.42
Comparison/1000000/find/vector-hashtables 16709242.48 6178348.57
Comparison/1000000/find/vector-hashtables (frozen) 12176361.82 3425505.60
Comparison/1000000/lookupIndex/hashtables basic 20222788.08 19753759.16
Comparison/1000000/lookupIndex/vector-hashtables 14041315.59 5357116.98
Comparison/1000000/fromList/hashtables basic 210947448.60 222974094.62
Comparison/1000000/fromList/vector-hashtables 56875691.60 49212505.34
Comparison/1000000/toList/hashtables basic 62256321.15 66351583.99
Comparison/1000000/toList/vector-hashtables 95883670.57 98441804.39
Benchmark v.0.1.1.4 (ns) current (ns)
Utilities/1000/at’ 14554.08 4755.41
Utilities/1000/insert 16704.55 6842.45
Utilities/1000/delete 11166.80 3959.44
Utilities/1000/lookup 14510.59 5161.87
Utilities/1000/lookup’ 14181.87 4739.19
Utilities/1000/lookupIndex 17171.76 4196.40
Utilities/1000/null 7.19 7.92
Utilities/1000/length 7.31 7.41
Utilities/1000/size 6.85 6.53
Utilities/1000/member 17364.48 4344.27
Utilities/1000/findWithDefault 15747.10 4802.97
Utilities/1000/upsert 32633.25 12708.79
Utilities/1000/alter 31908.54 11109.48
Utilities/1000/alterM 32564.14 11110.53
Utilities/1000/union 46432.10 29468.82
Utilities/1000/difference 25741.68 16296.53
Utilities/1000/intersection 58828.38 38587.57
Utilities/1000/fromList 45355.85 26156.93
Utilities/1000/toList 9626.89 10101.05
Utilities/10000/at’ 147509.66 48699.88
Utilities/10000/insert 171201.56 68568.34
Utilities/10000/delete 111650.42 39392.43
Utilities/10000/lookup 149138.47 49800.41
Utilities/10000/lookup’ 144283.31 46886.69
Utilities/10000/lookupIndex 172630.09 40088.94
Utilities/10000/null 7.20 7.24
Utilities/10000/length 7.30 6.77
Utilities/10000/size 6.87 6.43
Utilities/10000/member 170650.68 43369.07
Utilities/10000/findWithDefault 157236.92 49471.03
Utilities/10000/upsert 329212.06 125290.78
Utilities/10000/alter 322814.62 111817.84
Utilities/10000/alterM 330094.30 112444.63
Utilities/10000/union 478541.46 329790.79
Utilities/10000/difference 295042.17 193790.26
Utilities/10000/intersection 644396.71 419483.32
Utilities/10000/fromList 494164.34 331449.21
Utilities/10000/toList 151375.79 167580.99
Utilities/100000/at’ 1491045.70 495418.68
Utilities/100000/insert 1741058.94 765507.51
Utilities/100000/delete 1127146.84 436707.82
Utilities/100000/lookup 1601916.69 562205.51
Utilities/100000/lookup’ 1441526.57 488540.28
Utilities/100000/lookupIndex 1763172.42 405596.28
Utilities/100000/null 7.19 7.26
Utilities/100000/length 7.38 7.17
Utilities/100000/size 6.92 6.83
Utilities/100000/member 1740066.09 464281.90
Utilities/100000/findWithDefault 1577458.36 489790.85
Utilities/100000/upsert 3383104.75 1265454.18
Utilities/100000/alter 3329820.09 1211692.27
Utilities/100000/alterM 3356140.57 1220060.24
Utilities/100000/union 5563999.76 3705665.39
Utilities/100000/difference 6372930.19 5630405.29
Utilities/100000/intersection 12353680.59 9595098.36
Utilities/100000/fromList 5161712.37 3685646.90
Utilities/100000/toList 5109243.49 5118785.28
Utilities/1000000/at’ 14831244.23 5055419.26
Utilities/1000000/insert 17633535.06 7209602.12
Utilities/1000000/delete 11251853.98 4072535.57
Utilities/1000000/lookup 15169518.90 5208497.64
Utilities/1000000/lookup’ 14532451.21 4929673.79
Utilities/1000000/lookupIndex 17529914.96 4216663.23
Utilities/1000000/null 7.20 7.25
Utilities/1000000/length 7.30 6.81
Utilities/1000000/size 6.86 6.43
Utilities/1000000/member 17461069.35 4604944.15
Utilities/1000000/findWithDefault 15945541.78 5058608.89
Utilities/1000000/upsert 34444162.79 12052143.01
Utilities/1000000/alter 33820504.88 11842773.92
Utilities/1000000/alterM 33991841.71 11908234.12
Utilities/1000000/union 59911378.73 44470700.12
Utilities/1000000/difference 117323371.53 107670945.26
Utilities/1000000/intersection 195009586.71 161847790.47
Utilities/1000000/fromList 97086662.77 52734408.34
Utilities/1000000/toList 166554860.99 99619875.06

Changes

0.1.2.0 (2024-04-26)

  • Add upsert function to public interface (see #21).
  • Simplify support of 32-bit architectures via maxBound (see #22).
  • Improve performance via strictness annotations and bang patterns (see #24).
  • Suggest using strict boxed vectors to avoid accumulation of thunks (see #27).
  • Speed up division by bucket’s size (see #28).
  • Avoid deprecated sizeofMutablePrimArray (see #29).
  • Introduce findEntry_ and avoid examining MutVar twice in at (see #32).
  • Bump QuickCheck boundary (see #33).

0.1.1.4 (2023-12-13)

  • Add wasm32 support (see #20).

0.1.1.3 (2023-04-23)

  • cleanup the cabal file
  • CI based on Haskell-CI (see #15)
  • readme: minimal improvement of benchmark data presentation (see #16)
  • bump hspec to <2.12 (see #17)

0.1.1.2 (2023-01-31)

  • Relax hspec boundaries (see #14).
  • Set lower bound for primtive (see #12).

0.1.1.1 (2021-09-10)

  • Optimise insertWithIndex function (#10).

0.1.1.0 (2021-09-10)

  • Add alter function to public interface (#9).

0.1.0.1 (2021-09-10)

  • Remove outdated executable in favor of benchmark.

0.1.0.0 (2021-09-07)

  • Release vector-hastables to the world.