Schnelles Datenarray kopieren

Problem bei memcpy ist, dass es pro Element ein cmp ausführt

Bei welchem Compiler soll das so sein?

Bei Visual Studio, GCC usw.

Nehmen wir mal die gnulib:

void *
memcpy (void *destaddr, void const *srcaddr, size_t len)
{
  char *dest = destaddr;
  char const *src = srcaddr;

  while (len-- > 0) // jedes element ein vergleich ob len größer als 0 ist --> cmp
    *dest++ = *src++;
  return destaddr;
}

unskilled

klar - und so wird es auch immer sein...

wie willst es sonst machen? nur aller 8 elemente? naja - dann muss die anzahl auch nen vielfaches von 8 sein - aber egal ^^ wenigsten ist es 1/10000ns schneller - _vll_ !

bb

@ unskilled
LESEN! Ich habe gesagt zur Übersichtlichkeit, darum nur 8 Elemente! Dazu ist der Code nur ein Denkanstoß und daher nicht Funktionsfähig.

Du magst zwar sagen 1/100000000 ms. Ich sage dirs mal so: Kleinvieh macht auch Dreck und viel Kleinvieh macht viel Dreck. cmps, und sonstige Vergleiche die man sparen kann, sollte man auch sparen.

Aber die beiden Compiler haben auch optimierte Versionen die in Assembler programmiert sind. Hab gerade in glibc 2.9 nachgeguckt.

Das stimmt, aber viele benutzen oft keinen block prefetch mit 8 oder mehr bytes per iteration. Am besten ist denke ich eine Blockgröße von 64 Byte oder mehr. Den Unterschied merkt man schon. In der netbsd-Mailliste gabs zu sowas oft Diskussionen, hier mal eine von vielen:

http://mail-index.netbsd.org/tech-perform/2002/10/23/0004.html

Badestrand

@Erinyer: Auf meinem System ist das memcpy_rle mit 32-Rutsch-Kopieren um den Faktor 4 langsamer als memcpy. Mit welchen Implementierungen hattest du memcpy denn getestet?

Erinyer schrieb:

Hi!

Das "Problem" hatte ich auch mal in einem Projekt. Problem bei memcpy ist, dass es pro Element ein cmp ausführt, was bei mehreren Tausend/Millionen Elementen ordentlich auf die Bremse treten kann - kommt aber auch hier auf die Implementierung an.

Ich habe mir dafür ein eigene memcpy-Funktion geschrieben die in 64-Elementzyklen ein cmp macht und natürlich für den Rest jeweils pro Element ein cmp. Da konnte ich bei meinem Raytracer ordentlich was rausholen - kein Wunder, so etwas findet man u.A. bei RLE wieder.

Zur Übersicht habe ich mal eine abgespeckte Version der Funktion für dich:
void memcpy_rle (byte* to, byte* from, size_t count)
{
    size_t i = 0;
    // immer 8 elemente in einem rutsch kopieren.
    for (i = 0; i < count; i += 8)
    {
        to[i + 0] = from[i = 0];
        to[i + 1] = from[i = 1];
        to[i + 2] = from[i = 2];
        to[i + 3] = from[i = 3];
        to[i + 4] = from[i = 4];
        to[i + 5] = from[i = 5];
        to[i + 6] = from[i = 6];
        to[i + 7] = from[i = 7];
    }

    // restliche elemente.
    for (; i < count; ++i)
        to[i] = from[i];
}
Ich denke der Code ist selbsterklärend

Also ich ahbe versucht diesen Code zu implementieren, aber irgendwie stehe ich gerade auf dem Schlauch. Bei mir kommt ein Endloskopieren zustande. Ich komme nicht dahinter inwiefern dieser Code was machen soll und warum es schneller ist. Wäre für eine Erklärung echt dankbar

cheers

abrissbirne1 schrieb:

Erinyer schrieb:
Hi!

Das "Problem" hatte ich auch mal in einem Projekt. Problem bei memcpy ist, dass es pro Element ein cmp ausführt, was bei mehreren Tausend/Millionen Elementen ordentlich auf die Bremse treten kann - kommt aber auch hier auf die Implementierung an.

Ich habe mir dafür ein eigene memcpy-Funktion geschrieben die in 64-Elementzyklen ein cmp macht und natürlich für den Rest jeweils pro Element ein cmp. Da konnte ich bei meinem Raytracer ordentlich was rausholen - kein Wunder, so etwas findet man u.A. bei RLE wieder.

Zur Übersicht habe ich mal eine abgespeckte Version der Funktion für dich:
void memcpy_rle (byte* to, byte* from, size_t count)
{
    size_t i = 0;
    // immer 8 elemente in einem rutsch kopieren.
    for (i = 0; i < count; i += 8)
    {
        to[i + 0] = from[i = 0];
        to[i + 1] = from[i = 1];
        to[i + 2] = from[i = 2];
        to[i + 3] = from[i = 3];
        to[i + 4] = from[i = 4];
        to[i + 5] = from[i = 5];
        to[i + 6] = from[i = 6];
        to[i + 7] = from[i = 7];
    }

    // restliche elemente.
    for (; i < count; ++i)
        to[i] = from[i];
}
Ich denke der Code ist selbsterklärend
Also ich ahbe versucht diesen Code zu implementieren, aber irgendwie stehe ich gerade auf dem Schlauch. Bei mir kommt ein Endloskopieren zustande. Ich komme nicht dahinter inwiefern dieser Code was machen soll und warum es schneller ist. Wäre für eine Erklärung echt dankbar

cheers

Und was bedeutet Block Prefetch?

Danke

Superlexx

LOL lauter unaligned-Zugriffe. Das Zeug ist weder korrekt noch schnell noch portabel.

Ok, hat dann jemand einen besseren Vorschlag?

Danke

Superlexx

Einfach memcpy verwenden und wenn's immer noch zu langsam ist, dann wiederkommen. Wenn du z.B. einen aktuellen MS-Compiler mit /Ox verwendest, dann wirst du sehen, dass die Kopierschleife auf eine x86-Anweisung schrumpft, was bei aktueller x86-Hardware auf eine Vollauslastung der Speicherbusse hinausläuft. Deine 32MB/s sind ja eigentlich kein Akt.