Schnelles Datenarray kopieren

Hallo,
ich möchte mein Code optimieren. Kurz zu meiner Problemstellung:
Ich habe eine Software geschrieben die mit einer vom Hersteller mitgelieferten Bibliothek Daten aufnimmt. Während jeden Datenschusses wird eine Funktion aufgerufen welche mir die Daten in eine Queue kopieren soll. Die Daten liegen in einem 2D Array vor. Jetzt gibt es in der Bibliothek eine Funktion Get2DArray, welche aber sehr langsam arbeitet. Ich kann mir allerdings den Pointer auf das Datenarray auslesen.

Meine Frage:
Kann ich mit dem Pointer eine sehr schnelle C++ Funktion verwenden um die Daten in ein anderes Array gleicher Größe zu kopieren, verschieben? Der Pointer ist unsigned char *.

Danke

Nexus

abrissbirne1 schrieb:

Meine Frage:
Kann ich mit dem Pointer eine sehr schnelle C++ Funktion verwenden um die Daten in ein anderes Array gleicher Größe zu kopieren, verschieben?

Kopieren oder verschieben? Beim Verschieben reicht unter Umständen ein Zeigertausch, was natürlich sehr schnell ist. Für das Kopieren könntest du std::copy() nehmen, aber ich frage mich, ob die Implementierung der Bibliotheksfunktion dermassen schlecht ist, dass du selber schneller kopieren kannst...

Warum kopiert die Funktion das Array überhaupt, ist das nötig? Und wenn ja, wirklich die ganze Zeit? Sonst kannst du doch einen Zeiger auf das Array speichern.

Nexus schrieb:

abrissbirne1 schrieb:

Meine Frage:
Kann ich mit dem Pointer eine sehr schnelle C++ Funktion verwenden um die Daten in ein anderes Array gleicher Größe zu kopieren, verschieben?

Kopieren oder verschieben? Beim Verschieben reicht unter Umständen ein Zeigertausch, was natürlich sehr schnell ist. Für das Kopieren könntest du std::copy() nehmen, aber ich frage mich, ob die Implementierung der Bibliotheksfunktion dermassen schlecht ist, dass du selber schneller kopieren kannst...

Warum kopiert die Funktion das Array überhaupt, ist das nötig? Und wenn ja, wirklich die ganze Zeit? Sonst kannst du doch einen Zeiger auf das Array speichern.

Ob kopieren oder verschieben wäre mir prinzipiell egal. Maximal sollte die Anwendung 380Hz bei einer Arraygröße von 320x256 erreichen, was ja nicht besonders schnell ist. Der Aufnahmefunktion ist eine Hook Funktion angehakt, welche nach jedem Schuss die Daten kopieren oder verschieben soll. Wenn ich dies nicht mache muss ich vorher einen Speicher für genügen Schüsse anlegen. Dann bin ich aber abhängig von einer bestimmten Anzahl an Schüssen und kann nicht einfach die Aufnahme starten und beenden wann es mir passt. Momentan mache ich es so das jeder Schuss das Array überschreibt. Nun muss ich eine Funktion finden die mir 81920 Werte schneller kopiert als 380Hz, damit die Daten nicht verloren gehen.

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

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.