C++ Laufzeitunterschied Char/Int

[Legenbaer]

Hallo,

ich bin gerade dabei, ein wenig auszutesten wie ich den "Euklidischen Abstand" (ohne Wurzel) schnell errechnen kann. Die Verktoren liegen als Char und Int-Arrays vor. Ich habe zwei Funktionen:

inline float L2NORMALI(int* vec1, int* vec2){
	int	dist  = 0;

	//L2
	for(int i=0; i<128; i++){
		dist += (vec1[i] - vec2[i]) * (vec1[i] - vec2[i]); 
	}
	
	return dist;
}

und

inline float L2NORMAL(unsigned char* vec1, unsigned char* vec2){
	int	dist  = 0;

	//L2
	for(int i=0; i<128; i++){
		dist += ((int)vec1[i] - (int)vec2[i]) * ((int)vec1[i] - (int)vec2[i]); 
	}
	
	return dist;
}

Was für mich seltsam ist, dass die zweite Version trotz des castens schneller ist als die erste. Auf meine X2 2,4GhZ sieht das so aus:

Version 1: 157 ms.
Version 2: 94 ms.

Kann mir jemand sagen warum das so ist?

Besten Gruß & Dank

Legenbaer

 

[Dese]

also das casten im c-style hat normalerweise keine performance nachteile. aber warum der zweite code schneller ist, ist auch für mich merkwürdig.

interessant wäre hier zu wissen, wie du compilierst, d.h. mit welchen einstellungen.

wie rufst du eigentlich diese funktion auf? also L2NORMA, wie ist sie eingebettet. das wäre bei einer inline funktion mal interessant.

EDIT: teste das doch mal ohne inline. ich vermute, dass hier unterschiedliche optimierungen zum tragen kommen.

 

[LvlLord]

ich würde sagen es hängt ganz einfach am variablentyp.
unsigned char ist 8 bit
int ist 32/64 bit (je nach System)

Rechnen dürfte wohl bei 8bit-Zahlen immernoch schneller sein.

 

[Dese]

@LvLLord: verzeih, aber das ist quatsch, denn
1. ist die rechenoperation bei 8bit und 16bit und 32bit exakt gleich schnell, da es ein einheitlicher taktgebundener befehl ist
2. hier auch keine 8-bit rechenoperation ausgeführt wird, sondern 32bit, da er ja die variablen auf int castet BEVOR er rechnen läßt.

 

[Legenbaer]

Offensichtlich liegts wirklich an den Compileroptimierungen. Die genannten Werte sind mit /Ox entstanden. Deaktiviere ich die Optimierungen betragen die Laufzeiten 469 und 640 ms. Wobei hier die L2NORMAL die langsamere Funktion ist. Inline bietet in meinem Fall garkeine Vorteile wie ich merkte. Das ganze wird auch aus einer Schleife heraus aufgerufen:

	//NORMAL INT
	start = GetTickCount();
	for(int v=0; v<descs; v++){
		value = L2NORMALI(&_int1[v*128], &_int2[v*128]);
	}
	ende  = GetTickCount();

	cout << "L2Normali: " << ende - start << " ms. V:" << value << endl;
	
	
	//NORMAL
	start = GetTickCount();
	for(int v=0; v<descs; v++){
		value = L2NORMAL(&_char1[v*128], &_char2[v*128]);
	}
	ende  = GetTickCount();

	cout << "L2Normal : " << ende - start << " ms. V:" << value << endl;

 

[Dese]

ok, ich hab da nen verdacht. das was vermutlich den LZ unterschied ausmacht ist nicht deine funktion, sondern die adressierung der parameter:

einmal machst du:
&_int1[v*128], &_int2[v*128]

und bei der anderen funktion:
&_char1[v*128], &_char2[v*128]

und jeh nach compileroptimierungen kann der zugriff auf den speicher beim zweiten schneller ausfallen, wenn die daten besser zu cashen sind.

