Speicherverbrauch bei Bitoperationen

Hallo,

Ist jetzt eher eine Hintergrundfrage. Ich hoffe mir kann jemand helfen.
Ich entwickle ein Messsystem, das sehr viele Messdaten in Form einzelner Bits aufnimmt und verarbeitet. Im Programm werden dann viele Operationen auf die einzelnen Bits angewand. (Bit-Vergleich, -Vertauschen, -Neuordnen, -Löschen und die anderen Nachrücken usw.) Das ganze soll auf einem Embedded Linux System laufen. Speicherplatz ist also eher Mangelware. Damit das Programm so speichereffizient wie möglich läuft, lege ich die einzelnen Bits hinternander. (immer 8 zu einem Byte) Um auf die einzelnen Bits zuzugreifen, verwende ich Algorithmen wie:

if(del[i/8]&(1<<(i%8))){   
   if(k <= range){
      if(data_base[i/8]&(1<<(i%8)))                                   
         valid[k/4]|=(1<<(2*(k%4)));

      if(data_apd[i/4]&(1<<(2*(i%4))))                                
         valid[k/4]|=(1<<(2*(k%4)+1));

      k++;
   }
}

Dies ist natürlich sehr unübersichtlich und rechenintensiv. Die Operationen würden sich wesentlich leichter umsetzen lassen, wenn ich jedes einzelne Messwert-Bit in einem Byte innerhalb eines Arrays speichern und verarbeiten würde. Allerdings verschwende ich dann Unmengen an Speicher, wenn die restlichen 7 Bit im Byte ungenutzt bleiben. Noch besser würden sich Datentypen wie QByteArray in Qt eignen. Aber auch damit ist die Speicherauslastung nicht effektiver. Kann mir jemand sagen, was in dem Fall die bessere Variante ist? Vielleicht wird das Ganze ja bei der Verwendung solcher Datentypen durch den Compiler auch so optimiert, dass nicht soviel Speicherplatz unbenutzt bleibt?

volkard

Einfach vector<bool> nehmen?

SeppJ

Spricht was gegen bitset (statische Größe) oder vector<bool> (dynamisch, falls dies dein Gerät unterstützt)? Die machen das Packen und Entpacken so optimal, wie man es im allgemeinen Fall nur machen kann, ohne Speziallösungen für spezielle Probleme zu benutzen.

Ob du besser Speicherplatz gegen Rechenleistung tauschen solltest oder nicht, musst du selber wissen, das können wir dir nicht beantworten, da wir weder dein Gerät noch dein Vorhaben kennen. Entweder passt es ungepackt (dann packst du auch nicht) oder eben nicht (dann bleibt dir keine Wahl).

Könntest du den genauen Algorithmus zeigen? Oft lassen sich gleich 8 Bits gleichzeitig verarbeiten.

Danke für die schnellen Antworten!!

vector<bool> ist ein gutes Stichwort. Damit würde sich das schonmal eleganter programmieren lassen. Ich werde mir mal den Assemblercode dazu anzeigen lassen, mal sehen wie das dann wirklich verarbeitet wird.

Aber danke für den Tip!

volkard

kieweitzsch schrieb:

vector<bool> ist ein gutes Stichwort. Damit würde sich das schonmal eleganter programmieren lassen. Ich werde mir mal den Assemblercode dazu anzeigen lassen, mal sehen wie das dann wirklich verarbeitet wird.

Falls der Assembler-Code schlecht wird, was ich eigentlich weniger erwarte, dann denke trotzdem darüber nach, Dir eine eigene Klasse für Bitfelder zu bauen. Dein gezeigter Code geht damit sicherlich viel eleganter zu Null Zusatzkosten.
Eventuell hat vector<bool> vielleicht eine Schwäche gegenüber dem, was bei Dir optimal wäre, weil vector<bool> halt nicht genau für Dich gebaut wurde, sondern für möglischt breite Abdeckung der Bedürfnisse aller möglicher Programmierer.

knivil

std::bitset oder boost::dynamic_bitset oder so

Dies ist natürlich sehr unübersichtlich und rechenintensiv.

Dann baut man sich kleine Funktionen, die den Zugriff uebersichtlicher gestallten. Auf Performance wuerde ich im Hinterkopf behalten aber erst optimieren, wenn es noetig wird. D.h. es zu langsam wird oder Stromverbrauch zu hoch.

Ethon

Dies ist natürlich sehr unübersichtlich und rechenintensiv. Die Operationen würden sich wesentlich leichter umsetzen lassen, wenn ich jedes einzelne Messwert-Bit in einem Byte innerhalb eines Arrays speichern und verarbeiten würde.

Wie wäre es wenn du alle Bits aus dem Byte in ein Byte-Array entpackst, damit arbeitest und dann wieder in ein Byte packst?
Oder sind temporäre 8 Byte pro Byte wirklich so schmerzhaft?

Macht zumindestens Sinn wenn du immer wieder die gleichen Bits rauspfriemelst. Wenn auf jedes Bit nur 1-2x zugegriffen wird natürlich nicht.