Description
Efficient vector-based mutable hashtables implementation.
Description
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.
README.md
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 |