Performancemythen?

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).

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.

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.

ist doch blödsinn. flaschenhälse sind heutzutage doch sogut wie immer netzwerke, datenbanken, festplatten. wer da noch ein i++ durch ein ++i im assembler patcht oder versucht virtuelle methodenaufrufe zu vermeiden hat langeweile aber dicke

frenki

Ja, nee, is klaaar. Darum gibt es vermutlich auch soviele CPU-Limitierte Games.

DEvent

frenki schrieb:

Ja, nee, is klaaar. Darum gibt es vermutlich auch soviele CPU-Limitierte Games.

CPU-Limitierte Games?

QuickSort ist einfach.

Insert sort ist einfach, weil man nicht ueberlegen muss. Auf QuickSort muss man erstmal kommen.

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.

Leider hat die Strukturiertheit und Ubersichtlichkeit gar nichts mit der Geschwindigkeit des Codes zu tun. Also liegst du schon mal 2 mal falsch.

DEvent schrieb:

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.

Leider hat die Strukturiertheit und Ubersichtlichkeit gar nichts mit der Geschwindigkeit des Codes zu tun. Also liegst du schon mal 2 mal falsch.

du hast noch nie an einem mittelgroßen softwareprojekt gearbeitet oder?

Gregor

DEvent schrieb:

Leider hat die Strukturiertheit und Ubersichtlichkeit gar nichts mit der Geschwindigkeit des Codes zu tun. Also liegst du schon mal 2 mal falsch.

Doch, hat es. ...und zwar, wenn Du Dir die Frage stellst, wer den Code geschrieben hat. Dann wirst Du nämlich feststellen, dass Leute mit Erfahrung in der Programmierung, als auch entsprechendem Wissen im jeweiligen Themenbereich, die benötigten Voraussetzungen haben, qualitativ hochwertigen Code zu schreiben. ...und zwar in allen Aspekten. Wer diese Voraussetzungen nicht hat, kann nicht mit einer gleichartigen Systematik an das Projekt herangehen und entsprechend wird da schlechterer Code herauskommen.

Ponto

CStoll schrieb:

@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)

Alle drei Varianten sind nach Standard möglich.

frenki schrieb:

Ja, nee, is klaaar. Darum gibt es vermutlich auch soviele CPU-Limitierte Games.

nun, die hauptrechenleistung bei spielen geht wohl auf die grafik zurück. die wird zuallererst mal auf der gpu nich auf der cpu berechnet. desweiteren sind grafikberechnungen allesamt nur implementierungen von mathematischen algorithmen. also entweder entwickelt man neue algorithmen oder neue gpus. mit ++i vs i++ kannst du da absolut nichts rausholen.

ps: computerspiele sind scheiße

Gregor

dieser thread schrieb:

nun, die hauptrechenleistung bei spielen geht wohl auf die grafik zurück. die wird zuallererst mal auf der gpu nich auf der cpu berechnet. desweiteren sind grafikberechnungen allesamt nur implementierungen von mathematischen algorithmen. also entweder entwickelt man neue algorithmen oder neue gpus. mit ++i vs i++ kannst du da absolut nichts rausholen.

Vielleicht spielt DEvent am Computer eher Schach und eher weniger Killerspiele. ...wer weiß.

this-*gt*that

dieser thread schrieb:

nun, die hauptrechenleistung bei spielen geht wohl auf die grafik zurück.

Eher nicht. Die meiste Rechenleistung wird meistens durch die Logik (KI etc.) verbraten.