PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : .NET PLINQ: Warum wird das nicht schneller?


PatkIllA
2011-08-23, 21:03:50
Ich probiere gerade mal ein bisschen mit Plinq rum.
Folgender Anwendungsfall. Ich lese knapp 200 XML Dateien mit durchschnittlich 100 kB ein und lasse danach eine Handvoll Analysen das XML nach problematischen Einstellungen durchsuchen.

internal static class ProblemSearcher
{
private static IEnumerable<T> Multiply<T>(this IEnumerable<T> source, int count)
{
foreach (var item in source)
{
for (int i = 0; i < count; i++)
yield return item;
}
}

public static List<IProblem> GetProblems(string sourcePath, IList<IAnalysis> analyses, int multiply)
{
DirectoryInfo di = new DirectoryInfo(sourcePath);
return di.EnumerateFiles("*.csproj", SearchOption.AllDirectories)
.Multiply(multiply)
.AsParallel()
.WithExecutionMode(ParallelExecutionMode.ForceParallelism)
.Select(x => new Project(di, x))
.SelectMany(x => ProblemSearcher.GetProblems(x, analyses))
.OrderBy(x => x.Project)
.ToList();
}

private static IEnumerable<IProblem> GetProblems(Project project, IList<IAnalysis> analyses)
{
return analyses.AsParallel().SelectMany(x => x.Analyse(project));
}
}
Egal ob mit ohne AsParallel() dauert das im Rahmen der Messgenauigkeit gleichlang. (1,4 sek, Macht 7 ms pro Datei)
Als Test hab ich dann mal die Eingabe vertausendfacht (multiply = 1000), die Ausführungszeit verzehnfacht sich aber lediglich. (QuadCore mit HT, 0,07 ms pro Datei)
SSD vorhanden aber das sollte doch eh im Cache sein.

Ich hatte jetzt eigentlich einen ordentlichen Schub auch bei nur 200 Dateien erhofft.

Monger
2011-08-23, 21:18:49
Sowas muss man nachmessen, um vernünftige Aussagen machen zu können.

Aber meine Vermutung: dein einzig relevanter Flaschenhals hier ist die Zugriffszeit der Festplatte. 7ms klingen verdächtig nach Zugriffszeit. Deine Suche nach Csproj Dateien ist wahrscheinlich mit großem Abstand die langsamste Operation hier.

I/O Zugriffe sind ganz allgemein extrem schlecht bis gar nicht parallelisierbar. Ist nunmal alles die selbe Festplatte.

PatkIllA
2011-08-23, 21:22:44
Da bin ich in der Zwischenzeit auch drauf gekommen.
Das EnumerateFiles braucht in der Tat 1,2 von den 1,4 Sekunden.

Dabei liegen da doch nur 26250 Dateien in 12549 Ordnern.
Was macht man denn wenn man da mit einer normalen Festplatte zum ersten Mal zugreift? ;)

Monger
2011-08-23, 21:33:25
20000 Dateien sind kein Pappenstiel. Festplatten sind eigentlich nicht darauf ausgelegt, parallel so viele Dateien zu lesen.

In dem Fall hast du wahrscheinlich keine Wahl, aber aus Performance Sicht wäre es VIEL besser, wenn du die 20000 in eine Datei zippen könntest, und dann im Zip Stream suchen würdest. Das würde um Welten schneller gehen.

Nicht umsonst haben sich Cabinet Files o.ä. durchgesetzt. Kaum ein Setup besteht heute mehr als aus ein paar wenigen Dateien.

Edit: Auf der anderen Seite, ist das WIRKLICH zeitkritisch was du da tust, oder darf das auch ein paar Sekunden dauern? ;)

PatkIllA
2011-08-23, 21:40:38
Das Beispiel ist nicht wirklich zeitkritisch und mehr als Spielwiese gedacht. Wenn er denn die Dateien gefunden hat finde ich aber schon beeindruckend, dass man mit über 100 MB / Sekunde XML einlesen kann.
Mir fallen aber spontan noch einige Stellen ein, die zeitkritisch sind und da wollte ich Erfahrung sammeln.

Monger
2011-08-23, 22:34:35
Ich hab irgendwo mal Performance Tests von verschiedenen XML Parsern gesehen. Wenn das XML Dokument erstmal im Speicher vorliegt, sind die barbarisch schnell... hab irgendwas von zweistelligen GB/s im Kopf. Sobald das Dokument geparst ist, geht die Navigation darin natürlich auch extrem schnell. Sprich: XML ist auch als Datenstruktur für performancekritische Angelegenheiten nicht verkehrt. Natürlich nur solange du nicht ständig auf Festplatte speicherst.

Marscel
2011-08-23, 22:34:44
Indizierungsdienste machen u.U. ja durchaus Sinn ;)

Gast
2011-08-29, 19:49:31
1.) LINQ und gute Performance widersprechen sich meistens grundsätzlich schon. Das endet meistens in ziemlichen Performancelöchern, da hier niemand mehr weiß, wie die Klassen hier wirklich aufgerufen werden. PLINQ ist wirklich eine nette Spielerei, aber wenn man mehrere Kerne nutzen will, dass muss man die Arbeit selbst machen, anstatt einfach nur ein Attribut mehr zu setzen.
Von dem unlesbarem, nicht recyclebaren Code (LINQ Ergebnisse haben keinen benannten Typ d.h. man kann sie nicht Funktionen übergeben), der dabei meistens heraus kommt mit enorm vielen Threading Anomalien, die keiner mehr findet, will ich einmal gar nicht reden.

