Reduce allocations in TokenSegment.TryMatch

[kartheekp-ms]

Internal Tracking issue

[Nigusu-Allehu]

Proposed Solution

• Removing substrings by using a ReadOnlySpan
• Passing the full path and the indices to the parser.

Result

• According to my attempts using Span (passing the full path and the indices) was able to help
  me reduce allocation by the TryMatch function, However it resulted in the helper functions
  making the allocations

• I looked into replacing the helpers functions so that they also used Span. However the
  helper functions eventually call parses that almost always do lookups in a dictionary, which
  requires a string as a key(ReadOnlySpan can not be used for the dictionaries, it is stack only
  data type). As a result, eventually some function will end up producing the string.

Conclusion
Even though I was able to mitigate producing substrings in the TryMatch function and
almost all the functions it calls, all the parsers it uses eventually almost always do a lookup
in a dictionary and as a result end up producing a substring.
As a result, improving the performance of TryMatch by removing the substrings it produces
will only result in the better performance of TryMatch, however the system in general does
not improve in performance

possible solution

• We currently, store file paths for a package content as a string. For example, "contetFiles/any/img.jpg"
• This is formed by looping through the directories that would lead to img.jpg and concatenating them.
• The TryMatch function is then tasked with tokenizing this path by delimiter "/" when we could have actually kept the file path to img.jpg as a list of tokens(the directories) which will lead to img.jpg. This way TryMatch won't have to tokenize a long file path string and result in unnecessary allocations. In addition, TryMatch won't have to loop through each character in a file path, making it faster.
• Drawback: I am not sure yet, but if we need the file paths as a string at any point, we will have to do concatenation; possibly multiple times.

[davkean]

@Nigusu-Allehu Can you point me to the dictionary lookup?

[Nigusu-Allehu]

@Nigusu-Allehu Nigusu Yenework FTE Can you point me to the dictionary lookup?

The TryMatch method eventually, most of the time, calls on of the parsers in the ManagedCodeConventions.cs. Here is an example : https://github.com/NuGet/NuGet.Client/blob/b02fdbb36d34947c24496b2c0b505aa785bc657f/src/NuGet.Core/NuGet.Packaging/ContentModel/ManagedCodeConventions.cs#L128

[zivkan]

Is this code path only used by packages that have contentFiles/, or is it also used by lib/, build/, and so on?

[Nigusu-Allehu]

It is used by all of them. https://github.com/NuGet/NuGet.Client/blob/b02fdbb36d34947c24496b2c0b505aa785bc657f/src/NuGet.Core/NuGet.Packaging/ContentModel/ManagedCodeConventions.cs#L411 in here there is a list of patterns that a package could have for its asset files. TokenSegments in these patterns always use a parser. For example for the pattern "lib/{tfm}/{assembly}", tfm and assembly are TokenSegments and as a result a parser would be used to identify the tfm and assembly.

[zivkan]

Ok. What I'm thinking is that NuGet could "pre-compute" assets lists per TFM on package extraction, and save the results in the values in the .nupkg.metadata computed file. Then, when NuGet is doing asset selection for a project, "all" it has to do is select the "closest TFM", then it already has the List<string> of matching files, and per-project restore won't need to use ManagedCodeConventions at all.

This will be a lot more difficult to implement than refactoring a single class for optimizations. But I think it has the potential for significant perf improvements. Other people should definately think about the suggestion, in case I'm way off base. CI restore might not benefit a whole lot, since they'll have to extract packages and do the asset pre-compute on every restore. But on developer boxes where the global packages folder isn't deleted frequently (for example, where customers use VS), I think it could really have a decent (maybe even big?) improvement.

I think NuGet's "convention based" approach makes manually creating packages a little easier, but I think it harms restore performance. We can't change the past (and I might be wrong that a more explicit package format would be faster to restore), but we can take advantage of NuGet's "generated on extraction" files. The .nupkg.metadata file already has a version property, so we can detect when an older version without the asset pre-compute exists, then do a one-time update.

Unfortunately, for read-only fallback folders, we'll need to keep using the convention based approach, but if whatever creates these fallback folder layouts updates to a newer NuGet, then the higher .nupkg.metadata file version will be pre-created there.

However, the big question is whether this idea will actually benefit perf. ManagedCodeConventions, and TokenSegment cause a lot of allocations, but so can deserializing "large" json files. Obviously, I suspect reading the json file will be better than doing convention based filtering every restore. But I don't think it's a 100% sure thing, so if there's a way to quickly prototype and benchmark to validate it's a good idea, that can tell us if it's worthwhile doing a big change.

[davkean]

@Nigusu-Allehu Is this the table you a referring to? This is currently defined using strings, but doesn't have to be, this could be:

        private readonly Dictionary<ReadOnlyMemory<Char>, Dictionary<ReadOnlyMemory<Char>, object>> _table = new Dictionary<ReadOnlyMemory<Char>, Dictionary<ReadOnlyMemory<Char>, object>>(ReadOnlyMemoryCharOrdinalComparer.Instance);       

Where ReadOnlyMemoryCharOrdinalComparer is a comparer that delegates to MemoryExtensions.Equals and a custom GetHashCode. Or an implementation similar to Drew's StringPool which takes a Span and returns a "string".

[davkean]

I do want to say that @zivkan's idea is a good one, but I don't want to lose sight here that there might be an easier approach we can take to reduce the allocations on this path first.

[zivkan]

I intended to write "if we can't find easy wins" in my previous message. Looks like I forgot to 🤦‍♂️

[Nigusu-Allehu]

