ImmutableHashSetExtensions.AddRange could probably be faster

[rauhs]

Hi all,

on my dev PC I'm noticing a very busy (CPU) 'Roslyn.Worker` (Resharper). Our code base is relatively big. 28k files.

I've just ran a very quick 20s PerfView and noticed the following:

 microsoft.codeanalysis.netanalyzers!AnalysisEntity.WithMergedInstanceLocation                                                                                                                       65.2      22,616     0.3     95       0     J2KJOMLNLNKMLKJKLLMNMNNMNNNMMNKG    21.093  10,351.362
+ microsoft.codeanalysis.netanalyzers!Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.PointsToAnalysis.PointsToAnalysis+PointsToAbstractValueDomain.Merge(PointsToAbstractValue,PointsToAbstractValue)  56.8      19,692     0.4    137       0     1HIHKJIIJKIIJIHIJIKKJJKKKKKJJJIC    21.093  10,351.362
|+ microsoft.codeanalysis.netanalyzers!ImmutableHashSetExtensions.AddRange                                                                                                                           53.5      18,552     1.1    369       0     1GIHJHGHIIGIGHHHIHHJIJIIJIIIJIGC    21.093  10,351.362

Note: This method is about 66% of all my CPU time.

which lead me to:

https://github.com/dotnet/roslyn-analyzers/blob/main/src/Utilities/Compiler/Extensions/ImmutableHashSetExtensions.cs#L10-L35

I think this could be made faster. Note, the entire performance is in "Union" (which is what's called inside HashSet.ToImmutableHashSet).

I think it would be better to:

1. Take the bigger immutable hashset.
2. Call bigger.Union(smaller)

This should be strictly faster since currently set.ToImmutable does the same but starts with an empty set.

I'm sorry I can't try it out myself. I have honestly no clue about roslyn analyzers and this repo.

There is also immutableHashSet.Union() but it seems it does not take the "bigger" set as the base of where to start from.

[sharwell]

Can you rebuild from the command line with /p:ReportAnalyzer=true /bl? This will produce an msbuild.binlog file in the build directory that can be opened with the MSBuild Log Viewer. In the middle pane you'll see an Analyzer Summary similar to the one shown in KirillOsenkov/MSBuildStructuredLog#452. Can you get some screenshots showing the cost of specific analyzers in this build?

[sharwell]

Take the bigger immutable hashset.

We can't make this change blindly. The algorithm currently has specific semantics surrounding which instance of two equal items is included in the final set, and this is order-dependent.

It does seem likely that we can improve things by calling Union instead of constructing a whole new set.

[rauhs]

Thanks for the quick reply and instructions.

Result:

Analyzer Summary
    14:22.455   SonarAnalyzer.CSharp, Version=8.33.0.0, Culture=neutral, PublicKeyToken=c5b62af9de6d7244
        SonarAnalyzer.Rules.CSharp.DeadStores (S1854) = 6:25.949
        SonarAnalyzer.Rules.CSharp.PrivateFieldUsedAsLocalVariable (S1450) = 1:22.248
        SonarAnalyzer.Rules.CSharp.ClassAndMethodName (S100, S101) = 23.728 s
        [...]
    2:32.987   Microsoft.CodeAnalysis.NetAnalyzers, Version=6.0.5.1901, Culture=neutral, PublicKeyToken=31bf3856ad364e35
        Microsoft.CodeQuality.Analyzers.Maintainability.AvoidDeadConditionalCode (CA1508) = 47.422 s
        Microsoft.NetCore.Analyzers.Security.ReviewCodeForInformationDisclosureVulnerabilities (CA3004) = 20.500 s
        Microsoft.NetCore.Analyzers.Runtime.DisposeObjectsBeforeLosingScope (CA2000) = 16.725 s
        [...]
    1:28.953   StyleCop.Analyzers, Version=1.1.118.34620, Culture=neutral, PublicKeyToken=cfeb5dbada5e1c25
        StyleCop.Analyzers.ReadabilityRules.SA1121UseBuiltInTypeAlias (SA1121) = 5.547 s
        StyleCop.Analyzers.LayoutRules.SA1516ElementsMustBeSeparatedByBlankLine (SA1516) = 4.522 s
        [...]
    5.853 s   Microsoft.CodeAnalysis.CSharp.NetAnalyzers, Version=6.0.5.1901, Culture=neutral, PublicKeyToken=31bf3856ad364e35
    1.397 s   nunit.analyzers, Version=3.1.0.0, Culture=neutral, PublicKeyToken=null

I reported it to SonarSource.

Though, I'm not sure at this point if this should be fixed by both or neither :)

FWIW, some more PerfView traces:

  ||+ microsoft.codeanalysis.netanalyzers!Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.DataFlowAnalysis`5[System.__Canon,System.__Canon,System.__Canon,System.__Canon,System.__Canon].RunCore(class Microsoft.CodeAnalysis.FlowAnalysis.ControlFlowGraph,class Analyzer.Utilities.PooledObjects.PooledSortedSet`1,class Analyzer.Utilities.PooledObjects.PooledSortedSet`1,!0,class Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.DataFlowAnalysisResultBuilder`1,class Analyzer.Utilities.PooledObjects.PooledHashSet`1,class Analyzer.Utilities.PooledObjects.PooledDictionary`2>,class Analyzer.Utilities.PooledObjects.PooledDictionary`2,class Analyzer.Utilities.PooledObjects.PooledDictionary`2,class Analyzer.Utilities.PooledObjects.PooledDictionary`2>>,class Analyzer.Utilities.PooledObjects.PooledDictionary`2,bool)	 81.9	   4,102
  |||+ microsoft.codeanalysis.netanalyzers!Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.PredicatedAnalysisDataDomain`2[System.__Canon,System.__Canon].Merge(!0,!0)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                	 74.7	   3,741
  ||||+ microsoft.codeanalysis.netanalyzers!PointsToAnalysisData.WithMergedData                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   	 74.7	   3,741
  |||| + microsoft.codeanalysis.netanalyzers!Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.AnalysisEntityBasedPredicateAnalysisData`1[System.__Canon]..ctor(class Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.AnalysisEntityBasedPredicateAnalysisData`1,class Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.AnalysisEntityBasedPredicateAnalysisData`1,class Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.MapAbstractDomain`2)                                                                                                                                                                                                                                                                                                                                                                                                    	 74.7	   3,741
  ||||  + microsoft.codeanalysis.netanalyzers!Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.AnalysisEntityMapAbstractDomain`1[System.__Canon].Merge(class Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.DictionaryAnalysisData`2,class Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.DictionaryAnalysisData`2)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       	 74.6	   3,738
  ||||  |+ microsoft.codeanalysis.netanalyzers!AnalysisEntity.WithMergedInstanceLocation                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          	 42.8	   2,144
  ||||  |+ mscorlib.ni!?                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          	 24.9	   1,249
  ||||  ||+ microsoft.codeanalysis.netanalyzers!Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.CacheBasedEquatable`1[System.__Canon].GetOrComputeHashCode()                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         	 22.3	   1,117
  ||||  |||+ microsoft.codeanalysis.netanalyzers!AnalysisEntity.ComputeHashCodeParts                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              	 18.8	     943
  ||||  ||||+ microsoft.codeanalysis.netanalyzers!Microsoft.CodeAnalysis.FlowAnalysis.DataFlow.CacheBasedEquatable`1[System.__Canon].GetOrComputeHashCode()                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       	 18.7	     936
  ||||  |||||+ microsoft.codeanalysis.netanalyzers!PointsToAbstractValue.ComputeHashCodeParts                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     	 18.3	     916
  ||||  ||||||+ microsoft.codeanalysis.netanalyzers!HashUtilities.Combine                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         	 17.1	     854

[rauhs]

Another side note: Is there an easier way to investigate what assembly (or file) is the issue? I'm personally a big fan of ETW events. Has roslyn analzyer thought about adding ETW event? For instance Analyzing{Assembly,Namespace,File}{Start,Stop} events.

Getting the our project to finish compiling with the analyzers on was very challenging. I had to take a smaller part and run the compilation on it. Building a full solution with the analyzer never finished.

[rauhs]

Sam,

just a quick note before the weekend: I removed all the SonarSource analyzers completely. Still seeing a lot of time in the PointsToAbstractValueDomain.Merge function. So I think still a good idea to potentially improve something in there.

I wish I could help more but I have no clue how I would try out any source code changes in this repo :/

[Therzok]

There is a section in the README about setting up the environment, although it's a bit hidden between other sections.