2.) Wenn die Testdaten zu klein sind, dann sagt es überhaupt nichts aus, wenn du dasselbe 1.000 Mal durchführst, egal ob die die Testdaten vervielfachst oder einfach eine Schleife 1 Mio. Mal durchlaufen lässt. Da musst du dir schon mehr Testdaten organisieren z.B. mit Zufallszahlen.

3.) Bei der Team Edition ist ein Profiler dabei (da gibt es eine kostenlose zeitbefristete Testversion). Teste einmal damit. Da kannst du dann genau sehen, in welcher Zeile die meiste CPU Zeit verbraucht wird.

4.) Eine heutige CPU schafft um die 100K Thread Operationen pro Sekunde d.h. jede Arbeit, die kürzer ist, wird dadurch nicht schneller werden, sondern höchstens langsamer. Es macht nur Sinn auf oberster Ebene zu parallelisieren. Wenn du eine Operation 1 Mio. Mal ausführst, musst du die Schleife mit den 1 Mio. Durchläufen parallelisieren und nicht die Einzeloperation, die sowieso nur ein paar CPU Zyklen braucht.

PatkIllA
2011-08-29, 19:57:10
natürlich haben die Ergebnisse von Linq-Statements einen Typ. Mindestens IEnumerable<T> evtl auch spezieller.
Warum sollte Linq zwangsweise langsam sein? Bei normalen Linq wird oft nur iteriert und das kann auch deutlich schneller sein. Insbesondere wenn man es gar nicht komplett ausgeführt hätte sondern ein Ergebnis in eine Liste gepackt hätte, was bei vielen die IEnumerable<T> und yield return nicht kennen oft gemacht wird.

Monger
2011-08-29, 21:16:04
1.) LINQ und gute Performance widersprechen sich meistens grundsätzlich schon.

Was ein Quark.
LINQ ist echt nicht unklever. Kaum einer macht sich in der Praxis die Mühe eine Late Evaluation zu implementieren, und das kann irrsinnig viel Performance sparen. Es kann natürlich auch langsam sein, aber das liegt nunmal am Anwender.


Von dem unlesbarem, nicht recyclebaren Code (LINQ Ergebnisse haben keinen benannten Typ d.h. man kann sie nicht Funktionen übergeben), der dabei meistens heraus kommt mit enorm vielen Threading Anomalien, die keiner mehr findet, will ich einmal gar nicht reden.

Pauschal ebenfalls quatsch. Nicht alle LINQ Queries enthalten anonyme Typen.
PLINQ ist natürlich kein Allheilmittel, aber dafür dass es einfach so out-of-the-box kommt, ist es kein schlechtes Feature.

Natürlich gilt hier wie überall: nur parallelisieren wenn es wirklich einen Bedarf gibt, und man algorithmische Optimierungen ausgeschöpft hat. Multithreading ist nunmal immer ein heißes Eisen.

Gast
2011-09-01, 00:58:54
natürlich haben die Ergebnisse von Linq-Statements einen Typ. Mindestens IEnumerable<T> evtl auch spezieller.

Ein IEnumerable<T> ist absolut nichtssagend. Dahinter kann sich so gut wie alles verbergen.

Warum sollte Linq zwangsweise langsam sein? Bei normalen Linq wird oft nur iteriert und das kann auch deutlich schneller sein. Insbesondere wenn man es gar nicht komplett ausgeführt hätte sondern ein Ergebnis in eine Liste gepackt hätte, was bei vielen die IEnumerable<T> und yield return nicht kennen oft gemacht wird.

LINQ kann nur so schnell sein, wie der Datentyp, auf den die Operationen angewendet werden. Wenn ich eine selbst geschriebene Implementierung einer List, eines Dictionary etc. verwendet, die noch an gewissen Stellen etwas komplexere Logik besitzen z.B. mit Hilfe eines Mutex synchronisiert oder automatisches Nachladen von Daten einer externen Quelle, dann kann das katastrophal langsam werden.
Wenn ich z.B. über einen Key zugreifen will, der das IComparable Interface relativ performant implementiert, dann werde ich ein Dictionary verwenden und über den Key zugreifen, während ein Iterator deutlich langsamer ist. Greife ich hingegen immer sequentiell zu, wo werde ich entweder ein Array oder eine List(wenn Objekte dazu kommen) verwenden. Mit LINQ arbeitet man nur mehr mit IEnumerables hat die ganzen Möglichkeiten den Zugriff zu optimieren nicht mehr. Stattdessen wird immer die Standardzugriffsmethode verwendet (ein Enumerator), ob das für den jeweiligen Datentyp jetzt sinnvoll ist oder nicht.

Was ein Quark.
LINQ ist echt nicht unklever. Kaum einer macht sich in der Praxis die Mühe eine Late Evaluation zu implementieren, und das kann irrsinnig viel Performance sparen. Es kann natürlich auch langsam sein, aber das liegt nunmal am Anwender.

Niemand kann durchschauen, was LINQ bei den Queries wirklich macht. Auch mit dem Profiler kommt hier meistens nicht viel brauchbares heraus. Mit handgeschriebenem Code, der halt 3 Zeilen mehr hat, kann ich auf einen Blick sehen, welche Zeile davon die Leistung frisst und gezielt optimieren.

