Use dictionary to track PackageRelationships instead of searching a list by twsouthwick · Pull Request #35978 · dotnet/runtime

twsouthwick · 2020-05-07T18:42:23Z

This change adds an OrderedDictionary<TKey,TValue> type to System.IO.Packaging to keep a list of relationships that have been added, while ensuring that the ids are unique with decent performance characteristics. The current implementation searches a list which gets really slow with large numbers of relationships. A Dictionary by itself does not work for this as the order of addition is important. Thus, this combines a LinkedList to track the order, while a Dictionary is used to for quick look up of existing items.

Fixes #983

ghost · 2020-05-07T18:42:31Z

Tagging subscribers to this area: @jozkee
Notify danmosemsft if you want to be subscribed.

twsouthwick · 2020-05-07T18:43:22Z

I ran some performance tests locally and see the following:

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.208 (2004/?/20H1)
AMD Ryzen 7 3700X, 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=3.1.300-preview-015135
  [Host]        : .NET Core 3.1.3 (CoreCLR 4.700.20.11803, CoreFX 4.700.20.12001), X64 RyuJIT
  .NET Core 3.1 : .NET Core 3.1.3 (CoreCLR 4.700.20.11803, CoreFX 4.700.20.12001), X64 RyuJIT

Job=.NET Core 3.1  Runtime=.NET Core 3.1

Before:

|              Method |     N |           Mean |          Error |         StdDev |    Gen 0 |    Gen 1 |    Gen 2 |  Allocated |
|-------------------- |------ |---------------:|---------------:|---------------:|---------:|---------:|---------:|-----------:|
|    AddRelationships |    10 |      22.388 us |      0.3962 us |      0.3706 us |   3.2043 |   0.0610 |        - |   26.36 KB |
| DeleteRelationships |    10 |       8.259 us |      0.1173 us |      0.1098 us |   0.8087 |   0.0153 |        - |    6.63 KB |
|     GetRelationship |    10 |      24.192 us |      0.3770 us |      0.3526 us |   3.2959 |   0.1526 |        - |    27.1 KB |
|    AddRelationships |   100 |     147.637 us |      1.5472 us |      1.3716 us |   9.2773 |   0.7324 |        - |   76.62 KB |
| DeleteRelationships |   100 |      95.864 us |      1.2001 us |      1.1226 us |   5.3711 |   0.7324 |        - |   44.44 KB |
|     GetRelationship |   100 |     186.724 us |      2.8160 us |      2.4963 us |  10.2539 |   1.7090 |        - |   83.82 KB |
|    AddRelationships |  1000 |   3,691.527 us |     33.1561 us |     25.8861 us |  85.9375 |  85.9375 |  85.9375 |  767.22 KB |
| DeleteRelationships |  1000 |   3,302.878 us |     64.8696 us |     60.6791 us |  50.7813 |  23.4375 |        - |  418.06 KB |
|     GetRelationship |  1000 |   6,626.254 us |     96.2316 us |     85.3068 us |  85.9375 |  85.9375 |  85.9375 |  838.66 KB |
|    AddRelationships | 10000 | 300,256.640 us |  5,678.6663 us |  5,311.8280 us | 500.0000 | 500.0000 | 500.0000 | 6859.76 KB |
| DeleteRelationships | 10000 | 299,635.808 us |  5,785.9288 us |  6,190.8790 us |        - |        - |        - | 4197.49 KB |
|     GetRelationship | 10000 | 589,829.177 us | 11,474.4863 us | 15,706.4063 us |        - |        - |        - | 7517.03 KB |

After:

|              Method |     N |          Mean |       Error |      StdDev |     Gen 0 |    Gen 1 |    Gen 2 |  Allocated |
|-------------------- |------ |--------------:|------------:|------------:|----------:|---------:|---------:|-----------:|
|    AddRelationships |    10 |     22.780 us |   0.3742 us |   0.3675 us |    3.3264 |   0.1221 |        - |   27.42 KB |
| DeleteRelationships |    10 |      9.362 us |   0.1550 us |   0.1374 us |    0.9308 |   0.0153 |        - |    7.67 KB |
|     GetRelationship |    10 |     24.421 us |   0.3950 us |   0.3298 us |    3.4180 |   0.1221 |        - |   28.16 KB |
|    AddRelationships |   100 |    128.471 us |   1.6193 us |   1.4355 us |   10.7422 |   0.9766 |        - |   89.06 KB |
| DeleteRelationships |   100 |     80.366 us |   1.5709 us |   1.6132 us |    6.9580 |   1.2207 |        - |   56.87 KB |
|     GetRelationship |   100 |    145.800 us |   2.7884 us |   2.8635 us |   11.7188 |   2.1973 |        - |   96.26 KB |
|    AddRelationships |  1000 |  1,421.037 us |  28.0402 us |  41.1010 us |   89.8438 |  89.8438 |  89.8438 |  897.64 KB |
| DeleteRelationships |  1000 |    833.369 us |  16.0594 us |  20.8817 us |   66.4063 |  33.2031 |        - |  548.47 KB |
|     GetRelationship |  1000 |  1,445.370 us |  14.9881 us |  14.0199 us |   89.8438 |  89.8438 |  89.8438 |  969.08 KB |
|    AddRelationships | 10000 | 13,337.722 us | 253.3764 us | 248.8495 us |  984.3750 | 984.3750 | 984.3750 | 7992.07 KB |
| DeleteRelationships | 10000 | 10,424.963 us | 122.3309 us | 114.4284 us |  656.2500 | 328.1250 | 328.1250 | 5329.43 KB |
|     GetRelationship | 10000 | 23,163.040 us | 381.3055 us | 356.6734 us | 1468.7500 | 968.7500 | 968.7500 |  8650.7 KB |

