Reducing allocations in completion by genlu · Pull Request #61620 · dotnet/roslyn

genlu · 2022-06-01T00:39:26Z

separate from #61477, which only include changes related to new editor API. This one deals with allocations completely controlled by Roslyn

The traces below are collected for a simple scenario (enabled import completion, triggered completion list 5 times on empty filter text, and each time refreshed the list once by typing an additional character). Top results are the baseline, and the bottom is with this change.

Total allocation is reduced from 251mb to 133mb (-47%), when comparing stacks including "Microsoft.CodeAnalysis" and "Completion"

Here's some of the most noticeable improvements (~ -100mb from those 4 types alone)

Here's the comparison of LOH allocation

Allocations from following types are no longer in LOH. and the rest will be addressed in #61477

Microsoft.CodeAnalysis.Completion.CompletionItem[]  
System.ValueTuple`2[Microsoft.CodeAnalysis.Completion.CompletionItem,System.Nullable`1[Microsoft.CodeAnalysis.PatternMatching.PatternMatch]][]
Microsoft.CodeAnalysis.Location[]

…locations

CyrusNajmabadi · 2022-06-02T00:32:16Z

src/Features/Core/Portable/Completion/CompletionItemFlags.cs


-        public static bool IsExpanded(this CompletionItemFlags flags)
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        public static bool IsExpanded(CompletionItemFlags flags)


what was the benefit of this change? (Also, it feels like in extension method form, it would still be ok).

This stood out to me as well. The changes related to this helper type seem unnecessary.