PatkIllA
2011-09-01, 08:28:15
Ein IEnumerable<T> ist absolut nichtssagend. Dahinter kann sich so gut wie alles verbergen.Das ist absolut aussagekräftig. Das T hat immer einen konkreten Typ und man darüber iterieren.
Auf der Arbeit benutzen wir das an hunderten Stellen. Man kann sie mit yield return sehr einfach selbst erzeugen, mit Linq filtern usw.
Wenn man da mit Collections oder Listen arbeiten würde müsste zig mal mehr umkopiert oder überhaupt ausgewertet werden.

Viele der Linq Funktionen sind auch genauso einfach programmiert wie man es selbst machen würden. Wenn man nicht das namensgebende Linq, sondern die Extensionsmethods auf System.Linq.Enumerable benutzt kann man das auch wie normalen Code schreiben und lesen.

Monger
2011-09-01, 10:26:02
LINQ kann nur so schnell sein, wie der Datentyp, auf den die Operationen angewendet werden. Wenn ich eine selbst geschriebene Implementierung einer List, eines Dictionary etc. verwendet, die noch an gewissen Stellen etwas komplexere Logik besitzen z.B. mit Hilfe eines Mutex synchronisiert oder automatisches Nachladen von Daten einer externen Quelle, dann kann das katastrophal langsam werden.

Wenn du bei der Implementierung pfuschst, ist es völlig egal ob du mit LINQ oder sonstwas auf die Collection zugreifst.


...Stattdessen wird immer die Standardzugriffsmethode verwendet (ein Enumerator), ob das für den jeweiligen Datentyp jetzt sinnvoll ist oder nicht.

Mal ein Gegenbeispiel, über dass ich erst vor kurzem unfreiwillig gestolpert bin:
Die Extension Method "ElementAt" lässt sich zwar für alle IEnumerable<T> anwenden, aber kennt intern zwei Implementierungen. Standardmäßig wird über den Enumerator x-mal iteriert, bis man an der passenden Stelle angelangt ist. Wenn aber die Collection vom Typ IList ist, wird der Index Operator benutzt (der im Fall von List<T> natürlich mal gleich O(1) ist, und nicht etwa O(n)).

LINQ ist ja nix magisches, sondern nur syntaktischer Zucker für einen Mix aus Extension methods und Lambda Ausdrücken. Die sind gut dokumentiert, und sofern du die Standard Interfaces von IDictionary, IList etc. sauber implementierst, verhält sich das ganze Konstrukt auch so wie erwartet.

Du kannst natürlich die LINQ Syntax meiden, und dir die Extension Methods von Hand zusammenfriemeln. Daraus wirst du im Profiler aber auch nicht schlauer.
Bliebe also die Möglichkeit, sich auf konventionellem Wege das nachzuimplementieren.

Natürlich kann man sich letztendlich immer auf den Standpunkt stellen: "Wenn ich es selber mache, weiß ich wenigstens was ich vor mir habe."
Aber wie so oft: in 99% der Fälle ist die Standardlösung weit robuster und schneller als alles was man sich selbst zusammen dichten kann.

PatkIllA
2011-09-01, 10:43:45
Wenn du bei der Implementierung pfuschst, ist es völlig egal ob du mit LINQ oder sonstwas auf die Collection zugreifst.Collections braucht man ja gar nicht.
IEnumberable<T> und die yield return/break Sytax scheinen echt viele nicht zu benutzen.
Mal ein Gegenbeispiel, über dass ich erst vor kurzem unfreiwillig gestolpert bin:
Die Extension Method "ElementAt" lässt sich zwar für alle IEnumerable<T> anwenden, aber kennt intern zwei Implementierungen. Standardmäßig wird über den Enumerator x-mal iteriert, bis man an der passenden Stelle angelangt ist. Wenn aber die Collection vom Typ IList ist, wird der Index Operator benutzt (der im Fall von List<T> natürlich mal gleich O(1) ist, und nicht etwa O(n)).Count() macht das z.B. auch so

Du kannst natürlich die LINQ Syntax meiden, und dir die Extension Methods von Hand zusammenfriemeln.
Ich find die Extensions eigentlich ziemlich praktischer und benutze die sogar öfter als die Linq-Syntax.
Ein großer Vorteil ist das dann edit und continue noch geht.

Gast
2011-09-04, 13:38:30
Das ist absolut aussagekräftig. Das T hat immer einen konkreten Typ und man darüber iterieren.
Auf der Arbeit benutzen wir das an hunderten Stellen. Man kann sie mit yield return sehr einfach selbst erzeugen, mit Linq filtern usw.
Wenn man da mit Collections oder Listen arbeiten würde müsste zig mal mehr umkopiert oder überhaupt ausgewertet werden.

Wenn ich statt einer List(Of T) nur mehr ein Enumerable(Of T) bekomme, wie will ich dann ein Element hinzufügen? Ja klar mit einem LINQ Statement, das dann wieder den gemeinsamen Weg aller IEnumerables geht und dann wahrscheinlich eine neue Liste erzeugt und alle bestehenden 1 Mio Elemente einfügt. Das ist nicht unbedingt sehr sinnvoll.

