Optimize VB lookup by sharwell · Pull Request #26398 · dotnet/roslyn

sharwell · 2018-04-25T21:34:11Z

This change defers the acquisition of LookupResult instances from the shared pool
to a point where they are known to be needed. In highly-concurrent compilation
scenarios (using AnalyzerRunner), this change was observed to reduce overall
allocations in the compiler by up to 50% (30GiB) when processing Roslyn.sln.

Ask Mode template not completed

Customer scenario

What does the customer do to get into this situation, and why do we think this
is common enough to address for this release. (Granted, sometimes this will be
obvious "Open project, VS crashes" but in general, I need to understand how
common a scenario is)

Bugs this fixes

(either VSO or GitHub links)

Workarounds, if any

Also, why we think they are insufficient for RC vs. RC2, RC3, or RTW

Risk

This is generally a measure our how central the affected code is to adjacent
scenarios and thus how likely your fix is to destabilize a broader area of code

Performance impact

(with a brief justification for that assessment (e.g. "Low perf impact because no extra allocations/no complexity changes" vs. "Low")

Is this a regression from a previous update?

Root cause analysis

How did we miss it? What tests are we adding to guard against it in the future?

How was the bug found?

(E.g. customer reported it vs. ad hoc testing)

Test documentation updated?

If this is a new non-compiler feature or a significant improvement to an existing feature, update https://github.com/dotnet/roslyn/wiki/Manual-Testing once you know which release it is targeting.

This change defers the acquisition of LookupResult instances from the shared pool to a point where they are known to be needed. In highly-concurrent compilation scenarios (using AnalyzerRunner), this change was observed to reduce overall allocations in the compiler by up to 50% (30GiB) when processing Roslyn.sln.

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

+                    End If
+
+                    result?.MergeOverloadedOrPrioritized(currentResult, True)
+                    currentResult?.Free()


src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

+                End If
+
+                result?.MergeOverloadedOrPrioritized(currentResult, checkIfCurrentHasOverloads:=False)
+                currentResult?.Free()


jaredpar · 2018-04-25T21:42:46Z

CC @dotnet/roslyn-compiler

jcouv · 2018-04-25T22:19:53Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

+                    Dim currentResult As LookupResult = Nothing
                    LookupWithoutInheritance(currentResult, currentType, name, arity, options, accessThroughType, binder, useSiteDiagnostics)
-                    If result.IsGoodOrAmbiguous AndAlso currentResult.IsGoodOrAmbiguous AndAlso Not LookupResult.CanOverload(result.Symbols(0), currentResult.Symbols(0)) Then
+                    If result IsNot Nothing AndAlso result.IsGoodOrAmbiguous AndAlso currentResult IsNot Nothing AndAlso currentResult.IsGoodOrAmbiguous AndAlso Not LookupResult.CanOverload(result.Symbols(0), currentResult.Symbols(0)) Then


Nit: consider breaking this long line #Closed

➡️ Resolved by removing the need for the additional null checks that increased the line length #Resolved

jcouv

LGTM (iteration 2)
Thanks

333fred · 2018-04-25T23:05:58Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

                    ' Match the native compiler which reports ERR_XmlFeaturesNotAvailable in this case.
                    Dim useSiteError = ErrorFactory.ErrorInfo(ERRID.ERR_XmlFeaturesNotAvailable)
-                    singleResult = New SingleLookupResult(LookupResultKind.NotReferencable, binder.GetErrorSymbol(name, useSiteError), useSiteError)
+                    singleResult = New SingleLookupResult(LookupResultKind.NotReferencable, Binder.GetErrorSymbol(name, useSiteError), useSiteError)


Binder [](start = 92, length = 6)

Looks like this is an incorrect casing change

The target of the invocation is static

333fred · 2018-04-25T23:10:45Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

 ExitForFor:

                    If ambiguityDiagnostics IsNot Nothing Then
+                        If lookupResult Is Nothing Then


This is nested inside a check for lookupResult IsNot Nothing, should never be true.

333fred · 2018-04-25T23:11:59Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

                currentResult.Free()

-                If methodsOnly AndAlso lookupResult.IsGood Then
+                If methodsOnly AndAlso lookupResult IsNot Nothing AndAlso lookupResult.IsGood Then


lookupResult IsNot Nothing AndAlso lookupResult.IsGood [](start = 39, length = 54)

Perhaps outside the scope of this PR, but the second half of this if exactly matches the next if. We should just combine them and nest the first part. #Closed

Actually, wait, nevermind. I missed that this could change the result.

In reply to: 184231979 [](ancestors = 184231979)

333fred · 2018-04-25T23:14:33Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

                If constraintClass IsNot Nothing Then
                    LookupInClass(result, constraintClass, name, arity, options, constraintClass, binder, useSiteDiagnostics)
-                    If result.StopFurtherLookup Then
+                    If result IsNot Nothing AndAlso result.StopFurtherLookup Then


Nit: feels like all of these similar cases are perfect use cases for result?.Property = True

Nit: feels like all of these similar cases are perfect use cases for result?.Property = True

The comparison with true is not needed in VB

In reply to: 184232418 [](ancestors = 184232418)

333fred · 2018-04-25T23:16:33Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

-                   lookupResult.HasSymbol AndAlso
-                   lookupResult.Symbols(0).Kind <> SymbolKind.Method Then
+                If lookupResult IsNot Nothing AndAlso
+                    methodsOnly AndAlso


Nit: formatting is off by a space on these lines.

No, I just verified this is the formatting applied by the IDE.

333fred

Done review (iteration 2).

CyrusNajmabadi · 2018-04-25T23:22:01Z

A few questions: is this an issue for C#? If so, do we want to fix things there? If it's not an issue, do we know why not?

jaredpar · 2018-04-25T23:25:39Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb


                ' Add all viable members from type lookup
-                If result.IsGood Then
+                If result IsNot Nothing AndAlso result.IsGood Then


result?.IsGood

jaredpar · 2018-04-25T23:25:52Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb


                tmp.Free()
-                If result.IsGood Then
+                If result IsNot Nothing AndAlso result.IsGood Then


result?.IsGood

AlekseyTs · 2018-04-26T00:02:36Z

Should this change go to master?

AlekseyTs · 2018-04-26T04:31:42Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

-                If Not result.HasSymbol Then
-                    result.SetFrom(nonViable)
+                If result Is Nothing OrElse Not result.HasSymbol Then
+                    If result Is Nothing AndAlso nonViable.Kind <> LookupResultKind.Empty Then


nonViable.Kind <> LookupResultKind.Empty [](start = 49, length = 40)

It feels like this check might miss something, consider using !nonViable.IsClear instead

~~The result Is Nothing isn't needed on the inner if, as it is covered by the outer if.~~

AlekseyTs · 2018-04-26T04:39:07Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

                End If

-                lookupResult.MergePrioritized(singleResult)
+                If lookupResult Is Nothing And singleResult.Kind <> LookupResultKind.Empty Then


And [](start = 43, length = 3)

AndAlso?

💭 The branch didn't seem to offer anything here

AlekseyTs · 2018-04-26T04:46:10Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb


                ' If no viable or ambiguous results, look in Object.
-                If Not lookupResult.IsGoodOrAmbiguous AndAlso (options And LookupOptions.NoSystemObjectLookupForInterfaces) = 0 Then
+                If lookupResult Is Nothing OrElse (Not lookupResult.IsGoodOrAmbiguous AndAlso (options And LookupOptions.NoSystemObjectLookupForInterfaces) = 0) Then


lookupResult Is Nothing OrElse (Not lookupResult.IsGoodOrAmbiguous AndAlso (options And LookupOptions.NoSystemObjectLookupForInterfaces) = 0) [](start = 19, length = 141)

It feels like grouping is wrong here. Should (options And LookupOptions.NoSystemObjectLookupForInterfaces) = 0) be checked even when lookupResult Is Nothing? #Closed