aber warte mal, ihc schau grad mal was nach, um genaueres sagen zu können.

edit: welcher compiler eigentlich? ^^

 

[Legenbaer]

Hmm...kann mir gerade nicht erklären warum das einen Unterschied machen sollte. oO
Ich arbeite mit MS VC 2008 und dem dazugehörigen Compiler.

Schonmal danke für die Antworten!

 

[Dese]

also, wie groß ist etwa "descs"?

der unterschied rührt vermutlich daher, dass die daten als char in einem 4 mal kleineren datenbereich reinpassen als als int. du sprichst sie ja der reihe nach an. das kann der compiler erkennen. aber unabhängig davon, der datenbeteich wird gecached. nur passen bei deiner char variante 4 mal mehr daten in den cache. das macht sehr wohl einen unterschied.

das ohne optimierungen die zweite funktion etwas langsamer war, liegt wohl daran, dass ganz ohne optimierungen das casten und die zugriffe wirklich grottig gemacht werden, mit diversen sicherheitschecks.

also ihc vermute es liegt einfach daran, dass du mehr daten gleichzeitig cachen kannst, als in der int-variante. überprüfen könntest du das, indem du statt bei den funktionsaufrufen:
value = L2NORMALI(&_int1[v*128], &_int2[v*128]);

es so machst:

value = L2NORMALI(&_int1[1*128], &_int2[1*128]);

d.h. du nimmst immer die gleichen werte. und innerhalb der funktionen selbst solltest du auch die laufvariable ignorieren und immer dieselben werte verrechnen. dann ist der cache egal, aber immer noch dieselbe menge an operationen.

heir sollte dann beide funktionen etwa gleichschnell sein.

 

[Legenbaer]

Also die Arrays besitzen 600000*128 Einträge.
Wenn ich immer den gleichen Bereich übegebe und auch innerhalb der Funktionsschleife immer den gleichen Wert multipliziere ist durch die Optimierung die Laufzeit bei 0ms da der Compiler sich die Schleife wohl spart und gleich Wert*128 zurück gibt.
Ohne Optimierungen ist die Variante ohne Casten aber auch wieder schneller.

Hier mal die Main des Programms, dann kannst du es auch testen wenn du möchstest:

	int				descs   = 400000; 
	unsigned char*	_char1  = new unsigned char[descs*128];
	unsigned char*	_char2  = new unsigned char[descs*128];
	int*			_int1 = new int[descs * 128];
	int*			_int2 = new int[descs * 128];
	int				start, ende;

	unsigned char tmp;
	for(int i=0; i<descs*128; i++){
		tmp = rand() % 128;
		_char1 [i]	= tmp;
		_int1[i]	= tmp;
		tmp = rand() % 128;
		_char2[i]	= tmp;
		_int2[i]	= tmp;
	}

	float value;

	//NORMAL INT
	start = GetTickCount();
	for(int v=0; v<descs; v++){
		value = L2NORMALI(&_int1[1*128], &_int2[1*128]);
	}
	ende  = GetTickCount();

	cout << "L2Normali: " << ende - start << " ms. V:" << value << endl;
	
	
	//NORMAL
	start = GetTickCount();
	for(int v=0; v<descs; v++){
		value = L2NORMAL(&_char1[1*128], &_char2[1*128]);
	}
	ende  = GetTickCount();

	cout << "L2Normal : " << ende - start << " ms. V:" << value << endl;

 

[Dese]

dann mach mal statt 1*128 sowas wie x*128 und setz die variable x irgendwo vorher einmal auf 1. evtl optimiert er das nicht weg. du kannst acuh in der schelife x immer wieder auf 1 setzten, damit das optimieren verhidnert wird.

wichtig ist aber, dass du das auch innerhalb der funkionen machst, da ja dort die schleife 128 werte durchgeht und da cachen auch nen einfluss drauf haben kann.

