ImTools

Fast and memory-efficient immutable and mutable collections and helper data structures.

Initially split from the DryIoc, and now used in the FastExpressionCompiler too.

• Windows, Linux, MacOS
• Lib package
• Code package
• Latest release

Benchmarks

The comparison is done against the previous versions and the variety of BCL C# collections including the experimental Microsoft.Collections.Extensions.DictionarySlim<K, V>.

Important: Keep in mind that immutable collections have a different use-case and a thread-safety guarantees compared to the Dictionary, DictionarySlim or even ConcurrentDictionary. The closest comparable would be the ImmutableDictionary. The benchmarks do not take the collections "nature" into account and run through the simplest available API path.

ImHashMap of Type keys and small string values

Population

The benchmark inserts from 10 to 1000 items into the ImHashMap<Type, string>:

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19043
Intel Core i9-8950HK CPU 2.90GHz (Coffee Lake), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=6.0.202
  [Host]     : .NET Core 6.0.4 (CoreCLR 6.0.422.16404, CoreFX 6.0.422.16404), X64 RyuJIT
  DefaultJob : .NET Core 6.0.4 (CoreCLR 6.0.422.16404, CoreFX 6.0.422.16404), X64 RyuJIT

| Method                            | Count |          Mean |        Error |       StdDev | Ratio | RatioSD |    Gen 0 |   Gen 1 | Gen 2 | Allocated |
| --------------------------------- | ----- | ------------: | -----------: | -----------: | ----: | ------: | -------: | ------: | ----: | --------: |
| V4_ImHashMap_AddOrUpdate          | 1     |      33.32 ns |     0.439 ns |     0.389 ns |  1.00 |    0.00 |   0.0178 |       - |     - |     112 B |
| V3_ImHashMap_AddOrUpdate          | 1     |      35.97 ns |     0.639 ns |     0.567 ns |  1.08 |    0.02 |   0.0178 |       - |     - |     112 B |
| V4_PartitionedHashMap_AddOrUpdate | 1     |      97.72 ns |     1.294 ns |     1.148 ns |  2.93 |    0.05 |   0.0370 |       - |     - |     232 B |
| DictSlim_TryAdd                   | 1     |      59.37 ns |     0.519 ns |     0.434 ns |  1.78 |    0.02 |   0.0229 |       - |     - |     144 B |
| Dict_TryAdd                       | 1     |      65.94 ns |     0.631 ns |     0.560 ns |  1.98 |    0.02 |   0.0343 |       - |     - |     216 B |
| ConcurrentDictionary_TryAdd       | 1     |     197.29 ns |     1.883 ns |     1.761 ns |  5.92 |    0.09 |   0.1466 |  0.0007 |     - |     920 B |
| ImmutableDict_Builder_Add         | 1     |     220.79 ns |     2.648 ns |     2.477 ns |  6.62 |    0.10 |   0.0355 |       - |     - |     224 B |
| ImmutableDict_Add                 | 1     |     264.15 ns |     4.786 ns |     3.737 ns |  7.93 |    0.16 |   0.0429 |       - |     - |     272 B |
|                                   |       |               |              |              |       |         |          |         |       |           |
| V4_ImHashMap_AddOrUpdate          | 10    |     307.91 ns |     5.281 ns |     4.940 ns |  1.00 |    0.00 |   0.1564 |  0.0005 |     - |     984 B |
| V3_ImHashMap_AddOrUpdate          | 10    |     389.09 ns |     6.482 ns |     5.746 ns |  1.27 |    0.03 |   0.1593 |  0.0005 |     - |    1000 B |
| V4_PartitionedHashMap_AddOrUpdate | 10    |     392.47 ns |     4.296 ns |     5.276 ns |  1.27 |    0.03 |   0.1144 |  0.0005 |     - |     720 B |
| DictSlim_TryAdd                   | 10    |     409.45 ns |     2.216 ns |     1.965 ns |  1.33 |    0.02 |   0.1707 |  0.0005 |     - |    1072 B |
| Dict_TryAdd                       | 10    |     413.38 ns |     5.460 ns |     5.107 ns |  1.34 |    0.03 |   0.1578 |  0.0005 |     - |     992 B |
| ConcurrentDictionary_TryAdd       | 10    |   1,319.88 ns |    20.332 ns |    19.019 ns |  4.29 |    0.11 |   0.4730 |  0.0076 |     - |    2968 B |
| ImmutableDict_Builder_Add         | 10    |   1,712.26 ns |    15.264 ns |    26.733 ns |  5.59 |    0.12 |   0.1259 |       - |     - |     800 B |
| ImmutableDict_Add                 | 10    |   2,986.38 ns |    17.824 ns |    14.884 ns |  9.70 |    0.18 |   0.4349 |       - |     - |    2744 B |
|                                   |       |               |              |              |       |         |          |         |       |           |
| V4_ImHashMap_AddOrUpdate          | 100   |   9,188.79 ns |   116.272 ns |   108.761 ns |  1.00 |    0.00 |   2.8229 |  0.0916 |     - |   17792 B |
| V3_ImHashMap_AddOrUpdate          | 100   |  10,591.30 ns |   169.894 ns |   141.869 ns |  1.15 |    0.03 |   3.1891 |  0.1068 |     - |   20032 B |
| V4_PartitionedHashMap_AddOrUpdate | 100   |   4,491.75 ns |    81.205 ns |    75.959 ns |  0.49 |    0.01 |   1.2360 |  0.0534 |     - |    7776 B |
| DictSlim_TryAdd                   | 100   |   3,201.77 ns |    48.216 ns |    42.743 ns |  0.35 |    0.01 |   1.1902 |  0.0305 |     - |    7488 B |
| Dict_TryAdd                       | 100   |   3,856.61 ns |    70.806 ns |    62.768 ns |  0.42 |    0.01 |   1.6174 |  0.0687 |     - |   10192 B |
| ConcurrentDictionary_TryAdd       | 100   |  16,035.70 ns |   320.350 ns |   356.068 ns |  1.75 |    0.04 |   4.9133 |  0.5798 |     - |   30824 B |
| ImmutableDict_Builder_Add         | 100   |  24,427.83 ns |   470.630 ns |   417.201 ns |  2.66 |    0.07 |   1.0376 |  0.0305 |     - |    6560 B |
| ImmutableDict_Add                 | 100   |  48,772.32 ns |   687.894 ns |   574.422 ns |  5.30 |    0.10 |   7.1411 |  0.2441 |     - |   44936 B |
|                                   |       |               |              |              |       |         |          |         |       |           |
| V4_ImHashMap_AddOrUpdate          | 1000  | 277,024.17 ns | 3,349.815 ns | 2,969.524 ns |  1.00 |    0.00 |  45.4102 | 10.7422 |     - |  286344 B |
| V3_ImHashMap_AddOrUpdate          | 1000  | 234,444.41 ns | 2,324.332 ns | 1,940.923 ns |  0.85 |    0.01 |  51.5137 | 12.2070 |     - |  324176 B |
| V4_PartitionedHashMap_AddOrUpdate | 1000  | 146,984.47 ns |   954.053 ns |   845.743 ns |  0.53 |    0.01 |  26.1230 |  7.5684 |     - |  164280 B |
| DictSlim_TryAdd                   | 1000  |  33,447.54 ns |   254.743 ns |   225.823 ns |  0.12 |    0.00 |   9.1553 |  1.7700 |     - |   57808 B |
| Dict_TryAdd                       | 1000  |  40,234.23 ns |   430.048 ns |   381.226 ns |  0.15 |    0.00 |  16.2354 |  5.3711 |     - |  102216 B |
| ConcurrentDictionary_TryAdd       | 1000  | 165,018.54 ns | 3,075.862 ns | 2,568.484 ns |  0.60 |    0.01 |  41.2598 | 13.6719 |     - |  259720 B |
| ImmutableDict_Builder_Add         | 1000  | 396,623.48 ns | 4,099.094 ns | 3,834.295 ns |  1.43 |    0.02 |   9.7656 |  2.4414 |     - |   64160 B |
| ImmutableDict_Add                 | 1000  | 813,397.08 ns | 9,203.453 ns | 8,608.916 ns |  2.94 |    0.04 | 105.4688 | 25.3906 |     - |  665001 B |