AlekseyTs · 2018-04-26T04:48:05Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

                        End If
-                        lookupResult.MergePrioritized(currentResult)
+
+                        If lookupResult Is Nothing AndAlso currentResult.Kind <> LookupResultKind.Empty Then


currentResult.Kind <> LookupResultKind.Empty [](start = 59, length = 45)

!IsClear?

An empty RHS is a NOP in MergePrioritized. I can make the change if you wish for future-proofing or some other reason, but it would not change the current behavior.

AlekseyTs · 2018-04-26T05:16:22Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

-                If Not result.HasSymbol Then
-                    result.SetFrom(nonViable)
+                If result Is Nothing OrElse Not result.HasSymbol Then
+                    If result Is Nothing AndAlso nonViable.Kind <> LookupResultKind.Empty Then


If result Is Nothing AndAlso nonViable.Kind <> LookupResultKind.Empty Then [](start = 20, length = 74)

It feels fragile that we are basing the logic here on intimate knowledge of what SetFrom is going to do. One of the reasons that logic was extracted is to avoid duplicating it in multiple places and here (and in other similar places) we are reintroducing the duplication, making it unsafe to modify SetFrom's implementation. The same issue probably exists around other "merge" helpers that are surrounded with custom logic to pre-allocate/avoid-invocation logic.
It feels like the code could be somewhat simpler and more allocations could probably be avoided if we convert all the affected SetFrom/"merge" helpers into extension methods that take "this" parameter ByRef and allocate on as needed bases inside them. Ideally, in this file we should only be left with null checks before dereferencing and no code that tries to predict what helpers are going to do.

AlekseyTs · 2018-04-26T05:19:19Z

Done with review pass (iteration 2).