Abgesehen davon ist es langsam. Versuche einmal einer Funktion 2 Arrays mit jeweils 1 Mio. Bytes zu übergeben und dann in er Schleife durchzulaufen. Dann probiere das stattdessen mit einer IList(Of T) bzw. IEnumerable(Of T). Ich bin gerade dabei, dass ich alle meine IList Funktionen wieder zurück baue auf Arrays und für meine Listen extra Funktionen schreibe, weil es einfach so viel unnötigen Overhead hat.

Wenn du bei der Implementierung pfuschst, ist es völlig egal ob du mit LINQ oder sonstwas auf die Collection zugreifst.

Wenn ich eine eigene Datenstruktur schreibe, dann muss die nur die Operationen mit hoher Performance unterstützen, für die sie vorgesehen ist. Wenn ich nicht vorhabe, diese Datenstruktur mit einer Enumerator durchzulaufen, dann werde ich mir kaum meinen Kopf darüber zerbrechen, wie das am Schnellsten zu realisieren ist. Wenn LINQ das dann trotzdem implizit macht, dann ist die Performance natürlich im Keller.

Mal ein Gegenbeispiel, über dass ich erst vor kurzem unfreiwillig gestolpert bin:
Die Extension Method "ElementAt" lässt sich zwar für alle IEnumerable<T> anwenden, aber kennt intern zwei Implementierungen. Standardmäßig wird über den Enumerator x-mal iteriert, bis man an der passenden Stelle angelangt ist. Wenn aber die Collection vom Typ IList ist, wird der Index Operator benutzt (der im Fall von List<T> natürlich mal gleich O(1) ist, und nicht etwa O(n)).

Wenn ich eine Datenstruktur habe, für die der Zugriff über einen Index nicht vorgesehen ist, dann werde ich bei konventioneller Programmierung schnell feststellen, dass es diese Methode nicht gibt und eine andere Datenstruktur verwenden, anders darauf zugreifen oder einen Index bauen, damit das funtioniert. Bei LINQ funktioniert es einfach und bis 10.000 Datensätzen habe ich dann auch kein Problem und der Test funktioniert, die Software ist beim Kunden und 2 Jahre später ändert sich irgendeine Kleinigkeit, ich habe 100.000 Datensätze und die ganze Aktion dauert statt 1 Sekunde 100 Sekunden und alles steht inkl. der ganzen Produktion. Es hat schon seinen Sinn, warum man z.B. auf eine Queue nicht per Index zugreifen kann.

LINQ ist ja nix magisches, sondern nur syntaktischer Zucker für einen Mix aus Extension methods und Lambda Ausdrücken. Die sind gut dokumentiert, und sofern du die Standard Interfaces von IDictionary, IList etc. sauber implementierst, verhält sich das ganze Konstrukt auch so wie erwartet.

Was verstehst du als sauber implementiert? Nach deiner Definition müsste die Klasse Dictionary(Of TKey,TValue) ja unsauber implementiert sein, weil man nicht per Index auf die Elemente zugreifen kann, sondern nur per Key?

Natürlich kann man sich letztendlich immer auf den Standpunkt stellen: "Wenn ich es selber mache, weiß ich wenigstens was ich vor mir habe."
Aber wie so oft: in 99% der Fälle ist die Standardlösung weit robuster und schneller als alles was man sich selbst zusammen dichten kann.

Wenn es um normale Methoden z.B. zur MD5 Key Berechnung, Wurzel ziehen etc. geht, dann gebe ich dir Recht. Da kann man händisch nie so schnell auf das selbe Niveau kommen und es ist nur aufwändig und fehleranfällig.
Wenn es jedoch darum geht diverse Klassen in einer Art zu missbrauchen, die so nie vorgesehen ist (z.B. auf ein Dictionary per Index zuzugreifen), dann denke ich, dass eine selbst geschriebene Lösung deutlich schneller und stabiler ist. Sobald es sich um selbstgeschriebene Datenstrukturen handelt, die bei sinnlosen Operstionen generell eine NotSupportedException werfen, dann wird man ziemlich schnell auf die Schnauze fliegen und nicht verstehen, warum LINQ das jetzt so gemacht hat. Das ist oft bei simplen for each Schleifen schon nicht so einfach, wenn man sich seinen Enumerator selbst implementiert hat.

PatkIllA
2011-09-04, 13:49:29
Wenn ich statt einer List(Of T) nur mehr ein Enumerable(Of T) bekomme, wie will ich dann ein Element hinzufügen? Ja klar mit einem LINQ Statement, das dann wieder den gemeinsamen Weg aller IEnumerables geht und dann wahrscheinlich eine neue Liste erzeugt und alle bestehenden 1 Mio Elemente einfügt. Das ist nicht unbedingt sehr sinnvoll.
Du sollst ja eben kein Element einfügen. Notfalls kannst du ein IEnumerable wieder kapseln und dann nach dem ablaufen der Originalelemente deine eigenen Elemente hinzufügen.
Wenn du die Listen aus deinen Objekten direkt zurückgibst, dann können ja alle Benutzer deine internen Datenstrukturen kaputt machen, weil die Kapselung nicht mehr gegeben ist.
Dann kannst du in deinem kleinen privaten Projekt vielleicht leben. In einer komplexeren Umgebung kriegst du das nicht voreinander.
Abgesehen davon ist es langsam. Versuche einmal einer Funktion 2 Arrays mit jeweils 1 Mio. Bytes zu übergeben und dann in er Schleife durchzulaufen. Dann probiere das stattdessen mit einer IList(Of T) bzw. IEnumerable(Of T). Ich bin gerade dabei, dass ich alle meine IList Funktionen wieder zurück baue auf Arrays und für meine Listen extra Funktionen schreibe, weil es einfach so viel unnötigen Overhead hat.
Das Ablaufen von Listen hat noch einige wenige Checks, die in praktisch allen Fällen nur minimalen Overhead haben.
Mal abgesehen davon sind Arrays in .NET nicht typsicher und wegen Typüberprüfung beim Einfügen eher langsamer. Außerdem Du kannst keine eigenen Implementierungen davon machen. Die Verwendung von Arrays führt in der Praxis dazu, dass jedesmal das komplette Array umkopiert werden muss, weil sonst die Kapslung im Eimer ist.

