Laden...

Warum haben WinForms, DataGridView & LINQ eine gute Performance? [==> lineare Aufwandsklasse]

Erstellt von Schildkroete vor 11 Jahren Letzter Beitrag vor 11 Jahren 3.948 Views
S
Schildkroete Themenstarter:in
80 Beiträge seit 2012
vor 11 Jahren
Warum haben WinForms, DataGridView & LINQ eine gute Performance? [==> lineare Aufwandsklasse]

Hallo zusammen,

früher habe ich mir nicht so oft Gedanken gemacht, was Performance angeht. Ich vermute, dass mein Beitrag evtl. nicht hier her gehört. Aber seit neuesten, ich versuche ein gutes bzw. spezielles abgeleitetes DataGridView zu erstellen, für bestimmte Zwecke, ist mir was aufgefallen.

Das DataGridView von den WinForms ist sehr sehr schnell - performant, was mich z.B. beim Darstellen von 1 Mio. Datenobjekten recht beeindruckt hat. Ob diese Anzahl von Objekten vorerst aus der Datenbank über eine Internetleitung geladen werden müssen, ist eine andere Sache.

Nun musste ich die Möglichkeit schaffen die Sachen zu sortieren. Ich habe mich für LINQ bzw. Lamba Ausdrücke entschieden. Davor gab es immer wieder Wiedersprüche, dass LINQ Ausdrücke nur Schleifen in Schleifen sind und keine besondere Erkenntnis liefern, was die Schnelligkeit angeht. Und siehe da, da wurde ich wieder überrascht!
Das Sortieren von 1 Mio. Datenobjekten mit Just-In-Time, sprich bei drücken einer Taste auf dem Keyboard im Filterfeld, war super schnell. Meistens hat es knapp eine Sekunde gedauert oder sogar noch schneller.

Von Performance verstehe ich nicht wirklich viel, nur "So wenige Funktionen bzw. Prozesse aufrufen um ans Ziel zu kommen!", aber könnte mir jemand es erklären bitte. Was steckt wirklich hinter LINQ & WinForms, dass diese Sachen so schnell sind. Ich habe versucht unter WPF DataGrid knapp 10.000 Datenobjekte darzustellen und es hat ewig gedauert, bis die Tabelle dargestellt wurde, zudem hat das Scrollen immer wieder gestockt.

Danke im Voraus für die Erklärung! 😁

----ehm............

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo Schildkroete,

in erster Linie sind die heutigen Rechner so schnell und haben soviel Speicher, dass 1Mio Einträge in Echtzeit zu sortieren kein Problem mehr ist. Linq verwendet zum Sortieren auch keinen anderen Algorithmus als Array.Sort, also Quicksort, der in der verwendeten Implementierung für alle praktisch vorkommenden Listen in O(nlog(n)) sortiert. Das bedeutet für Listen von einer 1Mio Einträgen, dass er jeden Eintrag im Schnitt 20mal anfassen muss (2^20 = ca. 1Mio, also log(1Mio) = 20). Macht etwas vereinfacht gesagt 20Mio Operationen() und die sind für einen heutigen Prozessor ein Klacks.

(*)Gemeint sind zwar nicht direkt Prozessoroperationen, aber eben doch relativ einfache Operationen, wie im Sort-Beispiel das Vergleichen und Vertauschen von zwei Einträgen.

Deine Frage scheint mir aber eher zu sein, warum es bei deiner Implementierung nicht so ist. Und der wahrscheinlichste Grund ist, dass du an irgendeiner Stelle Code verwendest, der eben keinen Aufwand von O(n) oder O(nlog(n)) hat, sondern von O(nn) oder mehr. Und dann wird es selbst für heutige Prozessoren mehr als knapp, denn das würde bedeuten 1Mio Einträge je 1Mio Mal anzufassen, also 1 Billion Operationen. Wo 20 Mio Operationen(*) in sagen wir einer Sekunde zu schaffen sind, benötigen 1 Billion Operationen 50.000 mal länger, also knapp 14 Stunden (=50000/3600).

Gegen solche Unterschiede (1 Sekunde vs. 14 Stunden) verblassen alle - meist vollkommen sinnlosen - Mikrooptimierungen (siehe auch Mergesort langsamer als Bubblesort? [==> Nein, Messfehler]). Deshalb sollte man sich "premature optimization is the root of all evil" zu Herzen nehmen.

