4. memcpy und compare mit SSE

memcpy und compare mit SSE

  • F

    Hallo,

    da ich eine schnellstmögliche Vergleichsfunktion, sowie eine MemCpy-Prozedur brauche, wollte ich ein paar Tests mit Hilfe von SSE-Befehlen starten, da das SIMD-Prinzip dafür ja sehr viel versprechend klingt.

    Da mir zugegebenermaßen noch nicht ganz klar ist, wie ich bei all den Vergleichsfunktionen das Ergebnis prüfe (Flags werden ja nicht gesetzt und alles was ich gelesen habe, war mir zu schleierhaft), habe ich mich erst mal auf die Internet-Recherche zur MemCpy-Funktion begeben, um einen Eindruck davon zu erhalten, was es da schon gibt.

    Ichc bin u.a. auf diesen Code gestoßen:

    void X_aligned_memcpy_sse2(void* dest, const void* src, const unsigned long size_t)
{

  __asm
  {
    mov esi, src;    //src pointer
    mov edi, dest;   //dest pointer

    mov ebx, size_t; //ebx is our counter 
    shr ebx, 7;      //divide by 128 (8 * 128bit registers)

    loop_copy:
      prefetchnta 128[ESI]; //SSE2 prefetch
      prefetchnta 160[ESI];
      prefetchnta 192[ESI];
      prefetchnta 224[ESI];

      movdqa xmm0, 0[ESI]; //move data from src to registers
      movdqa xmm1, 16[ESI];
      movdqa xmm2, 32[ESI];
      movdqa xmm3, 48[ESI];
      movdqa xmm4, 64[ESI];
      movdqa xmm5, 80[ESI];
      movdqa xmm6, 96[ESI];
      movdqa xmm7, 112[ESI];

      movntdq 0[EDI], xmm0; //move data from registers to dest
      movntdq 16[EDI], xmm1;
      movntdq 32[EDI], xmm2;
      movntdq 48[EDI], xmm3;
      movntdq 64[EDI], xmm4;
      movntdq 80[EDI], xmm5;
      movntdq 96[EDI], xmm6;
      movntdq 112[EDI], xmm7;

      add esi, 128;
      add edi, 128;
      dec ebx;

      jnz loop_copy; //loop please
    loop_copy_end:
  }
}

    Wenn ich das korrekt sehe, müsste Src hier 128 Byte(!) aligned sein, damit sich der Aufruf lohnen würde. In anderen Fällen kann es aus meiner Sicht sogar zu Zugriffsverletzungen kommen, weshalb ich die Funktion nicht wirklich gut finde.

    Ich habe mal ein kleines Test-Szenario aufgebaut:

    int main()
{
	void *src  = _aligned_malloc(200, 0),
		 *dest = _aligned_malloc(200, 0); 
	DWORD dwStart = GetTickCount();

	for( unsigned i = 0; i < (1 << 31); i++ ) {
		// memcpy(dest, src, 200);
		// aligned_memcpy(src, dest, 200);
		// X_aligned_memcpy_sse2(dest, src, 200);
	}
	cout << "Benoetigte Zeit:\t" << (GetTickCount() - dwStart) / 1000 << endl;

	_aligned_free(src);
	_aligned_free(dest);
}

    Meine Resultate waren:

    memcpy: 61 Sekunden