Wenn ich eine eigene Datenstruktur schreibe, dann muss die nur die Operationen mit hoher Performance unterstützen, für die sie vorgesehen ist. Wenn ich nicht vorhabe, diese Datenstruktur mit einer Enumerator durchzulaufen, dann werde ich mir kaum meinen Kopf darüber zerbrechen, wie das am Schnellsten zu realisieren ist. Wenn LINQ das dann trotzdem implizit macht, dann ist die Performance natürlich im Keller.
Linq will auch an gar keiner Stelle auf einer mit einzelnen Elementen umgehen. Wenn du in der Regel nur einzelne Elemente hast dann ist Linq das falsche Verfahren.

Wenn ich eine Datenstruktur habe, für die der Zugriff über einen Index nicht vorgesehen ist, dann werde ich bei konventioneller Programmierung schnell feststellen, dass es diese Methode nicht gibt und eine andere Datenstruktur verwenden, anders darauf zugreifen oder einen Index bauen, damit das funtioniert. Bei LINQ funktioniert es einfach und bis 10.000 Datensätzen habe ich dann auch kein Problem und der Test funktioniert, die Software ist beim Kunden und 2 Jahre später ändert sich irgendeine Kleinigkeit, ich habe 100.000 Datensätze und die ganze Aktion dauert statt 1 Sekunde 100 Sekunden und alles steht inkl. der ganzen Produktion. Es hat schon seinen Sinn, warum man z.B. auf eine Queue nicht per Index zugreifen kann.Das gehört wie üblich darunter, dass man den Anwendungsfall und die Methoden kennen muss. Von allem was geht ist nur ein Bruchteil sinnvoll.
Was verstehst du als sauber implementiert? Nach deiner Definition müsste die Klasse Dictionary(Of TKey,TValue) ja unsauber implementiert sein, weil man nicht per Index auf die Elemente zugreifen kann, sondern nur per Key?
Ein Dictionary hat nunmal keine Reihenfolge. In der .NET Implementierung kommen die auch mitnichten in der gleichen Reihenfolge raus, wie man sie reingetan hat.
Deswegen wird ja auch zwischen ICollection und IList unterschieden.
Wenn es jedoch darum geht diverse Klassen in einer Art zu missbrauchen, die so nie vorgesehen ist (z.B. auf ein Dictionary per Index zuzugreifen), dann denke ich, dass eine selbst geschriebene Lösung deutlich schneller und stabiler ist. Sobald es sich um selbstgeschriebene Datenstrukturen handelt, die bei sinnlosen Operstionen generell eine NotSupportedException werfen, dann wird man ziemlich schnell auf die Schnauze fliegen und nicht verstehen, warum LINQ das jetzt so gemacht hat. Das ist oft bei simplen for each Schleifen schon nicht so einfach, wenn man sich seinen Enumerator selbst implementiert hat.Du kannst auch mit eigenen Datenstrukturen nicht verhindern, dass sie missbraucht werden. Da ist man öfter mal erstaunt, auf was für "kreative" Möglichkeiten manche kommen. Da werden oft aus Unkenntnis die wildsten Dinge gemacht, obwohl es entweder einfacher geht oder es halt aus gutem Grund nicht von der Klasse angeboten wird.

Monger
2011-09-04, 15:57:52
Wenn ich statt einer List(Of T) nur mehr ein Enumerable(Of T) bekomme, wie will ich dann ein Element hinzufügen? Ja klar mit einem LINQ Statement, das dann wieder den gemeinsamen Weg aller IEnumerables geht und dann wahrscheinlich eine neue Liste erzeugt und alle bestehenden 1 Mio Elemente einfügt. Das ist nicht unbedingt sehr sinnvoll.

LINQ ist eine Query Sprache, ist also gedacht zum suchen und filtern von Collections. In bestehende Strukturen einfügen geht damit ohnehin nicht. Und da das ganze als Late Evaluation implementierst ist, bestimmst du und nur du allein wann und in welcher Weise die Query ausgewertet wird. Du kannst natürlich neue Listen damit erzeugen, musst du aber nicht.


Abgesehen davon ist es langsam. Versuche einmal einer Funktion 2 Arrays mit jeweils 1 Mio. Bytes zu übergeben und dann in er Schleife durchzulaufen. Dann probiere das stattdessen mit einer IList(Of T) bzw. IEnumerable(Of T).

Arrays SIND vom Typ IList(of T), und damit auch von IEnumerable(of T). Sonst würden weder Foreach Schleifen noch LINQ Queries auf Arrays funktionieren.