Kurz gesagt, sollte man bei großen Datenmengen alles vermeiden, was quadratischen oder höheren Aufwand verursacht. Grundsätzlich sollte man sich also nicht in sinnlosen Mikrooptimierungen verlieren, sondern den Blick vor allem auf die Aufwandsklasse der verwendeten Algorithmen richten.

Ein Beispiel wo man sich mit einem naiven Ansatz leicht quadratischen Aufwand einhandeln kann, ist das Löschen von vielen Einträgen (z.B. jedem zweiten Eintrag) aus Listen, siehe dazu auch [FAQ] Listenelemente suchen und entfernen (Abschnitt "Aufwandsklasse der naiven Lösung").

herbivore

Suchhilfe: 1000 Worte, Aufwandklasse, Quadratisch vs n*log n, optimieren, Optimierung, Optimierungen, Mikrooptimierung, Mikrooptimierungen, Microoptimierung, Microoptimierungen, Performance, Performanceoptimierung, Performanceoptimierungen, Laufzeit, Laufzeitoptimierung, Laufzeitoptimierungen, Laufzeitverbesserung, Laufzeitverbesserungen, Aufwand, verbessern, Verbesserung, Verbesserungen, premature optimization is the root of all evil

5.657 Beiträge seit 2006
vor 11 Jahren

Eigentlich sind das ja drei Fragen, die nicht so viel miteinander zu tun haben:

  • Warum werden Listen so schnell sortiert? (hat herbivore bereits beantwortet)
  • Warum wird das unter Windows Forms so schnell angezeigt?
  • Warum wird das unter WPF nicht so schnell angezeigt?

Die letzten beiden Fragen lassen sich aber nicht so einfach beantworten, da man zu diesem Vergleich zwei identische Projekte bräuchte. Ich bin ziemlich sicher, daß man unter WPF auch große Datenmengen in Echtzeit anzeigen lassen kann.

Christian

Weeks of programming can save you hours of planning

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo MrSparkle,

das Sortierbeispiel lässt sich auch auf auf die Darstellung bzw. das Füllen von Controls übertragen. Wenn man z.B. neue Einträge an den Anfang der Liste einträgt, statt ans Ende der Liste anzuhängen, bekommt man quadratischen Aufwand statt linearem (weil bei einer array-basierten Liste für jedes neue Element dann alle bestehenden Elemente nach hinten geschoben werden müssen). Wenn ein Control verwendet wird, das beim Hinzufügen der Elemente quadratischen Aufwand verursacht(*), haben die resultierenden Performance-Engpässe also ganz genau die gleiche Ursache wie bei dem Sortierbeispiel. Das gleiche gilt für den Code, der zum Füllen des Controls oder zum Laden der Daten oder deren Vorverarbeitung verwendet wird. Bei großen Datenmengen muss man an alle Stellen, die von den Daten durchlaufen werden, quadratischen Aufwand vermeiden. Wenn man das nur an einer Stelle missachtet, ist die Gesamtperformance im Keller.

herbivore

(*) Natürlich kann bei großen Datenmengen auch eine aufwändige Operation, die auf jedes Element angewendet wird, schon zu Performance-Problemen führen, selbst wenn der Gesamtaufwand immer noch linear ist. Das wäre z.B. der Fall, wenn sich das Control nach jedem hinzugefügten Element komplett neu zeichnet. Wenn dazu unabhängig von der Größe der Liste sagen wir 50000 Pixel neu gezeichnet werden müssen, bekommt man (wieder etwas vereinfacht betrachtet) auch so zu dem obigen Faktor 50000. Deshalb bietet viele Listen-Controls auch BeginUpdate/EndUpdate oder ähnliche Methoden, mit denen man die Aktualisierung während des Füllens ausschalten kann.

S
Schildkroete Themenstarter:in
80 Beiträge seit 2012
vor 11 Jahren

Danke für die ausführliche Antwort und den Beispiel,

ich glaube, es ist das erste Mal, dass Mathematik erfolgreich im realen Leben gezeigt wird, statt theoretisch auf einer Tafel ohne jeden Bezug zu einer Sache 😉 ...