X_aligned_memcpy_sse2: 296 Sekunden
aligned_memcpy: 294 Sekunden

    aligned_memcpy ist eine eigen Implementation von mir; mit wenig Erfolg wie man sieht.

    void aligned_memcpy(
	void*  src,
	void*  dest,
	size_t count
)
{
__asm {
[asm]	mov  esi, src
	mov  edi, dest
	mov  ecx, count
	mov  edx, count

	shr	 ecx, 4				// divide by 16 (Byte = 128 Bit)
	jnz	 SHORT begin_128
end_128:

	mov  ecx, edx
	shr  ecx, 3				// divide by 8 (Byte = 64 Bit)
	jnz  SHORT begin_64
end_64:

	mov  ecx, edx
	shr  ecx, 2				// divide by 4 (Byte = 32 Bit)
	jnz  SHORT begin_32
end_32:

	mov  ecx, edx
	and  ecx, 3				// prepare byte copy
	jnz  SHORT begin_byte

	jmp  SHORT done

begin_128:
	prefetchnta	[esi+16]
	movdqa	xmm0, [esi]
	movntdq [edi], xmm0

	add  esi, 16
	add  edi, 16
	sub  edx, 16
	dec	 ecx
	jnz  SHORT begin_128
	jmp  SHORT end_128

begin_64:
	prefetchnta [esi+8]
	movq   mm0, [esi]
	movntq [edi], mm0

	add  esi, 8
	add  edi, 8
	sub  edx, 8
	dec  ecx
	jnz  SHORT begin_64
	jmp  SHORT end_64

begin_32:
	repnz movsd
	jmp  SHORT end_32

begin_byte:
	repnz movsb

done:
	//ret
[/asm]}
}

    Soll das heißen, dass SSE für eine Kopierfunktion einfach nicht geeignet ist oder mache ich hier einfach grundsätzlich was falsch?

    0
  • T

    Ich habe das gerade mal bei mir (Core 2 Duo E8500) ausprobiert und das was die Funktionen langsam macht ist das movntdq. Nimmt man stattdessen auch movdqa hat man so ziemlich genau die Geschwindigkeit des normalen memcpy. Allerdings kann man sich so den Cache zumüllen. Das kommt in dem Testprogramm aber nicht rüber.

    www.agner.org/optimize/asmlib.zip enthält auch eine Implementierung für memcpy mit SSE und eine PDF die ein paar Details und Performancetests dazu gibt. Demnach lohnt sich das ganze nur wenn die Quelle und Ziel nicht aligned sind.

    0
  • F

    Tobiking2 schrieb:

    Ich habe das gerade mal bei mir (Core 2 Duo E8500) ausprobiert und das was die Funktionen langsam macht ist das movntdq. Nimmt man stattdessen auch movdqa hat man so ziemlich genau die Geschwindigkeit des normalen memcpy. Allerdings kann man sich so den Cache zumüllen. Das kommt in dem Testprogramm aber nicht rüber.

    Hi,
    genau das habe ich im Laufe des Vormittags auch herausgefunden. Tatsächlich erreicht man (fast) exakt die selben Zeiten, wenn man das "prefetchnta" und das "movntdq" herausnimmt, wie das normale memcpy.

    Mit dem oben gezeigten Code ist es ca. 3-4x langsamer. Irgendwie fehlt mir da noch das Verständnis führ. Ich ging zu Beginn eigentlich davon aus, dass gerade das Prefetching (macht zu gegeben auch nur den Bruchteil der Verzögerung aus) und vorallem das movntdq am Cache vorbei, richtig schnell sein müsste.
    Da jede Speicherstelle nur ein mal angepackt wird, brauche ich die Daten nämlich nicht im Cache.
    Man sollte doch meinen, dass das zusätzliche verarbeiten im Cache (inkl. Verdrängung) mehr Zeit in Anspruch nehmen müsste.

    Dass das Ganze unaligned schneller sein soll, kann ich mir fast nicht vorstellen. Müsste doch umgekehrt sein.
    Alles in allem ziemlich enttäuschendes Resultat. Allerdings benutzt auch das standard memcpy die Funktion _VEC_memcpy, insofern mehr als 255 Byte kopiert werden. Sollte auch die ungefähr gleichen Zeiten erklären.

    0
  • R

    http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/22007.pdf

    da gibt es ne schnelle mecpy implementierung.
    von amd gab es mal ein paper zur memcpy optimierung, angefangen beim simplen c for-loop bis zu der version da im paper, leider finde ich das optimierungspaper gerade nicht.

    0
  • C
    Mod

    Die Prefetchdistanz dürfte viel zu klein sein, um nützlich zu sein. Innerhalb der der gleichen Speicherseite greift einerseits normalerweise ohnehin Hardware-Prefetching ein, andererseits ist anderfalls die Latenz des Hauptspeichers wahrscheinlich zu groß, um die Daten noch rechtzeitig lesen zu können.

    0
  • F

    camper schrieb:

    Die Prefetchdistanz dürfte viel zu klein sein, um nützlich zu sein. Innerhalb der der gleichen Speicherseite greift einerseits normalerweise ohnehin Hardware-Prefetching ein, andererseits ist anderfalls die Latenz des Hauptspeichers wahrscheinlich zu groß, um die Daten noch rechtzeitig lesen zu können.

    Ja, das stimmt. Zudem bekomme ich bei meiner Zeitmessung natürlich auch nicht unbedingt die Zeit mit, in der die Daten wirklich in den Arbeitsspeicher geschrieben werden.
    Das Schreiben in den Cache ist natürlich schneller.

    Ich weiß nicht wie eure Erfahrungen sind. Aber sowohl auf einem Core 2 Duo, als auch Core 2 Quad, ist die Benutzung der XMM-Register u. 128 Bit Operationen deutlich langsamer, als wenn man die MMX-Register benutzt und 64 bitweise kopiert.

    EDIT:
    Ich kann erst morgen die Performance auf einem AMD-Rechner testen, jedoch ist die selbige auf meinen Core 2 Quad, Core i7 und Core 2 Duo Rechern die schlechteste von allen getesteten Verfahren, bei Speicherblöcken zwischen 16 u. 256 Byte, aligned und unaligned.

    0
  • L

    FrEEzE2046 schrieb:

    Mit dem oben gezeigten Code ist es ca. 3-4x langsamer. Irgendwie fehlt mir da noch das Verständnis führ. Ich ging zu Beginn eigentlich davon aus, dass gerade das Prefetching (macht zu gegeben auch nur den Bruchteil der Verzögerung aus) und vorallem das movntdq am Cache vorbei, richtig schnell sein müsste.
    Da jede Speicherstelle nur ein mal angepackt wird, brauche ich die Daten nämlich nicht im Cache.
    Man sollte doch meinen, dass das zusätzliche verarbeiten im Cache (inkl. Verdrängung) mehr Zeit in Anspruch nehmen müsste.

    Der Cache ist kein Overhead. Der Sinn vom Kopieren am Cache vorbei ist wie bereits gesagt, keine Daten aus dem Cache zu verdrängen. Deswegen wäre ein besserer Benchmark einer, der abwechselnd kopiert und komplexe Operationen auf Daten im Cache ausführt (komplexer als memcpy und so).

    0
  • K

    Solche Untersuchungen haben schon andere vorher gemacht: A survey about state of the art C compiler optimization tricks.

    Ich weiß nicht wie eure Erfahrungen sind.

    Der Compiler kann es (meist) besser!

    Deswegen wäre ein besserer Benchmark einer, der ...

    Nein, einfach den erzeugten Assemblercode fuer die Plattform betrachten und Takte gemaess den Instruktionen zaehlen. Man will ja nicht die Cacheperformance testen, sonder die Optimierungsmoeglichkeiten von Compilern.

    0
  • S

    knivil schrieb:

    Nein, einfach den erzeugten Assemblercode fuer die Plattform betrachten und Takte gemaess den Instruktionen zaehlen. Man will ja nicht die Cacheperformance testen, sonder die Optimierungsmoeglichkeiten von Compilern.

    Oh, wenn das so ist, muss ich was überlesen haben ...

    0
  • N

    Ich hab zu diesem Thema kürzlich auch Messungen auf meinem Rechner durchgeführt, unter der Nutzung von _mm_stream_si128.
    Habe das Test-Programm "CacheAndMemory" von AMD angepaßt.

    http://forum.ultimatespaceproject.de/medien/screenshots/EventPerf2k10.png

    0
  • F

    Grundsätzlich hängt es nach meinen Messungen stark vom verwendeten Prozessor ab. Man sollte also für ein optimales Ergebnis mehrere Funktionen für jeden Fall zur Verfügung haben.
    Das ganze kann ja über eine JumpTable ganz zu beginn (evtl. beim Laden einer DLL) als Initialisierung überprüft werden.

    Ganz nebenbei ist momentan movdq halt noch sehr langsam. DAher sollte man auch unter Verwendung der XMM Register weiterhin movq benutzen. Mal schauen wie's bei AVX aussieht.

    0
Anmelden zum Antworten