Dass Arrays bei so vielen Elementen performanter als z.B. List(of T) ist, hat rein gar nichts mit dem Enumerator zu tun, sondern einzig und allein mit den Implementierungsdetails der jeweiligen Datenstruktur. List(of T) skaliert halt sehr schlecht mit so vielen Elementen.

Tendentiell sind For Schleifen eher langsamer als Foreach Schleifen (und damit auch LINQ), weil du im Enumerator typspezifische Optimierungen machen kannst, die von außen eben nicht gehen. Wenn der Enumerator messbar langsamer als der Index Zugriff ist, hast du die Implementierung verbockt.


Wenn ich eine eigene Datenstruktur schreibe, dann muss die nur die Operationen mit hoher Performance unterstützen, für die sie vorgesehen ist. Wenn ich nicht vorhabe, diese Datenstruktur mit einer Enumerator durchzulaufen, dann werde ich mir kaum meinen Kopf darüber zerbrechen, wie das am Schnellsten zu realisieren ist. Wenn LINQ das dann trotzdem implizit macht, dann ist die Performance natürlich im Keller.

Wenn deine Datenstruktur nicht enumerierbar sein soll, dann implementier einfach IEnumerable nicht. Dann ist darauf weder foreach noch LINQ anwendbar, und damit gibt es auch keine Fehlbedienungen. Allerdings ist das eine komische Datenstruktur, die eine Menge von Elementen enthält, und trotzdem nicht enumerierbar ist.


Was verstehst du als sauber implementiert? Nach deiner Definition müsste die Klasse Dictionary(Of TKey,TValue) ja unsauber implementiert sein, weil man nicht per Index auf die Elemente zugreifen kann, sondern nur per Key?

Interfaces in .NET machen nie Aussagen über Performance. IList heißt nur, dass diese Datenstruktur über einen Index ansprechbar ist - nicht, ob das auch performant ist. Genauso wenig werden Einfüge- Lösch und Sortieroperationen in ihrer Performance beurteilt.
IList(of T) wird unter anderem von Array, List(of T), Stack(of T) und LinkedList(of T) implementiert - und alle von diesen unterscheiden sich in ihren Performancemerkmalen.


Deshalb ist es völliger Quatsch zu sagen dass LINQ inperformant ist. LINQ setzt auf einer ordnungsgemäßen Implementierung des Enumerators auf, und versucht den Zugriff bei Objekten von IList zu optimieren. Wenn eine Datenstruktur IEnumerable oder IList implementiert ohne den Design Contract von IEnumerable bzw. IList zu erfüllen, ist das ein Bug und nix anderes. Wenn die Datenstruktur für die in diesem Kontext vorkommenden Operationen inperformant ist, muss man halt eine andere nehmen.

PatkIllA
2011-09-04, 16:00:43
Arrays SIND vom Typ IList(of T), und damit auch von IEnumerable(of T). Sonst würden weder Foreach Schleifen noch LINQ Queries auf Arrays funktionieren.
Damit Foreach schleifen gehen, reicht es eine GetEnumerator() Methode zu besitzen.

Ist denn ein Array wirklich soviel schneller?
Man kann die List<T> ja nicht ohne Grund mit einer Kapazität erstellen. Im Hintergrund liegt dort nämlich auch sowas wie ein Array und wenn das nicht mehr groß genug ist wird das in ein doppelt so großes umkopiert. Und die Anzahl muss man beim Array erstellen auch wissen.

Monger
2011-09-04, 16:20:01
Damit Foreach schleifen gehen, reicht es eine GetEnumerator() Methode zu besitzen.

Foreach schaut, ob das Objekt IEnumerable implementiert, und ruft auf dem Interface GetEnumerator auf. Du musst wirklich das Interface implementieren, eine Methode mit dem Namen deklarieren alleine reicht nicht.


Ist denn ein Array wirklich soviel schneller?
Man kann die List<T> ja nicht ohne Grund mit einer Kapazität erstellen. Im Hintergrund liegt dort nämlich auch sowas wie ein Array und wenn das nicht mehr groß genug ist wird das in ein doppelt so großes umkopiert.
List macht noch ein bißchen mehr als das. List erzeugt z.B. eine Hashtable im Hintergrund, um Abfragen auf "Contains" möglichst schnell zu machen.

Ich muss zugeben, ich weiß nicht wie sehr sich die Performance wirklich unterscheidet.
Die KeyValue Elemente sind zwar sicher auch Value Types, aber Value werden ja nicht vom Garbage Collector verwaltet, sondern liegen auf einem eigenen Stack. Der ist außer bei elementaren Typen wie eben Integer o.ä. wohl nicht so performant.
Arrays führen ja sowieso aus der Sprache raus. Die Implementierung dahinter ist definitiv "magic". Kann sein, dass für große Mengen von Value Types Arrays besser performen.

List(of T) hat sicherlich einen gewissen Overhead - aber eben nicht grundlos. Sie ist eben auf einen ganz bestimmten Anwendungszweck hin optimiert worden, z.B. schnelle Suche, schneller Vergleich von zwei Mengen etc.

In der Praxis kommt es eigentlich nie vor, dass man Millionen von Elementen flach in einer Liste im Speicher liegen hat. Für sowas nimmt man dann eigentlich Streams. Ich kann mich auf jeden Fall nicht erinnern wann ich das letzte mal ein Array deklariert habe, in 99% der Fälle ist man mit einer List(of T) glücklicher.