ich muss jetzt leider ne weile weg. evtl meld ich mich später.

 

[Legenbaer]

Wenn nur der index innerhalb der funktionen identisch bleibt, dann sind die Funktionen auch gleich schnell. Das mit dem cashen wird wohl stimmen.

 

[bullsh1t]

ich finde es absolut einleuchtend warum hier laufzeitunterschiede festzustellen sind:

INTEGER:
die Referenzierungoperation vec1 läd 4 Byte aus dem RAM

CHAR:
die Referenzierungoperation vec1 läd 1 Byte aus dem RAM

warum sollte das laden von 4 Bytes gleich schnell sein als wenn nur ein Byte geladen werden muss?

 

[BerniG]

warum sollte das laden von 4 Bytes gleich schnell sein als wenn nur ein Byte geladen werden muss?

Man kann nicht einzelne Bits aus dem RAM lesen sondern immer nur ein ganzes "word". Bei gängigen x86-CPUs ist das meist 32Bit = 4Byte.
In dem Fall wird der Compiler eben es wohl so optimieren dass praktisch 4 Char-Werte auf einmal aus dem RAM geholt werden weshalb es tatsächlich etwas schneller ist. Ohne entsprechende Optimierungen wird aber tatsächlich bei einem Char genauso viel aus dem RAM gelesen wie bei einem Integer (der Rest wird eben "weggeworfen").

In diesem Zusammenhang auch interessant ist das Alignment (insbesondere wenn man structs verwendet): http://en.wikipedia.org/wiki/Data_structure_alignment

Im Übrigen sollte bei Benutzung von SSE die Wurzel erheblich schneller sein als die Schleife. Und dann gibts noch für 3D-Sachen (inverse Wurzel) so schöne Dinge wie http://hydra.geht.net/tino/howto/programming/algorithm/quake/

 

[Legenbaer]

Hallo BerniG,

danke dir für deine Antwort. Eine SSE implementierung habe ich auch versucht allerdings ist das casten nach FLOAT (bzw. _mm128) so langsam das die ganze Sache am Ende sogar deutlich langsamer ist. Vllt...liegts aber auch an der Implementierung.

inline float L2SSE(unsigned char* vec1, unsigned char* vec2){
	float  dist  = 0;
	float* fvec1 = (float*) _aligned_malloc(128 * sizeof(float), 16);
	float* fvec2 = (float*) _aligned_malloc(128 * sizeof(float), 16);

	__m128* _fvec1	= (__m128*) fvec1;
	__m128* _fvec2	= (__m128*) fvec2;
	
	__m128	vdist[32];
	__m128	q[32];

	
	__m128  p1[16];
	__m128  p2[8];
	__m128  p3[4];
	__m128  p4[2];
	__m128  p5;
		
	//convert
	for(int f=0; f<128; f++){
		fvec1[f] = (float)vec1[f];
		fvec2[f] = (float)vec2[f];
	}
	
	//L2
	for(int i=0; i<32; i++){
		vdist[i]	= _mm_sub_ps(_fvec1[i], _fvec2[i]);
		q[i]		= _mm_mul_ps(vdist[i] , vdist[i] );
	}

	//P1
	for(int i=0; i<16; i++){
		p1[i] = _mm_add_ps(q[i], q[i+16]);
	}

	//P2
	for(int i=0; i<8; i++){
		p2[i] = _mm_add_ps(p1[i], p1[i+8]);
	}

	//P3
	for(int i=0; i<4; i++){
		p3[i] = _mm_add_ps(p2[i], p2[i+4]);
	}

	//P4
	for(int i=0; i<2; i++){
		p4[i] = _mm_add_ps(p3[i], p3[i+2]);
	}

	//P5
	p5 = _mm_add_ps(p4[0], p4[1]);
	
	_aligned_free(fvec1);
	_aligned_free(fvec2);

	float* tmp = reinterpret_cast<float*>(&p5);

	return tmp[0] + tmp[1] + tmp[2] + tmp[3];
}

 