Zur WPF: Es war ein einfaches Model mit ca. 5 Properties, die von Typ String sind.
Dazu habe ich ganz normal DataTemplates erstellt bzw. DataGridColumns mit Bindings, also nichts komplexes. Auch den Style habe ich nicht mal angefasst.

Aber mit dem WPF & Performance Problem bin ich nicht der einzige. Hab schon deswegen viel recherchiert, aber keine vernünftige Lösung bzw. Antwort erhalten.

----ehm............

6.911 Beiträge seit 2009
vor 11 Jahren

Hallo Schildkroete,

bei WPF solltest du Virtualisierung verwenden, damit nur die tatsächlich angezeigten Elemente in der (grafischen) Verarbeitung berücksichtigt werden.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

S
Schildkroete Themenstarter:in
80 Beiträge seit 2012
vor 11 Jahren

Virtualisierung war einer der Punkte, die ich ausprobiert habe... war leider enttäuschend..

Vielleicht kannst du mir etwas Code zeigen, wie man es einbaut bitte.

----ehm............

95 Beiträge seit 2006
vor 11 Jahren

Hallo Schildkroete,

dazu ist noch zu sagen, dass bei Änderungen an Listen, die für Datenbindung verwendet werden oft nicht die Operation an sich das Problem ist, sondern die Aktualisierung der gebundenen Controls.
Viele Controls, die Listen darstellen (wie Grids) können deshalb die Aktualisierung der GUI zeitweise aussetzen.
Ich weiß nicht, ob das in deinem Fall zutrifft, aber such mal nach

Grid.BeginUpdate();
Grid.EndUpdate();

Alternativ dazu könntest du evtl. die Verbindung des Grids zur Liste vorübergehend trennen...

Wenn zwei dasselbe tun, ist es noch lange nicht dasselbe
(Adelphi)

C
2.121 Beiträge seit 2010
vor 11 Jahren

Ich würd mir da zuallererst überlegen, wem die Anzeige von 1 Mio Datensätzen wenigstens ansatzweise etwas bringt. Das kann doch längst keiner mehr scrollen oder durchsuchen.

Wenn du eine Suche einbaust und nur das anzeigst was der Benutzer gerade sehen will (und vielleicht noch ein bisschen was davor und danach), hast du ihm einen viel größeren Gefallen getan und sparst dem Anzeigeelement das Handling von hunderttausenden Datensätzen.

S
Schildkroete Themenstarter:in
80 Beiträge seit 2012
vor 11 Jahren

Vielen Dank für die ganze Info.

Ob die Anzeige mit 1 oder 2 Mio. Einträgen jemanden was nutzt ist zweitrangig. Obwohl es schon Anwendungen/Situationen gibt, zwar nicht viele, wo so eine Ansicht erfordert wird.
Für mich war primär zu verstehen, warum so viele Objekte so schnell geladen werden können, als z.B. beim WPF...

Wegen dem Tipp, da muss ich noch mehr anschauen und ausprobieren.

Im Endeffekt haben z.B. Firmen pro Liste/DataGrid zwischen 500 und 10.000 Einträgen, die auf einmal dargestellt werden und abgearbeitet. Wie oben schon gesagt wurde, bei ca. 10.000 Einträgen/Datenobjekten habe ich im Endeffekt 100.000.000 Prozesse oder sogar noch mehr.

----ehm............

C
2.121 Beiträge seit 2010
vor 11 Jahren

Für mich war primär zu verstehen, warum so viele Objekte so schnell geladen werden können, als z.B. beim WPF...

Listen im virtuellen Modus zeigen nur das an was Platz hat und kümmern sich auch nicht um die anderen Objekte. Praktisch geht es ja zunächst bei der Anzeige nur darum, den Scrollbalken richtig zu berechnen. Das Control merkt sich dass es die Elemente Nummer x bis y anzeigen soll und holt sich die aus der von dir bereitgestellten Liste. Das sind nur sehr sehr wenige (nämlich das was auf den Bildschirm passt).
Das Control in WPF scheint da was aufwendigeres zu machen.

die auf einmal dargestellt werden und abgearbeitet.

Optisch dargestellt werden sie nicht auf einmal 😃
Abgearbeitet werden sie im Code, über 10000 Elemente laufen und irgendwas draus berechnen ist kein Hexenwerk. Der Aufwand steckt in der Grafik.