PatkIllA
2011-09-04, 16:24:06
Foreach schaut, ob das Objekt IEnumerable implementiert, und ruft auf dem Interface GetEnumerator auf. Du musst wirklich das Interface implementieren, eine Methode mit dem Namen deklarieren alleine reicht nicht.Doch die Methode reicht. Das ist ein Detail aus der 1.x Version ohne Generics, wo sonst heftig mit boxing und gefummelt hätte werden müsste.
Die GetEnumerator Methode von List<T> benutzt als Optimieriung sogar einen struct um die Erzeugung eines Objektes zu verhindern. IEnumerator<T> IEnumerable<T>.GetEnumerator() ist als explizite Interface Methode implementiert. Von daher unterscheidet sich die Geschwindigkeit sogar abhängig davon von welchem Typ die Variable ist.
List macht noch ein bißchen mehr als das. List erzeugt z.B. eine Hashtable im Hintergrund, um Abfragen auf "Contains" möglichst schnell zu machen. Auch falsch
This method performs a linear search; therefore, this method is an O(n) operation, where n is Count.
Das denken in der Tat aber viele. kA warum.
Da ist die Methode von Linq praktisch gleich schnell und erlaubt auch noch einen eigenen IEqualityComparer<T> zu verwenden.

Monger
2011-09-04, 16:33:47
...
Das denken in der Tat aber viele. kA warum.

Komisch. Hast recht, aber ich frag mich, wieso ich da O(1) im Kopf habe. Sowas sauge ich mir doch nicht aus den Fingern...

PatkIllA
2011-09-04, 20:08:13
Zuviel PHP gemacht? ;)

Ich hab mal einen kleinen Benchmark mit einer Million Elementen gemacht

ArrayConstructor 7901 ticks 2.37 ms
ArrayFill 44353 ticks 13.31 ms
ArrayForeach 30226 ticks 9.07 ms
ArrayFor 28222 ticks 8.47 ms
UnsizedListConstructor 32 ticks 0.01 ms
UnsizedListFill 148920 ticks 44.70 ms
ListConstructor 15915 ticks 4.78 ms
ListFill 111195 ticks 33.38 ms
ListForeach 106443 ticks 31.95 ms
ListFor 86369 ticks 25.93 ms
EnumerableForeach 106866 ticks 32.08 ms
LinqAggregate 324937 ticks 97.54 ms

ArrayConstructor 20670 ticks 6.20 ms
ArrayFill 136899 ticks 41.10 ms
ArrayForeach 123483 ticks 37.07 ms
ArrayFor 123821 ticks 37.17 ms
UnsizedListConstructor 217 ticks 0.07 ms
UnsizedListFill 421884 ticks 126.65 ms
ListConstructor 35477 ticks 10.65 ms
ListFill 220971 ticks 66.33 ms
ListForeach 278806 ticks 83.69 ms
ListFor 172557 ticks 51.80 ms
EnumerableForeach 279696 ticks 83.96 ms
LinqAggregate 705917 ticks 211.91 ms

Array ist schon ein wenig schneller.
Interessant finde ich, dass der Vorsprung bei Objekten sinkt.

Hier noch der Code

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;
using System.Reflection;
using System.Text;