[Dese]

bzgl. 4byte int und 1 byte char hat ja bernig schon alles gesagt.

es ist also wie ich es mir dachte das cachen. najo, wenn's das nicht gewesen wäre, hät ich mal die jungs von algorithm enginiering nebenan gefragt.

 

[generalad]

Tach auch,

von meiner Seite erst einige Fragen vorneweg:

• Du verwendest durchgehend eine Vektorlänge von 128 bei der Berechnung. Ist das nur zu Testzwecken oder soll eine evtl. spätere Anwendung genau auf Vektoren dieser Länge arbeiten? (Falls nein, verfälscht das Hardcoding, insbesondere der Schleifenrumpf, nämlich in Verbindung mit Compileroptimierung Deine Ergebnisse)
• Hast Du getestet, ob beide Funktionen jeweils dasselbe Ergebnis liefern? (klingt blöd, ich weiß; dazu steht aber nichts - und ich habe in der Vergangenheit genau den Fehler auch schon gemacht)
• Warum willst Du den quadr. euklidischen Abstand auf ganzzahligen Vektoren berechnen?
• Warum läufst Du in Deiner Main immer wieder über die selben 128 Werte? Oo

Weiterhin kannst Du mal den folgenden Code versuchen

inline int L2NORMALI(int* vec1Start, int* vec1End, int* vec2Start, int* vec2End){
	int	dist  = 0;
	int* iter1 = vec1Start;
	int* iter2 = vec2Start;

	do {
		dist += ((*iter1) * (*iter2)) * ((*iter1) * (iter2));
		iter1++;
		iter2++;
	} while(iter1 != vec1End && iter2 != vec2End);
	
	return dist;
}

Das müsste - soweit mein langsam bröckelndes Wissen noch nicht ganz verfallen ist - deutlich schneller sein als Deine Varianten, solange man auf Vektoren variabler Länge arbeitet.

 

[Legenbaer]

Hallo General,
die Verktoren haben immer eine Länge von 128 Einträgen. Und was den Test des Ergebnisses angeht: Jo, das wurde getestet und alle geben das selbe zurück.

"Warum willst Du den quadr. euklidischen Abstand auf ganzzahligen Vektoren berechnen?" Warum nicht? Spricht etwas dagegen?

Das in der Main imer die gleichen Referenzen übergeben werden war nur ein Test. Real laufe ich über alle 600000 Einträge.

Ich habe deine Implementierung mal gegen die andere L2NORMALI gesetzt und sie ist langsamer als die ursprüngliche. 203 zu 172 ms.

Das du die Werte nicht subtrahierst sondern multiplizierst hab ich mal als Fehler gesehen und korregiert.


Hat noch jmd ne Idee zur SSE Implementierung?

 

[generalad]

Hallo General,
die Verktoren haben immer eine Länge von 128 Einträgen. Und was den Test des Ergebnisses angeht: Jo, das wurde getestet und alle geben das selbe zurück.

"Warum willst Du den quadr. euklidischen Abstand auf ganzzahligen Vektoren berechnen?" Warum nicht? Spricht etwas dagegen?

Spricht nix dagegen, war mehr aus Interesse, welche Anwendung das ganze hat. Mich hat auch irritiert, dass Du auf ganzzahligen Vektoren rechnest und einen float zurückgibst.

Das in der Main imer die gleichen Referenzen übergeben werden war nur ein Test. Real laufe ich über alle 600000 Einträge.

Ich habe deine Implementierung mal gegen die andere L2NORMALI gesetzt und sie ist langsamer als die ursprüngliche. 203 zu 172 ms.

Macht Sinn, wenn der Kopf der Schleife fix ist.

Das du die Werte nicht subtrahierst sondern multiplizierst hab ich mal als Fehler gesehen und korregiert.

Mea culpa