Lookup existing
Tries to find all existing keys in a random Map of size N.
Note that the table contains the overall times for looking up all keys, but the plot shows the average lookup time per element.
Using Intrinsics and some other micro-optimizations.
BenchmarkDotNet=v0.11.5, OS=Windows 10.0.17763.805 (1809/October2018Update/Redstone5)
AMD Ryzen Threadripper 2950X, 1 CPU, 32 logical and 16 physical cores
.NET Core SDK=3.0.100
[Host] : .NET Core 2.1.13 (CoreCLR 4.6.28008.01, CoreFX 4.6.28008.01), 64bit RyuJIT DEBUG
Job-PHBEOK : .NET Core 2.1.13 (CoreCLR 4.6.28008.01, CoreFX 4.6.28008.01), 64bit RyuJIT
MaxIterationCount=100
| Method | N | Mean | Error | StdDev | Gen 0 | Gen 1 | Gen 2 | Allocated |
|---|---|---|---|---|---|---|---|---|
| HashMapOkasaki_containsKey | 10 | 209.8 ns | 4.512 ns | 13.30 ns | - | - | - | - |
| ImTools_containsKey | 10 | 274.8 ns | 6.575 ns | 19.28 ns | 0.9151 | - | - | 720 B |
| FSharpMap_containsKey | 10 | 401.3 ns | 9.183 ns | 27.08 ns | - | - | - | - |
| HAMT_containsKey | 10 | 352.8 ns | 7.757 ns | 22.87 ns | - | - | - | - |
| FSharpX_containsKey | 10 | 1,439.3 ns | 31.648 ns | 93.32 ns | 1.2188 | - | - | 960 B |
| ImmutableDictionary_containsKey | 10 | 258.8 ns | 7.677 ns | 22.64 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 20 | 524.5 ns | 15.105 ns | 44.30 ns | - | - | - | - |
| ImTools_containsKey | 20 | 419.7 ns | 8.910 ns | 26.27 ns | 1.8306 | - | - | 1440 B |
| FSharpMap_containsKey | 20 | 1,116.5 ns | 29.183 ns | 86.05 ns | - | - | - | - |
| HAMT_containsKey | 20 | 1,095.9 ns | 27.251 ns | 79.92 ns | - | - | - | - |
| FSharpX_containsKey | 20 | 2,981.5 ns | 72.629 ns | 214.15 ns | 2.4376 | - | - | 1920 B |
| ImmutableDictionary_containsKey | 20 | 523.2 ns | 14.455 ns | 42.62 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 30 | 992.1 ns | 25.175 ns | 74.23 ns | - | - | - | - |
| ImTools_containsKey | 30 | 673.0 ns | 15.913 ns | 46.92 ns | 2.7456 | - | - | 2160 B |
| FSharpMap_containsKey | 30 | 1,811.4 ns | 36.109 ns | 98.24 ns | - | - | - | - |
| HAMT_containsKey | 30 | 1,719.9 ns | 34.166 ns | 94.67 ns | - | - | - | - |
| FSharpX_containsKey | 30 | 4,210.3 ns | 121.134 ns | 357.17 ns | 3.6545 | - | - | 2880 B |
| ImmutableDictionary_containsKey | 30 | 841.8 ns | 16.726 ns | 40.39 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 40 | 1,568.0 ns | 33.607 ns | 98.56 ns | - | - | - | - |
| ImTools_containsKey | 40 | 951.6 ns | 28.984 ns | 85.00 ns | 3.6602 | - | - | 2880 B |
| FSharpMap_containsKey | 40 | 2,785.7 ns | 69.206 ns | 202.97 ns | - | - | - | - |
| HAMT_containsKey | 40 | 2,522.1 ns | 63.894 ns | 188.39 ns | - | - | - | - |
| FSharpX_containsKey | 40 | 5,301.9 ns | 130.688 ns | 381.22 ns | 4.8752 | - | - | 3840 B |
| ImmutableDictionary_containsKey | 40 | 1,234.3 ns | 31.573 ns | 93.09 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 50 | 1,826.3 ns | 46.197 ns | 136.21 ns | - | - | - | - |
| ImTools_containsKey | 50 | 1,184.0 ns | 32.692 ns | 95.36 ns | 4.5757 | - | - | 3600 B |
| FSharpMap_containsKey | 50 | 3,486.5 ns | 70.643 ns | 207.18 ns | - | - | - | - |
| HAMT_containsKey | 50 | 3,354.5 ns | 67.132 ns | 193.69 ns | - | - | - | - |
| FSharpX_containsKey | 50 | 6,849.3 ns | 132.026 ns | 340.80 ns | 6.0959 | - | - | 4800 B |
| ImmutableDictionary_containsKey | 50 | 1,596.8 ns | 33.654 ns | 99.23 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 100 | 4,766.3 ns | 126.720 ns | 369.65 ns | - | - | - | - |
| ImTools_containsKey | 100 | 2,696.7 ns | 58.462 ns | 172.38 ns | 9.1515 | - | - | 7200 B |
| FSharpMap_containsKey | 100 | 8,025.8 ns | 223.440 ns | 658.82 ns | - | - | - | - |
| HAMT_containsKey | 100 | 8,406.4 ns | 224.175 ns | 660.98 ns | - | - | - | - |
| FSharpX_containsKey | 100 | 13,742.4 ns | 286.694 ns | 840.82 ns | 12.1918 | - | - | 9600 B |
| ImmutableDictionary_containsKey | 100 | 4,201.2 ns | 102.994 ns | 300.44 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 200 | 11,018.0 ns | 237.073 ns | 695.29 ns | - | - | - | - |
| ImTools_containsKey | 200 | 6,982.3 ns | 139.617 ns | 382.20 ns | 18.3029 | - | - | 14400 B |
| FSharpMap_containsKey | 200 | 18,538.9 ns | 686.294 ns | 1,969.11 ns | - | - | - | - |
| HAMT_containsKey | 200 | 20,259.0 ns | 470.869 ns | 1,373.55 ns | - | - | - | - |
| FSharpX_containsKey | 200 | 31,296.7 ns | 623.223 ns | 1,540.45 ns | 24.3835 | - | - | 19200 B |
| ImmutableDictionary_containsKey | 200 | 9,627.9 ns | 220.835 ns | 651.14 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 300 | 16,592.4 ns | 472.866 ns | 1,386.83 ns | - | - | - | - |
| ImTools_containsKey | 300 | 11,545.9 ns | 236.069 ns | 696.05 ns | 27.4506 | - | - | 21600 B |
| FSharpMap_containsKey | 300 | 29,445.9 ns | 586.953 ns | 1,546.27 ns | - | - | - | - |
| HAMT_containsKey | 300 | 30,922.5 ns | 882.285 ns | 2,601.44 ns | - | - | - | - |
| FSharpX_containsKey | 300 | 46,687.1 ns | 1,042.302 ns | 3,056.89 ns | 36.5601 | - | - | 28800 B |
| ImmutableDictionary_containsKey | 300 | 14,851.9 ns | 398.426 ns | 1,168.51 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 400 | 24,814.1 ns | 493.582 ns | 1,308.91 ns | - | - | - | - |
| ImTools_containsKey | 400 | 16,637.9 ns | 409.190 ns | 1,193.63 ns | 36.5906 | - | - | 28800 B |
| FSharpMap_containsKey | 400 | 40,058.5 ns | 1,128.577 ns | 3,327.63 ns | - | - | - | - |
| HAMT_containsKey | 400 | 39,264.8 ns | 868.736 ns | 2,547.85 ns | - | - | - | - |
| FSharpX_containsKey | 400 | 61,770.3 ns | 1,254.512 ns | 3,370.17 ns | 48.7671 | - | - | 38400 B |
| ImmutableDictionary_containsKey | 400 | 20,484.3 ns | 446.148 ns | 1,315.48 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 500 | 31,710.8 ns | 730.464 ns | 2,142.32 ns | - | - | - | - |
| ImTools_containsKey | 500 | 20,530.0 ns | 501.823 ns | 1,479.64 ns | 45.7458 | - | - | 36000 B |
| FSharpMap_containsKey | 500 | 53,433.8 ns | 1,053.899 ns | 2,005.15 ns | - | - | - | - |
| HAMT_containsKey | 500 | 50,423.1 ns | 1,008.434 ns | 2,743.52 ns | - | - | - | - |
| FSharpX_containsKey | 500 | 78,794.1 ns | 1,614.115 ns | 4,733.92 ns | 60.9131 | - | - | 48000 B |
| ImmutableDictionary_containsKey | 500 | 26,334.3 ns | 743.551 ns | 2,192.38 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 1000 | 70,900.5 ns | 1,677.150 ns | 4,945.11 ns | - | - | - | - |
| ImTools_containsKey | 1000 | 46,975.8 ns | 938.875 ns | 2,585.94 ns | 91.4917 | - | - | 72000 B |
| FSharpMap_containsKey | 1000 | 117,037.4 ns | 2,320.289 ns | 4,791.80 ns | - | - | - | - |
| HAMT_containsKey | 1000 | 120,849.4 ns | 2,402.735 ns | 5,223.35 ns | - | - | - | - |
| FSharpX_containsKey | 1000 | 149,282.5 ns | 3,349.525 ns | 9,770.72 ns | 121.8262 | - | - | 96000 B |
| ImmutableDictionary_containsKey | 1000 | 56,056.9 ns | 1,117.707 ns | 2,232.18 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 2000 | 146,877.9 ns | 3,622.260 ns | 10,680.32 ns | - | - | - | - |
| ImTools_containsKey | 2000 | 98,242.3 ns | 2,133.749 ns | 6,224.25 ns | 182.9834 | - | - | 144000 B |
| FSharpMap_containsKey | 2000 | 255,113.1 ns | 5,467.528 ns | 16,035.31 ns | - | - | - | - |
| HAMT_containsKey | 2000 | 265,605.1 ns | 5,854.346 ns | 17,077.40 ns | - | - | - | - |
| FSharpX_containsKey | 2000 | 302,973.2 ns | 6,507.526 ns | 19,187.59 ns | 243.6523 | - | - | 192000 B |
| ImmutableDictionary_containsKey | 2000 | 114,954.1 ns | 2,274.683 ns | 5,040.54 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 3000 | 225,230.4 ns | 4,617.624 ns | 12,325.37 ns | - | - | - | - |
| ImTools_containsKey | 3000 | 156,401.4 ns | 3,109.163 ns | 8,511.28 ns | 274.4141 | - | - | 216000 B |
| FSharpMap_containsKey | 3000 | 402,440.9 ns | 8,034.077 ns | 18,134.25 ns | - | - | - | - |
| HAMT_containsKey | 3000 | 406,041.8 ns | 8,058.912 ns | 21,088.77 ns | - | - | - | - |
| FSharpX_containsKey | 3000 | 466,333.5 ns | 10,042.129 ns | 19,347.77 ns | 365.7227 | - | - | 288000 B |
| ImmutableDictionary_containsKey | 3000 | 181,829.8 ns | 3,760.979 ns | 10,911.28 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 4000 | 300,200.8 ns | 6,128.161 ns | 17,483.99 ns | - | - | - | - |
| ImTools_containsKey | 4000 | 210,989.7 ns | 4,200.285 ns | 10,460.17 ns | 365.9668 | - | - | 288000 B |
| FSharpMap_containsKey | 4000 | 569,026.1 ns | 14,146.256 ns | 40,815.18 ns | - | - | - | - |
| HAMT_containsKey | 4000 | 547,745.5 ns | 11,782.902 ns | 34,557.21 ns | - | - | - | - |
| FSharpX_containsKey | 4000 | 623,073.0 ns | 14,348.748 ns | 42,307.61 ns | 487.3047 | - | - | 384000 B |
| ImmutableDictionary_containsKey | 4000 | 239,181.8 ns | 5,730.266 ns | 16,715.45 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 5000 | 393,884.2 ns | 7,864.453 ns | 18,842.73 ns | - | - | - | - |
| ImTools_containsKey | 5000 | 280,760.2 ns | 6,257.065 ns | 18,350.89 ns | 457.5195 | - | - | 360000 B |
| FSharpMap_containsKey | 5000 | 711,643.7 ns | 14,430.885 ns | 42,323.29 ns | - | - | - | - |
| HAMT_containsKey | 5000 | 711,704.3 ns | 14,367.559 ns | 38,100.73 ns | - | - | - | - |
| FSharpX_containsKey | 5000 | 803,307.1 ns | 16,061.753 ns | 36,904.55 ns | 609.3750 | - | - | 480000 B |
| ImmutableDictionary_containsKey | 5000 | 300,036.9 ns | 5,981.962 ns | 17,163.37 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 10000 | 806,343.3 ns | 16,099.052 ns | 35,337.81 ns | - | - | - | - |
| ImTools_containsKey | 10000 | 569,193.7 ns | 14,261.510 ns | 41,826.54 ns | 915.0391 | - | - | 720000 B |
| FSharpMap_containsKey | 10000 | 1,544,110.9 ns | 30,572.430 ns | 76,135.96 ns | - | - | - | - |
| HAMT_containsKey | 10000 | 1,591,187.3 ns | 31,290.407 ns | 69,337.38 ns | - | - | - | - |
| FSharpX_containsKey | 10000 | 1,958,385.4 ns | 49,549.289 ns | 144,537.60 ns | 1218.7500 | - | - | 960000 B |
| ImmutableDictionary_containsKey | 10000 | 626,855.2 ns | 12,651.837 ns | 36,906.00 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 20000 | 1,660,455.3 ns | 32,801.737 ns | 67,741.28 ns | - | - | - | - |
| ImTools_containsKey | 20000 | 1,189,375.6 ns | 25,138.178 ns | 74,120.49 ns | 1830.0781 | - | - | 1440000 B |
| FSharpMap_containsKey | 20000 | 3,368,456.1 ns | 67,033.165 ns | 135,410.30 ns | - | - | - | - |
| HAMT_containsKey | 20000 | 3,398,435.7 ns | 67,878.500 ns | 175,216.08 ns | - | - | - | - |
| FSharpX_containsKey | 20000 | 4,422,207.9 ns | 109,991.526 ns | 322,586.11 ns | 2437.5000 | - | - | 1920000 B |
| ImmutableDictionary_containsKey | 20000 | 1,294,252.7 ns | 25,881.087 ns | 68,632.97 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 30000 | 2,564,359.8 ns | 51,783.811 ns | 152,685.73 ns | - | - | - | - |
| ImTools_containsKey | 30000 | 1,895,216.8 ns | 38,689.591 ns | 113,469.87 ns | 2746.0938 | - | - | 2160000 B |
| FSharpMap_containsKey | 30000 | 5,235,760.8 ns | 103,564.796 ns | 276,435.41 ns | - | - | - | - |
| HAMT_containsKey | 30000 | 5,249,754.1 ns | 123,109.385 ns | 362,990.80 ns | - | - | - | - |
| FSharpX_containsKey | 30000 | 6,760,266.8 ns | 134,543.614 ns | 361,442.68 ns | 3656.2500 | - | - | 2880000 B |
| ImmutableDictionary_containsKey | 30000 | 2,010,969.4 ns | 47,732.844 ns | 140,741.37 ns | - | - | - | - |