Sortieralgorithmen unter 64-Bit

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?