fsprojects / fsharp-hashcollections

Library providing fast hash based immutable map and set
MIT License
59 stars 4 forks source link

Lower equality reqs #8

Closed mvkara closed 4 years ago

mvkara commented 4 years ago

The default equality constraints no longer need IEquatable<'tk> allowing usage of this library in more scenarios (e.g. tuple keys for hashMap)

The option is still there to define your own StandardEqualityTemplate<_> using IEquatable<_> for slightly better performance. Performance hit is round 6-13.1% (bigger collections -> smaller collections).

e.g. Using an equality comparer like below given the below Get statistics.

type [<Struct>] IntEqualityTemplate = 
    struct end
    interface IEqualityComparer<int> with
        [<MethodImpl(MethodImplOptions.AggressiveInlining)>]
        member __.Equals(x: int, y: int): bool = x = y
        [<MethodImpl(MethodImplOptions.AggressiveInlining)>]
        member __.GetHashCode(obj: int): int = obj
// * Summary *

BenchmarkDotNet=v0.12.0, OS=arch 
AMD Ryzen 7 3700X, 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=3.1.100
  [Host]     : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT DEBUG
  DefaultJob : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT

|                           Method | CollectionSize |         Mean |     Error |     StdDev |
|--------------------------------- |--------------- |-------------:|----------:|-----------:|
|                       GetHashMap |             10 |     9.926 ns | 0.0050 ns |  0.0045 ns |
|                GetImToolsHashMap |             10 |    28.958 ns | 0.3388 ns |  0.3169 ns |
|                     GetFSharpMap |             10 |    40.643 ns | 0.7644 ns |  0.8180 ns |
|                GetFSharpXHashMap |             10 |   101.132 ns | 1.4956 ns |  1.3990 ns |
| GetSystemCollectionsImmutableMap |             10 |    24.802 ns | 0.0192 ns |  0.0180 ns |
|         GetFSharpDataAdaptiveMap |             10 |    21.508 ns | 0.0242 ns |  0.0226 ns |
|                       GetHashMap |            100 |    12.975 ns | 0.0122 ns |  0.0114 ns |
|                GetImToolsHashMap |            100 |    42.124 ns | 0.1862 ns |  0.1650 ns |
|                     GetFSharpMap |            100 |    68.672 ns | 1.3138 ns |  1.4058 ns |
|                GetFSharpXHashMap |            100 |   108.293 ns | 1.7887 ns |  1.6732 ns |
| GetSystemCollectionsImmutableMap |            100 |    37.061 ns | 0.1476 ns |  0.1380 ns |
|         GetFSharpDataAdaptiveMap |            100 |    43.039 ns | 0.2861 ns |  0.2676 ns |
|                       GetHashMap |           1000 |    10.848 ns | 0.0630 ns |  0.0558 ns |
|                GetImToolsHashMap |           1000 |    64.617 ns | 0.7955 ns |  0.7052 ns |
|                     GetFSharpMap |           1000 |   103.911 ns | 1.5896 ns |  1.4869 ns |
|                GetFSharpXHashMap |           1000 |   114.621 ns | 1.5813 ns |  1.4791 ns |
| GetSystemCollectionsImmutableMap |           1000 |    53.906 ns | 0.1334 ns |  0.1248 ns |
|         GetFSharpDataAdaptiveMap |           1000 |    64.895 ns | 0.0290 ns |  0.0257 ns |
|                       GetHashMap |         100000 |    21.664 ns | 0.0152 ns |  0.0142 ns |
|                GetImToolsHashMap |         100000 |   197.040 ns | 0.2883 ns |  0.2696 ns |
|                     GetFSharpMap |         100000 |   199.662 ns | 1.8501 ns |  1.7306 ns |
|                GetFSharpXHashMap |         100000 |   142.963 ns | 0.9620 ns |  0.8999 ns |
| GetSystemCollectionsImmutableMap |         100000 |   140.797 ns | 0.1237 ns |  0.1097 ns |
|         GetFSharpDataAdaptiveMap |         100000 |   140.721 ns | 0.0986 ns |  0.0874 ns |
|                       GetHashMap |         500000 |    68.142 ns | 0.2851 ns |  0.2527 ns |
|                GetImToolsHashMap |         500000 |   504.818 ns | 1.2397 ns |  1.0989 ns |
|                     GetFSharpMap |         500000 |   309.818 ns | 1.5171 ns |  1.4191 ns |
|                GetFSharpXHashMap |         500000 |   235.187 ns | 0.6484 ns |  0.6065 ns |
| GetSystemCollectionsImmutableMap |         500000 |   314.714 ns | 2.7851 ns |  2.6052 ns |
|         GetFSharpDataAdaptiveMap |         500000 |   304.446 ns | 0.1927 ns |  0.1708 ns |
|                       GetHashMap |         750000 |    95.958 ns | 0.0394 ns |  0.0329 ns |
|                GetImToolsHashMap |         750000 |   633.324 ns | 0.7520 ns |  0.7034 ns |
|                     GetFSharpMap |         750000 |   402.166 ns | 6.9027 ns |  6.4567 ns |
|                GetFSharpXHashMap |         750000 |   354.521 ns | 0.5895 ns |  0.5226 ns |
| GetSystemCollectionsImmutableMap |         750000 |   398.067 ns | 0.5295 ns |  0.4694 ns |
|         GetFSharpDataAdaptiveMap |         750000 |   347.982 ns | 0.1823 ns |  0.1616 ns |
|                       GetHashMap |        1000000 |   105.326 ns | 0.0559 ns |  0.0523 ns |
|                GetImToolsHashMap |        1000000 |   691.492 ns | 0.4034 ns |  0.3576 ns |
|                     GetFSharpMap |        1000000 |   455.620 ns | 8.9881 ns | 11.3670 ns |
|                GetFSharpXHashMap |        1000000 |   347.568 ns | 1.2698 ns |  1.1878 ns |
| GetSystemCollectionsImmutableMap |        1000000 |   483.456 ns | 0.6303 ns |  0.5896 ns |
|         GetFSharpDataAdaptiveMap |        1000000 |   385.804 ns | 0.2885 ns |  0.2409 ns |
|                       GetHashMap |        5000000 |   134.836 ns | 0.1230 ns |  0.1090 ns |
|                GetImToolsHashMap |        5000000 | 1,264.685 ns | 2.9860 ns |  2.7931 ns |
|                     GetFSharpMap |        5000000 |   853.400 ns | 2.6057 ns |  2.4374 ns |
|                GetFSharpXHashMap |        5000000 |   382.427 ns | 0.8251 ns |  0.7314 ns |
| GetSystemCollectionsImmutableMap |        5000000 |   855.713 ns | 0.4535 ns |  0.4242 ns |
|         GetFSharpDataAdaptiveMap |        5000000 |   609.845 ns | 0.4041 ns |  0.3583 ns |
|                       GetHashMap |       10000000 |   152.434 ns | 0.0767 ns |  0.0718 ns |
|                GetImToolsHashMap |       10000000 | 1,605.469 ns | 1.2254 ns |  1.1463 ns |
|                     GetFSharpMap |       10000000 | 1,046.320 ns | 2.3946 ns |  2.2399 ns |
|                GetFSharpXHashMap |       10000000 |   390.366 ns | 1.5520 ns |  1.4517 ns |
| GetSystemCollectionsImmutableMap |       10000000 | 1,019.647 ns | 1.5931 ns |  1.4902 ns |
|         GetFSharpDataAdaptiveMap |       10000000 |   707.831 ns | 0.3499 ns |  0.3102 ns |