namespace EnumberableBenchmark
{
internal class Benchmark<T>
{
public void Run(int repeat, int elementCount, T value)
{
for (int i = 0; i < repeat; i++)
{
Run(elementCount, value);
}
}

private void Run(int elementCount, T value)
{
Stopwatch stopwatch = new Stopwatch();
int hash = 0;
stopwatch.Start();

{
T[] array = new T[elementCount];
ArrayConstructor += stopwatch.ElapsedTicks;
stopwatch.Restart();

for (int i = 0; i < elementCount; i++)
array[i] = value;
ArrayFill += stopwatch.ElapsedTicks;
stopwatch.Restart();

for (int i = 0; i < elementCount; i++)
hash ^= array[i].GetHashCode();
ArrayFor += stopwatch.ElapsedTicks;
stopwatch.Restart();

foreach (var item in array)
hash ^= item.GetHashCode();
ArrayForeach += stopwatch.ElapsedTicks;
stopwatch.Restart();

}

{
List<T> unsizedList = new List<T>();
UnsizedListConstructor += stopwatch.ElapsedTicks;
stopwatch.Restart();

for (int i = 0; i < elementCount; i++)
unsizedList.Add(value);
UnsizedListFill += stopwatch.ElapsedTicks;
stopwatch.Restart();
}

{
List<T> sizedList = new List<T>(elementCount);
ListConstructor += stopwatch.ElapsedTicks;
stopwatch.Restart();

for (int i = 0; i < elementCount; i++)
sizedList.Add(value);
ListFill += stopwatch.ElapsedTicks;
stopwatch.Restart();

for (int i = 0; i < elementCount; i++)
hash ^= sizedList[i].GetHashCode();

ListFor += stopwatch.ElapsedTicks;
stopwatch.Restart();

foreach (var item in sizedList)
hash ^= item.GetHashCode();

ListForeach += stopwatch.ElapsedTicks;
IEnumerable<T> enumerable = sizedList;
stopwatch.Restart();

foreach (var item in sizedList)
hash ^= item.GetHashCode();

EnumerableForeach += stopwatch.ElapsedTicks;
stopwatch.Restart();

hash = sizedList.Aggregate(hash, (x, y) => x ^ y.GetHashCode());

LinqAggregate += stopwatch.ElapsedTicks;
}
}

public long ArrayConstructor { get; private set; }

public long ArrayFill { get; private set; }

public long ArrayForeach { get; private set; }

public long ArrayFor { get; private set; }

public long UnsizedListConstructor { get; private set; }

public long UnsizedListFill { get; private set; }

public long ListConstructor { get; private set; }

public long ListFill { get; private set; }

public long ListForeach { get; private set; }

public long ListFor { get; private set; }

public long EnumerableForeach { get; private set; }

public long LinqAggregate { get; private set; }

public override string ToString()
{
StringBuilder sb = new StringBuilder();
PropertyInfo[] propertyInfos = GetType().GetProperties(BindingFlags.Public | BindingFlags.Instance);

int maxNameLength = propertyInfos.Select(x => x.Name.Length).Max();
long maxValue = propertyInfos.Select(x => (long)x.GetValue(this, null)).Max();
int maxValueLength = (int)Math.Ceiling(Math.Log10(maxValue));
int maxMsLength = (int)Math.Ceiling(Math.Log10(Benchmark<T>.TicksToTime(maxValue)));
maxMsLength += 3;

foreach (var propertyInfo in propertyInfos)
{
sb.Append(propertyInfo.Name);
sb.Append(' ', maxNameLength - propertyInfo.Name.Length + 2);
long ticks = (long)propertyInfo.GetValue(this, null);

{
string ticksString = ticks.ToString("d", CultureInfo.InvariantCulture);
sb.Append(' ', maxValueLength - ticksString.Length);
sb.Append(ticksString);
sb.Append(" ticks ");
}

{
double ms = Benchmark<T>.TicksToTime(ticks);
string msString = ms.ToString("0.00", CultureInfo.InvariantCulture);
sb.Append(' ', maxMsLength - msString.Length);
sb.Append(msString);
sb.Append(" ms");
}

sb.AppendLine();
}

return sb.ToString();
}

private static double TicksToTime(long value)
{
return (value * 1000.0) / Stopwatch.Frequency;
}

}

static class Program
{
/// <summary>
/// The main entry point for the application.
/// </summary>
static void Main()
{

const int elementCount = 1000 * 1000;
const int repeat = 10;

{
Benchmark<int> benchmark = new Benchmark<int>();
benchmark.Run(repeat, elementCount, 0);
Console.WriteLine(benchmark);
}

{

Benchmark<object> benchmark = new Benchmark<object>();
benchmark.Run(repeat, elementCount, new object());
Console.WriteLine(benchmark);
}
}
}
}

del_4901
2011-09-05, 16:43:27
Tendentiell sind For Schleifen eher langsamer als Foreach Schleifen (und damit auch LINQ), weil du im Enumerator typspezifische Optimierungen machen kannst, die von außen eben nicht gehen. Wenn der Enumerator messbar langsamer als der Index Zugriff ist, hast du die Implementierung verbockt.
Nicht unbedingt, das Compact Framework erzeugt auf der Xbox durch Enumeratoren soviel Garbage, dass der Index Zugriff wirklich um ein vielfaches schneller ist.

Gast
2011-09-08, 21:30:46
Die Unterschiede liegen in erster Linie in der Verwendung

Bei einem Zugriff per Enumerator kann man keine Änderungen an der zu Grunde liegenden Datenstruktur machen, sonst wird eine Exception geworfen. Man kann z.B. keine Elemente entfernen oder hinzufügen. Per Index muss man zwar aufpassen, dass man die Elemente trotzdem noch in der richtigen Reihenfolge durchläuft, aber grundsätzlich geht es.

Dafür kann man einen Enumerator immer benutzen. Ein Indexzugriff ist nicht immer möglich z.B. bei einem Dictionary nicht.

Weiters hat man bei einer einfachen for Schleife auch automatisch einen Schleifenzähler, den man verwenden kann z.B. um die Daten an eine gewisse Stelle zu schreiben. Dies müsste man sonst immer händisch machen, was wieder 2 unnötige Zeilen Code pro Schleife sind.
Weiters ist per Definition die Reihenfolge fix festgelegt. Bei einem Enumerator ist nicht unbedingt gesagt, in welcher Reihenfolge dieser die Elemente liefern muss. Diese könnten je nach Implementierung in irgendeiner Reihenfolge kommen. for each garantiert nur, dass alle Elemente bearbeitet werden, aber nicht zwingend in welcher Reihenfolge. Diese ist eventuell auch gar nicht definiert.

Bei sehr kurzen Schleifen dauert das Erzeugen eines Enumerators oft länger als gleich alles durchzulaufen. Klar sollte eine saubere Implementierung einfach nur auf die Elemente zugreifen, aber manchmal geht es einfach nicht anders und man muss z.B. erst alle Elemente auf einen anderen Typ casten, bevor man etwas damit machen kann. Ist zwar nicht sauber, aber eben manchmal notwendig bzw. die Alternative noch schlechter.
Natürlich gibt es auch Datenstrukturen, wo der Zugriff per Index ewig lange dauert, aber hier ist eher der Programmierer gefragt, dies generell nicht zu machen.