vector-hashtables (empty) → 0.1.0.0
raw patch · 14 files changed
+2576/−0 lines, 14 filesdep +QuickCheckdep +basedep +containerssetup-changed
Dependencies added: QuickCheck, base, containers, criterion, hashable, hashtables, hspec, primitive, quickcheck-instances, unordered-containers, vector, vector-hashtables
Files
- LICENSE +30/−0
- README.md +580/−0
- Setup.hs +2/−0
- bench/Main.hs +343/−0
- changelog.md +3/−0
- exe1/Main.hs +67/−0
- src-gen/Data/Vector/Hashtables/Internal/Mask.hs +11/−0
- src-i386/Data/Vector/Hashtables/Internal/Mask.hs +11/−0
- src/Data/Primitive/PrimArray/Utils.hs +66/−0
- src/Data/Vector/Hashtables.hs +85/−0
- src/Data/Vector/Hashtables/Internal.hs +871/−0
- test/Data/Vector/HashTablesSpec.hs +417/−0
- test/Spec.hs +1/−0
- vector-hashtables.cabal +89/−0
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright Author name here (c) 2017++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution.++ * Neither the name of Author name here nor the names of other+ contributors may be used to endorse or promote products derived+ from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,580 @@+# vector-hashtables++```+benchmarking Comparison/1000/insert/hashtables basic+time 38.91 μs (38.65 μs .. 39.23 μs)+ 0.999 R² (0.998 R² .. 0.999 R²)+mean 40.21 μs (39.56 μs .. 41.53 μs)+std dev 3.067 μs (1.758 μs .. 5.396 μs)+variance introduced by outliers: 75% (severely inflated)++benchmarking Comparison/1000/insert/vector-hashtables boxed+time 25.68 μs (25.34 μs .. 26.04 μs)+ 0.998 R² (0.998 R² .. 0.999 R²)+mean 25.86 μs (25.61 μs .. 26.32 μs)+std dev 1.143 μs (855.4 ns .. 1.690 μs)+variance introduced by outliers: 51% (severely inflated)++benchmarking Comparison/1000/insert/vector-hashtables unboxed keys+time 26.35 μs (25.21 μs .. 27.85 μs)+ 0.986 R² (0.975 R² .. 0.996 R²)+mean 26.24 μs (25.58 μs .. 27.13 μs)+std dev 2.476 μs (1.857 μs .. 3.427 μs)+variance introduced by outliers: 83% (severely inflated)++benchmarking Comparison/1000/insert/vector-hashtables+time 22.07 μs (21.75 μs .. 22.36 μs)+ 0.999 R² (0.998 R² .. 0.999 R²)+mean 21.87 μs (21.68 μs .. 22.10 μs)+std dev 712.6 ns (602.6 ns .. 840.7 ns)+variance introduced by outliers: 36% (moderately inflated)++benchmarking Comparison/1000/insert/mutable vector boxed+time 3.046 μs (3.026 μs .. 3.071 μs)+ 0.999 R² (0.999 R² .. 1.000 R²)+mean 3.081 μs (3.050 μs .. 3.135 μs)+std dev 135.7 ns (81.76 ns .. 205.2 ns)+variance introduced by outliers: 58% (severely inflated)++benchmarking Comparison/1000/insert/mutable vector+time 999.2 ns (985.1 ns .. 1.014 μs)+ 0.998 R² (0.996 R² .. 0.999 R²)+mean 992.8 ns (980.4 ns .. 1.024 μs)+std dev 63.94 ns (32.65 ns .. 118.9 ns)+variance introduced by outliers: 77% (severely inflated)++benchmarking Comparison/1000/insert (resize)/hashtables basic+time 165.2 μs (157.5 μs .. 175.6 μs)+ 0.986 R² (0.975 R² .. 0.999 R²)+mean 161.5 μs (158.8 μs .. 166.6 μs)+std dev 11.69 μs (7.190 μs .. 18.99 μs)+variance introduced by outliers: 68% (severely inflated)++benchmarking Comparison/1000/insert (resize)/vector-hashtables boxed+time 46.66 μs (46.13 μs .. 47.17 μs)+ 0.999 R² (0.999 R² .. 1.000 R²)+mean 46.32 μs (46.06 μs .. 46.65 μs)+std dev 962.5 ns (764.8 ns .. 1.199 μs)+variance introduced by outliers: 17% (moderately inflated)++benchmarking Comparison/1000/insert (resize)/vector-hashtables unboxed keys+time 46.91 μs (45.02 μs .. 49.26 μs)+ 0.991 R² (0.984 R² .. 0.999 R²)+mean 45.45 μs (44.88 μs .. 46.62 μs)+std dev 2.576 μs (1.633 μs .. 4.527 μs)+variance introduced by outliers: 62% (severely inflated)++benchmarking Comparison/1000/insert (resize)/vector-hashtables+time 41.94 μs (41.55 μs .. 42.45 μs)+ 0.999 R² (0.998 R² .. 0.999 R²)+mean 42.17 μs (41.75 μs .. 42.70 μs)+std dev 1.597 μs (1.186 μs .. 2.039 μs)+variance introduced by outliers: 41% (moderately inflated)++benchmarking Comparison/1000/insert, delete/hashtables basic+time 75.68 μs (75.01 μs .. 76.54 μs)+ 0.999 R² (0.999 R² .. 1.000 R²)+mean 75.93 μs (75.38 μs .. 76.58 μs)+std dev 2.069 μs (1.738 μs .. 2.488 μs)+variance introduced by outliers: 25% (moderately inflated)++benchmarking Comparison/1000/insert, delete/vector-hashtables+time 40.85 μs (40.20 μs .. 41.98 μs)+ 0.995 R² (0.991 R² .. 0.998 R²)+mean 41.97 μs (41.18 μs .. 43.06 μs)+std dev 2.971 μs (2.164 μs .. 3.842 μs)+variance introduced by outliers: 72% (severely inflated)++benchmarking Comparison/1000/find/hashtables basic+time 19.88 μs (19.76 μs .. 20.02 μs)+ 0.999 R² (0.998 R² .. 1.000 R²)+mean 19.98 μs (19.83 μs .. 20.68 μs)+std dev 925.7 ns (277.3 ns .. 2.032 μs)+variance introduced by outliers: 54% (severely inflated)++benchmarking Comparison/1000/find/vector-hashtables+time 14.03 μs (13.95 μs .. 14.14 μs)+ 1.000 R² (0.999 R² .. 1.000 R²)+mean 14.05 μs (13.98 μs .. 14.20 μs)+std dev 353.4 ns (220.1 ns .. 604.7 ns)+variance introduced by outliers: 27% (moderately inflated)++benchmarking Comparison/1000/find/vector-hashtables (frozen)+time 12.82 μs (12.77 μs .. 12.87 μs)+ 1.000 R² (1.000 R² .. 1.000 R²)+mean 12.85 μs (12.79 μs .. 13.02 μs)+std dev 296.8 ns (149.9 ns .. 608.0 ns)+variance introduced by outliers: 23% (moderately inflated)++benchmarking Comparison/1000/lookupIndex/hashtables basic+time 21.46 μs (21.15 μs .. 21.83 μs)+ 0.999 R² (0.998 R² .. 0.999 R²)+mean 21.07 μs (20.93 μs .. 21.27 μs)+std dev 569.5 ns (424.5 ns .. 765.8 ns)+variance introduced by outliers: 28% (moderately inflated)++benchmarking Comparison/1000/lookupIndex/vector-hashtables+time 14.47 μs (14.30 μs .. 14.62 μs)+ 0.999 R² (0.999 R² .. 0.999 R²)+mean 14.35 μs (14.22 μs .. 14.49 μs)+std dev 444.7 ns (370.8 ns .. 588.5 ns)+variance introduced by outliers: 36% (moderately inflated)++benchmarking Comparison/1000/fromList/hashtables basic+time 167.0 μs (166.6 μs .. 167.5 μs)+ 1.000 R² (1.000 R² .. 1.000 R²)+mean 167.2 μs (166.9 μs .. 167.8 μs)+std dev 1.486 μs (982.6 ns .. 2.227 μs)++benchmarking Comparison/1000/fromList/vector-hashtables+time 46.81 μs (46.51 μs .. 47.10 μs)+ 1.000 R² (1.000 R² .. 1.000 R²)+mean 46.74 μs (46.58 μs .. 47.13 μs)+std dev 755.5 ns (401.2 ns .. 1.348 μs)+variance introduced by outliers: 11% (moderately inflated)++benchmarking Comparison/1000/toList/hashtables basic+time 11.86 μs (11.85 μs .. 11.90 μs)+ 1.000 R² (1.000 R² .. 1.000 R²)+mean 11.88 μs (11.87 μs .. 11.92 μs)+std dev 84.27 ns (45.86 ns .. 133.1 ns)++benchmarking Comparison/1000/toList/vector-hashtables+time 13.84 μs (13.75 μs .. 13.93 μs)+ 1.000 R² (1.000 R² .. 1.000 R²)+mean 13.83 μs (13.78 μs .. 13.88 μs)+std dev 167.8 ns (111.9 ns .. 238.2 ns)++benchmarking Comparison/10000/insert/hashtables basic+time 508.3 μs (498.3 μs .. 518.3 μs)+ 0.995 R² (0.989 R² .. 0.998 R²)+mean 541.8 μs (519.9 μs .. 602.4 μs)+std dev 118.0 μs (61.67 μs .. 214.9 μs)+variance introduced by outliers: 95% (severely inflated)++benchmarking Comparison/10000/insert/vector-hashtables boxed+time 249.9 μs (247.3 μs .. 252.8 μs)+ 0.999 R² (0.999 R² .. 1.000 R²)+mean 249.6 μs (247.9 μs .. 251.5 μs)+std dev 6.103 μs (5.190 μs .. 7.198 μs)+variance introduced by outliers: 17% (moderately inflated)++benchmarking Comparison/10000/insert/vector-hashtables unboxed keys+time 228.9 μs (226.1 μs .. 233.0 μs)+ 0.996 R² (0.992 R² .. 0.999 R²)+mean 234.6 μs (231.4 μs .. 240.0 μs)+std dev 13.52 μs (8.957 μs .. 20.81 μs)+variance introduced by outliers: 55% (severely inflated)++benchmarking Comparison/10000/insert/vector-hashtables+time 205.9 μs (203.8 μs .. 208.0 μs)+ 0.999 R² (0.999 R² .. 1.000 R²)+mean 206.1 μs (204.6 μs .. 207.7 μs)+std dev 5.295 μs (4.282 μs .. 6.831 μs)+variance introduced by outliers: 20% (moderately inflated)++benchmarking Comparison/10000/insert/mutable vector boxed+time 39.74 μs (39.40 μs .. 40.13 μs)+ 0.999 R² (0.999 R² .. 1.000 R²)+mean 39.63 μs (39.39 μs .. 39.94 μs)+std dev 913.7 ns (732.1 ns .. 1.260 μs)+variance introduced by outliers: 21% (moderately inflated)++benchmarking Comparison/10000/insert/mutable vector+time 8.912 μs (8.849 μs .. 8.978 μs)+ 1.000 R² (0.999 R² .. 1.000 R²)+mean 8.913 μs (8.868 μs .. 8.984 μs)+std dev 187.5 ns (139.6 ns .. 251.6 ns)+variance introduced by outliers: 21% (moderately inflated)++benchmarking Comparison/10000/insert (resize)/hashtables basic+time 1.409 ms (1.395 ms .. 1.425 ms)+ 0.999 R² (0.998 R² .. 1.000 R²)+mean 1.399 ms (1.391 ms .. 1.409 ms)+std dev 31.18 μs (25.99 μs .. 38.49 μs)+variance introduced by outliers: 10% (moderately inflated)++benchmarking Comparison/10000/insert (resize)/vector-hashtables boxed+time 511.9 μs (507.1 μs .. 517.1 μs)+ 0.999 R² (0.998 R² .. 1.000 R²)+mean 515.3 μs (510.9 μs .. 520.4 μs)+std dev 16.47 μs (11.77 μs .. 22.61 μs)+variance introduced by outliers: 24% (moderately inflated)++benchmarking Comparison/10000/insert (resize)/vector-hashtables unboxed keys+time 469.3 μs (464.0 μs .. 474.3 μs)+ 0.999 R² (0.998 R² .. 0.999 R²)+mean 469.1 μs (465.1 μs .. 473.4 μs)+std dev 13.57 μs (11.12 μs .. 17.63 μs)+variance introduced by outliers: 21% (moderately inflated)++benchmarking Comparison/10000/insert (resize)/vector-hashtables+time 397.4 μs (389.8 μs .. 405.4 μs)+ 0.997 R² (0.993 R² .. 0.999 R²)+mean 395.9 μs (390.7 μs .. 404.8 μs)+std dev 21.76 μs (10.93 μs .. 37.13 μs)+variance introduced by outliers: 50% (severely inflated)++benchmarking Comparison/10000/insert, delete/hashtables basic+time 961.8 μs (940.0 μs .. 991.4 μs)+ 0.994 R² (0.990 R² .. 0.997 R²)+mean 974.8 μs (961.4 μs .. 990.4 μs)+std dev 51.11 μs (39.48 μs .. 77.48 μs)+variance introduced by outliers: 42% (moderately inflated)++benchmarking Comparison/10000/insert, delete/vector-hashtables+time 390.5 μs (386.3 μs .. 394.0 μs)+ 0.999 R² (0.999 R² .. 1.000 R²)+mean 388.3 μs (386.2 μs .. 391.1 μs)+std dev 8.246 μs (6.102 μs .. 12.95 μs)+variance introduced by outliers: 13% (moderately inflated)++benchmarking Comparison/10000/find/hashtables basic+time 198.3 μs (197.3 μs .. 199.7 μs)+ 0.999 R² (0.997 R² .. 0.999 R²)+mean 206.2 μs (203.0 μs .. 211.8 μs)+std dev 13.78 μs (8.640 μs .. 23.14 μs)+variance introduced by outliers: 64% (severely inflated)++benchmarking Comparison/10000/find/vector-hashtables+time 144.4 μs (142.2 μs .. 146.8 μs)+ 0.998 R² (0.998 R² .. 0.999 R²)+mean 145.5 μs (144.1 μs .. 147.2 μs)+std dev 5.118 μs (4.170 μs .. 6.713 μs)+variance introduced by outliers: 33% (moderately inflated)++benchmarking Comparison/10000/find/vector-hashtables (frozen)+time 127.4 μs (126.3 μs .. 128.8 μs)+ 1.000 R² (0.999 R² .. 1.000 R²)+mean 127.6 μs (127.0 μs .. 128.4 μs)+std dev 2.436 μs (1.921 μs .. 3.124 μs)+variance introduced by outliers: 14% (moderately inflated)++benchmarking Comparison/10000/lookupIndex/hashtables basic+time 201.2 μs (198.1 μs .. 204.4 μs)+ 0.994 R² (0.986 R² .. 0.999 R²)+mean 215.8 μs (205.8 μs .. 238.5 μs)+std dev 50.42 μs (21.99 μs .. 91.35 μs)+variance introduced by outliers: 96% (severely inflated)++benchmarking Comparison/10000/lookupIndex/vector-hashtables+time 168.8 μs (149.7 μs .. 190.9 μs)+ 0.922 R² (0.875 R² .. 0.987 R²)+mean 158.5 μs (151.4 μs .. 171.9 μs)+std dev 30.82 μs (17.89 μs .. 48.16 μs)+variance introduced by outliers: 94% (severely inflated)++benchmarking Comparison/10000/fromList/hashtables basic+time 1.498 ms (1.495 ms .. 1.500 ms)+ 1.000 R² (1.000 R² .. 1.000 R²)+mean 1.486 ms (1.483 ms .. 1.490 ms)+std dev 11.33 μs (9.989 μs .. 14.19 μs)++benchmarking Comparison/10000/fromList/vector-hashtables+time 437.5 μs (434.7 μs .. 442.0 μs)+ 1.000 R² (0.999 R² .. 1.000 R²)+mean 435.6 μs (434.8 μs .. 437.6 μs)+std dev 4.145 μs (2.185 μs .. 7.752 μs)++benchmarking Comparison/10000/toList/hashtables basic+time 180.6 μs (179.2 μs .. 182.7 μs)+ 0.999 R² (0.996 R² .. 1.000 R²)+mean 180.7 μs (179.6 μs .. 183.2 μs)+std dev 5.564 μs (2.368 μs .. 10.37 μs)+variance introduced by outliers: 26% (moderately inflated)++benchmarking Comparison/10000/toList/vector-hashtables+time 308.0 μs (306.0 μs .. 310.8 μs)+ 1.000 R² (0.999 R² .. 1.000 R²)+mean 306.9 μs (306.1 μs .. 308.2 μs)+std dev 3.495 μs (2.409 μs .. 5.571 μs)++benchmarking Comparison/100000/insert/hashtables basic+time 10.78 ms (10.14 ms .. 11.47 ms)+ 0.981 R² (0.968 R² .. 0.993 R²)+mean 10.27 ms (9.907 ms .. 10.69 ms)+std dev 1.037 ms (801.2 μs .. 1.404 ms)+variance introduced by outliers: 55% (severely inflated)++benchmarking Comparison/100000/insert/vector-hashtables boxed+time 7.378 ms (7.178 ms .. 7.568 ms)+ 0.989 R² (0.978 R² .. 0.995 R²)+mean 7.406 ms (7.188 ms .. 7.717 ms)+std dev 717.3 μs (511.6 μs .. 977.4 μs)+variance introduced by outliers: 54% (severely inflated)++benchmarking Comparison/100000/insert/vector-hashtables unboxed keys+time 5.746 ms (5.562 ms .. 5.909 ms)+ 0.991 R² (0.986 R² .. 0.995 R²)+mean 5.662 ms (5.496 ms .. 5.886 ms)+std dev 581.5 μs (442.4 μs .. 834.2 μs)+variance introduced by outliers: 63% (severely inflated)++benchmarking Comparison/100000/insert/vector-hashtables+time 2.358 ms (2.270 ms .. 2.452 ms)+ 0.980 R² (0.970 R² .. 0.988 R²)+mean 2.401 ms (2.318 ms .. 2.533 ms)+std dev 345.3 μs (242.2 μs .. 535.8 μs)+variance introduced by outliers: 82% (severely inflated)++benchmarking Comparison/100000/insert/mutable vector boxed+time 2.058 ms (1.992 ms .. 2.119 ms)+ 0.984 R² (0.972 R² .. 0.991 R²)+mean 2.036 ms (1.954 ms .. 2.155 ms)+std dev 308.0 μs (226.0 μs .. 446.1 μs)+variance introduced by outliers: 83% (severely inflated)++benchmarking Comparison/100000/insert/mutable vector+time 87.63 μs (86.94 μs .. 88.32 μs)+ 0.999 R² (0.999 R² .. 1.000 R²)+mean 87.65 μs (87.10 μs .. 88.31 μs)+std dev 1.928 μs (1.609 μs .. 2.504 μs)+variance introduced by outliers: 17% (moderately inflated)++benchmarking Comparison/100000/insert (resize)/hashtables basic+time 22.66 ms (22.02 ms .. 23.25 ms)+ 0.995 R² (0.989 R² .. 0.998 R²)+mean 22.77 ms (22.18 ms .. 23.40 ms)+std dev 1.398 ms (1.082 ms .. 1.831 ms)+variance introduced by outliers: 24% (moderately inflated)++benchmarking Comparison/100000/insert (resize)/vector-hashtables boxed+time 12.87 ms (12.33 ms .. 13.40 ms)+ 0.988 R² (0.978 R² .. 0.994 R²)+mean 12.59 ms (12.09 ms .. 13.00 ms)+std dev 1.168 ms (825.4 μs .. 1.670 ms)+variance introduced by outliers: 47% (moderately inflated)++benchmarking Comparison/100000/insert (resize)/vector-hashtables unboxed keys+time 10.16 ms (9.768 ms .. 10.60 ms)+ 0.988 R² (0.981 R² .. 0.994 R²)+mean 9.993 ms (9.541 ms .. 10.35 ms)+std dev 1.102 ms (758.4 μs .. 1.623 ms)+variance introduced by outliers: 58% (severely inflated)++benchmarking Comparison/100000/insert (resize)/vector-hashtables+time 6.202 ms (5.965 ms .. 6.467 ms)+ 0.987 R² (0.980 R² .. 0.992 R²)+mean 6.151 ms (5.999 ms .. 6.429 ms)+std dev 606.8 μs (409.8 μs .. 1.002 ms)+variance introduced by outliers: 59% (severely inflated)++benchmarking Comparison/100000/insert, delete/hashtables basic+time 14.78 ms (14.31 ms .. 15.29 ms)+ 0.988 R² (0.975 R² .. 0.995 R²)+mean 14.66 ms (14.22 ms .. 15.13 ms)+std dev 1.165 ms (886.6 μs .. 1.561 ms)+variance introduced by outliers: 38% (moderately inflated)++benchmarking Comparison/100000/insert, delete/vector-hashtables+time 4.196 ms (4.035 ms .. 4.329 ms)+ 0.986 R² (0.974 R² .. 0.993 R²)+mean 4.220 ms (4.122 ms .. 4.392 ms)+std dev 400.7 μs (246.1 μs .. 636.6 μs)+variance introduced by outliers: 60% (severely inflated)++benchmarking Comparison/100000/find/hashtables basic+time 1.982 ms (1.970 ms .. 2.000 ms)+ 0.999 R² (0.999 R² .. 1.000 R²)+mean 1.989 ms (1.980 ms .. 2.001 ms)+std dev 35.28 μs (28.03 μs .. 49.47 μs)++benchmarking Comparison/100000/find/vector-hashtables+time 1.407 ms (1.393 ms .. 1.418 ms)+ 0.999 R² (0.999 R² .. 1.000 R²)+mean 1.403 ms (1.397 ms .. 1.416 ms)+std dev 27.15 μs (17.89 μs .. 44.48 μs)++benchmarking Comparison/100000/find/vector-hashtables (frozen)+time 1.268 ms (1.262 ms .. 1.274 ms)+ 1.000 R² (0.999 R² .. 1.000 R²)+mean 1.281 ms (1.273 ms .. 1.292 ms)+std dev 30.55 μs (18.11 μs .. 49.86 μs)+variance introduced by outliers: 13% (moderately inflated)++benchmarking Comparison/100000/lookupIndex/hashtables basic+time 2.373 ms (2.225 ms .. 2.521 ms)+ 0.972 R² (0.957 R² .. 0.988 R²)+mean 2.237 ms (2.172 ms .. 2.335 ms)+std dev 267.0 μs (194.6 μs .. 359.7 μs)+variance introduced by outliers: 75% (severely inflated)++benchmarking Comparison/100000/lookupIndex/vector-hashtables+time 1.414 ms (1.410 ms .. 1.421 ms)+ 1.000 R² (1.000 R² .. 1.000 R²)+mean 1.419 ms (1.415 ms .. 1.422 ms)+std dev 11.58 μs (8.924 μs .. 15.33 μs)++benchmarking Comparison/100000/fromList/hashtables basic+time 20.81 ms (20.05 ms .. 22.64 ms)+ 0.985 R² (0.964 R² .. 1.000 R²)+mean 20.19 ms (19.97 ms .. 21.22 ms)+std dev 947.6 μs (85.26 μs .. 1.999 ms)+variance introduced by outliers: 18% (moderately inflated)++benchmarking Comparison/100000/fromList/vector-hashtables+time 5.839 ms (5.151 ms .. 6.424 ms)+ 0.881 R² (0.801 R² .. 0.936 R²)+mean 5.539 ms (5.131 ms .. 6.241 ms)+std dev 1.524 ms (1.059 ms .. 2.189 ms)+variance introduced by outliers: 92% (severely inflated)++benchmarking Comparison/100000/toList/hashtables basic+time 6.273 ms (5.820 ms .. 6.908 ms)+ 0.958 R² (0.919 R² .. 1.000 R²)+mean 5.884 ms (5.753 ms .. 6.247 ms)+std dev 573.7 μs (303.4 μs .. 1.114 ms)+variance introduced by outliers: 59% (severely inflated)++benchmarking Comparison/100000/toList/vector-hashtables+time 9.543 ms (9.023 ms .. 10.54 ms)+ 0.950 R² (0.899 R² .. 0.997 R²)+mean 9.244 ms (8.973 ms .. 9.883 ms)+std dev 1.062 ms (424.3 μs .. 1.792 ms)+variance introduced by outliers: 63% (severely inflated)++benchmarking Comparison/1000000/insert/hashtables basic+time 101.7 ms (95.97 ms .. 105.4 ms)+ 0.996 R² (0.988 R² .. 1.000 R²)+mean 101.1 ms (98.80 ms .. 104.9 ms)+std dev 4.771 ms (2.658 ms .. 7.959 ms)+variance introduced by outliers: 10% (moderately inflated)++benchmarking Comparison/1000000/insert/vector-hashtables boxed+time 83.26 ms (81.36 ms .. 84.79 ms)+ 0.998 R² (0.993 R² .. 1.000 R²)+mean 82.90 ms (81.79 ms .. 84.60 ms)+std dev 2.347 ms (1.267 ms .. 3.740 ms)++benchmarking Comparison/1000000/insert/vector-hashtables unboxed keys+time 61.02 ms (58.60 ms .. 63.35 ms)+ 0.996 R² (0.991 R² .. 0.999 R²)+mean 60.33 ms (57.50 ms .. 61.81 ms)+std dev 3.690 ms (1.587 ms .. 6.637 ms)+variance introduced by outliers: 16% (moderately inflated)++benchmarking Comparison/1000000/insert/vector-hashtables+time 25.63 ms (24.93 ms .. 26.30 ms)+ 0.996 R² (0.991 R² .. 0.998 R²)+mean 25.59 ms (24.82 ms .. 26.34 ms)+std dev 1.693 ms (1.170 ms .. 2.724 ms)+variance introduced by outliers: 25% (moderately inflated)++benchmarking Comparison/1000000/insert/mutable vector boxed+time 34.80 ms (33.16 ms .. 36.42 ms)+ 0.994 R² (0.989 R² .. 0.998 R²)+mean 35.03 ms (33.63 ms .. 35.97 ms)+std dev 2.381 ms (1.429 ms .. 3.737 ms)+variance introduced by outliers: 24% (moderately inflated)++benchmarking Comparison/1000000/insert/mutable vector+time 1.420 ms (1.283 ms .. 1.589 ms)+ 0.936 R² (0.900 R² .. 0.970 R²)+mean 1.360 ms (1.290 ms .. 1.456 ms)+std dev 252.9 μs (209.8 μs .. 344.6 μs)+variance introduced by outliers: 90% (severely inflated)++benchmarking Comparison/1000000/insert (resize)/hashtables basic+time 282.2 ms (267.1 ms .. 300.9 ms)+ 0.997 R² (0.990 R² .. 1.000 R²)+mean 272.8 ms (259.4 ms .. 281.7 ms)+std dev 13.93 ms (5.206 ms .. 20.42 ms)+variance introduced by outliers: 16% (moderately inflated)++benchmarking Comparison/1000000/insert (resize)/vector-hashtables boxed+time 130.5 ms (125.3 ms .. 135.4 ms)+ 0.998 R² (0.994 R² .. 1.000 R²)+mean 127.5 ms (116.8 ms .. 131.6 ms)+std dev 9.768 ms (2.293 ms .. 15.96 ms)+variance introduced by outliers: 23% (moderately inflated)++benchmarking Comparison/1000000/insert (resize)/vector-hashtables unboxed keys+time 98.64 ms (93.18 ms .. 104.1 ms)+ 0.995 R² (0.986 R² .. 0.999 R²)+mean 95.41 ms (87.57 ms .. 98.86 ms)+std dev 8.158 ms (2.788 ms .. 12.88 ms)+variance introduced by outliers: 21% (moderately inflated)++benchmarking Comparison/1000000/insert (resize)/vector-hashtables+time 50.70 ms (48.53 ms .. 52.56 ms)+ 0.995 R² (0.990 R² .. 0.998 R²)+mean 50.26 ms (46.79 ms .. 52.22 ms)+std dev 4.736 ms (2.266 ms .. 8.080 ms)+variance introduced by outliers: 29% (moderately inflated)++benchmarking Comparison/1000000/insert, delete/hashtables basic+time 150.6 ms (142.2 ms .. 159.1 ms)+ 0.995 R² (0.983 R² .. 0.999 R²)+mean 148.2 ms (141.4 ms .. 154.9 ms)+std dev 9.927 ms (6.353 ms .. 15.02 ms)+variance introduced by outliers: 13% (moderately inflated)++benchmarking Comparison/1000000/insert, delete/vector-hashtables+time 43.85 ms (42.67 ms .. 45.16 ms)+ 0.998 R² (0.996 R² .. 0.999 R²)+mean 43.91 ms (43.17 ms .. 45.42 ms)+std dev 2.058 ms (1.052 ms .. 3.472 ms)+variance introduced by outliers: 13% (moderately inflated)++benchmarking Comparison/1000000/find/hashtables basic+time 19.90 ms (19.66 ms .. 20.15 ms)+ 0.999 R² (0.998 R² .. 1.000 R²)+mean 19.83 ms (19.73 ms .. 19.95 ms)+std dev 254.3 μs (194.8 μs .. 320.2 μs)++benchmarking Comparison/1000000/find/vector-hashtables+time 14.77 ms (14.35 ms .. 15.36 ms)+ 0.996 R² (0.992 R² .. 0.999 R²)+mean 14.37 ms (14.23 ms .. 14.59 ms)+std dev 441.9 μs (272.6 μs .. 624.3 μs)+variance introduced by outliers: 11% (moderately inflated)++benchmarking Comparison/1000000/find/vector-hashtables (frozen)+time 12.86 ms (12.71 ms .. 13.03 ms)+ 0.999 R² (0.998 R² .. 1.000 R²)+mean 12.86 ms (12.79 ms .. 12.95 ms)+std dev 214.6 μs (162.1 μs .. 260.9 μs)++benchmarking Comparison/1000000/lookupIndex/hashtables basic+time 23.83 ms (21.04 ms .. 27.48 ms)+ 0.927 R² (0.863 R² .. 0.995 R²)+mean 22.73 ms (21.38 ms .. 26.29 ms)+std dev 4.433 ms (2.231 ms .. 7.776 ms)+variance introduced by outliers: 74% (severely inflated)++benchmarking Comparison/1000000/lookupIndex/vector-hashtables+time 15.29 ms (12.94 ms .. 17.73 ms)+ 0.844 R² (0.697 R² .. 0.948 R²)+mean 17.93 ms (16.57 ms .. 20.28 ms)+std dev 4.048 ms (2.744 ms .. 5.619 ms)+variance introduced by outliers: 82% (severely inflated)++benchmarking Comparison/1000000/fromList/hashtables basic+time 269.2 ms (242.7 ms .. 308.4 ms)+ 0.991 R² (0.982 R² .. 1.000 R²)+mean 248.1 ms (242.8 ms .. 263.9 ms)+std dev 11.73 ms (85.78 μs .. 14.59 ms)+variance introduced by outliers: 16% (moderately inflated)++benchmarking Comparison/1000000/fromList/vector-hashtables+time 61.62 ms (56.18 ms .. 70.59 ms)+ 0.948 R² (0.872 R² .. 0.986 R²)+mean 56.62 ms (51.73 ms .. 62.25 ms)+std dev 9.794 ms (7.418 ms .. 12.15 ms)+variance introduced by outliers: 57% (severely inflated)++benchmarking Comparison/1000000/toList/hashtables basic+time 74.11 ms (68.99 ms .. 81.85 ms)+ 0.980 R² (0.950 R² .. 1.000 R²)+mean 70.93 ms (68.79 ms .. 74.82 ms)+std dev 4.712 ms (474.1 μs .. 6.422 ms)+variance introduced by outliers: 17% (moderately inflated)++benchmarking Comparison/1000000/toList/vector-hashtables+time 107.4 ms (99.87 ms .. 113.3 ms)+ 0.991 R² (0.970 R² .. 1.000 R²)+mean 104.2 ms (101.7 ms .. 108.1 ms)+std dev 5.246 ms (3.609 ms .. 6.996 ms)+variance introduced by outliers: 10% (moderately inflated)++```
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ bench/Main.hs view
@@ -0,0 +1,343 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE TypeFamilies #-}++module Main (main) where++import qualified Data.Vector.Storable as V+import qualified Data.Vector.Storable.Mutable as VM+import qualified Data.Vector.Mutable as BV+import Control.Monad.Primitive (PrimMonad(PrimState))+import qualified Data.HashTable.IO as H++import Criterion.Main (bench, bgroup, defaultMain, nfIO)+import Criterion (Benchmark)++import qualified Data.Vector.Hashtables.Internal as VH++vh :: Int -> IO (VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int)+vh n = do+ ht <- VH.initialize n :: IO (VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int)+ let go !i | i <= n = VH.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0+ return ht++fvh :: Int -> IO (VH.FrozenDictionary V.Vector Int V.Vector Int)+fvh n = do+ h <- vh n+ c <- VH.clone h+ VH.unsafeFreeze c++bh :: Int -> IO (H.BasicHashTable Int Int)+bh n = do+ ht <- H.newSized n :: IO (H.BasicHashTable Int Int)+ let go !i | i <= n = H.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0+ return ht++fl :: Int -> [(Int, Int)]+fl n = mkPair <$> [0 .. n]+ where+ mkPair !x = (x, x)++vhfind :: Int -> VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int -> IO Int+vhfind n ht = do+ let go !i !s | i <= n = do+ x <- VH.findEntry ht i+ go (i + 1) (s + x)+ | otherwise = return s+ go 0 0++fvhfind :: Int -> VH.FrozenDictionary V.Vector Int V.Vector Int -> IO Int+fvhfind n ht = return $ go 0 0 where+ go !i !s | i <= n = go (i + 1) (s + VH.findElem ht i)+ | otherwise = s++bhfind :: Int -> H.BasicHashTable Int Int -> IO Int+bhfind n ht = do+ let go !i !s | i <= n = do+ Just x <- H.lookup ht i+ go (i + 1) (s + x)+ | otherwise = return s+ go 0 0++htb :: Int -> IO ()+htb n = do+ ht <- H.newSized n :: IO (H.BasicHashTable Int Int)+ let go !i | i <= n = H.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0+++vht :: Int -> IO ()+vht n = do+ ht <- VH.initialize n :: IO (VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int)+ let go !i | i <= n = VH.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0++vhtd :: Int -> IO ()+vhtd n = do+ ht <- VH.initialize n :: IO (VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int)+ let go !i | i <= n = VH.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0+ let go1 !i | i <= n = VH.delete ht i >> go1 (i + 1)+ | otherwise = return ()+ go1 0++htbd :: Int -> IO ()+htbd n = do+ ht <- H.newSized n :: IO (H.BasicHashTable Int Int)+ let go !i | i <= n = H.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0+ let go1 !i | i <= n = H.delete ht i >> go1 (i + 1)+ | otherwise = return ()+ go1 0++vhtb :: Int -> IO ()+vhtb n = do+ ht <- VH.initialize n :: IO (VH.Dictionary (PrimState IO) BV.MVector Int BV.MVector Int)+ let go !i | i <= n = VH.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0++vhtk :: Int -> IO ()+vhtk n = do+ ht <- VH.initialize n :: IO (VH.Dictionary (PrimState IO) VM.MVector Int BV.MVector Int)+ let go !i | i <= n = VH.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0++htbg :: Int -> IO ()+htbg n = do+ ht <- H.newSized 1 :: IO (H.BasicHashTable Int Int)+ let go !i | i <= n = H.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0++vhtg :: Int -> IO ()+vhtg n = do+ ht <- VH.initialize 1 :: IO (VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int)+ let go !i | i <= n = VH.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0++vhtbg :: Int -> IO ()+vhtbg n = do+ ht <- VH.initialize 1 :: IO (VH.Dictionary (PrimState IO) BV.MVector Int BV.MVector Int)+ let go !i | i <= n = VH.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0++vhtkg :: Int -> IO ()+vhtkg n = do+ ht <- VH.initialize 1 :: IO (VH.Dictionary (PrimState IO) VM.MVector Int BV.MVector Int)+ let go !i | i <= n = VH.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0++mvb :: Int -> IO ()+mvb n = do+ ht <- BV.new (n+1)+ let go !i | i <= n = BV.write ht i i >> go (i + 1)+ | otherwise = return ()+ go 0++mv :: Int -> IO ()+mv n = do+ ht <- VM.new (n+1)+ let go !i | i <= n = VM.write ht i i >> go (i + 1)+ | otherwise = return ()+ go 0++bhfromList l = do+ _bht <- H.fromList l :: IO (H.BasicHashTable Int Int)+ return ()++vhfromList l = do+ _ht <- VH.fromList l :: IO (VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int)+ return ()++bhlookupIndex :: Int -> H.BasicHashTable Int Int -> IO Int+bhlookupIndex n ht = do+ let go !i !s | i <= n = do+ Just x <- H.lookupIndex ht i+ go (i + 1) (s + fromIntegral x)+ | otherwise = return s+ go 0 0++vhlookupIndex :: Int -> VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int -> IO Int+vhlookupIndex n ht = do+ let go !i !s | i <= n = do+ Just x <- VH.lookupIndex ht i+ go (i + 1) (s + x)+ | otherwise = return s+ go 0 0++bhtoList = H.toList++vhtoList = VH.toList++bgc :: Int -> IO Benchmark+bgc n = do+ h <- vh n+ h2 <- bh n+ fh <- fvh n+ let l = fl n+ return $ bgroup (show n)+ [ bgroup "insert" + [ bench "hashtables basic" $ nfIO (htb n)+ , bench "vector-hashtables boxed" $ nfIO (vhtb n)+ , bench "vector-hashtables unboxed keys" $ nfIO (vhtk n)+ , bench "vector-hashtables" $ nfIO (vht n) + , bench "mutable vector boxed" $ nfIO (mvb n)+ , bench "mutable vector" $ nfIO (mv n) ]+ , bgroup "insert (resize)"+ [ bench "hashtables basic" $ nfIO (htbg n)+ , bench "vector-hashtables boxed" $ nfIO (vhtbg n)+ , bench "vector-hashtables unboxed keys" $ nfIO (vhtkg n)+ , bench "vector-hashtables" $ nfIO (vhtg n) ]+ , bgroup "insert, delete"+ [ bench "hashtables basic" $ nfIO (htbd n)+ , bench "vector-hashtables" $ nfIO (vhtd n) ]+ , bgroup "find"+ [ bench "hashtables basic" $ nfIO (bhfind n h2)+ , bench "vector-hashtables" $ nfIO (vhfind n h)+ , bench "vector-hashtables (frozen)" $ nfIO (fvhfind n fh) ]+ , bgroup "lookupIndex"+ [ bench "hashtables basic" $ nfIO (bhlookupIndex n h2)+ , bench "vector-hashtables" $ nfIO (vhlookupIndex n h) ]+ , bgroup "fromList"+ [ bench "hashtables basic" $ nfIO (bhfromList l)+ , bench "vector-hashtables" $ nfIO (vhfromList l) ]+ , bgroup "toList"+ [ bench "hashtables basic" $ nfIO (bhtoList h2)+ , bench "vector-hashtables" $ nfIO (vhtoList h) ]]++main :: IO ()+main = do+ let inputs = [1000,10000,100000,1000000]+ comparisonBench <- mapM bgc inputs+ utilitiesBench <- mapM utilities inputs+ defaultMain+ [ bgroup "Comparison" comparisonBench+ , bgroup "Utilities" utilitiesBench ]++-- ** Utilities benchmark++utilities n = do+ -- utilities input data+ hAt' <- vh n+ hInsert <- vh n+ hDelete <- vh n+ hLookup <- vh n+ hLookup' <- vh n+ hLookupIndex <- vh n+ hNull <- vh n+ hLength <- vh n+ hSize <- vh n+ hMember <- vh n+ hFindWithDefault <- vh n+ hAlter <- vh n+ hAlterM <- vh n+ hUnion1 <- vh n+ hUnion2 <- vh n+ hDifference1 <- vh n+ hDifference2 <- vh n+ hIntersection1 <- vh n+ hIntersection2 <- vh n+ hFromList <- VH.toList =<< vh n+ hToList <- vh n++ return $ bgroup (show n)+ [ bench "at'" $ nfIO (bhuat' n hAt')+ , bench "insert" $ nfIO (bhuinsert n hInsert)+ , bench "delete" $ nfIO (bhudelete n hDelete)+ , bench "lookup" $ nfIO (bhulookup n hLookup)+ , bench "lookup'" $ nfIO (bhulookup' n hLookup')+ , bench "lookupIndex" $ nfIO (bhulookupIndex n hLookupIndex)+ , bench "null" $ nfIO (bhunull hNull)+ , bench "length" $ nfIO (bhulength hLength)+ , bench "size" $ nfIO (bhusize hSize)+ , bench "member" $ nfIO (bhumember n hMember)+ , bench "findWithDefault" $ nfIO (bhufindWithDefault n hFindWithDefault)+ , bench "alter" $ nfIO (bhualter n hAlter)+ , bench "alterM" $ nfIO (bhualterM n hAlterM)+ , bench "union" $ nfIO (bhuunion hUnion1 hUnion2)+ , bench "difference" $ nfIO (bhudifference hDifference1 hDifference2)+ , bench "intersection" $ nfIO (bhuintersection hIntersection1 hIntersection2)+ , bench "fromList" $ nfIO (bhufromList hFromList)+ , bench "toList" $ nfIO (VH.toList hToList) ]++bhuat' n ht = do+ let go !i | i <= n = VH.at' ht i >> go (i + 1)+ | otherwise = return ()+ go 0++bhuinsert n ht = do+ let go !i | i <= n = VH.insert ht i i >> go (i + 1)+ | otherwise = return ()+ go 0++bhudelete n ht = do+ let go !i | i <= n = VH.delete ht i >> go (i + 1)+ | otherwise = return ()+ go 0++bhulookup n ht = do+ let go !i | i <= n = VH.lookup ht i >> go (i + 1)+ | otherwise = return ()+ go 0++bhulookup' n ht = do+ let go !i | i <= n = VH.lookup' ht i >> go (i + 1)+ | otherwise = return ()+ go 0++bhulookupIndex n ht = do+ let go !i | i <= n = VH.lookupIndex ht i >> go (i + 1)+ | otherwise = return ()+ go 0++bhunull = VH.null++bhulength = VH.length++bhusize = VH.size++bhumember n ht = do+ let go !i | i <= n = VH.member ht i >> go (i + 1)+ | otherwise = return ()+ go 0++bhufindWithDefault n ht = do+ let go !i | i <= n = VH.findWithDefault ht 0 i >> go (i + 1)+ | otherwise = return ()+ go 0++bhualter n ht = do+ let go !i | i <= n = VH.alter ht (fmap succ) i >> go (i + 1)+ | otherwise = return ()+ go 0++bhualterM :: Int -> VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int -> IO ()+bhualterM n ht = do+ let f = return . fmap succ+ go !i | i <= n = VH.alterM ht f i >> go (i + 1)+ | otherwise = return ()+ go 0++bhuunion ht1 ht2 = VH.union ht1 ht2 >> return ()++bhudifference ht1 ht2 = VH.difference ht1 ht2 >> return ()++bhuintersection ht1 ht2 = VH.intersection ht1 ht2 >> return ()++bhufromList htlist = do+ ht <- VH.fromList htlist :: IO (VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int)+ return ()++bhutoList ht = VH.toList ht >> return ()
+ changelog.md view
@@ -0,0 +1,3 @@+# 0.1.0.0 (2021-09-07)++- Release vector-hastables to the world.
+ exe1/Main.hs view
@@ -0,0 +1,67 @@+{-# LANGUAGE BangPatterns, TypeFamilies #-} + +module Main where + +import qualified Data.Vector.Hashtables.Internal as VH +import qualified Data.Vector.Storable.Mutable as VM +import qualified Data.Vector.Storable as V + +import qualified Data.Vector.Mutable as BV + +import qualified Data.HashTable.IO as H + +-- import qualified Data.HashMap.Strict as Map + +import Control.Monad +import Control.Monad.Primitive +import Data.IORef + +n = 10000000 + +vh :: IO (VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int) +vh = do + ht <- VH.initialize n :: IO (VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int) + let go !i | i <= n = VH.insert ht i i >> go (i + 1) + | otherwise = return () + go 0 + return ht + +fvh :: IO (VH.FrozenDictionary V.Vector Int V.Vector Int) +fvh = do + h <- vh + c <- VH.clone h + VH.unsafeFreeze c + +bh :: IO (H.BasicHashTable Int Int) +bh = do + ht <- H.newSized n :: IO (H.BasicHashTable Int Int) + let go !i | i <= n = H.insert ht i i >> go (i + 1) + | otherwise = return () + go 0 + return ht + +vhfind :: VH.Dictionary (PrimState IO) VM.MVector Int VM.MVector Int -> IO Int +vhfind ht = do + let go !i !s | i <= n = do + x <- VH.findEntry ht i + go (i + 1) (s + x) + | otherwise = return s + go 0 0 + +fvhfind :: VH.FrozenDictionary V.Vector Int V.Vector Int -> IO Int +fvhfind ht = return $ go 0 0 where + go !i !s | i <= n = go (i + 1) (s + VH.findElem ht i) + | otherwise = s + +bhfind :: H.BasicHashTable Int Int -> IO Int +bhfind ht = do + let go !i !s | i <= n = do + Just x <- H.lookup ht i + go (i + 1) (s + x) + | otherwise = return s + go 0 0 + +main = do + ht <- fvh + s <- replicateM 10 $ fvhfind ht + print $ s
+ src-gen/Data/Vector/Hashtables/Internal/Mask.hs view
@@ -0,0 +1,11 @@+{-|+Module : Data.Vector.Hashtables.Internal.Mask+Description : Provides arch-dependent mask for hashtables.+Copyright : (c) klapaucius, swamp_agr, 2016-2021+License : BSD3+-}+module Data.Vector.Hashtables.Internal.Mask where++-- | 'Int' mask. For 32-bit it is equal to @0x7FFFFFFF@. Otherwise, @0x7FFFFFFFFFFFFFFF@.+mask = 0x7FFFFFFFFFFFFFFF :: Int+{-# INLINE mask #-}
+ src-i386/Data/Vector/Hashtables/Internal/Mask.hs view
@@ -0,0 +1,11 @@+{-|+Module : Data.Vector.Hashtables.Internal.Mask+Description : Provides arch-dependent mask for hashtables.+Copyright : (c) klapaucius, swamp_agr, 2016-2021+License : BSD3+-}+module Data.Vector.Hashtables.Internal.Mask where++-- | 'Int' mask. For 32-bit it is equal to @0x7FFFFFFF@. Otherwise, @0x7FFFFFFFFFFFFFFF@.+mask = 0x7FFFFFFF :: Int+{-# INLINE mask #-}
+ src/Data/Primitive/PrimArray/Utils.hs view
@@ -0,0 +1,66 @@+{-|+Module : Data.Primitive.PrimArray.Utils+Description : Provides useful utilities for operating with mutable primitive arrays.+Copyright : (c) klapaucius, swamp_agr, 2016-2021+License : BSD3+-}+module Data.Primitive.PrimArray.Utils where++import Data.Primitive.PrimArray+import Control.Monad.Primitive+import Data.Primitive++replicate :: (PrimMonad m, Prim a) + => Int -> a -> m (MutablePrimArray (PrimState m) a)+replicate n x = do+ xs <- newPrimArray n+ setPrimArray xs 0 (sizeofMutablePrimArray xs) x+ return xs++{-# INLINE replicate #-}++clone :: (PrimMonad m, Prim a) + => MutablePrimArray (PrimState m) a -> m (MutablePrimArray (PrimState m) a)+clone xs = cloneMutablePrimArray xs 0 (sizeofMutablePrimArray xs)++{-# INLINE clone #-}++unsafeFreeze :: PrimMonad m + => MutablePrimArray (PrimState m) a -> m (PrimArray a)+unsafeFreeze = unsafeFreezePrimArray++{-# INLINE unsafeFreeze #-}++unsafeThaw :: PrimMonad m + => PrimArray a -> m (MutablePrimArray (PrimState m) a)+unsafeThaw = unsafeThawPrimArray++{-# INLINE unsafeThaw #-}++growWith :: (PrimMonad m, Prim a) + => a -> MutablePrimArray (PrimState m) a -> Int -> m (MutablePrimArray (PrimState m) a)+growWith a xs delta = do + r <- growNoZ xs delta+ setPrimArray r (sizeofMutablePrimArray xs) delta a+ return r++{-# INLINE growWith #-}++growNoZ :: (PrimMonad m, Prim a) + => MutablePrimArray (PrimState m) a -> Int -> m (MutablePrimArray (PrimState m) a)+growNoZ xs delta = resizeMutablePrimArray xs (sizeofMutablePrimArray xs + delta)++{-# INLINE growNoZ #-}++freeze :: (PrimMonad m, Prim a) + => MutablePrimArray (PrimState m) a -> m (PrimArray a)+freeze xs = do + r <- unsafeFreezePrimArray xs+ return $ clonePrimArray r 0 (sizeofPrimArray r)++{-# INLINE freeze #-}++length :: Prim a => MutablePrimArray s a -> Int+length = sizeofMutablePrimArray++{-# INLINE length #-}
+ src/Data/Vector/Hashtables.hs view
@@ -0,0 +1,85 @@+{-|+Module : Data.Vector.Hashtables+Description : Provides hashtables, basic interface and set of utilities.+Copyright : (c) klapaucius, swamp_agr, 2016-2021+License : BSD3+-}+module Data.Vector.Hashtables+ ( -- * Documentation+ -- $doc++ -- ** Usage+ -- $usage++ -- ** Types+ Dictionary (..)+ , FrozenDictionary (..)+ , findElem+ , Dictionary_ (..)+ , findEntry++ -- ** Construction+ , initialize+ , clone++ -- ** Basic interface+ , null+ , size+ , keys+ , values+ , lookup+ , lookup'+ , insert+ , delete+ , alterM++ -- ** Combine++ -- *** Union+ , union+ , unionWith+ , unionWithKey+ + -- *** Difference+ , difference+ , differenceWith++ -- *** Intersection+ , intersection+ , intersectionWith+ , intersectionWithKey++ -- ** Conversions+ + -- *** Mutable+ , unsafeFreeze+ , unsafeThaw++ -- *** List+ , fromList+ , toList++ , module Control.Monad.Primitive+ ) where++import Prelude hiding (null, lookup)+import Control.Monad.Primitive+import Data.Vector.Hashtables.Internal++-- $doc+--+-- - This package provides hashtable implementation similar to .NET Generic Dictionary implementation (at the time of 2015) <https://github.com/dotnet/coreclr/blob/3a0d638843472056c0cbb723beaed0b1152ca36d/src/mscorlib/src/System/Collections/Generic/Dictionary.cs>.+-- +-- - It was originated as response to <https://comp.lang.functional.narkive.com/uYVjkKfl/f-vs-ocaml-vs-python-vs-haskell-hash-table-performance#post5>.+--+-- - For more hashtables implementations see <https://rcoh.me/posts/hash-map-analysis/>.++-- $usage+--+-- >>> import qualified Data.Vector.Storable.Mutable as VM+-- >>> import qualified Data.Vector.Unboxed.Mutable as UM+-- >>> import Data.Vector.Hashtables+-- >>> type HashTable k v = Dictionary (PrimState IO) VM.MVector k UM.MVector v+-- >>> ht <- initialize 0 :: IO (HashTable Int Int)+-- >>> insert ht 0 1+--
+ src/Data/Vector/Hashtables/Internal.hs view
@@ -0,0 +1,871 @@+{-|+Module : Data.Vector.Hashtables.Internal+Description : Provides internals of hashtables and set of utilities.+Copyright : (c) klapaucius, swamp_agr, 2016-2021+License : BSD3+-}+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE RecordWildCards #-}+{-# LANGUAGE TypeFamilies #-}+module Data.Vector.Hashtables.Internal where++import Control.Monad+import Control.Monad.Primitive+import Data.Bits+import Data.Hashable+import Data.Maybe+import Data.Primitive.MutVar+import Data.Vector.Generic (Mutable, Vector)+import qualified Data.Vector.Generic as VI+import Data.Vector.Generic.Mutable (MVector)+import qualified Data.Vector.Generic.Mutable as V+import qualified Data.Vector.Mutable as B+import qualified Data.Vector.Storable as SI+import qualified Data.Vector.Storable.Mutable as S+import qualified Data.Vector.Unboxed as UI+import qualified Data.Vector.Unboxed.Mutable as U+import qualified GHC.Exts as Exts+import Prelude hiding (length, lookup)++import qualified Data.Primitive.PrimArray as A+import qualified Data.Primitive.PrimArray.Utils as A++import Data.Vector.Hashtables.Internal.Mask (mask)++-- | Alias for 'MutablePrimArray s Int'.+type IntArray s = A.MutablePrimArray s Int++-- | Single-element mutable array of 'Dictionary_' with primitive state token parameterized with state, keys and values types.+--+-- *Example*:+--+-- >>> import qualified Data.Vector.Storable.Mutable as VM+-- >>> import qualified Data.Vector.Unboxed.Mutable as UM+-- >>> import Data.Vector.Hashtables+-- >>> type HashTable k v = Dictionary (PrimState IO) VM.MVector k UM.MVector v+--+-- Different vectors could be used for keys and values:+--+-- - storable,+-- - mutable,+-- - unboxed.+--+-- In most cases unboxed vectors should be used. Nevertheless, it is up to you to decide about final form of hastable.+newtype Dictionary s ks k vs v = DRef { getDRef :: MutVar s (Dictionary_ s ks k vs v) }++-- | Represents collection of hashtable internal primitive arrays and vectors.+--+-- - hash codes,+--+-- - references to the next element,+--+-- - buckets,+--+-- - keys+--+-- - and values.+--+data Dictionary_ s ks k vs v = Dictionary {+ hashCode,+ next,+ buckets,+ refs :: IntArray s,+ key :: ks s k,+ value :: vs s v+}++getCount, getFreeList, getFreeCount :: Int+getCount = 0+getFreeList = 1+getFreeCount = 2++-- | Represents immutable dictionary as collection of immutable arrays and vectors.+-- See 'unsafeFreeze' and 'unsafeThaw' for conversions from/to mutable dictionary.+data FrozenDictionary ks k vs v = FrozenDictionary {+ fhashCode,+ fnext,+ fbuckets :: A.PrimArray Int,+ count, freeList, freeCount :: Int,+ fkey :: ks k,+ fvalue :: vs v+} deriving (Eq, Ord, Show)++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- Find dictionary entry by given key in immutable 'FrozenDictionary'.+-- If entry not found @-1@ returned.+findElem :: (Vector ks k, Vector vs v, Hashable k, Eq k)+ => FrozenDictionary ks k vs v -> k -> Int+findElem FrozenDictionary{..} key' = go $ fbuckets !. (hashCode' `rem` A.sizeofPrimArray fbuckets) where+ hashCode' = hash key' .&. mask+ go i | i >= 0 =+ if fhashCode !. i == hashCode' && fkey !.~ i == key'+ then i else go $ fnext !. i+ | otherwise = -1+{-# INLINE findElem #-}++-- | Infix version of @unsafeRead@.+(!~) :: (MVector v a, PrimMonad m) => v (PrimState m) a -> Int -> m a+(!~) = V.unsafeRead++-- | Infix version of @unsafeIndex@.+(!.~) :: (Vector v a) => v a -> Int -> a+(!.~) = VI.unsafeIndex++-- | Infix version of @unsafeWrite@.+(<~~) :: (MVector v a, PrimMonad m) => v (PrimState m) a -> Int -> a -> m ()+(<~~) = V.unsafeWrite++-- | Infix version of @readPrimArray@.+(!) :: PrimMonad m => A.MutablePrimArray (PrimState m) Int -> Int -> m Int+(!) = A.readPrimArray ++-- | Infix version of @indexPrimArray@.+(!.) :: A.PrimArray Int -> Int -> Int+(!.) = A.indexPrimArray++-- | Infix version of @writePrimArray@.+(<~) :: PrimMonad m => A.MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()+(<~) = A.writePrimArray++-- | /O(1)/ Dictionary with given capacity.+initialize+ :: (MVector ks k, MVector vs v, PrimMonad m)+ => Int+ -> m (Dictionary (PrimState m) ks k vs v)+initialize capacity = do+ let size = getPrime capacity+ hashCode <- A.replicate size 0+ next <- A.replicate size 0+ key <- V.new size+ value <- V.new size+ buckets <- A.replicate size (-1)+ refs <- A.replicate 3 0+ refs <~ 1 $ -1+ dr <- newMutVar Dictionary {..}+ return . DRef $ dr++-- | Create a copy of mutable dictionary.+clone+ :: (MVector ks k, MVector vs v, PrimMonad m)+ => Dictionary (PrimState m) ks k vs v+ -> m (Dictionary (PrimState m) ks k vs v)+clone DRef {..} = do+ Dictionary {..} <- readMutVar getDRef+ hashCode <- A.clone hashCode+ next <- A.clone next+ key <- V.clone key+ value <- V.clone value+ buckets <- A.clone buckets+ refs <- A.clone refs+ dr <- newMutVar Dictionary {..}+ return . DRef $ dr++-- | /O(1)/ Unsafe convert a mutable dictionary to an immutable one without copying.+-- The mutable dictionary may not be used after this operation.+unsafeFreeze+ :: (VI.Vector ks k, VI.Vector vs v, PrimMonad m)+ => Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v+ -> m (FrozenDictionary ks k vs v)+unsafeFreeze DRef {..} = do+ Dictionary {..} <- readMutVar getDRef+ fhashCode <- A.unsafeFreeze hashCode+ fnext <- A.unsafeFreeze next+ fbuckets <- A.unsafeFreeze buckets+ count <- refs ! getCount+ freeList <- refs ! getFreeList+ freeCount <- refs ! getFreeCount+ fkey <- VI.unsafeFreeze key+ fvalue <- VI.unsafeFreeze value+ return FrozenDictionary {..}++-- | /O(1)/ Unsafely convert immutable 'FrozenDictionary' to a mutable 'Dictionary' without copying.+-- The immutable dictionary may not be used after this operation.+unsafeThaw+ :: (Vector ks k, Vector vs v, PrimMonad m)+ => FrozenDictionary ks k vs v+ -> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)+unsafeThaw FrozenDictionary {..} = do+ hashCode <- A.unsafeThaw fhashCode+ next <- A.unsafeThaw fnext+ buckets <- A.unsafeThaw fbuckets+ refs <- A.unsafeThaw $ A.primArrayFromListN 3 [count, freeList, freeCount]+ key <- VI.unsafeThaw fkey+ value <- VI.unsafeThaw fvalue+ dr <- newMutVar Dictionary {..}+ return . DRef $ dr++-- | /O(n)/ Retrieve list of keys from 'Dictionary'.+keys :: (Vector ks k, PrimMonad m)+ => Dictionary (PrimState m) (Mutable ks) k vs v -> m (ks k)+keys DRef{..} = do+ Dictionary{..} <- readMutVar getDRef+ hcs <- A.freeze hashCode+ ks <- VI.freeze key+ count <- refs ! getCount+ return . VI.ifilter (\i _ -> hcs !. i >= 0) . VI.take count $ ks++-- | /O(n)/ Retrieve list of values from 'Dictionary'.+values :: (Vector vs v, PrimMonad m)+ => Dictionary (PrimState m) ks k (Mutable vs) v -> m (vs v)+values DRef{..} = do+ Dictionary{..} <- readMutVar getDRef+ hcs <- A.freeze hashCode+ vs <- VI.freeze value+ count <- refs ! getCount+ return . VI.ifilter (\i _ -> hcs !. i >= 0) . VI.take count $ vs++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- Find value by given key in 'Dictionary'. Throws an error if value not found.+at :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v -> k -> m v+at d k = do+ i <- findEntry d k+ if i >= 0+ then do+ Dictionary{..} <- readMutVar . getDRef $ d+ value !~ i+ else error "KeyNotFoundException!"+{-# INLINE at #-}++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- Find value by given key in 'Dictionary'. Like 'at'' but return 'Nothing' if value not found.+at' :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)+at' d k = do+ i <- findEntry d k+ if i >= 0+ then do+ Dictionary{..} <- readMutVar . getDRef $ d+ Just <$> value !~ i+ else pure Nothing+{-# INLINE at' #-}++atWithOrElse :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v+ -> k+ -> (Dictionary (PrimState m) ks k vs v -> Int -> m a)+ -> (Dictionary (PrimState m) ks k vs v -> m a)+ -> m a+atWithOrElse d k onFound onNothing = do+ i <- findEntry d k+ if i >= 0+ then onFound d i+ else onNothing d+{-# INLINE atWithOrElse #-}++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- Find dictionary entry by given key. If entry not found @-1@ returned.+findEntry :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v -> k -> m Int+findEntry d key' = do+ Dictionary{..} <- readMutVar . getDRef $ d+ let hashCode' = hash key' .&. mask+ go i | i >= 0 = do+ hc <- hashCode ! i+ if hc == hashCode'+ then do+ k <- key !~ i+ if k == key'+ then return i+ else go =<< next ! i+ else go =<< next ! i+ | otherwise = return $ -1+ go =<< buckets ! (hashCode' `rem` A.length buckets)+{-# INLINE findEntry #-}++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- Insert key and value in dictionary by key's hash.+-- If entry with given key found value will be replaced.+insert :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v -> k -> v -> m ()+insert DRef{..} key' value' = do+ d@Dictionary{..} <- readMutVar getDRef+ let+ hashCode' = hash key' .&. mask+ targetBucket = hashCode' `rem` A.length buckets++ go i | i >= 0 = do+ hc <- hashCode ! i+ if hc == hashCode'+ then do+ k <- key !~ i+ if k == key'+ then value <~~ i $ value'+ else go =<< next ! i+ else go =<< next ! i+ | otherwise = addOrResize++ addOrResize = do+ freeCount <- refs ! getFreeCount+ if freeCount > 0+ then do+ index <- refs ! getFreeList+ nxt <- next ! index+ refs <~ getFreeList $ nxt+ refs <~ getFreeCount $ freeCount - 1+ add index targetBucket+ else do+ count <- refs ! getCount+ refs <~ getCount $ count + 1+ if count == A.length next+ then do+ nd <- resize d count hashCode' key' value'+ writeMutVar getDRef nd+ else add (fromIntegral count) (fromIntegral targetBucket)++ add !index !targetBucket = do+ hashCode <~ index $ hashCode'+ b <- buckets ! targetBucket+ next <~ index $ b+ key <~~ index $ key'+ value <~~ index $ value'+ buckets <~ targetBucket $ index++ go =<< buckets ! targetBucket+{-# INLINE insert #-}++insertWithIndex+ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Int -> Int -> k -> v -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v) -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()+insertWithIndex !targetBucket !hashCode' key' value' getDRef d@Dictionary{..} i+ | i >= 0 = do+ hc <- hashCode ! i+ if hc == hashCode'+ then do+ k <- key !~ i+ if k == key'+ then value <~~ i $ value'+ else insertWithIndex targetBucket hashCode' key' value' getDRef d =<< next ! i+ else insertWithIndex targetBucket hashCode' key' value' getDRef d =<< next ! i+ | otherwise = addOrResize targetBucket hashCode' key' value' getDRef d+{-# INLINE insertWithIndex #-}++addOrResize+ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Int -> Int -> k -> v -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v) -> Dictionary_ (PrimState m) ks k vs v -> m ()+addOrResize !targetBucket !hashCode' !key' !value' dref d@Dictionary{..} = do+ freeCount <- refs ! getFreeCount+ if freeCount > 0+ then do+ index <- refs ! getFreeList+ nxt <- next ! index+ refs <~ getFreeList $ nxt+ refs <~ getFreeCount $ freeCount - 1+ add index targetBucket hashCode' key' value' d+ else do+ count <- refs ! getCount+ refs <~ getCount $ count + 1+ if count == A.length next+ then do+ nd <- resize d count hashCode' key' value'+ writeMutVar dref nd+ else add (fromIntegral count) (fromIntegral targetBucket) hashCode' key' value' d+{-# INLINE addOrResize #-}++add :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Int -> Int -> Int -> k -> v -> Dictionary_ (PrimState m) ks k vs v -> m ()+add !index !targetBucket !hashCode' !key' !value' Dictionary{..} = do+ hashCode <~ index $ hashCode'+ b <- buckets ! targetBucket+ next <~ index $ b+ key <~~ index $ key'+ value <~~ index $ value'+ buckets <~ targetBucket $ index+{-# INLINE add #-}+++resize Dictionary{..} index hashCode' key' value' = do+ let newSize = getPrime (index*2)+ delta = newSize - index++ buckets <- A.replicate newSize (-1)++ hashCode <- A.growNoZ hashCode delta+ next <- A.growNoZ next delta+ key <- V.grow key delta+ value <- V.grow value delta++ let go i | i < index = do+ hc <- hashCode ! i+ when (hc >= 0) $ do+ let bucket = hc `rem` newSize+ nx <- buckets ! bucket+ next <~ i $ nx+ buckets <~ bucket $ i+ go (i + 1)+ | otherwise = return ()+ go 0++ let targetBucket = hashCode' `rem` A.length buckets+ hashCode <~ index $ hashCode'+ b <- buckets ! targetBucket+ next <~ index $ b+ key <~~ index $ key'+ value <~~ index $ value'+ buckets <~ targetBucket $ index+ return Dictionary{..}++{-# INLINE resize #-}++class DeleteEntry xs where+ deleteEntry :: (MVector xs x, PrimMonad m) => xs (PrimState m) x -> Int -> m ()++instance DeleteEntry S.MVector where+ deleteEntry _ _ = return ()++instance DeleteEntry U.MVector where+ deleteEntry _ _ = return ()++instance DeleteEntry B.MVector where+ deleteEntry v i = v <~~ i $ undefined++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- Delete entry from 'Dictionary' by given key.+delete :: (Eq k, MVector ks k, MVector vs v, Hashable k, PrimMonad m, DeleteEntry ks, DeleteEntry vs)+ => Dictionary (PrimState m) ks k vs v -> k -> m ()+delete DRef{..} key' = do+ Dictionary{..} <- readMutVar getDRef+ let hashCode' = hash key' .&. mask+ bucket = hashCode' `rem` A.length buckets+ go !last !i | i >= 0 = do+ hc <- hashCode ! i+ k <- key !~ i+ if hc == hashCode' && k == key' then do+ nxt <- next ! i+ if last < 0+ then buckets <~ bucket $ nxt+ else next <~ last $ nxt+ hashCode <~ i $ -1+ next <~ i =<< refs ! getFreeList+ deleteEntry key i+ deleteEntry value i+ refs <~ getFreeList $ i+ fc <- refs ! getFreeCount+ refs <~ getFreeCount $ fc + 1+ else go i =<< next ! i+ | otherwise = return ()+ go (-1) =<< buckets ! bucket++{-# INLINE delete #-}++deleteWithIndex+ :: (Eq k, MVector ks k, MVector vs v, Hashable k, PrimMonad m, DeleteEntry ks, DeleteEntry vs)+ => Int -> Int -> Dictionary_ (PrimState m) ks k vs v -> k -> Int -> Int -> m ()+deleteWithIndex !bucket !hashCode' d@Dictionary{..} key' !last !i+ | i >= 0 = do+ hc <- hashCode ! i+ k <- key !~ i+ if hc == hashCode' && k == key' then do+ nxt <- next ! i+ if last < 0+ then buckets <~ bucket $ nxt+ else next <~ last $ nxt+ hashCode <~ i $ -1+ next <~ i =<< refs ! getFreeList+ deleteEntry key i+ deleteEntry value i+ refs <~ getFreeList $ i+ fc <- refs ! getFreeCount+ refs <~ getFreeCount $ fc + 1+ else deleteWithIndex bucket hashCode' d key' i =<< next ! i+ | otherwise = return ()+{-# INLINE deleteWithIndex #-}++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- Find value by given key in 'Dictionary'. Like 'lookup'' but return 'Nothing' if value not found.+lookup :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)+lookup = at'+{-# INLINE lookup #-}++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- Find value by given key in 'Dictionary'. Throws an error if value not found.+lookup' :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v -> k -> m v+lookup' = at+{-# INLINE lookup' #-}++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- Lookup the index of a key, which is its zero-based index in the sequence sorted by keys.+-- The index is a number from 0 up to, but not including, the size of the dictionary.+lookupIndex :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe Int)+lookupIndex ht k = do+ let safeIndex i | i < 0 = Nothing+ | otherwise = Just i+ return . safeIndex =<< findEntry ht k+{-# INLINE lookupIndex #-}++-- | /O(1)/ Return 'True' if dictionary is empty, 'False' otherwise.+null+ :: (MVector ks k, PrimMonad m)+ => Dictionary (PrimState m) ks k vs v -> m Bool+null ht = return . (== 0) =<< length ht+{-# INLINE null #-}++-- | /O(1)/ Return the number of non-empty entries of dictionary.+length+ :: (MVector ks k, PrimMonad m)+ => Dictionary (PrimState m) ks k vs v -> m Int+length DRef {..} = do+ Dictionary {..} <- readMutVar getDRef+ count <- refs ! getCount+ freeCount <- refs ! getFreeCount+ return (count - freeCount)+{-# INLINE length #-}++-- | /O(1)/ Return the number of non-empty entries of dictionary. Synonym of 'length'.+size+ :: (MVector ks k, PrimMonad m)+ => Dictionary (PrimState m) ks k vs v -> m Int+size = length+{-# INLINE size #-}++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- Return 'True' if the specified key is present in the dictionary, 'False' otherwise.+member+ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v -> k -> m Bool+member ht k = return . (>= 0) =<< findEntry ht k+{-# INLINE member #-}++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- The expression @'findWithDefault' ht def k@ returns+-- the value at key @k@ or returns default value @def@+-- when the key is not in the dictionary.+findWithDefault+ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v -> v -> k -> m v+findWithDefault ht v k = return . fromMaybe v =<< at' ht k+{-# INLINE findWithDefault #-}++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- The expression (@'alter' ht f k@) alters the value @x@ at @k@, or absence thereof.+-- 'alter' can be used to insert, delete, or update a value in a 'Dictionary'.+--+-- > let f _ = Nothing+-- > ht <- fromList [(5,"a"), (3,"b")]+-- > alter ht f 7+-- > toList ht+-- > [(3, "b"), (5, "a")]+--+-- > ht <- fromList [(5,"a"), (3,"b")]+-- > alter ht f 5+-- > toList ht+-- > [(3 "b")]+-- +-- > let f _ = Just "c"+-- > ht <- fromList [(5,"a"), (3,"b")]+-- > alter ht f 7+-- > toList ht+-- > [(3, "b"), (5, "a"), (7, "c")]+-- +-- > ht <- fromList [(5,"a"), (3,"b")]+-- > alter ht f 5+-- > toList ht+-- > [(3, "b"), (5, "c")]+-- +alter+ :: ( MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs+ , PrimMonad m, Hashable k, Eq k+ )+ => Dictionary (PrimState m) ks k vs v -> (Maybe v -> Maybe v) -> k -> m ()+alter ht f k = do+ d@Dictionary{..} <- readMutVar . getDRef $ ht+ let+ hashCode' = hash k .&. mask+ targetBucket = hashCode' `rem` A.length buckets++ onFound' value' dict i = insertWithIndex targetBucket hashCode' k value' (getDRef ht) dict i+ onNothing' dict i = deleteWithIndex targetBucket hashCode' d k (-1) i++ onFound dict i = do+ d'@Dictionary{..} <- readMutVar . getDRef $ dict+ v <- value !~ i+ case f (Just v) of+ Nothing -> onNothing' d' i+ Just v' -> onFound' v' d' i++ onNothing dict = do+ d' <- readMutVar . getDRef $ dict+ case f Nothing of+ Nothing -> return ()+ Just v' -> onFound' v' d' (-1)++ void $ atWithOrElse ht k onFound onNothing++{-# INLINE alter #-}++-- | /O(1)/ in the best case, /O(n)/ in the worst case.+-- The expression (@'alterM' ht f k@) alters the value @x@ at @k@, or absence thereof.+-- 'alterM' can be used to insert, delete, or update a value in a 'Dictionary' in the same @'PrimMonad' m@.+alterM+ :: ( MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs+ , PrimMonad m, Hashable k, Eq k+ )+ => Dictionary (PrimState m) ks k vs v -> (Maybe v -> m (Maybe v)) -> k -> m ()+alterM ht f k = do+ d@Dictionary{..} <- readMutVar . getDRef $ ht+ let+ hashCode' = hash k .&. mask+ targetBucket = hashCode' `rem` A.length buckets++ onFound' value' dict i = insertWithIndex targetBucket hashCode' k value' (getDRef ht) dict i+ onNothing' dict i = deleteWithIndex targetBucket hashCode' d k (-1) i++ onFound dict i = do+ d'@Dictionary{..} <- readMutVar . getDRef $ dict+ v <- value !~ i+ res <- f (Just v)+ case res of+ Nothing -> onNothing' d' i+ Just v' -> onFound' v' d' i++ onNothing dict = do+ d' <- readMutVar . getDRef $ dict+ res <- f Nothing+ case res of+ Nothing -> return ()+ Just v' -> onFound' v' d' (-1)++ void $ atWithOrElse ht k onFound onNothing++{-# INLINE alterM #-}++-- * Combine++-- | /O(min n m)/ in the best case, /O(min n m * max n m)/ in the worst case.+-- The union of two maps.+-- If a key occurs in both maps,+-- the mapping from the first will be the mapping in the result.+union+ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v+ -> Dictionary (PrimState m) ks k vs v+ -> m (Dictionary (PrimState m) ks k vs v)+union = unionWith const++{-# INLINE union #-}++-- | /O(min n m)/ in the best case, /O(min n m * max n m)/ in the worst case.+-- The union of two maps.+-- The provided function (first argument) will be used to compute the result.+unionWith+ :: (MVector ks k, MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => (v -> v -> v)+ -> Dictionary (PrimState m) ks k vs v+ -> Dictionary (PrimState m) ks k vs v+ -> m (Dictionary (PrimState m) ks k vs v)+unionWith f = unionWithKey (const f)++{-# INLINE unionWith #-}++-- | /O(min n m)/ in the best case, /O(min n m * max n m)/ in the worst case.+-- The union of two maps.+-- If a key occurs in both maps,+-- the provided function (first argument) will be used to compute the result.+unionWithKey+ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => (k -> v -> v -> v)+ -> Dictionary (PrimState m) ks k vs v+ -> Dictionary (PrimState m) ks k vs v+ -> m (Dictionary (PrimState m) ks k vs v)+unionWithKey f t1 t2 = do+ l1 <- length t1+ l2 <- length t2+ let smallest = min l1 l2+ greatest = max l1 l2+ g k v1 v2 = if smallest == l1 then f k v1 v2 else f k v2 v1+ (tS, tG) = if smallest == l1 then (t1, t2) else (t2, t1)+ ht <- clone tG+ dictG <- readMutVar . getDRef $ tG+ dictS <- readMutVar . getDRef $ tS+ hcsS <- A.freeze . hashCode $ dictS+ let indices = catMaybes . zipWith collect [0 ..] . take smallest . A.primArrayToList $ hcsS+ collect i _ | hcsS !. i >= 0 = Just i+ | otherwise = Nothing++ go !i = do+ k <- key dictS !~ i+ v <- value dictS !~ i+ let+ hashCode' = hash k .&. mask+ targetBucket = hashCode' `rem` A.length (buckets dictG)++ onFound dict i = do+ d@Dictionary{..} <- readMutVar . getDRef $ dict+ vG <- value !~ i+ insertWithIndex targetBucket hashCode' k (g k v vG) (getDRef dict) d i++ onNothing dict = do+ d@Dictionary{..} <- readMutVar . getDRef $ dict+ insertWithIndex targetBucket hashCode' k v (getDRef dict) d+ =<< buckets ! targetBucket++ void $ atWithOrElse ht k onFound onNothing+ mapM_ go indices+ return ht++{-# INLINE unionWithKey #-}++-- * Difference and intersection++-- | /O(n)/ in the best case, /O(n * m)/ in the worst case.+-- Difference of two tables. Return elements of the first table+-- not existing in the second.+difference+ :: (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v+ -> Dictionary (PrimState m) ks k vs w+ -> m (Dictionary (PrimState m) ks k vs v)+difference a b = do+ kvs <- toList a+ ht <- initialize 10+ mapM_ (go ht) kvs+ return ht+ where+ go ht (!k, !v) = do+ mv <- lookup b k+ case mv of+ Nothing -> insert ht k v+ _ -> return ()+{-# INLINE difference #-}++-- | /O(n)/ in the best case, /O(n * m)/ in the worst case.+-- Difference with a combining function. When two equal keys are+-- encountered, the combining function is applied to the values of these keys.+-- If it returns 'Nothing', the element is discarded (proper set difference). If+-- it returns (@'Just' y@), the element is updated with a new value @y@.+differenceWith+ :: (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k)+ => (v -> w -> Maybe v)+ -> Dictionary (PrimState m) ks k vs v+ -> Dictionary (PrimState m) ks k vs w+ -> m (Dictionary (PrimState m) ks k vs v)+differenceWith f a b = do+ kvs <- toList a+ ht <- initialize 10+ mapM_ (go ht) kvs+ return ht+ where+ go ht (!k, !v) = do+ mv <- lookup b k+ case mv of+ Nothing -> insert ht k v+ Just w -> maybe (return ()) (insert ht k) (f v w)+{-# INLINE differenceWith #-}++-- | /O(n)/ in the best case, /O(n * m)/ in the worst case.+-- Intersection of two maps. Return elements of the first+-- map for keys existing in the second.+intersection+ :: (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k)+ => Dictionary (PrimState m) ks k vs v+ -> Dictionary (PrimState m) ks k vs w+ -> m (Dictionary (PrimState m) ks k vs v)+intersection a b = do+ kvs <- toList a+ ht <- initialize 10+ mapM_ (go ht) kvs+ return ht+ where+ go ht (!k, !v) = do+ mv <- lookup b k+ case mv of+ Nothing -> return ()+ Just _ -> insert ht k v+{-# INLINE intersection #-}++-- | Intersection of two maps. If a key occurs in both maps+-- the provided function is used to combine the values from the two+-- maps.+intersectionWith+ :: (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k)+ => (v1 -> v2 -> v3)+ -> Dictionary (PrimState m) ks k vs v1+ -> Dictionary (PrimState m) ks k vs v2+ -> m (Dictionary (PrimState m) ks k vs v3)+intersectionWith f a b = do+ kvs <- toList a+ ht <- initialize 10+ mapM_ (go ht) kvs+ return ht+ where+ go ht (!k, !v) = do+ mv <- lookup b k+ case mv of+ Nothing -> return ()+ Just w -> insert ht k (f v w)+{-# INLINE intersectionWith #-}++-- | Intersection of two maps. If a key occurs in both maps+-- the provided function is used to combine the values from the two+-- maps.+intersectionWithKey+ :: (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k)+ => (k -> v1 -> v2 -> v3)+ -> Dictionary (PrimState m) ks k vs v1+ -> Dictionary (PrimState m) ks k vs v2+ -> m (Dictionary (PrimState m) ks k vs v3)+intersectionWithKey f a b = do+ kvs <- toList a+ ht <- initialize 10+ mapM_ (go ht) kvs+ return ht+ where+ go ht (!k, !v) = do+ mv <- lookup b k+ case mv of+ Nothing -> return ()+ Just w -> insert ht k (f k v w)+{-# INLINE intersectionWithKey #-}++-- * List conversions++-- | /O(n)/ Convert list to a 'Dictionary'. +fromList+ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => [(k, v)] -> m (Dictionary (PrimState m) ks k vs v)+fromList kv = do+ ht <- initialize 1+ mapM_ (uncurry (insert ht)) kv+ return ht++{-# INLINE fromList #-}++-- | /O(n)/ Convert 'Dictionary' to a list.+toList+ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)+ => (Dictionary (PrimState m) ks k vs v) -> m [(k, v)]+toList DRef {..} = do+ Dictionary {..} <- readMutVar getDRef+ hcs <- A.freeze hashCode+ count <- refs ! getCount+ let go !i xs+ | i < 0 = return xs+ | hcs !. i < 0 = go (i - 1) xs+ | otherwise = do+ k <- key !~ i+ v <- value !~ i+ go (i - 1) ((k, v) : xs)+ {-# INLINE go #-}+ go (count - 1) []+{-# INLINE toList #-}++-- * Extras++primes :: UI.Vector Int+primes = UI.fromList [+ 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631,+ 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143,+ 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363,+ 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897,+ 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471,+ 7199369, 8639249, 10367101, 12440537, 14928671, 17914409, 21497293, 25796759, 30956117,+ 37147349, 44576837, 53492207, 64190669, 77028803, 92434613, 110921543, 133105859, 159727031,+ 191672443, 230006941, 276008387, 331210079, 397452101, 476942527, 572331049, 686797261,+ 824156741, 988988137, 1186785773, 1424142949, 1708971541, 2050765853 ]++getPrime :: Int -> Int+getPrime n = fromJust $ UI.find (>= n) primes
+ test/Data/Vector/HashTablesSpec.hs view
@@ -0,0 +1,417 @@+{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE DerivingStrategies #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE InstanceSigs #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE RecordWildCards #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE StandaloneDeriving #-}+{-# LANGUAGE TypeApplications #-}+{-# LANGUAGE TypeFamilies #-}+module Data.Vector.HashTablesSpec where++import Control.Monad.Primitive+import Data.Hashable (Hashable (hashWithSalt))+import qualified Data.List as L+import Data.Primitive.MutVar+import Data.Proxy (Proxy (..))+import qualified Data.Set as Set+import Data.Vector.Generic (Mutable, Vector)+import qualified Data.Vector.Generic as VI+import Data.Vector.Generic.Mutable (MVector)+import qualified Data.Vector.Mutable as M+import qualified Data.Vector.Storable.Mutable as SM+import qualified Data.Vector.Unboxed as U+import qualified Data.Vector.Unboxed.Mutable as UM+import GHC.Generics (Generic)+import Test.Hspec.QuickCheck (modifyMaxSuccess)+import Test.QuickCheck (Arbitrary (..), Gen,+ NonNegative (..),+ Positive (..), Property,+ choose, elements, forAll,+ generate, property, shuffle,+ vector)++import Test.Hspec (Spec, describe, errorCall, it,+ shouldBe, shouldThrow)++import qualified Data.Vector.Hashtables.Internal as VH++newtype AlwaysCollide = AC Int+ deriving newtype (Arbitrary, SM.Storable, Num, Eq, Ord, Show)+ deriving stock Generic++instance Hashable AlwaysCollide where+ hashWithSalt _ _ = 1++listN :: Int -> Gen [(Int, Int)]+listN n = do+ keys <- vector n+ vals <- vector n+ let keys' = Set.toList (Set.fromList keys)+ return (zip keys' vals)++shuffledListN :: Int -> Gen ([(Int, Int)], [(Int, Int)])+shuffledListN n = do+ testData <- listN n+ shuffledTestData <- shuffle testData+ return (testData, shuffledTestData)++listsForRemoveN :: Int -> Gen ([(Int, Int)], [Int])+listsForRemoveN n = do+ testData <- listN n+ dropCount <- min (n - 1) <$> choose (1, n)+ let deleteData = fst <$> take dropCount testData+ return (testData, deleteData)++twoListsN :: Int -> Gen ([(Int, Int)], [(Int, Int)])+twoListsN n = do+ list1 <- listN n+ list2 <- listN n+ return (list1, list2)++spec :: Spec+spec = mutableSpec+ *> storableMutableSpec+ *> storableKeysSpec+ *> unboxedKeysSpec++class HashTableTest ks vs where++ specDescription :: Proxy ks -> Proxy vs -> String++ testInit :: Proxy ks -> Proxy vs -> Int -> IO (VH.Dictionary (PrimState IO) ks Int vs Int)++ testInsert :: (VH.Dictionary (PrimState IO) ks Int vs Int) -> Int -> Int -> IO ()++ testAt :: (VH.Dictionary (PrimState IO) ks Int vs Int) -> Int -> IO Int++ testAt' :: (VH.Dictionary (PrimState IO) ks Int vs Int) -> Int -> IO (Maybe Int)++ testDelete :: (VH.Dictionary (PrimState IO) ks Int vs Int) -> Int -> IO ()++ testInitCollide+ :: Proxy ks+ -> Proxy vs+ -> Int+ -> IO (VH.Dictionary (PrimState IO) ks AlwaysCollide vs Int)++ testInsertCollide+ :: (VH.Dictionary (PrimState IO) ks AlwaysCollide vs Int) -> AlwaysCollide -> Int -> IO ()++ testAtCollide+ :: (VH.Dictionary (PrimState IO) ks AlwaysCollide vs Int) -> AlwaysCollide -> IO Int++ testFromList+ :: Proxy ks -> Proxy vs -> [(Int, Int)] -> IO (VH.Dictionary (PrimState IO) ks Int vs Int)++ testToList :: VH.Dictionary (PrimState IO) ks Int vs Int -> IO [(Int, Int)]++ testLength :: VH.Dictionary (PrimState IO) ks Int vs Int -> IO Int++ testNull :: VH.Dictionary (PrimState IO) ks Int vs Int -> IO Bool++ testMember :: VH.Dictionary (PrimState IO) ks Int vs Int -> Int -> IO Bool++ testAlter :: VH.Dictionary (PrimState IO) ks Int vs Int -> (Maybe Int -> Maybe Int) -> Int -> IO ()++ testUnion+ :: VH.Dictionary (PrimState IO) ks Int vs Int+ -> VH.Dictionary (PrimState IO) ks Int vs Int+ -> IO (VH.Dictionary (PrimState IO) ks Int vs Int)++ testDifference+ :: VH.Dictionary (PrimState IO) ks Int vs Int+ -> VH.Dictionary (PrimState IO) ks Int vs Int+ -> IO (VH.Dictionary (PrimState IO) ks Int vs Int)++ testIntersection+ :: VH.Dictionary (PrimState IO) ks Int vs Int+ -> VH.Dictionary (PrimState IO) ks Int vs Int+ -> IO (VH.Dictionary (PrimState IO) ks Int vs Int)++mkSpec+ :: forall ks vs. (HashTableTest ks vs)+ => Proxy ks -> Proxy vs -> Spec+mkSpec ksp vsp = describe (specDescription ksp vsp) $+ modifyMaxSuccess (const 1000) $ do+ it "lookup for inserted value at specific index returns value" $+ property prop_insertLookup++ it "lookup for inserted value at specific index returns nothing" $+ property prop_insertLookupNothing++ it "lookup for inserted value at specific index throws error" $+ property prop_insertLookupError++ it "lookup for updated value at specific index returns updated value" $+ property prop_insertUpdateLookup++ it "lookup for deleted value at specific index returns nothing" $+ property prop_insertDeleteLookupNothing++ it "lookup for deleted value at specific index throws error" $+ property prop_insertDeleteLookupError++ it "table size increases when multiple elements added" $+ property prop_insertMultipleElements++ it "lookup for inserted value with hash collision returns value" $+ property prop_insertLookupHashCollisions++ it "fromList . toList === id" $ property prop_fromListToList++ it "deleted entries are not present in key-value list after deleting from hashtable" $+ property prop_insertDeleteKeysSize++ it "new table is null" $ property prop_newIsNull++ it "non-empty table is not null" $ property prop_fromListIsNotNull++ it "inserted key is table member" $ property prop_isMember++ it "deleted key is not a member" $ property prop_isNotMember++ it "when altering is nothing - key deleted from table" $ property prop_alterDelete++ it "when altering is just a result - key updated with result" $ property prop_alterUpdate+ it "intersection + symmetric difference of two tables is equal to union of two tables" $ property prop_union++ where+ prop_insertLookup+ :: HashTableTest ks vs => (Int, Int) -> IO ()+ prop_insertLookup (x, y) = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 10+ testInsert ht x y+ v <- testAt ht x+ v `shouldBe` y++ prop_insertLookupNothing :: HashTableTest ks vs => (Int, Int) -> IO ()+ prop_insertLookupNothing (x, y) = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 10+ testInsert ht (x + 1) y+ v <- testAt' ht x+ v `shouldBe` Nothing++ prop_insertLookupError :: HashTableTest ks vs => (Int, Int) -> IO ()+ prop_insertLookupError (x, y) = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 10+ testInsert ht (x + 1) y+ testAt ht x `shouldThrow` errorCall "KeyNotFoundException!"++ prop_insertUpdateLookup :: HashTableTest ks vs => (Int, Int) -> IO ()+ prop_insertUpdateLookup (x, y) = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 10+ testInsert ht x y+ testInsert ht x (y + 1)+ v <- testAt ht x+ v `shouldBe` (y + 1)++ prop_insertDeleteLookupNothing :: HashTableTest ks vs => (Int, Int) -> IO ()+ prop_insertDeleteLookupNothing (x, y) = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 10+ testInsert ht x y+ testDelete ht x+ v <- testAt' ht x+ v `shouldBe` Nothing++ prop_insertDeleteLookupError :: HashTableTest ks vs => (Int, Int) -> IO ()+ prop_insertDeleteLookupError (x, y) = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 10+ testInsert ht 0 1+ testDelete ht 0+ testAt ht 0 `shouldThrow` errorCall "KeyNotFoundException!"++ prop_insertMultipleElements+ :: HashTableTest ks vs+ => (NonNegative Int) -> Property+ prop_insertMultipleElements (NonNegative n) = forAll (listN n) $ \xs -> do+ ht <- testInit (Proxy @ks) (Proxy @vs) 2+ mapM_ (uncurry (testInsert ht)) xs+ htl <- testLength ht+ htl `shouldBe` (length . Set.toList . Set.fromList) (fst <$> xs)++ prop_insertLookupHashCollisions+ :: HashTableTest ks vs => (AlwaysCollide, Int) -> (AlwaysCollide, Int) -> IO ()+ prop_insertLookupHashCollisions (x1, y1) (x2, y2) = do+ ht <- testInitCollide (Proxy @ks) (Proxy @vs) 10+ let x2' = if x1 /= x2 then x2 else x2 + 1+ testInsertCollide ht x1 y1+ testInsertCollide ht x2' y2+ v <- testAtCollide ht x1+ v `shouldBe` y1++ prop_fromListToList :: NonNegative Int -> Property+ prop_fromListToList (NonNegative n) = forAll (shuffledListN n) $ \(xs, ys) -> do+ ht <- testFromList (Proxy @ks) (Proxy @vs) xs+ xs' <- testToList ht+ L.sort xs' `shouldBe` L.sort ys++ prop_insertDeleteKeysSize :: NonNegative Int -> Property+ prop_insertDeleteKeysSize (NonNegative n) = forAll (listsForRemoveN n) go+ where+ go (insertData, deleteData) = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 2+ mapM_ (uncurry (testInsert ht)) insertData+ mapM_ (testDelete ht) deleteData+ kvs <- testToList ht+ L.length insertData - L.length deleteData `shouldBe` L.length kvs++ prop_newIsNull :: IO ()+ prop_newIsNull = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 2+ result <- testNull ht+ result `shouldBe` True++ prop_fromListIsNotNull :: Positive Int -> Property+ prop_fromListIsNotNull (Positive n) = forAll (listN n) $ \xs -> do+ ht <- testFromList (Proxy @ks) (Proxy @vs) xs+ result <- testNull ht+ result `shouldBe` False++ prop_isMember :: HashTableTest ks vs => (Int, Int) -> IO ()+ prop_isMember (x, y) = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 10+ testInsert ht x y+ v <- testMember ht x+ v `shouldBe` True++ prop_isNotMember :: HashTableTest ks vs => (Int, Int) -> IO ()+ prop_isNotMember (x, y) = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 10+ testInsert ht x y+ testDelete ht x+ v <- testMember ht x+ v `shouldBe` False++ prop_alterDelete :: HashTableTest ks vs => (Int, Int) -> IO ()+ prop_alterDelete (x, y) = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 10+ testInsert ht x y+ testAlter ht (const Nothing) x+ v <- testMember ht x+ v `shouldBe` False++ prop_alterUpdate :: HashTableTest ks vs => (Int, Int) -> IO ()+ prop_alterUpdate (x, y) = do+ ht <- testInit (Proxy @ks) (Proxy @vs) 10+ testInsert ht x y+ testAlter ht (fmap negate) x+ v <- testAt ht x+ v `shouldBe` (negate y)++ prop_union :: Positive Int -> Property+ prop_union (Positive n) = forAll (twoListsN n) $ \(xs, ys) -> do+ ht1 <- testFromList (Proxy @ks) (Proxy @vs) xs+ ht2 <- testFromList (Proxy @ks) (Proxy @vs) ys+ u1 <- testUnion ht1 ht2+ d1 <- testDifference ht1 ht2+ d2 <- testDifference ht2 ht1+ i <- testIntersection ht1 ht2++ res <- do+ u2 <- testUnion d1 d2+ testUnion i u2++ resultList <- testToList res+ unionList <- testToList u1++ Set.fromList resultList `shouldBe` Set.fromList unionList+++instance HashTableTest M.MVector M.MVector where+ specDescription _ _ = "Data.Vector.HashTables.Mutable keys and values"+ testInit _ _ n = VH.initialize n+ testInitCollide _ _ n = VH.initialize n+ testInsert = VH.insert+ testAt = VH.at+ testAt' = VH.at'+ testDelete = VH.delete+ testInsertCollide = VH.insert+ testAtCollide = VH.at+ testLength = VH.length+ testFromList _ _ = VH.fromList+ testToList = VH.toList+ testNull = VH.null+ testMember = VH.member+ testAlter = VH.alter+ testUnion = VH.union+ testDifference = VH.difference+ testIntersection = VH.intersection++mutableSpec :: Spec+mutableSpec = mkSpec (Proxy :: Proxy M.MVector) (Proxy :: Proxy M.MVector)+++instance HashTableTest SM.MVector SM.MVector where+ specDescription _ _ = "Data.Vector.HashTables.Storable.Mutable keys and values"+ testInit _ _ n = VH.initialize n+ testInitCollide _ _ n = VH.initialize n+ testInsert = VH.insert+ testAt = VH.at+ testAt' = VH.at'+ testDelete = VH.delete+ testInsertCollide = VH.insert+ testAtCollide = VH.at+ testLength = VH.length+ testFromList _ _ = VH.fromList+ testToList = VH.toList+ testNull = VH.null+ testMember = VH.member+ testAlter = VH.alter+ testUnion = VH.union+ testDifference = VH.difference+ testIntersection = VH.intersection++storableMutableSpec :: Spec+storableMutableSpec = mkSpec (Proxy @SM.MVector) (Proxy @SM.MVector)+++instance HashTableTest SM.MVector M.MVector where+ specDescription _ _ = "Data.Vector.HashTables.Mutable keys and Data.Vector.HashTables.Storable.Mutable values"+ testInit _ _ n = VH.initialize n+ testInitCollide _ _ n = VH.initialize n+ testInsert = VH.insert+ testAt = VH.at+ testAt' = VH.at'+ testDelete = VH.delete+ testInsertCollide = VH.insert+ testAtCollide = VH.at+ testLength = VH.length+ testFromList _ _ = VH.fromList+ testToList = VH.toList+ testNull = VH.null+ testMember = VH.member+ testAlter = VH.alter+ testUnion = VH.union+ testDifference = VH.difference+ testIntersection = VH.intersection++storableKeysSpec :: Spec+storableKeysSpec = mkSpec (Proxy @SM.MVector) (Proxy @M.MVector)+++instance HashTableTest M.MVector UM.MVector where+ specDescription _ _ = "Data.Vector.HashTables.Mutable keys and Data.Vector.HashTables.Unboxed.Mutable values"+ testInit _ _ n = VH.initialize n+ testInitCollide _ _ n = VH.initialize n+ testInsert = VH.insert+ testAt = VH.at+ testAt' = VH.at'+ testDelete = VH.delete+ testInsertCollide = VH.insert+ testAtCollide = VH.at+ testLength = VH.length+ testFromList _ _ = VH.fromList+ testToList = VH.toList+ testNull = VH.null+ testMember = VH.member+ testAlter = VH.alter+ testUnion = VH.union+ testDifference = VH.difference+ testIntersection = VH.intersection++unboxedKeysSpec :: Spec+unboxedKeysSpec = mkSpec (Proxy @M.MVector) (Proxy @UM.MVector)
+ test/Spec.hs view
@@ -0,0 +1,1 @@+{-# OPTIONS_GHC -F -pgmF hspec-discover #-}
+ vector-hashtables.cabal view
@@ -0,0 +1,89 @@+name: vector-hashtables+version: 0.1.0.0+synopsis: 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.+homepage: https://github.com/klapaucius/vector-hashtables#readme+license: BSD3+license-file: LICENSE+author: klapaucius+maintainer: klapaucius, swamp_agr+copyright: 2016-2021 klapaucius, swamp_agr+category: Data+build-type: Simple+extra-source-files: README.md,+ src-i386/Data/Vector/Hashtables/Internal/Mask.hs,+ src-gen/Data/Vector/Hashtables/Internal/Mask.hs,+ changelog.md+cabal-version: >=1.10++library+ if arch(i386)+ hs-source-dirs: src, src-i386+ else+ hs-source-dirs: src, src-gen+ exposed-modules: Data.Vector.Hashtables,+ Data.Vector.Hashtables.Internal,+ Data.Vector.Hashtables.Internal.Mask,+ Data.Primitive.PrimArray.Utils+ ghc-options: -O2+ build-depends: base >= 4.7 && < 5+ , primitive+ , vector+ , hashable+ default-language: Haskell2010++executable bench1+ hs-source-dirs: exe1+ main-is: Main.hs+ ghc-options: -O2 -rtsopts+ build-depends: base+ , vector-hashtables+ , vector+ , primitive+ , hashtables+ , unordered-containers+ default-language: Haskell2010++benchmark vector-hashtables-bench+ type: exitcode-stdio-1.0+ hs-source-dirs: bench+ main-is: Main.hs+ ghc-options: -O2 -rtsopts+ build-depends: base+ , vector-hashtables+ , vector+ , primitive+ , criterion+ , hashtables+ , unordered-containers+ default-language: Haskell2010++test-suite vector-hashtables-test+ type: exitcode-stdio-1.0+ hs-source-dirs: test+ main-is: Spec.hs+ ghc-options: -threaded -rtsopts -with-rtsopts=-N+ default-language: Haskell2010+ other-modules: Data.Vector.HashTablesSpec+ build-depends: base+ , primitive+ , containers+ , hashable+ , vector+ , vector-hashtables++ -- Additional dependencies+ build-depends:+ hspec >= 2.6.0 && < 2.8+ , QuickCheck >= 2.12.6.1 && < 2.15+ , quickcheck-instances >= 0.3.19 && < 0.4++ build-tool-depends:+ hspec-discover:hspec-discover >= 2.6.0 && < 2.8++source-repository head+ type: git+ location: https://github.com/klapaucius/vector-hashtables