Performancemythen?

[Jester]

CStoll schrieb:

Wenn du mit der vorhandenen std::list<> unzufrieden bist, kannst du dir gerne eine eigene Listenklasse aufbauen, die genau deine Wünsche erfüllt Und das Gute daran ist, daß du die vorhandenen STL-Algorithmen problemlos mit deiner Liste zusammenarbeiten lassen kannst.

ich klinke mich dann mal aus der folgenden C++-Werbesendung aus... Es ist echt unglaublich.

Aber eine Frage sei mir noch gestattet: wieviele Listen hast Du schon als Hilfsdatenstrukturen eingesetzt?

Und nebenbei bemerkt: die MSVC-Implementierung würde einem meiner Algorithmen von linearer zu quadratischer Laufzeit verhelfen... richtig tolles Ding.

[CStoll]

Jester schrieb:

ich klinke mich dann mal aus der folgenden C++-Werbesendung aus... Es ist echt unglaublich.

Mach doch, was du denkst.

Aber eine Frage sei mir noch gestattet: wieviele Listen hast Du schon als Hilfsdatenstrukturen eingesetzt?

Bislang noch nicht viele - das liegt aber daran, daß ich meistens andere Anforderungen an meine Hilfsstrukturen habe (z.B. direkter Indexzugriff (vector) oder Sortierung (set/map)).

Und nebenbei bemerkt: die MSVC-Implementierung würde einem meiner Algorithmen von linearer zu quadratischer Laufzeit verhelfen... richtig tolles Ding.

Nur aus Interesse: Was ist denn das für ein Algorithmus?

[Jester]

CStoll schrieb:

Nur aus Interesse: Was ist denn das für ein Algorithmus?

Es geht um ein Graphen-Problem. Der Graph ist planar und hat noch einige weitere Eigenschaften. Ich zerlege den dann in immer kleinere Teile. Dadurch dass alles in Listen gespeichert ist kann ich jederzeit entlang einer Kante in zwei Teile zerlegen (und erhalte dadurch zwei unabhängige Graphen -- geht natürlich nicht immer, aber die spezielle Problemstruktur gibt das her). Durch das ständige weiter-zerlegen kann ich es mir nicht leisten für jeden Knoten festzustellen in welcher konkreten Liste er gerade drin ist.

Wobei es da ne ganze Reihe von Listenstrukturen gibt... die Knoten sind in ner doppelt verketteten List drin, die Kanten um einen Knoten herum (im Gegenuhrzeigersinn) auch usw.

[Simon2]

Hi,

Wo sind denn die "Performance-Mythen" geblieben ?

Eigentlich fand ich das Thema ganz interessant - interessanter jedenfalls als eine Diskussion über verschiedene Möglichkeiten "list" (das ich noch nie verwendet habe) zu implementieren ...

Mein Vorschlag: Koppelt doch die Diskussion ab (kann die ForenSW bestimmt).

@Topic: Einen "Performancemythos" hätte ich noch: "Performance ist das wichtigste an einem Programm !" (gemeint ist hiermit "niedrige Programmlaufzeiten")
Wenn ich mal vergleiche, wie viele Klagen über die Langsamkeit und wie viele es über mangelnde Stabilität von Programmen gibt, würde ich denken, dass Zweiteres deutlich mehr Gewicht erhalten sollte.

Gruß,

Simon2.

[Jester]

Simon2 schrieb:

Eigentlich fand ich das Thema ganz interessant - interessanter jedenfalls als eine Diskussion über verschiedene Möglichkeiten "list" (das ich noch nie verwendet habe) zu implementieren ...

tja, du vielleicht...

Mein Vorschlag: Koppelt doch die Diskussion ab (kann die ForenSW bestimmt).

Aus meiner Sicht ist das Thema eh erledigt.

