Was hat ihr schon optimiert?



  • Welche Programme habt ihr schon optimiert und wie? Habt ihr einen besseren Algorithmus verwendet oder den Code einfach nur besser (oder mit Assembler...) geschrieben? Wieviel Prozent hat das dann gebracht?



  • esskimoe schrieb:

    Welche Programme habt ihr schon optimiert und wie? Habt ihr einen besseren Algorithmus verwendet oder den Code einfach nur besser (oder mit Assembler...) geschrieben? Wieviel Prozent hat das dann gebracht?

    Bessere Mathe: 10000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000000000%

    Besserer Algo: 1000000000000000000000000000000000%

    Asm: 1000%

    Multithreading: 600%

    SSE/MMX: 150%



  • Intrinsics: 150%

    volkard schrieb:

    Asm: 1000%

    Wirklich? Wie kommt dieser grosse Sprung zustande?



  • nonbeliever schrieb:

    Intrinsics: 150%

    volkard schrieb:

    Asm: 1000%

    Wirklich? Wie kommt dieser grosse Sprung zustande?

    Nee, nicht wirklich. Ein paar Nullen weniger mögen es sein. Aber je nach Problem und unangemessenheit des naiven Algorithmus.

    Der Sprung kommt daher zustande, daß die starken Optimierungen in ihrem Prozentsatz mit der Problemgröße wachsen, während die schwachen Optimierungen nur an Hardware/Compiler/Sprache hängen.

    Ich mach mal ein Beispiel…

    Ich suche alle pythagoräischen Tripel, also alle natürlichen Zahlen a,b,c mit a2+b2=c^2, wie 32+42=5^2. Und der Einfachheit halter sollen a,b,c kleiner 1000000 sein und ich vernächlässige die reine Ausgabezeit.

    #include <iostream>
    using namespace std;
    
    int main(){
    	for(int64_t a=1;a<1000000;++a){
    		for(int64_t b=1;b<1000000;++b){
    			for(int64_t c=1;c<1000000;++c){
    				if(a*a+b*b==c*c){
    					cout<<a<<' '<<b<<' '<<c<<'\n';
    				}
    			}
    		}
    	}
    }
    

    Das Programm sieht auf den ersten Blick vernünftig aus. Laufzeit ungefähr 70 Jahre.

    Algorithmisch fällt auf, daß das Ausprobieren von c recht blöd ist.

    #include <iostream>
    #include <arcoth>
    using namespace std;
    
    int main(){
    	for(int64_t a=1;a<1000000;++a){
    		for(int64_t b=1;b<1000000;++b){
    			int64_t c=isqrt(a*a+b*b);
    			if(c<1000000 and a*a+b*b==c*c){
    				cout<<a<<' '<<b<<' '<<c<<endl;
    			}
    		}
    	}
    }
    

    Laufzeit ungefähr 2 Tage. Das ist doch mal ein Knaller! Damit Multithreading so viel bringt, bräuchte ich schon 10000 Kerne, hab ich aber nicht.

    Und dann könnte man zufällig auf https://de.wikipedia.org/wiki/Pythagoreisches_Tripel#Erzeugung_der_pythagoreischen_Tripel gestoplert werden.

    //Code ist mir zu schwierig, das überlasse ich dem geneigten Leser.
    

    Laufzeit ca 1 Sekunde.



  • Ich habe schon einiges optimiert, allerdings meist einige Programme. Allerdings nie mit Assembler, das kann mein Compiler deutlich besser als ich. 😉

    Meistens verbessere ich den Algorithmus, wobei das Programm durchaus 100mal so schnell werden kann. Häufig ineffiziente Stringoperationen oder Enumeratoren, oder zu häufiges Kopieren von Daten.
    Wobei ich meistens eher an Programmen arbeite die in Echtzeit laufen sollen, da ist die Performance nicht so wichtig solange es nicht ruckelt. Und falls es doch zu langsam ist liegt das normalerweise an einem größeren Designfehler. Zum Beispiel ein großes Bild viel zu häufig neuzeichnen, oder Daten jedesmal neuzuberechnen statt sie zu Cachen. Das umzuschrieben macht das dann schnell 10mal schneller.

    Oft benutze ich dann einfach noch Multihtreaded zum Beschleunigen, wobei ich mir nicht sicher bin ob man Multithreading bei simple Tasks wirklich "optimieren" nennen kann. Jedenfalls führt das je nach Anspruch des Tasks zu einer Beschleunigung von 90%-100% pro Kern. Und falls das Problem nicht paralellisierbar ist versuche ich den Algorithmus noch im kleinen zu verbessern, so dass der Compiler effizienteren Code generiert. Aber viel mehr als doppelt so schnell bekomme ich das kann auch nicht mehr hin.



  • Erfolgstipp: Man kann das Optimierungs-Ergebnis um ein vielfaches verbessern wenn man die ursprüngliche Lösung besonders schlecht programmiert! So konnte ich bereits Verbesserungen von mehreren 1000% erreichen 💡



  • volkard schrieb:

    Bessere Mathe: 10000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000000000%

    Besserer Algo: 1000000000000000000000000000000000%

    Was ist für Dich der Unterschied zwischen besserer Mathe und einem besseren Algorithmus?



  • In den 90ern hab ich mir regelmäßig TurboC-code als ASM ausgeben lassen und dann die Registerbenutzung optimiert. War oft ganz erfolgreich.



  • Ich habe eine paar crypto Algorithmen implementiert (SHA-2, Keccak, Chacha20, etc.) und es ist schon erstaunlich wie viel performance man bekommt indem man einfach nur manuell (oder durch template-rekursion ;)) loops unrolled, und indem man viele einzelne Variablen statt Arrays benutzt. Man wuerde denken sowas einfaches koennten Compiler mittlerweile selbststaendig, aber nope. Jedenfalls nicht VS und g++. (Auch nicht mit inline everything & favor fast code etc.) Clang teste ich vielleicht irgendwann mal. Dafuer wird memcpy einfach zu einer instruction weg optimiert, guter weg um alignment und strict aliasing Problemen aus dem Weg zu gehen. 😃



  • Gregor schrieb:

    volkard schrieb:

    Bessere Mathe: 10000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000000000%

    Besserer Algo: 1000000000000000000000000000000000%

    Was ist für Dich der Unterschied zwischen besserer Mathe und einem besseren Algorithmus?

    Würde mich auch interessieren.



  • Cpp_Junky schrieb:

    Erfolgstipp: Man kann das Optimierungs-Ergebnis um ein vielfaches verbessern wenn man die ursprüngliche Lösung besonders schlecht programmiert! So konnte ich bereits Verbesserungen von mehreren 1000% erreichen 💡

    QFT!



  • cooky451 schrieb:

    und indem man viele einzelne Variablen statt Arrays benutzt. Man wuerde denken sowas einfaches koennten Compiler mittlerweile selbststaendig, aber nope. Jedenfalls nicht VS und g++. (Auch nicht mit inline everything & favor fast code etc.)

    Ich hab ne Theorie was der Grund sein könnte dass weder VS noch GCC das optimieren können. Zeig den Code her, dann kann ich gucken ob die Theorie aufgeht.



  • Sowas kann auch Spass machen. Es ist ein tolles Gefühl, wenn man nach Jahren endlich eine primitive stümperhafte Implementierung ersetzen kann, die so tief drinnen war, dass niemand sich getraut hatte, sie zu ersetzen, und man dabei das Programm um Größenordnungen beschleunigt.



  • cooky451 schrieb:

    Ich habe eine paar crypto Algorithmen implementiert (SHA-2, Keccak, Chacha20, etc.) und es ist schon erstaunlich wie viel performance man bekommt indem man einfach nur manuell (oder durch template-rekursion ;)) loops unrolled, und indem man viele einzelne Variablen statt Arrays benutzt.

    Wieviel Prozent sind viel?



  • CRC32 Berechnung von C++ nach ASM -> Faktor 6 schneller. Aber wahrscheinlich auch nur deshalb, weil die Compileroptimierungen nicht eingeschaltet sein durften (Vorschrift).



  • Cpp_Junky schrieb:

    Erfolgstipp: Man kann das Optimierungs-Ergebnis um ein vielfaches verbessern wenn man die ursprüngliche Lösung besonders schlecht programmiert! So konnte ich bereits Verbesserungen von mehreren 1000% erreichen 💡

    dito, hab mal eine CRC Berechnung für Dateien in C# verbessert. Der Ursprungscode hat Byte für Byte eingelesen und das dauerte bei großen Dateien recht lange. Nach Änderung auf Einlesen in jeweils 4KB Blöcke und darauf die CRC Berechnung ist nun überhaupt keine Berechnungszeit mehr wahrzunehmen.



  • Ich habe schon viele Demos und Intros optimiert. Wird im schlimmsten Fall ein paar % langsamer, aber was tut man nicht um die letzten paar Bytes auszunutzen (http://www.pouet.net/prod.php?which=66062 ;-).



  • Ich habe momentan gerade das Vergnügen, einen lang laufenden Prozess (Grössenordnung von Stunden), der auf Web Services zugreifen muss, zu optimieren. Das Problem hierbei sind die vielen Requests, welche bisher einzeln abgesetzt werden. An vielen Stellen kann man vermutlich Bulk Processing betreiben. An anderen Stellen werden viele Daten rumgeschoben, welche gar nie gebraucht werden (liegt am bequemen Programmiermodell).

    Burkhi schrieb:

    CRC32 Berechnung von C++ nach ASM -> Faktor 6 schneller. Aber wahrscheinlich auch nur deshalb, weil die Compileroptimierungen nicht eingeschaltet sein durften (Vorschrift).

    *kopfschüttel*



  • Gregor schrieb:

    volkard schrieb:

    Bessere Mathe: 10000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000000000%

    Besserer Algo: 1000000000000000000000000000000000%

    Was ist für Dich der Unterschied zwischen besserer Mathe und einem besseren Algorithmus?

    Ihr habt doch genug bei den Primzahlenthreads von unserem EH mitgelesen, also stellt Euch nicht doof.
    Es gibt da etliche Optimierungen, die rein mit den Eigenschaften der Zahlen zu tun haben, wie daß man keine ungeraden Teiler testen muss (klappt nur bei Primzahlen, was unser Forschungsgegenstand dort ist).
    Und es gibt etliche Optimierungen, denen vollkommen egal ist, was man sucht, wie memoization (klappt auch bei std::strings und Großmüttern, sogar bei Elefanten).

    Klar entschwuppt der Unterschied, wenn man beide Richtungen ausgeschöpf. Praktische Mathematik oder theoretische Informatik? In der Sache kein Unterschied, allein, welches Institut das Gehalt zahlt, des Fachrichtung steht auf dem Paper.



  • @volkard
    Also mehr als eine schemenhafte Vorstellung wie du die Unterscheidung triffst hab ich jetzt auch nicht. Ist aber immerhin schon mehr als gar keine Ahnung 🙂



  • hustbaer schrieb:

    @volkard
    Also mehr als eine schemenhafte Vorstellung wie du die Unterscheidung triffst hab ich jetzt auch nicht. Ist aber immerhin schon mehr als gar keine Ahnung 🙂

    Geht mir ähnlich. Vielleicht kann man das so unterscheiden:

    Bessere Mathe = Erkennen, was für eine Problemstellung man eigentlich hat. Vor allem hat man es vielleicht mit einem Spezialfall zu tun, mit dem man viel leichter umgehen kann. Wenn einem bestimmte Eigenschaften von Problemstellungen klar werden, dann kann das ganz neue Möglichkeiten eröffnen.

    Besserer Algo = Umstellung auf den besten Algorithmus für die jeweilige Problemstellung. Also von "naiv implementiert" zu "gut recherchiert / gut erdacht", aber ohne eine Neuklassifikation der Problemstellung.


Anmelden zum Antworten