Not sure where to add performance tests to the repo. Unit tests already cover the functional side of things.

twsouthwick · 2020-05-13T21:30:14Z

@carlossanlop Looks like you may own this area of code. Can you take a look?

src/libraries/System.IO.Packaging/src/System/IO/Packaging/InternalRelationshipCollection.cs

src/libraries/System.IO.Packaging/src/System/IO/Packaging/OrderedDictionary.cs

carlossanlop

Thanks for submitting this change, @twsouthwick. I left a couple of comments.

src/libraries/System.IO.Packaging/src/System/IO/Packaging/OrderedDictionary.cs

stephentoub · 2020-05-26T17:06:19Z

src/libraries/System.IO.Packaging/src/System/IO/Packaging/OrderedDictionary.cs

+
+        public bool Remove(TKey key)
+        {
+            if (_dictionary.TryGetValue(key, out var value))


Can this use the Remove overload that gives back the associated value as an out? Then we wouldn't need the below call to Remove and would avoid the secondary lookup.

This has to compile against .NET Standard 1.3 and 2.0 and that's not available. Should I do an #if/#def?

Probably not worth it just for this.

src/libraries/System.IO.Packaging/src/System/IO/Packaging/InternalRelationshipCollection.cs

src/libraries/System.IO.Packaging/src/System/IO/Packaging/OrderedDictionary.cs

stephentoub

A few questions/comments, but otherwise looks good.

twsouthwick · 2020-05-28T17:12:26Z

The CI build got deprovisioned.

/azp run runtime

ghost · 2020-05-28T17:20:56Z

Hello @twsouthwick!

Because this pull request has the auto-merge label, I will be glad to assist with helping to merge this pull request once all check-in policies pass.

p.s. you can customize the way I help with merging this pull request, such as holding this pull request until a specific person approves. Simply @mention me (`@msftbot`) and give me an instruction to get started! Learn more here.

danmoseley · 2020-05-28T19:32:44Z

Thanks for contributing, @twsouthwick !

carlossanlop · 2020-05-28T21:12:50Z

Thanks @twsouthwick! 🎉

Dotnet-GitSync-Bot added the area-System.IO label May 7, 2020

carlossanlop reviewed May 15, 2020

View reviewed changes

src/libraries/System.IO.Packaging/src/System/IO/Packaging/InternalRelationshipCollection.cs Outdated Show resolved Hide resolved

carlossanlop reviewed May 15, 2020

View reviewed changes

src/libraries/System.IO.Packaging/src/System/IO/Packaging/OrderedDictionary.cs Outdated Show resolved Hide resolved

carlossanlop reviewed May 15, 2020

View reviewed changes

Use dictionary to track PackageRelationships instead of searching a list

1d3cd0f

twsouthwick force-pushed the internalrelatinoshipcollection-scaling branch from 62e4f38 to 1d3cd0f Compare May 16, 2020 00:08

jaredpar mentioned this pull request May 18, 2020

OSX machines are de-provisioned during CI / PR runs leading to failures #34472

Closed

stephentoub reviewed May 26, 2020

View reviewed changes

src/libraries/System.IO.Packaging/src/System/IO/Packaging/OrderedDictionary.cs Outdated Show resolved Hide resolved

stephentoub reviewed May 26, 2020

View reviewed changes

src/libraries/System.IO.Packaging/src/System/IO/Packaging/OrderedDictionary.cs Outdated Show resolved Hide resolved

stephentoub reviewed May 26, 2020

View reviewed changes

src/libraries/System.IO.Packaging/src/System/IO/Packaging/InternalRelationshipCollection.cs Show resolved Hide resolved

stephentoub reviewed May 26, 2020

View reviewed changes

src/libraries/System.IO.Packaging/src/System/IO/Packaging/OrderedDictionary.cs Show resolved Hide resolved

stephentoub approved these changes May 26, 2020

View reviewed changes

Responding to feedback

ccc5249

stephentoub approved these changes May 27, 2020

View reviewed changes

twsouthwick closed this May 28, 2020

twsouthwick reopened this May 28, 2020

twsouthwick added the auto-merge label May 28, 2020

twsouthwick removed the auto-merge label May 28, 2020

twsouthwick merged commit 0249b0f into dotnet:master May 28, 2020

twsouthwick deleted the internalrelatinoshipcollection-scaling branch May 28, 2020 18:48

carlossanlop added this to the 5.0 milestone May 28, 2020

twsouthwick mentioned this pull request May 30, 2020

WordprocessingDocument.Open is very slow dotnet/Open-XML-SDK#628

Closed

ghost locked as resolved and limited conversation to collaborators Dec 9, 2020

Conversation

twsouthwick commented May 7, 2020

Uh oh!

ghost commented May 7, 2020

Uh oh!

twsouthwick commented May 7, 2020

Uh oh!

twsouthwick commented May 13, 2020

Uh oh!

Uh oh!

Uh oh!

carlossanlop left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

stephentoub May 26, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

twsouthwick May 26, 2020

Choose a reason for hiding this comment

Uh oh!

stephentoub May 27, 2020

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

stephentoub left a comment

Choose a reason for hiding this comment

Uh oh!

twsouthwick commented May 28, 2020

Uh oh!

ghost commented May 28, 2020

p.s. you can customize the way I help with merging this pull request, such as holding this pull request until a specific person approves. Simply @mention me (@msftbot) and give me an instruction to get started! Learn more here.

Uh oh!

danmoseley commented May 28, 2020

Uh oh!

carlossanlop commented May 28, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

stephentoub May 26, 2020 •

edited

Loading

p.s. you can customize the way I help with merging this pull request, such as holding this pull request until a specific person approves. Simply @mention me (`@msftbot`) and give me an instruction to get started! Learn more here.