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?

volkard

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?

volkard

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 a^2+b2=c^2, wie 3²⁺⁴2=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.

DarkShadow44

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.

Cpp_Junky

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

Gregor

volkard schrieb:

Bessere Mathe: 10000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000%

Besserer Algo: 1000000000000000000000000000000000%

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

EOP

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

cooky451

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.

hustbaer

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.

hustbaer

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!

hustbaer

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.

Mechanics

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?

Burkhi

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

Burkhi

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.

TGGC

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

*rant*

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*

volkard

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.

hustbaer

@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

Gregor

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.