Sortieralgorithmen unter 64-Bit

[mulek]

Hallo,
Hab schon mal zu einem ähnlichen Thema gepostet da ich Laufzeitvergleiche von 32-Bit und 64-Bit Systemen durchführen will.
Bei meinen Ergebnisse zeigt sich jedoch nie ein Laufzeitunterschied der eigentlich durch Cache Misses verursacht werden sollte.

int main(){

	int const maxlength =10000;	//10000, 100000, 131072, 174763,  //200000, 262144
	int const NumberOfArrays = 1;
	int **pNumbers = new int* [maxlength];  

	double time = 0.0;
	double SumUpTime = 0.0;

	for(int i=0;i<NumberOfArrays;i++){
		RandomGenerator(pNumbers, maxlength);

		time = 0.0;
		stw::Start();
		BubbleSort(pNumbers, maxlength, Ascending);
		//sort(pNumbers,pNumbers+maxlength,NumberAscending);
		//QuickSort(pNumbers, LowerIndex, UpperIndex, Ascending); // selbst implementiert
		//stable_sort(pNumbers,pNumbers+maxlength,NumberAscending);
		time = stw::Stop();
		SumUpTime = SumUpTime + time;
		//Output(pNumbers, maxlength);
	}

	cout << "Die durchschnittliche Sortierungsdauer beträgt: " << (double) SumUpTime/NumberOfArrays << " Sekunden!" << endl;
	getchar(); 
	return 0;
}

Bei meiner CPU beträgt der Level 2 Cache eine Größe von 2MB. Das bedeutet das bei 32-Bit Version theoretisch maximal 2097152/2*4 Arrayelemente in meinen Cache passen (131072 Pointer und 131072 Integer). Da bei 64-Bit die Pointer von 4 Byte auf 8Byte anwachsen sollten daher nicht mehr alle Daten in den Cache passen und in der Laufzeit meines Programms sollte eine größere Laufzeitdifferenz durch Cache - Misses feststellbar sein. Ich führe Messungen mit BubbleSort, QuickSort und StableSort durch.

Bei QuickSort zum Beispiel sollte sich eine größere Laufzeitdifferenz einstellen da die Daten bei der Sortierung typischerweise durch die schlechte Effektivität des Sortieralgo öfters verwendet werden als beispielsweise bei einem QuickSort und daher der BubbleSort mehr vom Cache "profitiert" als andere Sortieralgos.

Ich hoffe das mir jemand helfen kann da ich schon ziemlich lange an der Thematik arbeite und einfach nicht weiterkomme!!!
Würde mich auch freuen wenn jemand mir Dokumente zu diesem Thema zur Verfügung stellen könnte!!!!!

Wusste nicht wie ich die Ergebnisse meiner Messung online stellen kann und hab einfach mal einen Screenshot "upgeloaded":
http://img341.imageshack.us/img341/9364/ergebnisse.png

[SeppJ]

Tja, dann gibt es eben keinen Effekt. Du hast die These selbst widerlegt. So lange weiter zu messen, bis man ein gewünschtes Ergebnis erhält, wäre unwissenschaftlich.

Ich setze mal voraus, dass du bei der Messung auch alles richtig gemacht hast, deine kurze Beschreibung reicht nicht aus, um das zu beurteilen.

edit: Oh, ich sehe gerade selbst bei deinem kurzen Beispiel, dass du wahrscheinlich doch Mist gemacht hast: Sortierst du da ints die alle über einen einzelnen Zeiger angesprochen werden? Und vorher mittels new wild im Speicher verteilt wurden? Was soll das denn? Ich vermute mal, dass deine Programmlaufzeit derart von Cache-Misses dominiert wird, dass es nichts ausmacht, ob du mit 32- oder 64-Bit Pointern arbeitest.

[knivil]

Da bei 64-Bit die Pointer von 4 Byte auf 8Byte anwachse

Ach, und wie gross ist ein int bei einer 64Bit Architektur? sizeof(int) hilft!

eigentlich durch Cache Misses verursacht ... sollte eine größere Laufzeitdifferenz

