vector-hashtables: Efficient vector-based mutable hashtables implementation.
This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.
Warnings:
- 'ghc-options: -O2' is rarely needed. Check that it is giving a real benefit and not just imposing longer compile times on your users.
- These packages miss upper bounds: - hashable - primitive - vector Please add them, using `cabal gen-bounds` for suggestions. For more information see: https://pvp.haskell.org/
This package provides efficient vector-based hashtable implementation similar to .NET Generic Dictionary implementation (at the time of 2015).
See Data.Vector.Hashtables for documentation.
[Skip to Readme]
Properties
| Versions | 0.1.0.0, 0.1.0.1, 0.1.1.0, 0.1.1.1, 0.1.1.2, 0.1.1.3, 0.1.1.4, 0.1.2.0, 0.1.2.0 |
|---|---|
| Change log | changelog.md |
| Dependencies | base (>=4.7 && <5), hashable, primitive (>=0.7.1.0), vector [details] |
| License | BSD-3-Clause |
| Copyright | 2016-2024 klapaucius, swamp_agr |
| Author | klapaucius |
| Maintainer | klapaucius, swamp_agr, ArtemPelenitsyn |
| Category | Data |
| Home page | https://github.com/klapaucius/vector-hashtables#readme |
| Source repo | head: git clone https://github.com/klapaucius/vector-hashtables |
| Uploaded | by swamp_agr at 2024-04-26T18:32:48Z |
Modules
[Index] [Quick Jump]
Downloads
- vector-hashtables-0.1.2.0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
Package maintainers
For package maintainers and hackage trustees
Readme for vector-hashtables-0.1.2.0
[back to package description]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 |
Utilities benchmark:
| 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 |