Lookup nonexisting
Tries to find N random keys that are not contained 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.
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 | 142.0 ns | 3.544 ns | 10.450 ns | - | - | - | - |
| ImTools_containsKey | 10 | 111.2 ns | 2.236 ns | 5.358 ns | - | - | - | - |
| FSharpMap_containsKey | 10 | 496.4 ns | 14.672 ns | 43.030 ns | - | - | - | - |
| HAMT_containsKey | 10 | 213.8 ns | 4.302 ns | 10.471 ns | - | - | - | - |
| FSharpX_containsKey | 10 | 987.7 ns | 24.397 ns | 71.553 ns | 1.2188 | - | - | 960 B |
| ImmutableDictionary_containsKey | 10 | 237.0 ns | 5.102 ns | 14.722 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 20 | 381.9 ns | 7.745 ns | 16.167 ns | - | - | - | - |
| ImTools_containsKey | 20 | 377.2 ns | 7.551 ns | 21.048 ns | - | - | - | - |
| FSharpMap_containsKey | 20 | 1,192.2 ns | 28.647 ns | 84.017 ns | - | - | - | - |
| HAMT_containsKey | 20 | 669.7 ns | 15.390 ns | 45.378 ns | - | - | - | - |
| FSharpX_containsKey | 20 | 2,147.0 ns | 48.506 ns | 142.259 ns | 2.4376 | - | - | 1920 B |
| ImmutableDictionary_containsKey | 20 | 521.8 ns | 13.028 ns | 38.415 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 30 | 891.6 ns | 25.096 ns | 73.996 ns | - | - | - | - |
| ImTools_containsKey | 30 | 555.9 ns | 12.333 ns | 35.976 ns | - | - | - | - |
| FSharpMap_containsKey | 30 | 2,076.1 ns | 47.459 ns | 136.930 ns | - | - | - | - |
| HAMT_containsKey | 30 | 1,133.5 ns | 25.934 ns | 76.466 ns | - | - | - | - |
| FSharpX_containsKey | 30 | 3,201.3 ns | 63.744 ns | 166.806 ns | 3.6583 | - | - | 2880 B |
| ImmutableDictionary_containsKey | 30 | 836.6 ns | 24.153 ns | 71.215 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 40 | 1,003.1 ns | 26.510 ns | 78.166 ns | - | - | - | - |
| ImTools_containsKey | 40 | 735.0 ns | 14.627 ns | 40.775 ns | - | - | - | - |
| FSharpMap_containsKey | 40 | 3,180.0 ns | 64.307 ns | 189.610 ns | - | - | - | - |
| HAMT_containsKey | 40 | 2,208.0 ns | 50.148 ns | 144.690 ns | - | - | - | - |
| FSharpX_containsKey | 40 | 4,234.5 ns | 105.093 ns | 308.218 ns | 4.8752 | - | - | 3840 B |
| ImmutableDictionary_containsKey | 40 | 1,185.7 ns | 26.492 ns | 77.279 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 50 | 1,463.3 ns | 29.279 ns | 78.150 ns | - | - | - | - |
| ImTools_containsKey | 50 | 1,148.0 ns | 26.763 ns | 78.490 ns | - | - | - | - |
| FSharpMap_containsKey | 50 | 3,811.1 ns | 75.954 ns | 144.511 ns | - | - | - | - |
| HAMT_containsKey | 50 | 2,926.4 ns | 59.556 ns | 175.603 ns | - | - | - | - |
| FSharpX_containsKey | 50 | 5,204.3 ns | 103.294 ns | 293.028 ns | 6.0959 | - | - | 4800 B |
| ImmutableDictionary_containsKey | 50 | 1,408.3 ns | 29.160 ns | 85.060 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 100 | 3,985.9 ns | 108.617 ns | 320.259 ns | - | - | - | - |
| ImTools_containsKey | 100 | 2,428.2 ns | 51.999 ns | 151.684 ns | - | - | - | - |
| FSharpMap_containsKey | 100 | 9,095.6 ns | 181.012 ns | 528.020 ns | - | - | - | - |
| HAMT_containsKey | 100 | 7,002.7 ns | 183.127 ns | 531.285 ns | - | - | - | - |
| FSharpX_containsKey | 100 | 10,133.8 ns | 247.534 ns | 729.859 ns | 12.1918 | - | - | 9600 B |
| ImmutableDictionary_containsKey | 100 | 3,069.0 ns | 60.770 ns | 153.573 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 200 | 9,092.6 ns | 188.979 ns | 557.208 ns | - | - | - | - |
| ImTools_containsKey | 200 | 5,620.2 ns | 117.813 ns | 343.666 ns | - | - | - | - |
| FSharpMap_containsKey | 200 | 21,251.9 ns | 462.696 ns | 1,342.366 ns | - | - | - | - |
| HAMT_containsKey | 200 | 16,163.5 ns | 393.351 ns | 1,159.806 ns | - | - | - | - |
| FSharpX_containsKey | 200 | 22,276.6 ns | 462.218 ns | 1,355.606 ns | 24.3835 | - | - | 19200 B |
| ImmutableDictionary_containsKey | 200 | 6,212.1 ns | 124.242 ns | 285.466 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 300 | 13,906.7 ns | 387.713 ns | 1,143.180 ns | - | - | - | - |
| ImTools_containsKey | 300 | 9,243.2 ns | 184.586 ns | 514.553 ns | - | - | - | - |
| FSharpMap_containsKey | 300 | 32,749.8 ns | 777.927 ns | 2,293.735 ns | - | - | - | - |
| HAMT_containsKey | 300 | 26,376.3 ns | 524.616 ns | 1,344.791 ns | - | - | - | - |
| FSharpX_containsKey | 300 | 38,889.6 ns | 1,184.411 ns | 3,398.297 ns | 36.5601 | - | - | 28800 B |
| ImmutableDictionary_containsKey | 300 | 10,742.0 ns | 248.256 ns | 731.988 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 400 | 19,925.6 ns | 460.271 ns | 1,349.896 ns | - | - | - | - |
| ImTools_containsKey | 400 | 12,442.5 ns | 246.749 ns | 691.911 ns | - | - | - | - |
| FSharpMap_containsKey | 400 | 44,532.6 ns | 890.489 ns | 2,526.170 ns | - | - | - | - |
| HAMT_containsKey | 400 | 34,868.3 ns | 727.463 ns | 2,110.503 ns | - | - | - | - |
| FSharpX_containsKey | 400 | 47,283.7 ns | 939.706 ns | 2,524.459 ns | 48.7671 | - | - | 38400 B |
| ImmutableDictionary_containsKey | 400 | 15,445.4 ns | 404.707 ns | 1,193.287 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 500 | 27,502.2 ns | 539.453 ns | 1,149.617 ns | - | - | - | - |
| ImTools_containsKey | 500 | 16,773.5 ns | 397.835 ns | 1,166.781 ns | - | - | - | - |
| FSharpMap_containsKey | 500 | 61,457.2 ns | 1,922.767 ns | 5,639.141 ns | - | - | - | - |
| HAMT_containsKey | 500 | 44,566.5 ns | 885.799 ns | 2,270.641 ns | - | - | - | - |
| FSharpX_containsKey | 500 | 57,543.5 ns | 1,150.677 ns | 2,734.706 ns | 60.9741 | - | - | 48000 B |
| ImmutableDictionary_containsKey | 500 | 20,253.5 ns | 402.387 ns | 1,173.781 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 1000 | 62,196.6 ns | 1,574.463 ns | 4,592.781 ns | - | - | - | - |
| ImTools_containsKey | 1000 | 36,794.4 ns | 780.839 ns | 2,302.321 ns | - | - | - | - |
| FSharpMap_containsKey | 1000 | 127,166.5 ns | 2,526.075 ns | 5,491.479 ns | - | - | - | - |
| HAMT_containsKey | 1000 | 106,639.6 ns | 2,129.733 ns | 5,647.749 ns | - | - | - | - |
| FSharpX_containsKey | 1000 | 118,398.5 ns | 2,423.107 ns | 7,144.586 ns | 121.9482 | - | - | 96000 B |
| ImmutableDictionary_containsKey | 1000 | 49,590.2 ns | 987.781 ns | 2,478.150 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 2000 | 120,244.8 ns | 2,849.786 ns | 8,402.659 ns | - | - | - | - |
| ImTools_containsKey | 2000 | 76,179.1 ns | 1,507.039 ns | 4,125.495 ns | - | - | - | - |
| FSharpMap_containsKey | 2000 | 293,504.7 ns | 6,895.826 ns | 20,115.448 ns | - | - | - | - |
| HAMT_containsKey | 2000 | 239,418.2 ns | 4,769.662 ns | 12,140.312 ns | - | - | - | - |
| FSharpX_containsKey | 2000 | 226,247.7 ns | 4,460.707 ns | 10,426.759 ns | 243.8965 | - | - | 192000 B |
| ImmutableDictionary_containsKey | 2000 | 107,118.8 ns | 2,134.980 ns | 5,156.216 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 3000 | 187,092.3 ns | 3,814.589 ns | 11,127.336 ns | - | - | - | - |
| ImTools_containsKey | 3000 | 126,871.5 ns | 3,180.189 ns | 9,326.944 ns | - | - | - | - |
| FSharpMap_containsKey | 3000 | 471,897.5 ns | 9,429.813 ns | 12,907.634 ns | - | - | - | - |
| HAMT_containsKey | 3000 | 358,664.1 ns | 7,160.565 ns | 18,988.803 ns | - | - | - | - |
| FSharpX_containsKey | 3000 | 334,645.1 ns | 7,237.286 ns | 21,339.301 ns | 365.7227 | - | - | 288000 B |
| ImmutableDictionary_containsKey | 3000 | 166,241.9 ns | 3,449.926 ns | 9,088.484 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 4000 | 254,975.8 ns | 5,832.545 ns | 17,013.807 ns | - | - | - | - |
| ImTools_containsKey | 4000 | 163,511.8 ns | 3,505.297 ns | 10,335.448 ns | - | - | - | - |
| FSharpMap_containsKey | 4000 | 617,516.9 ns | 15,509.177 ns | 45,240.998 ns | - | - | - | - |
| HAMT_containsKey | 4000 | 523,450.8 ns | 11,620.165 ns | 33,712.207 ns | - | - | - | - |
| FSharpX_containsKey | 4000 | 477,557.9 ns | 9,516.993 ns | 24,904.313 ns | 487.7930 | - | - | 384000 B |
| ImmutableDictionary_containsKey | 4000 | 227,449.3 ns | 4,632.671 ns | 10,644.332 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 5000 | 334,204.1 ns | 6,624.414 ns | 15,220.693 ns | - | - | - | - |
| ImTools_containsKey | 5000 | 216,199.7 ns | 4,301.813 ns | 10,139.880 ns | - | - | - | - |
| FSharpMap_containsKey | 5000 | 796,350.6 ns | 15,890.050 ns | 38,978.564 ns | - | - | - | - |
| HAMT_containsKey | 5000 | 664,490.6 ns | 13,923.409 ns | 41,053.485 ns | - | - | - | - |
| FSharpX_containsKey | 5000 | 652,284.1 ns | 15,191.511 ns | 44,792.512 ns | 609.3750 | - | - | 480000 B |
| ImmutableDictionary_containsKey | 5000 | 292,575.0 ns | 6,700.714 ns | 19,652.035 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 10000 | 698,840.7 ns | 13,963.275 ns | 37,988.119 ns | - | - | - | - |
| ImTools_containsKey | 10000 | 490,095.7 ns | 9,904.196 ns | 29,047.292 ns | - | - | - | - |
| FSharpMap_containsKey | 10000 | 1,725,827.8 ns | 34,488.855 ns | 72,748.701 ns | - | - | - | - |
| HAMT_containsKey | 10000 | 1,516,943.4 ns | 29,983.612 ns | 74,112.060 ns | - | - | - | - |
| FSharpX_containsKey | 10000 | 1,435,555.3 ns | 28,389.329 ns | 73,787.642 ns | 1218.7500 | - | - | 960000 B |
| ImmutableDictionary_containsKey | 10000 | 610,250.0 ns | 13,902.945 ns | 40,993.147 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 20000 | 1,488,175.1 ns | 29,461.650 ns | 78,639.108 ns | - | - | - | - |
| ImTools_containsKey | 20000 | 1,053,261.7 ns | 24,115.568 ns | 70,726.786 ns | - | - | - | - |
| FSharpMap_containsKey | 20000 | 3,917,270.3 ns | 84,813.588 ns | 246,059.597 ns | - | - | - | - |
| HAMT_containsKey | 20000 | 3,243,693.5 ns | 64,334.363 ns | 162,581.144 ns | - | - | - | - |
| FSharpX_containsKey | 20000 | 3,221,606.2 ns | 63,427.912 ns | 125,200.511 ns | 2437.5000 | - | - | 1920000 B |
| ImmutableDictionary_containsKey | 20000 | 1,265,764.8 ns | 25,545.317 ns | 72,051.020 ns | - | - | - | - |
| HashMapOkasaki_containsKey | 30000 | 2,322,374.9 ns | 54,981.687 ns | 162,114.745 ns | - | - | - | - |
| ImTools_containsKey | 30000 | 1,624,837.3 ns | 35,984.283 ns | 105,535.673 ns | - | - | - | - |
| FSharpMap_containsKey | 30000 | 6,108,415.1 ns | 120,972.266 ns | 341,204.423 ns | - | - | - | - |
| HAMT_containsKey | 30000 | 4,886,458.9 ns | 97,275.891 ns | 196,502.097 ns | - | - | - | - |
| FSharpX_containsKey | 30000 | 5,244,153.4 ns | 112,037.325 ns | 326,818.136 ns | 3656.2500 | - | - | 2880000 B |
| ImmutableDictionary_containsKey | 30000 | 1,949,218.3 ns | 53,310.866 ns | 157,188.291 ns | - | - | - | - |