sharwell · 2018-04-26T14:02:29Z

A few questions: is this an issue for C#? If so, do we want to fix things there? If it's not an issue, do we know why not?

This problem was not observed in C# during profiling.

Should this change go to master?

The change is based on dev15.7.x and can merge into anything forward of that. It's a very high impact change for machines with many processors. In the least noticable case, allocations processing Roslyn.sln with both C# and VB analyzers enabled were reduced by 15.3% (20GB).

* Use VB handling of nullable conditions * Remove unnecessary null check * Fix logic error in condition

333fred · 2018-04-26T17:35:02Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb

                ' it may look like a Good result, but it may have ambiguities inside
                ' so we need to check that to be sure.
-                If lookupResult.IsGood Then
+                If lookupResult IsNot Nothing AndAlso lookupResult.IsGood Then


Still more instances of lookupResult?.IsGood substitution.

CyrusNajmabadi · 2018-04-26T18:04:49Z

A few questions: is this an issue for C#? If so, do we want to fix things there? If it's not an issue, do we know why not?

This problem was not observed in C# during profiling.

That leads to hte latter part of my question: If it's not an issue, do we know why not?

C# also uses a pooled LookupResult object. So something about C# is making it so that the same issue is not observed (even though they're used extensively in c# binding as well).

To me, it woudl be worthwhile to understand what compilation pattern C# is employing that makes this a non-issue. It might then be better to adopt that pattern in the VB compiler versus trying to address things from this direction.

AlekseyTs · 2018-04-26T20:52:41Z

src/Compilers/VisualBasic/Portable/Binding/Binder_Lookup.vb


                ' If no viable or ambiguous results, look in Object.
-                If Not lookupResult.IsGoodOrAmbiguous AndAlso (options And LookupOptions.NoSystemObjectLookupForInterfaces) = 0 Then
+                If lookupResult?.IsGoodOrAmbiguous <> True AndAlso (options And LookupOptions.NoSystemObjectLookupForInterfaces) = 0 Then


lookupResult?.IsGoodOrAmbiguous <> True [](start = 19, length = 39)

This still looks suspicious. In VB lookupResult?.IsGoodOrAmbiguous <> True will be Boolean? and null value is not true, but I think we would want to continue when lookupResult is Nothing. #Closed

The original code is Not lookupResult.IsGoodOrAmbiguous. An empty LookupResult would have produced True for this expression. The new expression is intended to treat Nothing the same as empty, and also produce True for the expression.

The new expression is intended to treat Nothing the same as empty, and also produce True for the expression.

Why do you think so? Comparing nullable null to anything yields null in VB, not true, not false

In reply to: 184547523 [](ancestors = 184547523)

Is there any short form here? The alternative I know of is this expression:

lookupResult Is Nothing OrElse Not lookupResult.IsGoodOrAmbiguous

Is there any short form here

I think this is fine. There is an alternative Not If(lookupResult?.IsGoodOrAmbiguous, False), but I think explicit null check is easier to follow.

In reply to: 184820315 [](ancestors = 184820315)

AlekseyTs · 2018-04-26T20:55:54Z

Done with review pass (iteration 3). I am still not comfortable with the issue raised in #26398 (review)

sharwell · 2018-04-27T22:35:56Z

That leads to the latter part of my question: If it's not an issue, do we know why not?

I didn't look into it. This is a targeted fix for a localized/acute problem revealed by profiling. I couldn't find an explanation for why the object pool for VB was missing at the observed rate, but the results were consistent across more than a dozen runs.

I am still not comfortable with the issue raised in #26398 (review)

I don't think I'm going to be able to address this item. I plan to address the remaining items aside from this one and then leave the final direction open:

Accept the current PR, possibly with a bug filed to address this item as a follow-up
Transfer ownership of the PR to someone else to complete the work on this item
File a bug for the original issue (abandon PR with no immediate replacement)

The <> operator in VB behaves differently from the != operator and C# when comparing nullable values. The semantics of the latter were intended in this code, so the expression is expanded to correct the logic.

AlekseyTs · 2018-04-27T22:54:22Z

I didn't look into it. This is a targeted fix for a localized/acute problem revealed by profiling. I couldn't find an explanation for why the object pool for VB was missing at the observed rate, but the results were consistent across more than a dozen runs.

I also think we should try to understand what is going on here. Pools are supposed to be fast and they were introduced exactly to make it relatively cheap to "allocate" objects.

Are we leaking pooled instances somewhere?
Is the scenario too contrived, too many threads are trying to do a lookup at the same time and simply use up all 128 slots available?
Would increasing the size of the pool help?

sharwell · 2018-04-28T16:18:16Z

Are we leaking pooled instances somewhere?

I could not find any evidence of this.

Is the scenario too contrived, too many threads are trying to do a lookup at the same time and simply use up all 128 slots available?