Lookup

The benchmark lookups for the specific key in the ImHashMap<Type, string> containing the specified Count of elements.

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19043
Intel Core i9-8950HK CPU 2.90GHz (Coffee Lake), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=6.0.202
  [Host]     : .NET Core 6.0.4 (CoreCLR 6.0.422.16404, CoreFX 6.0.422.16404), X64 RyuJIT
  DefaultJob : .NET Core 6.0.4 (CoreCLR 6.0.422.16404, CoreFX 6.0.422.16404), X64 RyuJIT

| Method                           | Count |      Mean |     Error |    StdDev | Ratio | RatioSD | Gen 0 | Gen 1 | Gen 2 | Allocated |
| -------------------------------- | ----- | --------: | --------: | --------: | ----: | ------: | ----: | ----: | ----: | --------: |
| V4_ImHashMap_TryFind             | 1     |  8.915 ns | 0.1853 ns | 0.1733 ns |  1.00 |    0.00 |     - |     - |     - |         - |
| V3_ImHashMap_TryFind             | 1     |  7.834 ns | 0.1769 ns | 0.1568 ns |  0.88 |    0.02 |     - |     - |     - |         - |
| V4_PartitionedHashMap_TryFind    | 1     |  8.292 ns | 0.1082 ns | 0.0959 ns |  0.93 |    0.02 |     - |     - |     - |         - |
| V3_PartitionedHashMap_TryFind    | 1     |  7.681 ns | 0.1245 ns | 0.1039 ns |  0.86 |    0.02 |     - |     - |     - |         - |
| DictionarySlim_TryGetValue       | 1     |  8.861 ns | 0.1423 ns | 0.1188 ns |  0.99 |    0.02 |     - |     - |     - |         - |
| Dictionary_TryGetValue           | 1     | 17.914 ns | 0.3447 ns | 0.3055 ns |  2.01 |    0.05 |     - |     - |     - |         - |
| ConcurrentDictionary_TryGetValue | 1     | 13.381 ns | 0.2709 ns | 0.2401 ns |  1.50 |    0.04 |     - |     - |     - |         - |
| ImmutableDict_TryGet             | 1     | 19.040 ns | 0.3068 ns | 0.2870 ns |  2.14 |    0.06 |     - |     - |     - |         - |
|                                  |       |           |           |           |       |         |       |       |       |           |
| V4_ImHashMap_TryFind             | 10    |  9.462 ns | 0.2690 ns | 0.2246 ns |  1.00 |    0.00 |     - |     - |     - |         -