LINQ sieht linear aus. Die Laufzeit tut es nicht.

Warum ein Export minutenlang braucht, obwohl die Datei unschuldig ist.

Viele langsame Exporte werden zuerst an der falschen Stelle gesucht.

Die Datei ist gross. Die Library ist bekannt dafür, mit vielen Zeilen zu kämpfen. Der Server hat viel zu tun. Also schaut man auf das Schreiben der Datei.

Manchmal stimmt das. Oft nicht.

Was langsam ist, ist häufig nicht das Erzeugen der Datei. Es ist die Vorbereitung der Zeilen. Zwei Listen, die zusammengehören, werden so verknüpft, als wäre die zweite Liste jedes Mal neu zu durchsuchen.

In C# sieht das oft harmlos aus. Es steht in einer Select-Zeile. Es heisst Find oder FirstOrDefault. Es liest sich wie ein Filter.

Es ist keiner.

Der Code, der sich linear anfühlt

Ein typisches Muster:

var rows = movements
    .Select(item =>
    {
        var master = masters.Find(m => m.Id == item.MasterId);
        return master is null ? null : Map(item, master);
    })
    .Where(row => row is not null)
    .ToList();

Fachlich ist das klar. Für jede Bewegung die passende Stammdatenzeile. Fehlt sie, fällt die Zeile weg.

Laufzeittechnisch steht dort eine Schleife in der Schleife.

Für jede Bewegung wird die Stammliste von vorn durchsucht. Bei n Bewegungen und m Stammsätzen sind das im schlechten Fall etwa n · m Vergleiche.

Bei fünfzig plus fünfzig fällt das niemandem auf. Bei achthundert Stammsätzen und fünfzehnhundert Bewegungen sind das rund 2,4 Millionen Vergleiche — nur für den Join. Die Datei selbst wurde noch nicht angefasst.

LINQ ändert daran nichts. Es macht die innere Schleife nur höflicher.

Warum das in Reviews so leicht durchgeht

Der Code ist kurz. Die Absicht ist sichtbar. Es gibt keine offensichtliche Endlosschleife.

Komplexität steckt selten in dem, was laut ist. Sie steckt in dem, was sich wiederholt, ohne so auszusehen.

Find auf einer Liste ist linear. Einmal aufgerufen ist das in Ordnung. In einer Abbildung über eine zweite Liste ist es quadratisch.

Dasselbe gilt für FirstOrDefault, Contains auf einer List<T> und für Where(...).First(). Die Namen klingen nach Auswahl. Die Kosten wachsen mit der Länge der durchsuchten Menge — und zwar bei jedem Aufruf erneut.

Ein Dictionary oder ein HashSet verschiebt die Arbeit nach vorn: einmal indexieren, dann nachschlagen. Der Join wird O(n + m) statt O(n · m).

Das ist kein Mikro-Tuning. Es ist die gleiche Einsicht, die man in einem Informatikkurs als Hash-Tabelle kennenlernt. Nur sitzt sie hier nicht in einer Übungsaufgabe, sondern in einem Export, den jemand zweimal am Tag auslöst.

Die Zahl, die man sich merken kann

Angenommen, die Stammliste hat 800 Einträge und die Bewegungsliste 1 500.

Vorgehen	Grobe Arbeit für den Join
Find / FirstOrDefault je Zeile	~2 Mio. Vergleiche
einmal ToDictionary, dann TryGetValue	~800 Inserts, dann ~1 500 Lookups

Der Faktor liegt in der Grössenordnung der Stammliste. Verdoppeln sich beide Mengen, vervierfacht sich die nested Variante. Die Dictionary-Variante wächst ungefähr mit der Summe.

Genau das meint Laufzeitkomplexität: nicht «ist es auf meinem Rechner schnell», sondern «wie wächst es, wenn die Daten wachsen».

Ein System kann Jahre unauffällig bleiben. Dann wächst der Stamm. Dann wächst die Bewegung. Dann ist der Export «plötzlich» langsam. Der Code war schon immer derselbe.

Ein Eigentor, das ich unterschätzt habe

Es gibt eine Variante, die noch ärgerlicher ist als das originale Find.

Man baut das Dictionary. Und wirft es in der Abbildung wieder weg:

var byId = masters.ToDictionary(m => m.Id);

var rows = movements
    .Select(item =>
    {
        var list = byId.Values.ToList(); // jede Zeile eine neue Liste
        var master = list.Find(m => m.Id == item.MasterId);
        return Map(item, master);
    })
    .ToList();

