Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Optimize Im(Hash)Map memory and performance #12

Closed
4 of 5 tasks
dadhi opened this issue Dec 9, 2018 · 1 comment
Closed
4 of 5 tasks

Optimize Im(Hash)Map memory and performance #12

dadhi opened this issue Dec 9, 2018 · 1 comment
Assignees
@dadhi
Labels
enhancement
Milestone
2.0.0

Comments

@dadhi
Copy link
Owner

dadhi commented Dec 9, 2018 •
edited
Loading

The list of opportunities:

  • Optimize KeepBalanced, remove thrown away allocations
  • Inline internal _data, benchmark vs inlined, compacted hierarchy
  • Make a struct Enumerator, benchmark
  • (X) Compact leaf nodes
  • [?] Enumerate should return nodes as-is without allocations
  • Benchmark different ways of Equals and GetHashCode. Select the right way.
  • (X) Encode height disbalance in 2 bits of hash and get rid of the height field
    • Seems that there is a way, but it still needs some bits and a separate field.
  • Fix the lookup in empty maps to don't necessarily call GetHashCode
@dadhi
Copy link
Owner Author

dadhi commented Jan 16, 2019 •
edited
Loading

V1 is the old version. V2 is the variant with split nodes to Branch / Leaf with virtual properties.

BenchmarkDotNet=v0.11.3, OS=Windows 10.0.17134.523 (1803/April2018Update/Redstone4)
Intel Core i7-8750H CPU 2.20GHz (Coffee Lake), 1 CPU, 12 logical and 6 physical cores
Frequency=2156249 Hz, Resolution=463.7683 ns, Timer=TSC
.NET Core SDK=2.2.100
  [Host]     : .NET Core 2.1.6 (CoreCLR 4.6.27019.06, CoreFX 4.6.27019.05), 64bit RyuJIT
  DefaultJob : .NET Core 2.1.6 (CoreCLR 4.6.27019.06, CoreFX 4.6.27019.05), 64bit RyuJIT


         Method | Count |           Mean |         Error |        StdDev |         Median | Ratio | RatioSD | Gen 0/1k Op | Gen 1/1k Op | Gen 2/1k Op | Allocated Memory/Op |
--------------- |------ |---------------:|--------------:|--------------:|---------------:|------:|--------:|------------:|------------:|------------:|--------------------:|
 AddOrUpdate_v1 |    10 |       987.6 ns |      36.53 ns |      99.99 ns |       934.3 ns |  0.94 |    0.17 |      0.5589 |           - |           - |             2.58 KB |
    AddOrUpdate |    10 |     1,067.5 ns |      50.43 ns |     136.33 ns |     1,073.5 ns |  1.00 |    0.00 |      0.4044 |           - |           - |             1.87 KB |
 ConcurrentDict |    10 |     1,943.9 ns |      92.31 ns |      81.83 ns |     1,921.3 ns |  1.85 |    0.25 |      0.6371 |           - |           - |             2.95 KB |
 AddOrUpdate_v2 |    10 |     2,688.3 ns |     229.79 ns |     677.55 ns |     2,342.9 ns |  2.50 |    0.77 |      0.4349 |           - |           - |             2.02 KB |
  ImmutableDict |    10 |     5,903.1 ns |     749.28 ns |     801.72 ns |     5,607.8 ns |  5.66 |    1.06 |      0.5875 |           - |           - |             2.73 KB |
                |       |                |               |               |                |       |         |             |             |             |                     |
 ConcurrentDict |   100 |    14,476.1 ns |   1,184.05 ns |   1,215.93 ns |    14,193.3 ns |  0.48 |    0.21 |      3.6011 |      0.0305 |           - |            16.66 KB |
 AddOrUpdate_v1 |   100 |    16,999.4 ns |   1,522.75 ns |   4,441.93 ns |    14,281.8 ns |  0.59 |    0.25 |      8.4686 |           - |           - |            39.05 KB |
 AddOrUpdate_v2 |   100 |    28,695.4 ns |      41.78 ns |      32.62 ns |    28,697.6 ns |  0.94 |    0.33 |      7.7515 |           - |           - |            35.81 KB |
    AddOrUpdate |   100 |    31,854.4 ns |   2,882.03 ns |   8,497.72 ns |    36,547.9 ns |  1.00 |    0.00 |      7.3242 |           - |           - |            33.91 KB |
  ImmutableDict |   100 |    89,602.2 ns |   1,873.19 ns |   2,229.89 ns |    88,767.5 ns |  2.98 |    1.05 |      9.3994 |           - |           - |            43.68 KB |
                |       |                |               |               |                |       |         |             |             |             |                     |
 ConcurrentDict |  1000 |   219,064.7 ns |     559.14 ns |     466.91 ns |   218,894.7 ns |  0.69 |    0.01 |     49.3164 |     17.8223 |           - |           254.29 KB |
 AddOrUpdate_v1 |  1000 |   297,651.6 ns |   1,073.37 ns |     838.02 ns |   297,421.1 ns |  0.93 |    0.01 |    120.6055 |      3.4180 |           - |           556.41 KB |
    AddOrUpdate |  1000 |   319,478.3 ns |   2,768.11 ns |   2,161.16 ns |   319,079.8 ns |  1.00 |    0.00 |    113.2813 |      0.9766 |           - |           526.48 KB |
 AddOrUpdate_v2 |  1000 |   615,321.8 ns |  72,410.43 ns | 213,503.80 ns |   467,207.0 ns |  1.97 |    0.66 |    118.6523 |      0.4883 |           - |            547.3 KB |
  ImmutableDict |  1000 | 1,516,613.7 ns | 107,376.35 ns | 290,298.20 ns | 1,387,325.2 ns |  4.95 |    1.19 |    140.6250 |      1.9531 |           - |           648.02 KB |