@Nigusu-Allehu Nigusu Yenework FTE Is this the table you a referring to? This is currently defined using strings, but doesn't have to be, this could be:

        private readonly Dictionary<ReadOnlyMemory<Char>, Dictionary<ReadOnlyMemory<Char>, object>> _table = new Dictionary<ReadOnlyMemory<Char>, Dictionary<ReadOnlyMemory<Char>, object>>(ReadOnlyMemoryCharOrdinalComparer.Instance);       

Where ReadOnlyMemoryCharOrdinalComparer is a comparer that delegates to MemoryExtensions.Equals and a custom GetHashCode. Or an implementation similar to Drew's StringPool which takes a Span and returns a "string".

Thank you, David! I will look into it

[nkolev92]

Related PRs:

• Reduce allocations in TokenSegment.TryMatch NuGet.Client#5933
• Use ReadOnlyMemory when calculating the related file extensions NuGet.Client#5943
• Propagate match only in asset selection to reduce allocations when grouping NuGet.Client#5944 The selection is currently "group", and then "select most compatible".
  The group part can pretty much be done without as many allocations.

What I'll look into next is the number of dictionaries we create.
After all the changes in the above PRs, we've shaved off about ~25MB, and from what remains new Dictionary tends to be 40%.

[nkolev92]

A couple of more:

• Use concurrent dictionary in related extensions calculation NuGet.Client#5951
• Reduce collections resizing and yield allocations NuGet.Client#5952

The 2nd is not just this codepath, but related as well, and the savings are about ~50MB there.

[nkolev92]

A 6th change:

• Change the way raw values are preserved in TryParse NuGet.Client#5960

After all these changes, we're down from:

Name                                                                                                                                                                                                                     	Inc %	           Inc
 nuget.packaging!NuGet.ContentModel.Infrastructure.PatternExpression+TokenSegment.TryMatch(class NuGet.ContentModel.ContentItem&,class System.String,class System.Collections.Generic.IReadOnlyDictionary`2,int32,int32&)	  1.3	   110,683,792
+ mscorlib.ni!System.String.Substring(Int32, Int32)                                                                                                                                                                      	  0.4	    37,942,624
+ mscorlib.ni!System.Collections.Generic.Dictionary`2[System.__Canon,System.__Canon].Insert(System.__Canon, System.__Canon, Boolean)                                                                                     	  0.4	    35,833,368
+ clr!JIT_New                                                                                                                                                                                                            	  0.4	    32,210,392
+ nuget.packaging!ContentPropertyDefinition.TryLookup 

to:

Name                                                                                                                                                                                                                     	Inc %	          Inc
 nuget.packaging!NuGet.ContentModel.Infrastructure.PatternExpression+TokenSegment.TryMatch(class NuGet.ContentModel.ContentItem&,class System.String,class System.Collections.Generic.IReadOnlyDictionary`2,int32,int32&)	  0.8	   69,501,008
+ mscorlib.ni!System.Collections.Generic.Dictionary`2[System.__Canon,System.__Canon].Insert(System.__Canon, System.__Canon, Boolean)                                                                                     	  0.4	   32,375,832
+ nuget.packaging!NuGet.ContentModel.ContentItem.get_Properties()                                                                                                                                                        	  0.2	   19,186,544
+ nuget.packaging!ContentPropertyDefinition.TryLookup                                                                                                                                                                    	  0.1	   10,983,648
+ clr!JIT_New            

40MB of improvement in TryMatch, or about 36% in OrchardCore scenarios.

What's leftover is dictionary usage for tokens found.
All these tokens are currently used, so there are no empty dictionaries created. The dictionary size varies from 1-3 in my tests, but things like locale can bring it to 4 max as far as I can tell.
Changing that would require more breaking changes, but the dynamic nature of the token names is why dictionary was chosen as very appropriate in the first place. I'll play with it a little bit, but it's getting more and more difficult.

At this point, there are might be more opportunities for improvement in other codepaths rather than this one. I'll timebox some POC tests with removing the dictionary and see if I can get that to improve.

[davkean]

Great progress @nkolev92, appreciate the updates.

[nkolev92]

1. Instead of dictionary I pack all properties into fields: Pack ContentItem with fields NuGet.Client#5962. This saves us about 40MB. After this change we're down a total of 80MB to 36MB of allocations in the TryParse codepath.
2. In the compatibility checking for projects, there's code that assumes non-default behavior. The non-default behavior is only project.json specific, so separating these 2 codepaths shaves off between 12-15MB total in CreateLockFile. I'll do a follow-up PR on that since it's calling codepaths.

At this point, I think I've reached my limit. I think the numbers look pretty good. If anyone is curious, my current playground branch is (along with benchmark code) is https://github.com/NuGet/NuGet.Client/compare/nkolev92-benchmarks?expand=1

[nkolev92]

#13712 fixed by NuGet/NuGet.Client#5977, is #2 above. Reduces 100MB in OrchardCore. It affects TryMatch a little bit as well since it gets called less frequently.

I'll collect a final trace when both PRs are merged.

[nkolev92]

When NuGet/NuGet.Client#5977 is merged, it'll be down to ~34MB.

Name                                                                                                                                                                                                                     	Inc %	          Inc
 nuget.packaging!NuGet.ContentModel.Infrastructure.PatternExpression+TokenSegment.TryMatch(class NuGet.ContentModel.ContentItem&,class System.String,class System.Collections.Generic.IReadOnlyDictionary`2,int32,int32&)	  0.4	   34,245,616
+ nuget.packaging!PatternExpression.Match                                                                                                                                                                                	  0.4	   34,245,616
 + nuget.packaging!ContentItemCollection.PopulateItemGroups                                                                                                                                                              	  0.2	   20,487,376
 + nuget.packaging!ContentItemCollection.FindItemsImplementation                                                                                                                                                         	  0.1	   13,758,240