Wert aus Array verschieben [C]

[Aaron43]

Hallo zusammen.

Ich würde gerne in C eine Art Ringspeicher entwerfen. Gedacht ist das ganze folgendermaßen. In einer Varablen "Value" ist mein aktueller Wert enthalten, dieser soll in einem Array "Test" das erste Element belegen (Test[0]). Ändert sich der Wert von "Value" soll der Wert aus dem Array Test[0] nach Test[1] verschoben und der aktuelle Wert in T[0] gesichert werden und immer so weiter (je nach Größe des Arrays werden die älteren Werte überschrieben). Das ganze habe ich schon mit einer for-Schleife realisiert:

int Value;
int Test[10];
......
Value = ....;
if (...) {

for(int i = 9 ; i > 0 ; i--)
{
  Test[i+1] = Test[i];
}
Test[0] =Value;

}

Um jedoch effizienter zu arbeiten, gerade für ein größeres Array, möchte ich das ganze gerne mit Hilfe eines Zeigers umsetzen. Ich hatte gelesen, dass dies möglich sei bin aber leider noch auf kein Ergebnis gestoßen. Ich würde mich freuen wenn mir jemand helfen könnte.
Viele Grüße.

 

[BlackMark]

1. Deine Implementierung ist fehlerhaft. Du gehst in der for-Schleife out of bounds. Außerdem bei jedem hinzufügen eines neuen Elements alle vorherigen zu verschieben ist so ziemlich das Ineffizienteste was man machen kann.
2. Das was du suchst nennt sich Circular buffer oder auch Ring buffer und dazu findet man massenhaft Implementierungen im Internet.

Gruß
BlackMark

 

[Aaron43]

1. Deine Implementierung ist fehlerhaft. Du gehst in der for-Schleife out of bounds.

Kann sein... Hab den Code jetzt nicht aus dem Programm kopiert.

Außerdem bei jedem hinzufügen eines neuen Elements alle vorherigen zu verschieben ist so ziemlich das Ineffizienteste was man machen kann.

Ach was?! Aus dem Grund habe ich doch das Thema eröffnet.

Nach dem Circular buffer hatte ich auch schon gesucht, bin aber leider auf kein passendes Ergebnis gestoßen.
Grüße

 

[Kayleigh]

Ob Du das Konzept mit Zeiger oder mit Variablen realisierst, ist erstmal uninteressant. Deine Vorgehensweise (Daten verschieben) wird nie effizient sein.

Du solltest nicht die Daten im Array verschieben, sondern eine Indexvariable benutzen, mit der Du dann immer auf die Elemente im Array zugreifst. Die Indexvariable wird jeweils um "1" erhoeht, bis Du die Obergrenze vom Array erreicht hast. Dann die Indexvariable wieder auf die Untergrenze setzen und fertig ist der Ringpuffer.

 

[Aaron43]

Erstmal Danke für deine Antwort. Ich würde es aber gerne so realisieren, wie ich es beschrieben habe und suche anstelle der for-Schleife eine "effizientere" Lösung (auch wenn es nicht die effizienteste ist).

 

[Kayleigh]

Wenn's denn unbedingt sein muss... "memmove" duerfte klappen.

http://man7.org/linux/man-pages/man3/memmove.3.html

 

[Miuwa]

Wenn's denn unbedingt sein muss... "memmove" duerfte klappen.

Definitiv besser (weil einfacher) als die Schleife, aber ich wäre nicht überrascht, wenn der compiler aus beiden Versionen genau den selben Binärcode erzeugen würde.

 

[asdfman]

memmove() erzeugt garantiert nicht den selben Code und ist garantiert auch nicht schneller. Es kopiert den zu verschiebenden Puffer vor dem Verschieben in eine temporären Puffer, um Probleme mit überlappenden Speicherregionen (die OP hier ja offensichtlich hat) zu vermeiden (die früher bei memcpy() z.B. undefiniertes Verhalten hatten).

 

[Kayleigh]

Ich bin mir ziemlich sicher, dass nicht der gleiche Code erzeugt wird. Aber ich denke auch, dass memmove() wesentlich effizienter umgesetzt wird werden kann als eine Schleife, aufgrund des "rep" statements in x86.
Zumindest wuerde ich das von einem "optimierenden Compiler" fuer eine Standardfunktion erwarten:

mov esi, source      ; source address of the code in DS:SI
mov edi, destination ; destination address of the code in ES:DI
mov ecx, 512         ; Number of bytes
rep movsb            ; Repeat Move Byte

Das laesst sich ausbauen - wenn die Laenge durch 4 teilbar ist, dann koennen 4 bytes mit einem Zugriff kopiert werden:

movsd

anstelle von

movsb

und Laenge natuerlich durch 4 teilen.

 

[nullPtr]

Memmove kann einfach anhand der Pointer feststellen, wo (am Anfang oder am Ende) sich die Speicherbereiche überlappen und dann entweder vorwärts oder rückwärts kopieren.

 

[VikingGe]

Zumindest wuerde ich das von einem "optimierenden Compiler" fuer eine Standardfunktion erwarten:

Ich nicht, weil:
- Ist die Datenmenge sehr klein und zur Compile-Zeit bekannt, sind explizite Move-Befehle mit passendem Alignment quasi immer schneller (clang macht das auch, gcc und der hoch gelobte Intel-Compiler nur bei memcpy)
- Ist die Datenmenge relativ klein (≤ L1-Cache), sind Schleifen mit aligned SSE/AVX-Stores auf vielen CPUs schneller, aber nie langsamer.
- Ist die Datenmenge sehr groß (≥ Last Level-Cache), sind Non-Temporal Stores und ggf. Prefetching Pflicht, da sind entsprechend optimierte Schleifen quasi auf jeder CPU schneller.
- Ist die Datenmenge irgendwo dazwischen (passt also in den L2/L3), ist rep movsq auf den meisten Chips recht flott.

Wegen den Fällen 2 bis 4 werden memmove/memcpy in aller Regel nicht inlined, wenn die Länge nicht zur Compile-Zeit bekannt ist.

Zum Nachsehen: http://gcc.godbolt.org
-O3 -march=core-avx2

#include <cstring>

constexpr size_t ARR_LEN = 10;

void moveArray1(int* array) {
  memmove(array + 1, array, (ARR_LEN - 1) * sizeof(int));
}

void moveArray2(int* array) {
  for (size_t i = ARR_LEN - 1; i > 0; i--)
    array[i] = array[i - 1];
}

 

[Kayleigh]

Auf die Diskussion lasse ich mich nicht ein - zu viele verschiedene Moeglichkeiten und zu sehr vom Compiler abhaengig

Im Uebrigen denke ich, dass eine solche Diskussion sich besser im allgemeinen Rahmen bewegen sollte - Code-Optmierungen im Compiler lassen sich anhand des erzeugten Codes nachvollziehen; Prpzessor Cache/Prefetch kann ich nicht analysieren - dazu fehlen mir sowohl die Tools als auch die Kenntnisse; desweiteren auch Zugang zu den verschienenen Prozessoren zum Testen.

Ich denke mal, dass der Ersteller dieser Diskussion genug Anregungspunkte hat - vielleicht versucht er ja mehrere Moeglichkeiten und jagt das Ganze durch einen Profiler / Disassembler?

Wuerde mich zwar wirklich interessieren, aber mir fehlt dazu im Moment leider die Zeit, um dieses Szenario durchzuspielen.

 

[Miuwa]

Also bei mir spuck gcc für beide Versionen den exakt gleichen Assembler Code aus (memmove), bei clang hängt es interessanter Weise von der Größe des Arrays ab und VS scheint beide Versionen mehr oder weniger wörtlich zu übersetzen.

 

[Kayleigh]

Das kann ich mit GCC hier nachvollziehen - Code::Blocks mit GCC erzeugt hier den folgenden Code:

Optimierung -O2
Fall 1 - Adressen ermitteln, dann memmove aufrufen
Fall 2 - Schleife umsetzen

__Z10moveArray1Pi:
    subl    $28, %esp
    movl    32(%esp), %eax
    movl    $36, 8(%esp)
    movl    %eax, 4(%esp)
    addl    $4, %eax
    movl    %eax, (%esp)
    call    _memmove
    addl    $28, %esp
    ret

__Z10moveArray2Pi:
    movl    4(%esp), %ecx
    leal    32(%ecx), %eax
    subl    $4, %ecx
    .p2align 4,,10
L4:
    movl    (%eax), %edx
    subl    $4, %eax
    movl    %edx, 8(%eax)
    cmpl    %ecx, %eax
    jne    L4
    rep ret

Optimierung -O3
Fall 1 und Fall 2 erzeugen den gleichen Code - Adressberechnung und dann memmove Aufruf:
​

__Z10moveArray1Pi:
    subl    $28, %esp
    movl    32(%esp), %eax
    movl    $36, 8(%esp)
    movl    %eax, 4(%esp)
    addl    $4, %eax
    movl    %eax, (%esp)
    call    _memmove
    addl    $28, %esp
    ret

__Z10moveArray2Pi:
    subl    $28, %esp
    movl    32(%esp), %eax
    movl    $36, 8(%esp)
    movl    %eax, 4(%esp)
    addl    $4, %eax
    movl    %eax, (%esp)
    call    _memmove
    addl    $28, %esp
    ret

​Jetzt richtet es sich natuerlich danach, wie memmove in der Library implementiert wurde. Aufgrund der Verwaltung der Schleifenvariable (Dekrementierung und Vergleich) denke ich, dass die Schleife, zumindest bei groesseren Arrays, nicht sehr effizient ist. Das scheint der GCC Compiler zu erkennen und versucht, diesen Aufwand zu vermeiden.

Andere Compiler habe ich im Moment erstmal nicht zur Hand - also gebe ich fuer den Moment auf. Ich bin den Rest der Woche sowieso sehr beschaeftigt, werde also das Thema erstmal nur noch lesend verfolgen.

Viel Spass beim Testen - ich werde zumindest noch schauen, ob jemand andere Codebeispiele zeigt - das Thema interessiert mich irgendwie


PS an Miuawa: Gute Vorahnung - Du mit Deinem ersten Beitrag hier voll ins Schwarze getroffen. Bei voller Optimierung erzeugt zumindest GCC den selben Code. Ich bin jetzt wirklich beindruckt vom GCC, zumindest was Optimierungen betrifft.

 

[asdfman]

Danke an die Leute, die sich den Code mal angesehen haben. Da merke ich wie sehr ich mich mit so Pauschalbehauptungen zurückhalten sollte.
In der Spezifikation steht sogar "[...] copying takes place as though the bytes in src are first copied into a temporary array [...]", nicht dass es tatsächlich so gemacht werden MUSS.

Lasst euch knuddeln :3