New results:

         Method | Count |           Mean |         Error |        StdDev | Ratio | RatioSD | Gen 0/1k Op | Gen 1/1k Op | Gen 2/1k Op | Allocated Memory/Op |
--------------- |------ |---------------:|--------------:|--------------:|------:|--------:|------------:|------------:|------------:|--------------------:|
    AddOrUpdate |    10 |       884.8 ns |     12.682 ns |     11.242 ns |  1.00 |    0.00 |      0.4978 |           - |           - |              2.3 KB |
 AddOrUpdate_v1 |    10 |       943.8 ns |      1.244 ns |      1.103 ns |  1.07 |    0.01 |      0.5589 |           - |           - |             2.58 KB |
 ConcurrentDict |    10 |     2,082.3 ns |     14.652 ns |     13.705 ns |  2.35 |    0.04 |      0.6371 |           - |           - |             2.95 KB |
  ImmutableDict |    10 |     6,139.6 ns |     94.146 ns |     88.064 ns |  6.93 |    0.11 |      0.5875 |           - |           - |             2.73 KB |
                |       |                |               |               |       |         |             |             |             |                     |
    AddOrUpdate |   100 |    14,324.0 ns |    226.034 ns |    200.373 ns |  1.00 |    0.00 |      7.6904 |           - |           - |            35.48 KB |
 ConcurrentDict |   100 |    15,350.0 ns |     42.027 ns |     37.256 ns |  1.07 |    0.02 |      3.6011 |      0.0153 |           - |            16.66 KB |
 AddOrUpdate_v1 |   100 |    15,350.3 ns |     76.381 ns |     71.447 ns |  1.07 |    0.02 |      8.4534 |           - |           - |            39.05 KB |
  ImmutableDict |   100 |    96,223.9 ns |  1,199.140 ns |  1,121.676 ns |  6.72 |    0.13 |      9.3994 |           - |           - |            43.68 KB |
                |       |                |               |               |       |         |             |             |             |                     |
 ConcurrentDict |  1000 |   233,148.4 ns |  2,400.504 ns |  2,004.530 ns |  0.77 |    0.01 |     49.3164 |     17.8223 |           - |           254.29 KB |
    AddOrUpdate |  1000 |   301,259.0 ns |  4,495.453 ns |  4,205.050 ns |  1.00 |    0.00 |    111.8164 |     32.7148 |           - |           515.39 KB |
 AddOrUpdate_v1 |  1000 |   321,037.8 ns |  2,588.303 ns |  2,421.100 ns |  1.07 |    0.02 |    120.6055 |      3.4180 |           - |           556.41 KB |
  ImmutableDict |  1000 | 1,504,531.8 ns | 28,456.502 ns | 31,629.327 ns |  4.99 |    0.10 |    140.6250 |      1.9531 |           - |           648.02 KB |

Here is the Lookup for the reference:

                Method | Count |      Mean |     Error |    StdDev | Ratio | RatioSD | Gen 0/1k Op | Gen 1/1k Op | Gen 2/1k Op | Allocated Memory/Op |
---------------------- |------ |----------:|----------:|----------:|------:|--------:|------------:|------------:|------------:|--------------------:|
            TryFind_v1 |    10 |  7.274 ns | 0.0410 ns | 0.0384 ns |  0.98 |    0.01 |           - |           - |           - |                   - |
               TryFind |    10 |  7.422 ns | 0.0237 ns | 0.0222 ns |  1.00 |    0.00 |           - |           - |           - |                   - |
 ConcurrentDict_TryGet |    10 | 21.664 ns | 0.0213 ns | 0.0189 ns |  2.92 |    0.01 |           - |           - |           - |                   - |
  ImmutableDict_TryGet |    10 | 71.199 ns | 0.1312 ns | 0.1228 ns |  9.59 |    0.03 |           - |           - |           - |                   - |
                       |       |           |           |           |       |         |             |             |             |                     |
            TryFind_v1 |   100 |  8.426 ns | 0.0236 ns | 0.0221 ns |  0.91 |    0.00 |           - |           - |           - |                   - |
               TryFind |   100 |  9.304 ns | 0.0305 ns | 0.0270 ns |  1.00 |    0.00 |           - |           - |           - |                   - |
 ConcurrentDict_TryGet |   100 | 21.791 ns | 0.1072 ns | 0.0951 ns |  2.34 |    0.01 |           - |           - |           - |                   - |
  ImmutableDict_TryGet |   100 | 74.985 ns | 0.1053 ns | 0.0879 ns |  8.06 |    0.03 |           - |           - |           - |                   - |
                       |       |           |           |           |       |         |             |             |             |                     |
               TryFind |  1000 | 13.837 ns | 0.0291 ns | 0.0272 ns |  1.00 |    0.00 |           - |           - |           - |                   - |
            TryFind_v1 |  1000 | 16.108 ns | 0.0415 ns | 0.0367 ns |  1.16 |    0.00 |           - |           - |           - |                   - |
 ConcurrentDict_TryGet |  1000 | 21.876 ns | 0.0325 ns | 0.0288 ns |  1.58 |    0.00 |           - |           - |           - |                   - |
  ImmutableDict_TryGet |  1000 | 83.563 ns | 0.1046 ns | 0.0873 ns |  6.04 |    0.01 |           - |           - |           - |                   - |

@dadhi dadhi self-assigned this Apr 14, 2019
@dadhi dadhi added this to the 2.0.0 milestone Apr 14, 2019
@dadhi dadhi closed this as completed Apr 14, 2019
@dadhi dadhi mentioned this issue Apr 14, 2019
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@dadhi dadhi

Labels
enhancement
Projects
None yet
Milestone
2.0.0
Development

No branches or pull requests
1 participant
@dadhi