Improve searching for symbols when a name is known ahead of time. (And avoid O(n) enumerations)#26330
Conversation
|
This appears to contain deltas from #26325. Can we wrap that one up before I review this? |
|
Yup. Removed "Blocked" tag. Will take a look tonight or tomorrow. |
| ''' <see cref="CaseInsensitiveComparison.Comparer"/> so that name lookup happens in an | ||
| ''' appropriate manner for VB identifiers. This allows fast member name O(log(n)) even if | ||
| ''' the casing doesn't match. | ||
| ''' </summary> |
There was a problem hiding this comment.
note: we have lot of case sensitivty tests for VB (including directly in symbol search) to validate this behavior.
| private static readonly ObjectPool<ImmutableHashSet<string>.Builder> s_memberNameBuilderPool = | ||
| new ObjectPool<ImmutableHashSet<string>.Builder>(() => ImmutableHashSet.CreateBuilder<string>()); | ||
|
|
||
| private static ImmutableHashSet<string> ToImmutableAndFree(ImmutableHashSet<string>.Builder builder) |
There was a problem hiding this comment.
If there is a chance that we'd want to use pooled ImmutableHashSet in other parts of the code, it may be good to pull into a dedicated type (like PooledHashSet).
Update: hum, I see that VB needs to use hash sets with a case-insensitive comparer... I see why you didn't factor this out. #Resolved
| declFlags |= SingleTypeDeclaration.TypeDeclarationFlags.HasAnyNontypeMembers; | ||
| } | ||
|
|
||
| // PERF: The member names collection tends to be long-lived. Use a string array since |
jcouv
left a comment
There was a problem hiding this comment.
The change looks good, but I'm not convinced that it helps for perf/allocation trade-off.
Getting some data point would help (maybe benchmark on compiling Roslyn?).
|
Compiling roslyn shows no change in perf for me. How do you guys normally validate compiler changes wrt perf yourself? |
|
I'll let @agocke reply (he has some instructions on how to validate). |
|
I wrote up a tool to help test perf changes here: https://github.com/dotnet/roslyn-tools/tree/master/src/CompilerPerfTests |
|
Awesome. I'll try this out this weekend! |
|
@agocke I tried this, but i got:
|
|
@CyrusNajmabadi Fixed here: dotnet/roslyn-tools#248. Looks like some changes were made to Roslyn that needed to be reflected in the powershell script. |
|
Thanks! Here are my results: Details// ***** BenchmarkRunner: Start ***** // Found benchmarks: // PlaceholderBenchmarkRunner.PlaceholderMethod: Job-EWQPHF(Toolchain=Perf.ExternalProcessToolchain, LaunchCount=0, RunStrategy=Monitoring, TargetCount=25, WarmupCount=0) [Commit=HEAD^] // PlaceholderBenchmarkRunner.PlaceholderMethod: Job-EWQPHF(Toolchain=Perf.ExternalProcessToolchain, LaunchCount=0, RunStrategy=Monitoring, TargetCount=25, WarmupCount=0) [Commit=HEAD]// Validating benchmarks: // *** Build *** commit b6d9b18 Repo Dir C:\GitHub\roslyn-internal\roslyn Restoring packages for C:\GitHub\roslyn-internal\roslyn\src\Compilers\Core\Portable\CodeAnalysis.csproj... Build succeeded. Time Elapsed 00:00:23.06 // *** Execute *** Mean = 4.7790 s, StdErr = 0.0352 s (0.74%); N = 25, StdDev = 0.1759 s // ************************** // *** Build *** commit bbb77e5 (HEAD -> symbolSearchO1, CyrusNajmabadi/symbolSearchO1) Repo Dir C:\GitHub\roslyn-internal\roslyn Restoring packages for C:\GitHub\roslyn-internal\roslyn\src\Compilers\CSharp\Portable\CSharpCodeAnalysis.csproj... Build succeeded. Time Elapsed 00:00:24.08 // *** Execute *** Mean = 4.8006 s, StdErr = 0.0331 s (0.69%); N = 25, StdDev = 0.1654 s // ***** BenchmarkRunner: Finish ***** // * Export * // * Detailed results * PlaceholderBenchmarkRunner.PlaceholderMethod: Job-EWQPHF(Toolchain=Perf.ExternalProcessToolchain, LaunchCount=0, RunStrategy=Monitoring, TargetCount=25, WarmupCount=0) [Commit=HEAD] Total time: 00:05:26 (326.04 sec) // * Summary * BenchmarkDotNet=v0.10.9, OS=Windows 10.0.16299 Toolchain=Perf.ExternalProcessToolchain LaunchCount=0 RunStrategy=Monitoring ------------------ |------- |--------:|---------:|---------:|-----:| // * Legends * // ***** BenchmarkRunner: End ***** |
|
@agocke can you help interpret this? It looks like the diffs are well within the margin of error. yes? |
|
@gafter can you take a look? The dependent PR has gone in now. |
|
@agocke Can you confirm my reading that this means there is no appreciable perf impact to this change? @gafter @jcouv could you take a look at this rather simple change. Note: actually testing this on Roslyn brought down the time to test lookup from over 7 seconds to an almost 0.2 seconds. That's a big win! :) Hash lookups much better than a linear scan of every top level symbol name in the entire solution |
jcouv
left a comment
There was a problem hiding this comment.
LGTM
Thanks for the perf analysis!
|
Note: this search function is used both by add-using and fully-qualify (though only for the direct project you start in, and not for searching other projects in the solution), as well as the public SymbolFinder.FindDeclarationsAsync entrypoint. So improvements here will def have a benefit. It is not currently used by FindRefs, or goto-impl/override. Though it's possible searches could be sped up by using these helpers before having to build/examine our own IDE indexes here. Though investigations would hav eto be done to know for sure. |
|
@CyrusNajmabadi The "rank" part of the output is the most important here. That both are rank "1" indicates that there was no statistically significant difference in end-to-end performance of the compiler between the two commits. |
|
If you have other perf measurements I think you should also post those benchmarks. Without some definite perf improvement in a specific scenario, I wouldn't take this change. |
|
@agocke i mentioned them above. Note: i was the person who added this API in the early days of Roslyn precisely for speeding up add-using and for other IDE search tasks. It looks like it was changed at one point to not be a set, without understanding that scenario, and also making it so we expose mutable data. To me, it was a mistake to have made that change, and this is simply rectifying things (both fixing the exposing of mutable data, and improving perf). I'm not sure hte best way for us to prevent these sorts of regressions in the future. At one point there was a roslyn perf harness, but i'm not sure the current state of it. |
|
My work is kind of the replacement for that, but it only measures end-to-end perf, which this change is too small to affect. Could you post detailed results for a benchmark of the API change, then? Means, standard deviations, maybe a t-test for significance? |
|
Do you have a good way to collect that data? All i did was make a scenairo and run it several hundred times. the results were consistent every time i tried to do this. |
|
https://github.com/dotnet/BenchmarkDotNet can give you that information. They have pretty good documentation for writing tests, as well. |
|
Ok. I had some trouble using htat directly. But just doing the benchmarking manually was no problem. Here are the results. Before my change: Raw run times. Note, these are in milliseconds. Details``` 11380 5980 5843 6852 5913 5896 6235 5914 5995 5879 6038 5905 5873 5869 5918 5870 6023 5883 5900 6597 6063 5874 5925 5899 5879 ```This gives the following values:
After my change: Details``` 679 917 1070 835 981 729 402 403 400 386 392 390 408 398 394 389 391 402 397 380 409 377 420 452 492 ```
This is roughly a 12x improvement. computation of average, stddev and error was done with Which is in line with how benchmark.net computes things. |
| mergedRoot, Function(n) IdentifierComparison.Equals(n, name), filter, cancellationToken) | ||
| Return ContainsNameHelper( | ||
| mergedRoot, | ||
| Function(n) IdentifierComparison.Equals(n, name), |
There was a problem hiding this comment.
Consider passing through name so you don't allocate in these lambdas.
There was a problem hiding this comment.
it's just a single allocation, so it's not too bad :)
|
@agocke are you ok merging in? |
…names searches. (#26331) Followup to #26325 and #26330. This PR updates the IDE to forward certain helpers to these more efficient implementations. This helps things out by more quickly being able to determine if a type even contains a member with name, and thus whether or not it should even be hydrated into a symbol and have its members created. Previous we would have to do a linear scan on all the members in a type to determine this. Now this data is in a set which can be queried much more efficiently.
Followup to #26325.
This also switches the backing store for the MemberNames collection to an ImmutableHashSet. That has two benefits. One, it fixes #26328 where the current system allows a client to potentially corrupt internal compiler state.
Second, it allows for O(log(n)) name lookups instead of O(n). this is because we use ImmutableHashSet which is an efficient AVL tree where the hashcode of the object is the key for the node**. This is an improvement on top of our own SmallDict ** , and means we can be immutable, have fast lookups, and not have much more overhead than an array/immutablearray.
--
** SmallDictionary is effectively the same, just with space for a 'value'. As we don't need that here, we save by just using ImmutableHashSet.