3. memcpy - Schneller als der Optimizer

memcpy - Schneller als der Optimizer

  • 3

    berndbernd schrieb:

    314159265358979 schrieb:

    while(d - n != dest)

    Das Berechnen der Differenz d-n scheint mir hier unnötig Performance zu verschenken.

    Ist aber Aufgabe des Optimizers das zu verbessern, nicht meine. 🙄

    0
  • E

    Versuchs mal so:

    void my_memcpy(void* dest_, void const* src_, unsigned int len)
{
  int const BEST_ALIGN = sizeof(std::size_t);

  int bytesOff = len % BEST_ALIGN;
  if(bytesOff)
  {
    char* dest = static_cast<char*>(dest_);
    char const* src = static_cast<char const*>(src_);

    for(int i = 0; i < bytesOff; ++i)
      *dest++ = *src++;

    len -= bytesOff;
  }

  std::size_t* dest = static_cast<std::size_t*>(dest_ + bytesOff);
  std::size_t const* src = static_cast<std::size_t const*>(src_ + bytesOff);
  while(len)
  {
    *dest++ = *src++;
    len -= sizeof(std::size_t);
  }
}

    Ungetestet, aber Maschienen-Wörter anstatt Bytes zu schicken sollte die Performance ziemlich pushen.

    0
  • Mod

    So hier mal ein Benchmark (leider nur POSIX):

    #include <cstring>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <sys/time.h>

using namespace std;

void* cookys_memcpy(void* s1, const void* s2, size_t n)
{
  size_t int_size = n / sizeof(int);
  size_t char_size = n % sizeof(int);
  int* is1 = (int*)s1, *is2 = (int*)s2;
  char* cs1, *cs2;
  while (int_size--)
    *is1++ = *is2++;
  cs1 = (char*)is1, cs2 = (char*)is2;
  while (char_size--)
    *cs1++ = *cs2++;
  return s1;
}

void* pis_memcpy(void* dest, const void* src, size_t n)
{
  char* d = static_cast<char*>(dest);
  const char* s = static_cast<const char*>(src);

  while(d - n != dest)
    *d++ = *s++;

  return dest;
}

void* intels_vorschlag_fuer_memcpy_auf_guten_compilern_mit_schlechter_standardbibliothek(void *restrict b, const void *restrict a, size_t n)
{
  char *s1 = static_cast<char*>(b);
  const char *s2 = static_cast<const char*>(a);
  for(; 0<n; --n)*s1++ = *s2++;
  return b;
}

const size_t size = 9999999;
const size_t small_chunk_size = 4;
const size_t medium_chunk_size = 40;
const size_t large_chunk_size = 40000;
const size_t amount = 100000000;  // 100 MB
const unsigned small_iterations = amount / small_chunk_size;
const unsigned medium_iterations = amount / medium_chunk_size;
const unsigned large_iterations = amount / large_chunk_size;

void copy_stuff(void *(*my_memcpy)(void *, const void*, size_t), size_t chunk_size, unsigned iterations, vector<int> &array)
{
  for(unsigned N = 0; N < iterations; ++N)
    {
      size_t start = rand() % (size - 2 * chunk_size);
      my_memcpy (&array[start], &array[start + chunk_size], chunk_size*sizeof(array[0]));
    }
}

void benchmark_memcpy(void *(*my_memcpy)(void *, const void*, size_t))
{
  srand(0);
  vector<int> array(size);
  for (size_t i = 0; i < size; ++i)
    array[i] = rand();

  timespec start, end;
  cout << "Kleine Blöcke: " << flush;
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
  copy_stuff(my_memcpy, small_chunk_size, small_iterations, array);
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
  long difference = (end.tv_nsec - start.tv_nsec) + (end.tv_sec - start.tv_sec) * 1000000000;
  cout << difference << " Nanoseconds\n";
  cout << "Mittlere Blöcke: " << flush;
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
  copy_stuff(my_memcpy, medium_chunk_size, medium_iterations, array);
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
  difference = (end.tv_nsec - start.tv_nsec) + (end.tv_sec - start.tv_sec) * 1000000000;
  cout << difference << " Nanoseconds\n";
  cout << "Große Blöcke: " << flush;
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
  copy_stuff(my_memcpy, large_chunk_size, large_iterations, array);
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
  difference = (end.tv_nsec - start.tv_nsec) + (end.tv_sec - start.tv_sec) * 1000000000;
  cout << difference << " Nanoseconds\n";

  unsigned anti_optimierung = 0;
  for (size_t i = 0; i < size; ++i)
    anti_optimierung += array[i];
  cout << "Anti-Super-cleverer-Compiler-Optimierungprüfsumme: " << anti_optimierung << '\n';
}

