ILLink Roslyn analyzer: analysis time is quadratic in the number of lambdas in one method

Aperta
  • Qualcosa non va?
#137,139 1 commento 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
48/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
csharp
Ambito
performance

Direzione di ricerca

Start in ILLink.RoslynAnalyzer at LocalDataFlowVisitor.VisitFlowAnonymousFunction and trace how InterproceduralState.TrackMethod feeds InterproceduralAnalyze; the report identifies repeated method-set rebuilding and fixpoint re-analysis as likely causes. Reproduce with the supplied generated lambda case, then profile the analyzer to confirm the hot path. Done when analysis time scales linearly with lambda count and the repro still produces no trim warnings.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

area-Tools-ILLink tenet-performance untriaged
Description

DynamicallyAccessedMembersAnalyzer (ILLink.RoslynAnalyzer) takes time quadratic in the number of lambdas inside one method. A method is one operation block, so all of it runs on a single thread and shows up directly as build wall time. Source generators that build delegate tables in a static constructor (for example compile-time DI containers) hit this with a few thousand lambdas. The same lambda bodies written as separate methods stay linear.

The analyzer runs when any of EnableTrimAnalyzer, EnableAotAnalyzer or EnableSingleFileAnalyzer is true, so IsTrimmable, IsAotCompatible, PublishAot, PublishTrimmed and PublishSingleFile all trigger it. Each of the three properties alone costs the same, and the analysis runs even when all its diagnostics are suppressed via .editorconfig or [UnconditionalSuppressMessage]. Generated files are analyzed too (ConfigureGeneratedCodeAnalysis(Analyze | ReportDiagnostics)).

Reproduction steps

Repro.csproj:

<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <TargetFramework>net10.0</TargetFramework>
    <IsAotCompatible>true</IsAotCompatible>
  </PropertyGroup>
</Project>

Generate Users.cs with L lambdas in one static constructor (PowerShell, L = 8000 here):

$entries = [string]::Join('', (1..8000 | ForEach-Object { ' static h => h,' }))
@"
public class Holder { }
public static class Users
{
    public static readonly System.Func<Holder, object>[] Table;
    static Users() { Table = new System.Func<Holder, object>[] {$entries }; }
}
"@ | Out-File -Encoding utf8 Users.cs

Then compare:

dotnet build --no-incremental -p:UseSharedCompilation=false -p:ReportAnalyzer=true -v:d
dotnet build --no-incremental -p:UseSharedCompilation=false -p:ReportAnalyzer=true -v:d -p:EnableTrimAnalyzer=false -p:EnableAotAnalyzer=false -p:EnableSingleFileAnalyzer=false

The code produces no trim warnings.

Expected behavior

Analysis time grows linearly with the number of lambdas, as it does when the same bodies are separate methods.

Actual behavior

csc /reportanalyzer, clean full compile, no compiler server, median of 3 runs:

Lambdas in one method (L) 1,000 2,000 4,000 8,000 16,000
DynamicallyAccessedMembersAnalyzer time 0.57 s 1.11 s 4.58 s 20.1 s 118 s
Total compile wall, analyzer on 1.7 s 2.4 s 6.8 s 22.8 s 120.4 s
Total compile wall, same bodies as separate methods 1.3 s 1.6 s 1.8 s 2.5 s 4.2 s

The exponent is 2.1 to 2.6 from 2,000 lambdas up. A plain dotnet build of the repro with 6,000 lambdas takes 13.0 s with the analyzer and 2.8 s without it.

In the real-world case (a generated DI container), the analyzer took 517 s at 800 services while the generator took under a second and the generated code grew linearly with the service count.

The 11.0.0-rc.3 analyzer package behaves the same (17.3 s against 18.6 s on the real-world case at 200 services).

Regression?

Not known.

Known workarounds

  • Replace lambdas with method groups, or split the method into chunks. Both remove the wall time cost. This is what we did in the generator.

  • Turn the analyzer off for local builds and keep it on for Release and CI. All three properties are needed, because each one enables the full analysis:

    <PropertyGroup Condition="'$(Configuration)' == 'Debug'">
  <EnableTrimAnalyzer>false</EnableTrimAnalyzer>
  <EnableAotAnalyzer>false</EnableAotAnalyzer>
  <EnableSingleFileAnalyzer>false</EnableSingleFileAnalyzer>
</PropertyGroup>
Configuration
  • .NET SDK 10.0.403 (Microsoft.NET.ILLink.Tasks 10.0.14), net10.0
  • Windows 11 Pro 26200, x64, Ryzen 9 6900HX (8 cores, 16 threads)
Other information

Likely cause: LocalDataFlowVisitor.VisitFlowAnonymousFunction calls InterproceduralState.TrackMethod for every lambda. TrackMethod has no "already tracked" check and rebuilds the whole method set each time (a new List, then a new ValueSet backed by a HashSet). InterproceduralAnalyze then re-analyzes every tracked method in each fixpoint pass. Checking for an already-tracked method and keeping a mutable set would make this linear.

Related: #136567. GetFlags (called from IsTypeInterestingForDataflow) walks the base-type chain and runs IsTypeOf on every direct interface on every call, with no per-type cache. In the same generated code, a type implements about two interfaces per registered service, and about 35 members per service handle values of that type, so the total analyzer CPU stays quadratic even after the lambdas are gone. Standalone: 2,000 one-line methods whose parameter type implements K = 0 / 200 / 400 / 800 interfaces cost 0.92 / 2.34 / 3.66 / 6.39 s of analyzer time, about 2.7 µs per method per interface. The two effects multiply when lambdas take or capture such a type.

Disclosure: I used AI to investigate the slow-down and draft this issue.

Lingua principale
C#
Stelle
18.4k
Fork
5.8k
Merge medio
2g 19h
PR unite (30g)
590

Preparare l'ambiente

Apri in Codespaces

Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di dotnet/runtime

Tutte le issue di dotnet/runtime

Issue simili

Altre issue su C#

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.