Sollte, koennte, muesste ... Anscheinend versuchst du nur ein bestimmtes Ergebnis zu erzwingen. So voreingenommen an eine Analyse zu gehen ist einfach nur traurig. Angenommen du stellst fest, dass 64 Bit beim Sortieren schneller ist, als 32 Bit. Warum soll es an Cachemisses liegen. Die 64 Bit Architektur hat z.B. auch mehr Register, so dass der Speicher im allgemeinen weniger angefasst werden muss. Auch weisst du nicht, in welcher Reihenfolge die Daten angefasst werden, oder wie die Daten im Cache abgelegt/ersetzt werden. Auch weisst du nicht, wie andere Prozesse sich auf den Cache auswirken. Vielleicht hat die 64 Bit Version aehnlich viele Cachemisses. Hinzu kommt die Zeitmessung ...

Kurz: Du hast keine Ahnung und willst nur deine Hypothese bestaetigen.

Nutze einfach einen Profiler, valgrind kann glaube auch Cachemisse zaehlen. Wie verlaesslich diese Daten sind, beim Programmablauf ohne Profiler sei aber dahingestellt.

!!! ... !!!!!

Ein Ausrufezeichen reicht.

[DocShoe]

Zumal du dem Compiler auch noch verbietest zu optimieren. Ich bin ja kein Freund von premature optimization, aber das hier ist ja das genaue Gegenteil. Du schreibst Code, der absichtlich untypisch ist, verhinderst durch Compilerschalter Optimierungen und versuchst daraus allgemeingültige Aussagen zu treffen. Das nix geht!

[mulek]

ja es ändert auch nichts an meinen Ergebnissen wenn ich die Optimierung anlasse!!!

was ist den an meiner datenstrukut so falsch?

int **pNumbers = new int* [maxlength];

Wenn ich hier nur ein dynamisches int Array verwende dann sortier ich bei 32-Bit und bei 64-Bit nur 4Byte Integer, da sollte sich kein Laufzeitunterschied ergeben.

Ich brauch ja auch Zeiger in meinem Array damit mehr Speicherplatz bei 64-Bit belegt wird(+ 4 Byte für jeden Pointer). Somit sollte sich durch die größere Datenmenge alleine schon ein Laufzeitunterschied feststellen.

Die Frage wie sinnvoll dieses Beispiel ist sei mal dahingestellt!

Warum geht ihr davon aus das mein Programm von Cache Misses überflutet wird?

[SeppJ]

mulek schrieb:

Die Frage wie sinnvoll dieses Beispiel ist sei mal dahingestellt!

Du kannst auch beim 64-Bit sortieren immer ein sleep nach jedem Schritt einbauen. Wäre genauso sinnvoll.

Sortieren ist auf 64-Bit Systemen nunmal im Realfall schneller (weil mehr Register usw.) und nicht langsamer (weil Pointer beim Sortieren keine Rolle spielen).

Warum geht ihr davon aus das mein Programm von Cache Misses überflutet wird?

Nehmen wir mal an, dein Cache wäre 6 * 32-Bit groß und du willst 3 integer Werte sortieren. Jetzt hast du ungefähr folgendes Speicherlayout:

|P1|P2|P3|....||*P1|...|*P2|...|*P3|

Jetzt sortierst du. du greifst auf P1 zu. Der Speichercontroller denkt sich: Oh, der Typ greift auf P1 zu, der braucht bestimmt auch bald die nächsten Werte, ich hole schonmal P2 und P3 in den Cache. Dann hast du im Cache stehen:

|P1|P2|P3||  |  |  |

Dann dereferenzierst du meinetwegen P1. Der Speichercontroller denkt sich: Oh, der Typ greift auf *P1 zu, der braucht bestimmt auch bald die nächsten Werte, ich hole die schonmal. Dann hast du im Cache stehen:

|P1|P2|P3||*P1|*(P1+1)|*(P1+2)|

Tja, aber dann greifst du als nächstes auf *P2 zu. Das steht nicht im Cache. Speichercontroller denkte sich: Oh, Mist, Cachemiss. Aber dieses Mal wil er bestimmt auf die auf *P2 folgenden Elemente zugreifen. Ich hole die schonmal. Dann hast du im Cache stehen:

|P1|P2|P3||*P2|*(P2+1)|*(P2+2)|

Und so weiter. Wie du siehst, auch bei 32-Bit massenhaft Cache-Misses.

[knivil]