No, I was just trying to see if it makes any difference (it didn't). Reverted

CyrusNajmabadi · 2022-06-02T00:33:05Z

src/Workspaces/Core/Portable/Shared/Extensions/ISymbolExtensions.cs

-                (s.Locations.Any(isSymbolDefinedInSource) || !s.HasUnsupportedMetadata) &&
+                // Check if symbol is namespace (which is always visible) first to avoid realizing all locations
+                // of each namespace symbol, which might end up allocating in LOH
+                (s.IsNamespace() || s.Locations.Any(isSymbolDefinedInSource) || !s.HasUnsupportedMetadata) &&


interesting. there are enough namespaces to matter? how many were you seeing in practice?

From the trace, allocations of 1.3MB on LOH, and 30MB on regular heap is eliminated by this single check

I have seen this in the past as well - accessing Locations or DeclaringSyntaxReferences for namespace symbols is costly as the declaring syntax references are not cached on the namespace symbol by the compiler.

CyrusNajmabadi · 2022-06-02T00:34:09Z

src/Features/Core/Portable/Completion/CompletionList.cs

+            if (items is ImmutableArray<CompletionItem>)
+                _lazyItems = new(() => (ImmutableArray<CompletionItem>)ItemsInternal);
+            else
+                _lazyItems = new(() => ItemsInternal.ToImmutableArray(), System.Threading.LazyThreadSafetyMode.PublicationOnly);


why PublicationOnly?

Should I use ExecutionAndPublication? I don't think it matters much though, since the value is not accessed concurrently in Roslyn.

well, i'm curious why this line is different than the one above. :) i would expect you'd have the same thread-safety-choices for both.

Note: you can also simplify this to a single lazy that does ToImmutableArrayOrEmpty inside (that extension already checks if the underlying type is an ImmutableArray).

CyrusNajmabadi · 2022-06-02T00:35:01Z

src/Features/Core/Portable/Completion/CompletionList.cs

            else
            {
-                return Create(newSpan, newItems, newRules, newSuggestionModeItem);
+                return Create(newSpan, newItems, newRules, newSuggestionModeItem, isExclusive: false);


why isExclusive: false here instead of _isExclusive?

This was the previous behavior, can't remember why though. Will take a closer look later, but not gonna change in this PR.

gotcha. it is concerning. but i agree it matches from before. can you file issue?

CyrusNajmabadi · 2022-06-02T00:35:39Z

src/Features/Core/Portable/Completion/CompletionServiceWithProviders.cs

+            // so use a dedicated pool to minimize array allocations. Set the size of pool to a small
+            // number 5 because we don't expect more than a couple of callers at the same time.
+            private static readonly ObjectPool<Dictionary<string, object>> s_uniqueSourcesPool = new(factory: () => new(), size: 3);
+            private static readonly ObjectPool<List<CompletionItem>> s_sortListPool = new(factory: () => new(), size: 3);


comment says '5', but code says '3' :)

Is it really helpful to have our own pools here? I would expect that just using PooledDictionary would be fine. There would b an underlying array, but we'd never resize it in practice.

or is thsi because we want to reuse the Dictionary entirely, even if it grew large (something the normal pools don't do).

but we'd never resize it in practice.

I think you are right, but since the Dictionary<string, object> might be a commonly used type, and we know the dictionary would get large here, hold on to the these few in our own pool would make sure we don't end up with a shared pool of large dictionaries.

CyrusNajmabadi · 2022-06-02T00:38:43Z

src/EditorFeatures/Core/IntelliSense/AsyncCompletion/ItemManager.CompletionListUpdater.cs

            private readonly bool _showCompletionItemFilters;

-            private readonly Func<ImmutableArray<(RoslynCompletionItem, PatternMatch?)>, string, ImmutableArray<RoslynCompletionItem>> _filterMethod;
+            private readonly Action<IEnumerable<(RoslynCompletionItem, PatternMatch?)>, string, IList<RoslynCompletionItem>> _filterMethod;


don't love taking a collection type weakly as IEnumerable. Can we tie it to a more strong interface which indicates the value will be realized and not lazy?

I think it really is an enumerable in this case, I used it instead of a collection type to avoid using another pooled list, but I guess it'd be fine to have another one-time allocation.

CyrusNajmabadi · 2022-06-02T00:39:27Z

src/Features/Core/Portable/Completion/CommonCompletionService.cs

-        internal override ImmutableArray<CompletionItem> FilterItems(Document document, ImmutableArray<(CompletionItem, PatternMatch?)> itemsWithPatternMatch, string filterText)
+        internal override void FilterItems(
+           Document document,
+           IEnumerable<(CompletionItem, PatternMatch?)> itemsWithPatternMatch,


same concern about IEnuemrable.

CyrusNajmabadi · 2022-06-02T00:40:10Z

src/Features/Core/Portable/Completion/CompletionService.cs

+
+            var builder = ImmutableArray.CreateBuilder<CompletionItem>();
+            FilterItems(helper, itemsWithPatternMatch, filterText, builder);
+            return builder.MoveToImmutable();


doc how you know MoveToImmutable is safe here.

😬 This method (MoveToImmutable) is a scary trap

CyrusNajmabadi · 2022-06-02T00:43:36Z

Overall i really like this. I'm not a huge fan though of weak-types like IEnumerable (which make lazyness unclear, and which may interface dispatch a ton), or even the IReadOnlyList-like types. Would it be possible to just update all these paths that take ImmutableArray and just move them to SegmentedArray to avoid the LOH issues?

Note: much of the PR is 100% ok with me, it's more about seeing if there's a simpler choice in terms of types to use that can give most/all of hte benefit without having to mix/match between all these different intermediary types.

sharwell · 2022-06-02T04:40:45Z

src/Features/Core/Portable/Completion/CompletionItemFlags.cs

+    internal static class CompletionItemFlagsHelper
    {
-        public static bool IsCached(this CompletionItemFlags flags)
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]


❔ Do we have an indication that this is not currently getting inlined?

sharwell · 2022-06-02T04:43:36Z

src/Features/Core/Portable/Completion/CompletionServiceWithProviders.cs

+            // so use a dedicated pool to minimize array allocations. Set the size of pool to a small
+            // number 5 because we don't expect more than a couple of callers at the same time.
+            private static readonly ObjectPool<Dictionary<string, object>> s_uniqueSourcesPool = new(factory: () => new(), size: 3);
+            private static readonly ObjectPool<List<CompletionItem>> s_sortListPool = new(factory: () => new(), size: 3);


💡 explicit type would be better than new() here for readability

src/Workspaces/Core/Portable/PatternMatching/PatternMatch.cs

sharwell · 2022-06-02T04:52:02Z

src/Workspaces/Core/Portable/Shared/Extensions/ISymbolExtensions.cs

+                // Check if symbol is namespace (which is always visible) first to avoid realizing all locations
+                // of each namespace symbol, which might end up allocating in LOH
+                (s.IsNamespace() || s.Locations.Any(isSymbolDefinedInSource) || !s.HasUnsupportedMetadata) &&


⚠️ Namespaces which are imported from metadata but do not contain any accessible symbols are not considered visible today (e.g. the CodeGen in Microsoft.CodeAnalysis.CodeGen is defined in Microsoft.CodeAnalysis.dll, but will not appear in completion within Microsoft.CodeAnalysis.Features.dll). Are we sure this code change will not impact this behavior?

It doesn't look like this change would have impacted this behavior though, given that s.Locations.Any(isSymbolDefinedInSource) || !s.HasUnsupportedMetadata would be true for your example? I will validate and figure out where exactly that filtering is handled. Thanks for bringing this up!

Added a test

genlu · 2022-06-03T00:16:37Z

Would it be possible to just update all these paths that take ImmutableArray and just move them to SegmentedArray to avoid the LOH issues?

Well, yes, such trade-off is definitely possible, and we'd still be able to avoid the problematic LOH allocation. However, given that we can eliminate all those allocationa with very small pools of size 1 or 2, I think it'd still be a better option (basically IReadOnlyList vs SegmentedArray)

genlu · 2022-06-03T00:17:48Z

@CyrusNajmabadi @sharwell PTAL, thanks!

CyrusNajmabadi · 2022-06-03T14:19:21Z

Well, yes, such trade-off is definitely possible, and we'd still be able to avoid the problematic LOH allocation. However, given that we can eliminate all those allocationa with very small pools of size 1 or 2, I think it'd still be a better option (basically IReadOnlyList vs SegmentedArray)

That's a good point. I'll review today. If you haven't already, it might be good to doc the cases with the reasoning. But up to you. Thanks!

genlu · 2022-06-03T17:39:50Z

it might be good to doc the cases with the reasoning.

Sure. I will wait for your review. If this is the only thing left, I will probably do that in another PR instead

CyrusNajmabadi · 2022-06-06T21:22:55Z

src/Features/Core/Portable/Completion/CompletionService.cs

-           string filterText)
+           IReadOnlyList<(CompletionItem, PatternMatch?)> itemsWithPatternMatch,
+           string filterText,
+           ImmutableArray<CompletionItem>.Builder builder)


not an ArrayBuilder?

CyrusNajmabadi · 2022-06-06T21:23:28Z

src/Features/Core/Portable/Completion/CompletionList.cs

+        /// <summary>
+        /// The completion items to present to the user.
+        /// </summary>
+        internal IReadOnlyList<CompletionItem> ItemsInternal { get; }


def doc what's going on here.

personally, i'd prefer calling this ItemsList.

CyrusNajmabadi · 2022-06-06T21:24:18Z

...rFeatures/CSharpTest/Completion/CompletionProviders/AbstractCSharpCompletionProviderTests.cs


            var service = GetCompletionService(document.Project);
            var completionList = await GetCompletionListAsync(service, document, position, RoslynTrigger.Invoke);
-            var item = completionList.Items.First(i => (i.DisplayText + i.DisplayTextSuffix).StartsWith(textTypedSoFar));


should we add this API the banned list internally, so we're forces to use ItemsInternal everywhere?

That's a good idea. Done!

CyrusNajmabadi · 2022-06-06T21:25:39Z

src/EditorFeatures/Core/IntelliSense/AsyncCompletion/ItemManager.CompletionListUpdater.cs

            private readonly bool _showCompletionItemFilters;

-            private readonly Func<ImmutableArray<(RoslynCompletionItem, PatternMatch?)>, string, ImmutableArray<RoslynCompletionItem>> _filterMethod;
+            private readonly Action<IReadOnlyList<(RoslynCompletionItem, PatternMatch?)>, string, ImmutableArray<RoslynCompletionItem>.Builder> _filterMethod;


always surprised to see ImmutableArray.Builder, instead of ArrayBuilder. Also, should these be segmentedarrays to help with the LOH issue? i'm not sure how some things are picked.

Since we are holding on to those objects, it's a one time allocation, which won't be an issue

CyrusNajmabadi · 2022-06-06T21:26:35Z

src/EditorFeatures/Core/IntelliSense/AsyncCompletion/ItemManager.CompletionListUpdater.cs

            // but we still use ObjectPool for concurrency handling just to be robust.
            private static readonly ObjectPool<List<MatchResult<VSCompletionItem>>> s_listOfMatchResultPool = new(factory: () => new(), size: 1);
+            private static readonly ObjectPool<List<(RoslynCompletionItem, PatternMatch?)>> s_listOfItemMatchPairPool = new(factory: () => new(), size: 1);
+            private static readonly ObjectPool<ImmutableArray<RoslynCompletionItem>.Builder> s_filteredItemBuilderPool = new(factory: () => ImmutableArray.CreateBuilder<RoslynCompletionItem>(), size: 1);


overall very confused about why we do a List in one place, but a IA.Builder in another. Feels very strange. Similarly, i'm personally surprised to see us capping the size at '1'. in that, in practice the default cap feels like it's totally fine. if we then have multiple, we still pool. But if we only have one, it's still fine.

us capping the size at '1'

I've done this because we absolutely don't expect this code path get executed in parallel (which would be a bug), and setting the size to 1 makes the expectation clear. But I agree that it should behave the same if everything works correctly (and avoid excessive allocations otherwise)

Fixed

CyrusNajmabadi · 2022-06-06T21:29:21Z

src/Features/Core/Portable/Completion/CompletionService.cs

+            var itemsWithPatternMatch = new SegmentedList<(CompletionItem, PatternMatch?)>(items.Select(
+                item => (item, helper.GetMatch(item.FilterText, filterText, includeMatchSpans: false, CultureInfo.CurrentCulture))));
+
+            var builder = ImmutableArray.CreateBuilder<CompletionItem>();


surprised this is an IA.Builder, not a ArrayBuilder.

CyrusNajmabadi · 2022-06-06T22:04:17Z

src/Features/Core/Portable/Completion/CompletionService.cs

-        }
+        // The FilterItems method might need to handle a large list of items when import completion is enabled and filter text is very short i.e. <= 1
+        // Therefore, use pooled list to avoid repeated (potentially LOH) allocations.
+        private static readonly ObjectPool<List<(CompletionItem item, PatternMatch? match)>> s_listOfItemMatchPairPool = new(factory: () => new(), size: 2);


