vector-hashtables
Efficient vector-based mutable hashtables implementation.
https://github.com/klapaucius/vector-hashtables#readme
LTS Haskell 22.33: | 0.1.2.0 |
Stackage Nightly 2024-09-07: | 0.1.2.0 |
Latest on Hackage: | 0.1.2.0 |
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
- Data
- Data.Primitive
- Data.Primitive.PrimArray
- Data.Vector
- Data.Primitive
Depends on 4 packages(full list with versions):
Used by 1 package in nightly-2024-05-30(full list with versions):
vector-hashtables
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 examiningMutVar
twice inat
(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)
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.