int main()
{
  cout << "Eingebautes memcpy:\n";
  benchmark_memcpy(memcpy);
  cout << "Cooky451s memcpy:\n";
  benchmark_memcpy(cookys_memcpy);
  cout << "314159265358979s memcpy:\n";
  benchmark_memcpy(pis_memcpy);
  cout << "Intels memcpy:\n";
  benchmark_memcpy(intels_vorschlag_fuer_memcpy_auf_guten_compilern_mit_schlechter_standardbibliothek);
}

    Ich hatte nicht die Muße, den asm-Code aus Cookys Link in die Syntax für GCC/Intel-Compiler zu übersetzen. Wenn das jemand machen möchte, kann ich das noch gerne einbauen.

    Compiliert mit dem Intel-Compiler, O3, SSE4.2, Interprozedurale Optimierung. Laufen gelassen auf einem recht modernen System (i7). Typischer Lauf:

    Eingebautes memcpy:
Kleine Blöcke: 1386042291 Nanoseconds
Mittlere Blöcke: 278028657 Nanoseconds
Große Blöcke: 77568309 Nanoseconds
Anti-Super-cleverer-Compiler-Optimierungprüfsumme: 2096334824
Cooky451s memcpy:
Kleine Blöcke: 1390421740 Nanoseconds
Mittlere Blöcke: 314205719 Nanoseconds
Große Blöcke: 123318491 Nanoseconds
Anti-Super-cleverer-Compiler-Optimierungprüfsumme: 2096334824
314159265358979s memcpy:
Kleine Blöcke: 2377948874 Nanoseconds
Mittlere Blöcke: 634769168 Nanoseconds
Große Blöcke: 417740182 Nanoseconds
Anti-Super-cleverer-Compiler-Optimierungprüfsumme: 2096334824
Intels memcpy:
Kleine Blöcke: 2264565311 Nanoseconds
Mittlere Blöcke: 517638897 Nanoseconds
Große Blöcke: 202675043 Nanoseconds
Anti-Super-cleverer-Compiler-Optimierungprüfsumme: 2096334824

    Wie ich schon gesagt hatte, unter ganz günstigen Bedingungen (hier anscheinend die kleinen Blöcke) kommt man an den Compiler ran. Ansonsten stinkt der handgeschriebene Code ab. Am besten ist noch Cookys Variante, die Vorschläge von 314159265358979 und Intel selbst ( ⚠ ) gehen total unter.

    edit: Hier noch das Ergebnis für den g++, vergleichbare Optimierungoptionen (man muss im Code noch restrict durch __restrict ersetzen):

    Eingebautes memcpy:
Kleine Blöcke: 1326405903 Nanoseconds
Mittlere Blöcke: 271873219 Nanoseconds
Große Blöcke: 76503074 Nanoseconds
Anti-Super-cleverer-Compiler-Optimierungprüfsumme: 2096334824
Cooky451s memcpy:
Kleine Blöcke: 1920048708 Nanoseconds
Mittlere Blöcke: 312840624 Nanoseconds
Große Blöcke: 111624942 Nanoseconds
Anti-Super-cleverer-Compiler-Optimierungprüfsumme: 2096334824
314159265358979s memcpy:
Kleine Blöcke: 2405088134 Nanoseconds
Mittlere Blöcke: 560277846 Nanoseconds
Große Blöcke: 343485706 Nanoseconds
Anti-Super-cleverer-Compiler-Optimierungprüfsumme: 2096334824
Intels memcpy:
Kleine Blöcke: 2367096530 Nanoseconds
Mittlere Blöcke: 536381668 Nanoseconds
Große Blöcke: 334356707 Nanoseconds
Anti-Super-cleverer-Compiler-Optimierungprüfsumme: 2096334824

    Wir sehen das gleiche wie oben, bloß dass der g++ anscheinend an anderen Stellen gut/schlecht optimiert als Intel-Compiler.

    Außerdem kann man in beiden Fällen sehen, dass restrict nicht wirklich etwas bringt (restrict ist der Unterschied zwischen 314159265358979s memcpy und dem Vorschlag von Intel), da moderne Compiler Pointerzugriffe sowieso ziemlich heftig optimieren, restrict hin oder her. (Somit ist auch der berühmte Geschwindigkeitsvorteil von Fortran gegenüber C eine Sache der Vergangenheit)

    0

  • 314159265358979 schrieb:

    berndbernd schrieb:

    314159265358979 schrieb:

    while(d - n != dest)

    Das Berechnen der Differenz d-n scheint mir hier unnötig Performance zu verschenken.

    Ist aber Aufgabe des Optimizers das zu verbessern, nicht meine. 🙄

    Richtig. Deine Aufgabe ist es, total bekiffte Schleifenbedingungen zu schreiben, damit der Optimizer sicher nicht draufkommt was da abgeht.

    Versuch mal eine Kopierschleife wie sie ein normaler Mensch schreiben würde.

    0
  • 3

    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.)

    0
  • A

    @SeppJ
    Mit g++ 4.6 (-O3) bekomme ich etwas andere Werte (das gleiche für g++ 4.5):

    `Eingebautes memcpy:

    Kleine Blöcke: 3518 ms

    Mittlere Blöcke: 538 ms

    Große Blöcke: 138 ms

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

    Cooky451s memcpy:

    Kleine Blöcke: 3588 ms

    Mittlere Blöcke: 540 ms

    Große Blöcke: 147 ms

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

    314159265358979s memcpy:

    Kleine Blöcke: 3889 ms

    Mittlere Blöcke: 537 ms

    Große Blöcke: 148 ms

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

    Intels memcpy:

    Kleine Blöcke: 3938 ms

    Mittlere Blöcke: 540 ms

    Große Blöcke: 148 ms

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

    Für große Blöcke ist die Performanz bei allen etwa gleich.
    Mit -march=native (Phenom II) verbessern sich alle bis auf das eingebaute memcpy auf ~130 ms.

    da moderne Compiler Pointerzugriffe sowieso ziemlich heftig optimieren, restrict hin oder her.

    Das muss hier nicht viel heißen, da die Parameter bekannt sind und Inlining betrieben werden kann. Wenn die Funktionen in einer anderen Übersetzungseinheit (ohne LTO) sind, kann das anders aussehen (__restríct wegzulassen scheint hier 5-10% Performanz zu kosten).

    0
  • Mod

    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.)

    Immerhin hat's der Optimierer ungefähr genau so gut optimiert wie die nicht ganz so bekiffte, angeblich optimiererfreundliche, Variante (siehe mein Benchmark, nur der Intel-Compiler bei großen Blöcken mag deine Variante nicht), du kannst dich als moralischer Sieger fühlen 🙂 . Siehe auch dort (der Intel vorschlag für gute Optimierer) für eine etwas verständlichere Schleife.

    edit: @Ather: Das finde ich sehr überraschend. Vor allem, dass die praktisch alle identisch sind. 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? Das Ergebnis ist phänomenal!

    0
  • 3

    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.

    0
  • Mod

    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.) .

    0
  • 3

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

    0
  • C

    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. 😃

    0
  • 3

    *Nach SSE Extensions google und besseres memcpy schreib*

    0
  • ?

    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.

    0
  • 3

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

    0
  • C

    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.

    0
  • A

    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).

    0

  • 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) ...

    0
  • 3

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

    0
  • E

    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ä.

    0
  • A

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

    0
Anmelden zum Antworten