memcpy - Schneller als der Optimizer

pumuckl

Kommt drauf an, was für einen Code du ihm zum Optimieren hingesetzt hast. Am Besten lieferst du uns 1) deinen inline-asm, 2) deinen C++-Code, 3) den asm, den der Compiler daraus gemacht hat. Dann haben wir ne Grundlage, um ernsthafte Aussagen über die Uterschiede und ihre Ursachen zu treffen. So können wir nur raten und das führt zu nichts.

CStoll

314159265358979 schrieb:

Ich gebe zu, die Einheit "x mal blinkt der Strich in der Konsole auf" ist vielleicht etwas ungenau, aber wenn sich hier schon solche Unterschiede zeigen, ist das doch sehr verwunderlich.

Wenn du genauere Aussagen willst, solltest du es vielleicht echt messen und nicht nur abschätzen (Stichwort: clock())

Ansonsten kannst du ja mal dein C++ memcpy() und die ASM-Variante nebeneinander präsentieren, damit andere deren Schwachpunkte vergleichen können. (wobei, bei deinem ASM-Code kenne ich mich nicht gut genug aus um zu wissen, was der überhaupt machen soll - trotzdem sieht er irgendwie "falsch" aus).

314159265358979

Die C++-Version (Ebenfalls nur so, wie ich sie im Kopf habe):

void cpp_memcpy(void* dest, void* src, int n)
{
    char* d = static_cast<char*>(dest);
    char* s = static_cast<char*>(src);

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

Den ASM-Code dafür hab ich komischerweise nicht im Kopf - der folgt dann heute Abend, wenn ich zuhause bin

SeppJ

Das würde mich auch mal interessieren. Zeig mal compilierbaren Code. Ich habe so etwas nämlich auch schon mal intensiv getestet und kam nicht ansatzweise an den Compiler ran (Das war allerdings der Intel-Compiler auf höchster Optimierung, der soll ganz gut sein ), selbst optimierte Asm-Codes aus dem Internet kamen nur unter bestimmten Bedingungen (bestimmtes Alignment) zumindest in die Nähe des Compilers, aber niemals schneller und niemals unter allen Bedingungen^*.

Mich würde auch interessieren, was bei dir passiert, wenn du mit den Optimierungsoptionen noch weiter hoch gehst.

^*: Eine asm-Routine für ganz allgemeine Bedingungen ist jedoch auch ganz schön fies zu vergleichen. Die eigene Routine muss alles zur Laufzeit machen, der Compiler kann im besten Fall den Code statisch analysieren und die optimale Routine zur Compilezeit einzetzen.

314159265358979

Mit Optimierungsoptionen weiter hochgehen? O2 ist doch schon das höchste bei MSVC.

SeppJ

314159265358979 schrieb:

Mit Optimierungsoptionen weiter hochgehen? O2 ist doch schon das höchste bei MSVC.

Ach so. Die ganzen Compiler die ich sonst benutze kennen noch höheres, aber das sind ja bloß Namen.

Und da das hier ja öfters vorkommt: Man muss beim MSVC nicht noch irgendwelche Makros setzen, damit irgendwelche Laufzeitprüfungen ausgeschaltet werden?

cooky451

SeppJ schrieb:

Und da das hier ja öfters vorkommt: Man muss beim MSVC nicht noch irgendwelche Makros setzen, damit irgendwelche Laufzeitprüfungen ausgeschaltet werden?

Ich glaube nicht. Probier mal:

void* my_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;
}

Und SSE2 gleich hinterher, das dürfte noch ein Stückchen schneller sein:
http://stackoverflow.com/questions/1715224/very-fast-memcpy-for-image-processing

berndbernd

314159265358979 schrieb:

while(d - n != dest)

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

314159265358979

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.

Ethon

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.

SeppJ

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)

hustbaer

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.

314159265358979

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

Athar

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

SeppJ

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!

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*