In der Praxis steht das selten so deutlich. Es steht als Collection-Ausdruck in der Lambda. Ein Dictionary existiert. Die Methode darunter erwartet aber eine Liste. Also wird kopiert — pro Zeile.

Damit zahlt man die Indexierung und behält die lineare Suche. Plus Allokationen.

Das ist der Moment, in dem «wir haben das schon optimiert» nicht mehr trägt. Optimiert wurde die Beschaffung der Daten. Der Join in der Abbildung ist der alte.

Ein halber Fix ist fachlich leicht zu übersehen. Ein Pfad lädt den Index einmal und schlägt nach. Der Nachbarpfad, derselbe Export, eine andere Teilmenge, sucht weiter linear. Im Profiler sieht man dann «den Export». Nicht «die eine Abbildung, die niemand angefasst hat».

Cache rettet die Komplexität nicht

Ein zweites Missverständnis liegt nahe.

Wenn die Stammliste ohnehin im Speicher liegt oder hinter einem Cache, fühlt sich wiederholtes Suchen billig an. Der teure I/O passiert nur einmal. Der Rest sei «nur CPU».

Stimmt. Und genau diese CPU ist das Problem.

Cache verkürzt den Weg zu den Daten. Er ändert nicht, wie oft über dieselben Daten gelaufen wird. Ein gecachter linearer Scan bleibt ein linearer Scan. Tausendmal hintereinander bleibt er tausend lineare Scans.

Dasselbe gilt für asynchrone Abrufe in der Schleife. Auch wenn jeder Abruf den Cache trifft: die Abfolge ist immer noch proportional zur Zeilenzahl. Komplexität ist nicht nur Rechenarbeit. Sie ist auch die Zahl der Schritte, die hintereinander stehen, bevor die erste Zeile geschrieben wird.

Was man stattdessen tut

Die Daten einmal indexieren. Den Index in die Abbildung geben. Nachschlagen.

var byId = masters.ToDictionary(m => m.Id);

var rows = new List<Row>(movements.Count);

foreach (var item in movements)
{
    if (!byId.TryGetValue(item.MasterId, out var master))
        continue;

    rows.Add(Map(item, master));
}

Oder LINQ, aber ohne innere Suche:

var rows = movements
    .Select(item => byId.TryGetValue(item.MasterId, out var master)
        ? Map(item, master)
        : null)
    .Where(row => row is not null)
    .ToList();

Die Signatur der Abbildung ändert sich. Statt List<Master> ein IReadOnlyDictionary<string, Master>. Das klingt nach Kleinigkeit. Es verhindert, dass jemand später wieder Find darüberlegt.

Contains auf einer Liste gehört in dieselbe Familie. Ein HashSet<T> macht die Mitgliedschaft zum Lookup. Wieder: einmal bauen, oft fragen.

Nicht jeder Lookup braucht ein Dictionary. Bei sehr kleinen, stabilen Mengen ist lineare Suche lesbarer und schnell genug. Die Schwelle liegt nicht bei «klingt unsauber», sondern bei «wird diese innere Menge mit der äusseren wachsen».

Danach ist der Engpass woanders

Wenn der Join linear ist, wird sichtbar, was vorher unter quadratischer Arbeit lag.

Dann kann die Library tatsächlich spürbar sein. Dann kann das Serialisieren der Datei spürbar sein. Dann kann der Speicherdruck durch eine komplette byte[] spürbar sein — das ist ein anderes Thema, und ich habe über Export-Architekturen schon an anderer Stelle geschrieben.

Wichtig ist die Reihenfolge.

Zuerst die Abbildung, die sich mit dem Produkt zweier Mengen bewegt. Dann messen. Dann entscheiden, ob Schreiben, Streaming oder Parallelität der nächste Hebel ist.

Sonst optimiert man die Dateierzeugung und wundert sich, warum der Export trotzdem skaliert wie n mal m.

Was ich mir daraus merke

Laufzeitkomplexität ist in Produktionscode selten ein griechischer Buchstabe an der Tafel. Sie ist eine innere Suche, die in einer äusseren Abbildung sitzt und sich wie Fachlogik liest.

Drei Fragen reichen meist:

1. Wird diese Liste für jedes Element einer anderen Liste durchsucht?
2. Wachsen beide Mengen unabhängig voneinander?
3. Habe ich den Index gebaut — und in der nächsten Zeile wieder zerstört?

Wenn die erste Antwort ja ist, ist die dritte oft die unbequeme.

LINQ ist dabei nicht der Gegner. LINQ ist eine Schreibweise. Die Komplexität steht in der Schachtelung, nicht in der Syntax.