@Topic: Einen "Performancemythos" hätte ich noch: "Performance ist das wichtigste an einem Programm !" (gemeint ist hiermit "niedrige Programmlaufzeiten")
Wenn ich mal vergleiche, wie viele Klagen über die Langsamkeit und wie viele es über mangelnde Stabilität von Programmen gibt, würde ich denken, dass Zweiteres deutlich mehr Gewicht erhalten sollte.

Da würde ich fast noch einen Schritt weiter gehen und behaupten, dass stabile Software meist auch schnell ist. Und zwar aus dem einfachen Grund, dass stabile Software meist so strukturiert ist, dass der Code vergleichsweise einfach ist (wäre er nicht einfach, so wäre die Software nicht so stabil). Und meist ist einfacher Code auch schnell.

[Mr. N]

CStoll schrieb:

Das Splice das Du da jetzt gepostet hat, hat aber lineare Laufzeit... es berechnet die Größe ja gleich mit.

Stimmt, das hat lineare Laufzeit. Aber irgendeine Einschränkung hast du immer.

Ja, sorum ist es aber 1. falschrum, 2. inkonsistent mit der libstdc++, weswegen man list so verwenden sollte als wären beide Operationen O(N), wenn man portablen Code schreibt.

Jester schrieb:

Da würde ich fast noch einen Schritt weiter gehen und behaupten, dass stabile Software meist auch schnell ist. Und zwar aus dem einfachen Grund, dass stabile Software meist so strukturiert ist, dass der Code vergleichsweise einfach ist (wäre er nicht einfach, so wäre die Software nicht so stabil). Und meist ist einfacher Code auch schnell.

VIM ist auch stabil, aber von einfachem oder sauberem Code würde ich da lieber nicht reden.

[Simon2]

Hi,

kommt drauf an, wie man Stabilität erzeugt. Gutes Design ist eins (und erstmal das Wichtigste), aber Konsistenzchecks sind ein Anderes - und die kosten auch Zeit.

Gruß,

Simon2.

[hustbaer]

Konsistenzchecks ändern an der "Stabilität" eines Programmes meist nicht viel, bloss daran wie schlimm sich verbleibende Fehler auswirken. Wenn ein Programm 100% Fehlerfrei ist, dann braucht man keine Konsistenzchecks mehr - und dann brauchen die auch keine Zeit mehr

[asc]

hustbaer schrieb:

Konsistenzchecks ändern an der "Stabilität" eines Programmes meist nicht viel, bloss daran wie schlimm sich verbleibende Fehler auswirken. Wenn ein Programm 100% Fehlerfrei ist, dann braucht man keine Konsistenzchecks mehr - und dann brauchen die auch keine Zeit mehr

Nur gibt es garantiert nicht ein einziges Projekt das 100% Fehlerfrei ist. Zumindest wenn es mehr als nur Hello World kann... Ich bin mir nicht ganz sicher, aber ich glaube das die letzte grobe Schätzung die ich hierzu gelesen habe besagt das sich in 100 Zeilen Code im Durchschnitt 4-10 Fehler befinden.

cu André

[DEvent]

Und meist ist einfacher Code auch schnell.

Das ist ja wohl falsch hoch 10. Dann ist Insert-Sort schneller als Quick-Sort? Dann ist stupides interpretieren schneller als ein Hotspot-Compiler?

[CStoll]

@list: Vielleicht sollte doch mal jemand, der den Standard vorliegen hat, die genauen Performance-Anforderungen der list-Methoden nachschlagen (ich habe hier nur Sekundär-Literatur und die liefert widersprüchliche Angaben). Ich kann mir zumindest drei Varianten vorstellen, wie splice() und size() zusammenarbeiten können:

• die libstdc++-Variante: splice() verbiegt nur die Zeiger und size() zählt jedes Mal durch (ergibt O(n) für size()).
• die MSVC-Variante: splice() aktualisiert die Größenangabe (ergibt O(n) für splice().
• lazy evaluation: splice() markiert die Größenwerte als ungültig und size() zählt nach, wenn notwendig (ergibt O(n) im worst case für size() - im Mittel haben beide vermutlich konstante Laufzeit)

@Performance: Ich glaube nicht, daß ein stabiles Programm automatisch schnell ist. Aber im Ernstfall muß man unterscheiden zwischen Mikro-Optimierung (dazu gehört auch ++x vs. x++), die eventuell die letzten Reserven aus dem Programm rausholt, und Makro-Optimierung (Geschichten wie lazy evaluation, over-eager evaluation oder der Unterschied zwischen BubbleSort und QuickSort), mit der man das Laufzeitverhalten des Programms in der Größenordnung verändern kann.
(btw, die Frage der list-Implementierung dürfte auch in den Bereich Makro-Optimierung fallen).

[m...m]

Was bringt eigentlich ein Just In Time Compiler?

[Gregor]

m...m schrieb:

Was bringt eigentlich ein Just In Time Compiler?

Im Vergleich zu interpretiertem Code bei Java zum Beispiel? Faktor 10 bei der Performance würde ich sagen. Kannst Du relativ leicht testen: Es gibt bei Java die Möglichkeit, den Jitter auszuschalten. Da müsstest Du aber selbst mal nach der entsprechenden JVM-Option suchen.

[m...m]

Gregor schrieb:

m...m schrieb:

Was bringt eigentlich ein Just In Time Compiler?

Im Vergleich zu interpretiertem Code bei Java zum Beispiel? Faktor 10 bei der Performance würde ich sagen. Kannst Du relativ leicht testen: Es gibt bei Java die Möglichkeit, den Jitter auszuschalten. Da müsstest Du aber selbst mal nach der entsprechenden JVM-Option suchen.

Und im Vergleich zu nem normalen Compiler? Man hätte ja die Möglichkeit je nach System anders zu kompileren und seine speziellen stärken auszunutzen. Aber was bringt sowas wirklich? Gibt es Anwendungen die wirklich auf mehreren stark unterschiedlichen Rechnern laufen und kann man dabei rausholen? Müsste der Programmierer nicht solche Hardware Besonderheiten mit Assembler ausnutzen, damit es wirklich was bringt oder kann ein JIT Compiler sowas genauso gut?

[Gregor]

m...m schrieb:

Und im Vergleich zu nem normalen Compiler? Man hätte ja die Möglichkeit je nach System anders zu kompileren und seine speziellen stärken auszunutzen. Aber was bringt sowas wirklich? Gibt es Anwendungen die wirklich auf mehreren stark unterschiedlichen Rechnern laufen und kann man dabei rausholen? Müsste der Programmierer nicht solche Hardware Besonderheiten mit Assembler ausnutzen, damit es wirklich was bringt oder kann ein JIT Compiler sowas genauso gut?

Die heutigen Jitter sind bei weitem nicht so perfekt, dass sie die hiermit verbundenen theoretischen Performancevorteile auch praktisch gegenüber statischen Compilern ausspielen könnten. Heutzutage werden statische Compiler also im Allgemeinen bessere Ergebnisse bringen. Aber das ist kein Naturgesetz oder so: Vielleicht sieht das in 10 Jahren anders aus. Hängt sicherlich auch davon ab, wie sich die Art des Programmierens in Zukunft verändert.

[Jester]

DEvent schrieb:

Und meist ist einfacher Code auch schnell.

Das ist ja wohl falsch hoch 10. Dann ist Insert-Sort schneller als Quick-Sort? Dann ist stupides interpretieren schneller als ein Hotspot-Compiler?

QuickSort ist einfach.
Aber genau darum ging es mir nicht. Ich sagte nicht: "simpler Code ist schnell", sondern "einfacher Code ist schnell". Wenn der Code klar strukturiert ist, Abläufe klar erkennbar sind und auch schnell zu ersehen ist welcher Teil des Codes was tut, dann ist er meist auch schnell. Oder anders gesagt: ein sauberes Design macht mehr aus als die ganzen low-level hacks.

[Helium]

DEvent schrieb:

Und meist ist einfacher Code auch schnell.

Das ist ja wohl falsch hoch 10. Dann ist Insert-Sort schneller als Quick-Sort?

Nein, ein Insertsort ist nur nicht so einfach, wie ein Quicksort:

-- quicksort
quicksort :: Ord a => [a] -> [a]
quicksort []    = []
quicksort (h:t) = quicksort [x | x<-t, x<h] ++ [h] ++ quicksort [x | x<-t, x>=t]

-- insertsort
insert :: Ord a => a -> [a] -> [a]
insert x []  = [x]
insert x (h:t)
	| x<=h =x:h:t
	| otherwise = h:insert x t

insertsort :: Ord a => [a] -> [a]
insertsort []    = []
insertsort (h:t) = insert x (insertsort t)

edit: wieso numeriert er mir den einen Code-Block und den anderen nicht?

[Mr. N]

Helium schrieb:

DEvent schrieb:

Und meist ist einfacher Code auch schnell.

Das ist ja wohl falsch hoch 10. Dann ist Insert-Sort schneller als Quick-Sort?

Nein, ein Insertsort ist nur nicht so einfach, wie ein Quicksort:

-- quicksort
quicksort :: Ord a => [a] -> [a]
quicksort []    = []
quicksort (h:t) = quicksort [x | x<-t, x<h] ++ [h] ++ quicksort [x | x<-t, x>=t]

Ich glaube aber irgendwie nicht, dass man quicksort so implementieren würde.

Außerdem, das wunderbare std::sort ist meistens ja ein aufgebohrtes Quicksort mit einigen Fallunterscheidungen, also einiges komplexer.

[Jester]

Helium schrieb:

edit: wieso numeriert er mir den einen Code-Block und den anderen nicht?

Ich glaube die Nummern werden erst ab 7 Zeilen verwendet.

[hustbaer]

Helium schrieb:

DEvent schrieb:

Und meist ist einfacher Code auch schnell.

Das ist ja wohl falsch hoch 10. Dann ist Insert-Sort schneller als Quick-Sort?

Nein, ein Insertsort ist nur nicht so einfach, wie ein Quicksort:

-- quicksort
quicksort :: Ord a => [a] -> [a]
quicksort []    = []
quicksort (h:t) = quicksort [x | x<-t, x<h] ++ [h] ++ quicksort [x | x<-t, x>=t]

-- insertsort
insert :: Ord a => a -> [a] -> [a]
insert x []  = [x]
insert x (h:t)
	| x<=h =x:h:t
	| otherwise = h:insert x t

insertsort :: Ord a => [a] -> [a]
insertsort []    = []
insertsort (h:t) = insert x (insertsort t)

edit: wieso numeriert er mir den einen Code-Block und den anderen nicht?

Ein Insertsort ist in Sprachen wie C++ einfacher zu schreiben und einfacher zu verstehen wenn man den Code sieht. Und es ist IMHO einfacher zu sehen ob er richtig implementiert ist.
Was nicht heisst dass es weniger Code ist.

Anderes Beispiel: Suchen von Strings in langen Texten. Einfach mit binärem Vergleich, also ohne Spielereien wie case-insensitive oder gar ärgeres.

Die einfachste und übersichtlichste Lösung ist hier wohl etwas in der Art:

int find(string text, string find)
{
    int n = text.size() - find.size() + 1;

    for (int i = 0; i < n; i++)
        if (text.substr(i, find.size()) == find)
            return i;

    return -1;
}

Ist aber verglichen mit schlaueren Algorithmen die erstmal diverse Tabellen erstellen (um z.B. zu wissen um wieviel bei einem "mismatch" weitergesprungen werden kann) um einiges langsamer. Je nach Anwendung kann der Unterschied dramatisch sein.