damit mehr Speicherplatz bei 64-Bit belegt wird

Dann nimm doch einfach einen groesseren Datentyp, sizeof(long) == 8 bei meinem 64 Bit System.

[mulek]

ok demnach wäre ein ganz normales dynamisches integerr Array besser, weil dadurch weniger Cache Misses auftreten?

int *pNumbers = new int [maxlength];

[/cpp]

Sortieren ist auf 64-Bit Systemen nunmal im Realfall schneller (weil mehr Register usw.) und nicht langsamer (weil Pointer beim Sortieren keine Rolle spielen).

So wie ich das verstehe nützen die Register dann wohl auch nichts bei maßenhaft Cache - Misses, da ja die Register dann auch ständig neu geladen werden müssen, ohne das jemals ein Datum öfters von den Registern gelesen wurde.

[SeppJ]

mulek schrieb:

So wie ich das verstehe nützen die Register dann wohl auch nichts bei maßenhaft Cache - Misses, da ja die Register dann auch ständig neu geladen werden müssen, ohne das jemals ein Datum öfters von den Registern gelesen wurde.

Bei dir nicht. Aber das was du machst, hat auch wenig mit Sortieren zu tun.

[mulek]

ok, kannst du mir dann ein Sortierbeispiel zeigen bei dem man von den Registererweiterung profiert?

Was sind sonst so typische Anwendungen bei den 64-Bit schneller ist?

[SeppJ]

mulek schrieb:

ok, kannst du mir dann ein Sortierbeispiel zeigen bei dem man von den Registererweiterung profiert?

Normales Sortieren? Ohne diesen Pointerquatsch den du da machst? Erwarte aber nicht viel, der Unterschied dürfte kaum messbar sein.

Was sind sonst so typische Anwendungen bei den 64-Bit schneller ist?

Wo immer mit großen Zahlen gerechnet wird, ist 64-Bit erheblich schneller. Wo nur mit kleinen Zahlen gerechnet wird, kann 64 Bit etwas langsamer sein, daprinzipiell etwas mehr Aufwand, ohne konkreten Nutzen.

[mulek]

Wenn ich also einen vector<int> sortiere sollte also 64-Bit ein wenig schneller sein wegen der zusätzlichen Regiser bei 64-Bit? Hängt dann aber auch von Vectorlänge ab?

Ist eine Matrixmultiplikation eines 2dimensionalen Arrays mit int Werten eine geeignetes Beispiel um Laufzeitunterschiede zwischen 32-Bit und 64-Bit zu zeigen?

Sonst vl noch Ideen zu konkreteren Beispielen?

lg

[SeppJ]

mulek schrieb:

Wenn ich also einen vector<int> sortiere sollte also 64-Bit ein wenig schneller sein wegen der zusätzlichen Regiser bei 64-Bit? Hängt dann aber auch von Vectorlänge ab?

Nicht unbedingt. Wenn dein Sortieralgortihmus ohnehin nicht alle Register ausreizen sollte, gewinnt man auch nichts.

Ist eine Matrixmultiplikation eines 2dimensionalen Arrays mit int Werten eine geeignetes Beispiel um Laufzeitunterschiede zwischen 32-Bit und 64-Bit zu zeigen?

Wie wäre es mit verschiedenen Arten von Anwendungen? Du wirst feststellen, dass es bei vielen Anwendungen (fast) keinen Unterschied macht, auf welcher Architektur du rechnest.

Wenn du etwas suchst, wo man einen großen Unterschied sieht, multipliziere mal zwei 64-Bit Zahlen. Auf der 64-Bit Architektur ist das 1 Schritt, auf der 32-Bit Architektur mindestens 4. Ein realistisches Beispiel dafür ist Software die auf großen Datensätzen arbeitet, beispielsweise Verschlüsselungsprogramme und Grafikbearbeitung.

Wenn du etwas suchst, wo 32-Bit deutlich überlegen ist, musst du etwas nehmen, wo die Größe eines Pointers geschwindigkeitsrelevant ist. Mir fällt spontan kein realistisches Beispiel für eine solche Software ein.

Aber viele Programme die nicht von den Vorteilen von 64-Bit Systemen profitieren, sind etwas langsamer als wenn man sie im 32-Bit Modus betreibt. Das liegt daran, weil die Executables etwas größer sind und die Pointer etwas größer sind.