AnalyzerRunner is intended to represent real-world scenarios as closely as possible. The inner loop can be reviewed here for accuracy:

https://github.com/ivanbasov/roslyn/blob/605212052fbca656b11b6800605c01531900fa0b/src/Tools/AnalyzerRunner/Program.cs#L362-L401

Would increasing the size of the pool help?

It's possible this could help, but it's not clear what size would help. It's also possible that the frequency of dropped objects in Free increases with the overall concurrency level.

Another alternative solution is making LookupResult a value type.

AlekseyTs · 2018-04-30T21:08:31Z

It looks like this change delayed LookupResult.GetInstance() calls only in 3 places( out of total 12) where it was called in Binder_Lookup.vb. Two of the delayed calls are inside loops, where LookupResult is allocated and freed on each iteration.
I am curious whether it would be sufficient to simply move two those allocations out of the loops, i.e. allocate before, free after and reuse after clearing on each iteration.
If that doesn't work, I think more investigation is needed to understand why 128 items in the pool is not enough for the AnalyzerRunner, what is using all these instances and why. If at the end we determine that there is a real reason that normal use of the pool isn't working for name lookup in VB, we should come up with a new strategy and apply it consistently across the board rather than doing it in ad hoc manner, creating coupling between components in the process (lookup routines, merge routines, etc.).

jcouv · 2018-05-09T17:46:45Z

@sharwell I'm marking the PR as private for the moment. Please ping when the PR is ready to review again.

sharwell · 2018-05-10T23:08:55Z

Closing this issue and filed #26779 instead

sharwell requested a review from a team as a code owner April 25, 2018 21:34

jaredpar added the Area-Compilers label Apr 25, 2018

jaredpar added this to the 15.8 milestone Apr 25, 2018

jaredpar reviewed Apr 25, 2018

View reviewed changes

jcouv reviewed Apr 25, 2018

View reviewed changes

Simplify null checks related to lazy initialization

b1b4ef6

jcouv approved these changes Apr 25, 2018

View reviewed changes

333fred reviewed Apr 25, 2018

View reviewed changes

jaredpar reviewed Apr 25, 2018

View reviewed changes

AlekseyTs reviewed Apr 26, 2018

View reviewed changes

Simplification and logic correction from code review

3b7ad0c

* Use VB handling of nullable conditions * Remove unnecessary null check * Fix logic error in condition

sharwell force-pushed the optimize-vb-lookup branch from 1e3b904 to 3b7ad0c Compare April 26, 2018 15:43

333fred reviewed Apr 26, 2018

View reviewed changes

AlekseyTs reviewed Apr 26, 2018

View reviewed changes

sharwell added 2 commits April 27, 2018 17:49

Fix logic error due to misuse of <> with nullable operand

6677e76

The <> operator in VB behaves differently from the != operator and C# when comparing nullable values. The semantics of the latter were intended in this code, so the expression is expanded to correct the logic.

Simplify 'a IsNot Nothing AndAlso a.Property'

1b31cf2

sharwell closed this Apr 27, 2018

sharwell reopened this Apr 27, 2018

jcouv added the PR For Personal Review Only The PR doesn’t require anyone other than the developer to review it. label May 9, 2018

sharwell mentioned this pull request May 10, 2018

VB LookupResult allocations dominating code analysis scenarios #26779

Closed

sharwell closed this May 10, 2018

Conversation

sharwell commented Apr 25, 2018

Customer scenario

Bugs this fixes

Workarounds, if any

Risk

Performance impact

Is this a regression from a previous update?

Root cause analysis

How was the bug found?

Test documentation updated?

Uh oh!

This comment was marked as resolved.

Uh oh!

This comment was marked as resolved.

Uh oh!

jaredpar commented Apr 25, 2018

Uh oh!

jcouv Apr 25, 2018 • 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!

sharwell Apr 25, 2018 • edited by jcouv Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jcouv left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

333fred Apr 25, 2018 • 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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

333fred left a comment

Choose a reason for hiding this comment

Uh oh!

CyrusNajmabadi commented Apr 25, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

AlekseyTs commented Apr 26, 2018

Uh oh!

AlekseyTs Apr 26, 2018 • 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!

AdamSpeight2008 Apr 28, 2018 • 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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

AlekseyTs Apr 26, 2018 • 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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jcouv Apr 25, 2018 •

edited

Loading

sharwell Apr 25, 2018 •

edited by jcouv

Loading

333fred Apr 25, 2018 •

edited

Loading

AlekseyTs Apr 26, 2018 •

edited

Loading

AdamSpeight2008 Apr 28, 2018 •

edited

Loading

AlekseyTs Apr 26, 2018 •

edited

Loading

AlekseyTs Apr 26, 2018 •

edited

Loading

sharwell commented Apr 27, 2018 •

edited

Loading