memcpy - Schneller als der Optimizer

314159265358979

Viel interessanter finde ich ja, dass bei Athar meine Version in 2/3 Kategorien gegen Intel gewinnt und in der dritten gleichauf liegt. Hätte ich mir nicht erwartet.

SeppJ

314159265358979 schrieb:

Viel interessanter finde ich ja, dass bei Athar meine Version in 2/3 Kategorien gegen Intel gewinnt und in der dritten gleichauf liegt. Hätte ich mir nicht erwartet.

Also Unterschiede im Prozentbereich würde ich noch auf zufällige Schwankungen zurückführen, bevor ich nicht sehr viele Messungen gemacht hätte. Für mich sehen die Werte alle identisch aus und ich wette es steckt jeweils der gleiche Maschinencode dahinter (außer eventuell für die kleinen Blöcke könnte es 2 Varianten geben, die eingebaute und cookys vs. deine und Intels.) .

314159265358979

Auch möglich - dennoch bin ich stolz, mit Intel gleichauf zu liegen.

cooky451

Visual Studio vielleicht noch interessant:

cooky's Rechenkiste schrieb:

Eingebautes memcpy:
Kleine Bloecke: 896 ms
Mittlere Bloecke: 142 ms
Gro▀e Bloecke: 39 ms
Anti-Super-cleverer-Compiler-Optimierungprⁿfsumme: 630733888
Cooky451s memcpy:
Kleine Bloecke: 885 ms
Mittlere Bloecke: 171 ms
Gro▀e Bloecke: 84 ms
Anti-Super-cleverer-Compiler-Optimierungprⁿfsumme: 630733888
314159265358979s memcpy:
Kleine Bloecke: 1221 ms
Mittlere Bloecke: 448 ms
Gro▀e Bloecke: 335 ms
Anti-Super-cleverer-Compiler-Optimierungprⁿfsumme: 630733888
Intels memcpy:
Kleine Bloecke: 1184 ms
Mittlere Bloecke: 445 ms
Gro▀e Bloecke: 335 ms
Anti-Super-cleverer-Compiler-Optimierungprⁿfsumme: 630733888

Scheint einerseits besser, andererseits schlechter zu optimieren.

314159265358979

*Nach SSE Extensions google und besseres memcpy schreib*

Zumindest für größere Blöcke dürfte es dir schwerfallen, das System-memcpy zu übertreffen. Für kleine bis mittlere Blöcke wird das ungefähr das gleiche wie cookys Variante machen (wichtige Ausnahme: Alignment!), aber sobald du mehr als ein paar Kilobyte hin- und herschieben willst, wird das System-memcpy ganze Pages auf einmal umhängen. Den entsprechenden Mechanismus müsstest du für deine Plattform erst mal aufstöbern.

314159265358979

Da fällt mir auf: Ihr habt ja gar nicht mein memcpy mit inline-asm genommen, sondern das C++. Langweilig!

cooky451

314159265358979 schrieb:

Da fällt mir auf: Ihr habt ja gar nicht mein memcpy mit inline-asm genommen, sondern das C++. Langweilig!

War doch deine Frage:

314159265358979 schrieb:

Ich will wissen: Warum ist mein Code so flott, und wieso erzeugt der Optimizer so suboptimalen Code?

Anwort:
Dein Code ist so flott weil Compilerhersteller nun mal auch nur mit Wasser kochen und dein C++ ist so langsam, weil du es besagtem Wasser nicht gerade leicht machst.

Athar

SeppJ schrieb:

Und die gewaltige Performancesteigerung bei großen Blöcken (hast du die gleichen Werte für Blockgröße und Iteration wie ich genommen?), es werden ja jedes mal 100MB hin und her geschoben. Wie macht der das? Haben AMD-Chips irgendwelche tollen eingebauten Kopieranweisungen? Oder hat der neue GCC (meins war eine Version 4.4) einen neuen Überoptimierer?

Außer der Ausgabe und __restrict habe ich nichts angefasst.
Und es scheint tatsächlich an Verbesserungen in GCC 4.5 zu liegen, denn ich habe gerade g++ 4.4 installiert und bekomme damit ähnliche Werte wie du.
Diese drei Punkte im Changelog von GCC 4.5 könnten damt zu tun haben:

• The automatic parallelization pass was enhanced to support parallelization of outer loops.
• Automatic parallelization can be enabled as part of Graphite. In addition to -ftree-parallelize-loops=, specify -floop-parallelize-all to enable the Graphite-based optimization.
• The infrastructure for optimizing based on restrict qualified pointers has been rewritten and should result in code generation improvements. Optimizations based on restrict qualified pointers are now also available when using -fno-strict-aliasing.

314159265358979 schrieb:

Da fällt mir auf: Ihr habt ja gar nicht mein memcpy mit inline-asm genommen, sondern das C++. Langweilig!

Na gut, habe deine Variante für 64-bit angepasst:

movq	%rdi, %rax
movq	%rdx, %rcx
shrq	$3, %rcx
rep movsq
movq	%rdx, %rcx
andq	$7, %rcx
rep movsb
ret

`Cooky451s memcpy:

Kleine Blöcke: 3340 ms

Mittlere Blöcke: 515 ms

Große Blöcke: 145 ms

Anti-Super-cleverer-Compiler-Optimierungprüfsumme: 2096334824

314159265358979s assembler memcpy:

Kleine Blöcke: 3310 ms

Mittlere Blöcke: 519 ms

Große Blöcke: 144 ms

Anti-Super-cleverer-Compiler-Optimierungprüfsumme: 2096334824`

Auch hier die gleiche Performanz. Allerdings sind diese 8 Instruktionen deutlich kürzer, als was g++ üblicherweise so bei -O3 generiert (z.B. 62 Instruktionen für Cooky's Variante).

hustbaer

314159265358979 schrieb:

Woher soll ich als bekiffter denn wissen, wie ein normaler Mensch eine Schleifenbedingung schreiben würde? (Übrigens war diese Schleifenbedingung nicht absichtlich so gewählt, mir ist auf die Schnelle nichts besseres eingefallen.)

Wie wär's mit while (n--) ... ?
Oder alternativ for (size_t i = 0; i < n; i++) ...
Oder auch char* dEnd = d + n; while (d != dEnd) ...

314159265358979

Okay, auf #1 hätte ich kommen können. Die anderen beiden sind viel zu umständlich.

Ethon

Hier mal die libc Implementierung:

void *
memcpy (dstpp, srcpp, len)
     void *dstpp;
     const void *srcpp;
     size_t len;
{
  unsigned long int dstp = (long int) dstpp;
  unsigned long int srcp = (long int) srcpp;

  /* Copy from the beginning to the end.  */

  /* If there not too few bytes to copy, use word copy.  */
  if (len >= OP_T_THRES)
    {
      /* Copy just a few bytes to make DSTP aligned.  */
      len -= (-dstp) % OPSIZ;
      BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);

      /* Copy whole pages from SRCP to DSTP by virtual address manipulation,
	 as much as possible.  */

      PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);

      /* Copy from SRCP to DSTP taking advantage of the known alignment of
	 DSTP.  Number of bytes remaining is put in the third argument,
	 i.e. in LEN.  This number may vary from machine to machine.  */

      WORD_COPY_FWD (dstp, srcp, len, len);

      /* Fall out and copy the tail.  */
    }

  /* There are just a few bytes to copy.  Use byte memory operations.  */
  BYTE_COPY_FWD (dstp, srcp, len);

  return dstpp;
}
libc_hidden_builtin_def (memcpy)

Also:

1. Bytes einzeln schreiben bis Alignment korrekt.
2. Ganze Pages kopieren, falls möglich.
3. Großtmögliche Kopieroperationen anwenden, wohl SSE oä.

abc.w

Übrigens, im Assembler Forum gab es neulich eine ähnlich Diskussion über memcpy & Co: http://www.c-plusplus.net/forum/289488-full

abc.w

Ethon schrieb:

unsigned long int dstp = (long int) dstpp;
    unsigned long int srcp = (long int) srcpp;
    ...

Toll, "unsigned" Variablen, "signed" Cast
Die GNU libc übrigens enthält auch Assembler-Varianten für i486, i586, SSE...

SeppJ

abc.w schrieb:

Übrigens, im Assembler Forum gab es neulich eine ähnlich Diskussion über memcpy & Co: http://www.c-plusplus.net/forum/289488-full

For a very fast general purpose memory copy routine, call the libc memcpy() function included
with the Microsoft or gcc tools. This function features optimizations for all block sizes and
alignments.