[mulek]

Ok danke mal soweit für die Infos.

Werd mal ein paar double Werte multiplizieren und Zeit messen.

[SeppJ]

mulek schrieb:

Ok danke mal soweit für die Infos.

Werd mal ein paar double Werte multiplizieren und Zeit messen.

doubles sind keine ints. Du wirst feststellen, dass bei doubles kein Unterschied besteht.

[mulek]

Wenn du etwas suchst, wo man einen großen Unterschied sieht, multipliziere mal zwei 64-Bit Zahlen. Auf der 64-Bit Architektur ist das 1 Schritt, auf der 32-Bit Architektur mindestens 4

double sind 8 Byte
integer bei mir unter 64-Bit nur 4 Byte
was soll ich dann bitte nehmen?

[SideWinder]

Wurde im Thread schon erwähnt -> long.

MfG SideWinder

[mulek]

So hab die Matrixmultiplikation mit verschiedenen Typen getestet unter anderem auch mit double.

int main(){

	double time = 0.0;
	double SumUpTime = 0.0;

	long test = 0;

	int const NumberOfMatrix = 1;

	double **matrixA;
	matrixA = new double* [size]; 

	double **matrixB;
	matrixB = new double* [size]; 

	double **matrixC;
	matrixC = new double* [size]; 

	for (int i=0;i<size; i++){
		matrixA[i] = new double[size]; 
		matrixB[i] = new double[size]; 
		matrixC[i] = new double[size]; 
	}

	for(int i=0;i<NumberOfMatrix;i++){
		RandomMatrix(matrixA);
		RandomMatrix(matrixB);
		RandomMatrix(matrixC);

		//Output(matrixA);
		//Output(matrixB);
		//Output(matrixC);

		time = 0.0;
		stw::Start();
		Multiplication(matrixA,matrixB,matrixC);
		//Multiplication_Loop_Blocking(matrixA,matrixB,matrixC);

		time = stw::Stop();

		SumUpTime = SumUpTime + time;
	}

		cout << "Die Matrixmultiplikation benötigt " << SumUpTime/NumberOfMatrix << " Sekunden!!" << endl;

	getchar();

	//Speicher freigeben
	for (int i=0;i<size; i++){
		delete matrixA[i]; matrixA[i]=0;
		delete matrixB[i]; matrixB[i]=0;
		delete matrixC[i]; matrixC[i]=0;
	}

	delete matrixA[size];
	delete matrixB[size];
	delete matrixC[size];

	return 0;
}

hab 1000x1000 - 4000x4000 gemessen,

Bei meinen Messungen stell ich fest das die Matrixmultiplikation ca. 4 % schneller ist bei 64-Bit, warum ist das so?

Hab dann auch in Erfahrung gebracht das ich mit LoopBlocking meine Multiplikation hinsichtlich des Caches optimieren kann. Nach dieser Optimierung ist 64-Bit ca. 45% schneller als 32-Bit. Nach der Optimerung werden die Register usw. ja viel besser genutzt. Aber warum ist bei der unoptimierten version64-Bit um ca. 4 % schneller, dass kann ich mir noch nicht erklären.

[Shade Of Mine]

mulek schrieb:

Bei meinen Messungen stell ich fest das die Matrixmultiplikation ca. 4 % schneller ist bei 64-Bit, warum ist das so?

Ohne den ganzen Code zu kennen schwer zu sagen, aber Prinzipiell ist 64bit code schneller als 32bit code. 4% fühlt sich da eigentlich ok an.

schau dir halt die assembler ausgabe an...

[mulek]

bin mit assembler ja nicht wirklich vertraut.
aber was mir im assembler code bei der 64-Bit Version gleich aufgefallen ist das hier die 128-Bit breiten xmm register verwendet werden.

bei 32-Bit kommen die ja irgendwie gar nicht zum einsatz, was irgendwie komisch ist weil für 32-Bit ja auch eine gewisse Anzahl an xmm Register zur verfügung steht?

Aber das erklärt mir ja trotzdem nicht die 4% Leistungssteigerung bei der unoptimierten version, da ich doch bei solch einer riesige datenmenge eine menge an cache - misses generiere?