why a list, and not an arraybuilder? (generally speaking, this is feedback on consistency across this part of hte codebase).

OK, changed it back to List, should be all consistent now

CyrusNajmabadi · 2022-06-06T22:04:59Z

src/Features/Core/Portable/Completion/CompletionService.cs

+                            !onlyDifferInCaseSensitivity ||
+                            highestMatchPriorityInBest <= pair.item.Rules.MatchPriority)
+                        {
+                            itemsWithCasingMismatchButHigherMatchPriority.Clear();


doc plz. this part isn't super clear to me as to what's happening.

CyrusNajmabadi · 2022-06-06T22:05:21Z

src/Features/Core/Portable/Completion/CompletionServiceWithProviders.cs

            return CompletionList.Create(
                finalCompletionListSpan,
-                builder.ToImmutable(),
+                displayNameToItemsMap.SortToSegmentedList(), // TODO(DustinCa): Revisit performance of this.


can likely remove. this comment doesn't seem actionable :)

CyrusNajmabadi

Signing off. but would love more uniformity of the collection types we use in this area.

genlu added 4 commits May 31, 2022 14:31

Use SegmentedList in CompletionContext

7b1c8e8

Add AggressiveInlining for methods in hot path

66eca3e

Don't realize Locations for namespace symbols to avoid unnecessary al…

bad5027

…locations

Add IReadOnlyList based CompletionList API

069dd89

ghost added the Area-IDE label Jun 1, 2022

Avoid allocation for FilterItems

8798536

genlu force-pushed the CompletionLOHAllocation branch from 50665b8 to 8798536 Compare June 1, 2022 18:39

Avoid allocating when resolving assembly symbols

4f1614b

genlu marked this pull request as ready for review June 1, 2022 23:27

genlu requested a review from a team as a code owner June 1, 2022 23:27

Inline comparsion logic to avoid boxing

770d8aa

genlu force-pushed the CompletionLOHAllocation branch from 2678096 to 770d8aa Compare June 1, 2022 23:31

genlu changed the title ~~Avoid LOH allocation in completion~~ Reduce allocations in completion Jun 1, 2022

genlu changed the title ~~Reduce allocations in completion~~ Reducing allocations in completion Jun 1, 2022

CyrusNajmabadi reviewed Jun 2, 2022

View reviewed changes

sharwell reviewed Jun 2, 2022

View reviewed changes

src/Workspaces/Core/Portable/PatternMatching/PatternMatch.cs Show resolved Hide resolved

sharwell reviewed Jun 2, 2022

View reviewed changes

src/Workspaces/Core/Portable/PatternMatching/PatternMatch.cs Show resolved Hide resolved

sharwell reviewed Jun 2, 2022

View reviewed changes

Address feedbacks

ccbec66

genlu mentioned this pull request Jun 2, 2022

Switch AsyncCompletion to new pooled CompletionItemList based APIs #61477

Merged

runfoapp bot mentioned this pull request Jun 3, 2022

roslyn.visualstudio.newintegrationtests.csharp.csharperrorlistnetcore.errorlist #61367

Open

CyrusNajmabadi reviewed Jun 6, 2022

View reviewed changes

CyrusNajmabadi approved these changes Jun 6, 2022

View reviewed changes

genlu added 4 commits June 6, 2022 16:41

Rename

9f55ddf

Add symbol to banned list

fa523c3

Make pooled object type consistent

75e4812

Add comments

1c0ccce

genlu requested a review from a team as a code owner June 7, 2022 21:53

genlu enabled auto-merge June 7, 2022 21:55

Fix inconsistent names

b25c329

genlu merged commit 15b68dc into dotnet:main Jun 8, 2022

ghost added this to the Next milestone Jun 8, 2022

genlu deleted the CompletionLOHAllocation branch June 8, 2022 04:23

This was referenced Jun 13, 2022

Promote CompletionList.ItemsList to public API #61869

Merged

Actually return filtered items for default implementation #61938

Merged

Promote CompletionList.ItemsList to public API #61971

Closed

RikkiGibson modified the milestones: Next, 17.3 P3 Jun 28, 2022

Conversation

genlu commented Jun 1, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

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!

genlu Jun 2, 2022 • 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!

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!

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!

sharwell Jun 2, 2022 • 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!

CyrusNajmabadi commented Jun 2, 2022

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!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

genlu Jun 2, 2022 • 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!

genlu commented Jun 3, 2022

Uh oh!

genlu commented Jun 3, 2022

Uh oh!

genlu commented Jun 1, 2022 •

edited

Loading

genlu Jun 2, 2022 •

edited

Loading

sharwell Jun 2, 2022 •

edited

Loading

genlu Jun 2, 2022 •

edited

Loading

genlu Jun 7, 2022 •

edited

Loading