Mehrere sehr kleine Integer in einem bool[] speichern



  • @seppj
    dass die Gesamtdatenmenge in 1-Byte-Einheiten kommt ist mir durchaus klar, dennoch: bei Speicherung in einem uint32 werden 4 byte verwendet. Bei zwei als seit 0 Uhr vergangenen Sekunden gespeicherten HH:MM:SS (nein, die sind nicht genauer, und nein, hier ist kein Datum oder sonst was dabei) wären das 8 Byte. Ich brauche, wie beschrieben, aber nur 34bit, die ich mir problemlos z.B. zusammenbasteln könnte in einem uint32 und einem uint8. Das wären insg. 5byte vs 8byte, damit 3byte Ersparnis. Und das sind bei 500 Mio Objekten immerhin ~200mb gesparter Speicher ohne irgendeinen overhead.



  • Dann bastel es dir eben einfach zusammen, so wie du es beschrieben hast? Nein, ein bool benötigt nicht ein Bit, sondern mindestens ein Byte und je nachdem, was der Compiler sich überlegt hat, auch gerne mal mehr. Einzelne Bits sind nicht addressierbar. Aber du kannst z.B. ein Array aus 5 unsigned char verwenden und eine Funktion schreiben, die dir deine Werte ver- und entpackt...


  • Mod

    sagredo schrieb:

    @seppj
    dass die Gesamtdatenmenge in 1-Byte-Einheiten kommt ist mir durchaus klar, dennoch: bei Speicherung in einem uint32 werden 4 byte verwendet. Bei zwei als seit 0 Uhr vergangenen Sekunden gespeicherten HH:MM:SS (nein, die sind nicht genauer, und nein, hier ist kein Datum oder sonst was dabei) wären das 8 Byte. Ich brauche, wie beschrieben, aber nur 34bit, die ich mir problemlos z.B. zusammenbasteln könnte in einem uint32 und einem uint8.

    Wie schon erklärt, das Problem ist, dass 5 Byte so krumm ist, dass du dadurch nicht wirklich etwas sparst. Es ist mit den genannten Stichwörtern an sich möglich. Zur allergrößten Not eben selbst geschrieben als 5*char. Aber das spart in der Regel nichts, wenn es Teil einer größeren Datenstruktur ist.

    Das wären insg. 5byte vs 8byte, damit 3byte Ersparnis. Und das sind bei 500 Mio Objekten immerhin ~200mb gesparter Speicher ohne irgendeinen overhead.

    Rechenzeitoverhead, falls Zugriffe oft erfolgen. Und wie schon gefragt: 200 MB von was? Die Daten selber haben doch auch eine Größe. Das müssen doch zig Gigabyte sein, kommt es da auf ein paar hundert MB an? Wieso braucht es die Daten überhaupt alle gleichzeitig im Speicher? Oder geht es um Plattenplatz? Wie schon gesagt: Diese Optimierung klingt nicht sehr sinnvoll, zumindest nicht so, wie du sie darstellst. Willst du irgendwas bestimmtes aus einem bestimmten Grund erreichen?



  • SeppJ schrieb:

    @Ruvi und sagredo: Ihr habt da so einiges falsch verstanden. Kleinste Adressierungseinheit in einem Computer ist immer 1 Byte, per Definition des Bytes.

    Sorry, mein Fehler.
    Der Wert war so hoch, dass ich gedanklich von Bytes zu Bits geshifted bin.

    SeppJ schrieb:

    Was Ruvi in seinem Testcode ausgegeben hat sind die Adressen der Proxyobjekte, die vector<bool>::operator[] zurück gibt. Diese Adressen haben nichts mit den eigentlichen Nutzdaten zu tun. Dies ist übrigens der Hauptgrund, wieso vector<bool> kein gültiger STL-Container ist und die größte Gefahr bei dessen Benutzung, wenn man nicht genau weiß, was man tut. Was du anscheinend nicht genau tust.

    Danke, das wusste ich in der Tat nicht, aber das gilt nur fuer den vector<bool> oder? Bei einem vector<int> bekomme ich doch so die direkte Speicheradresse der Nutzdaten, oder?


  • Mod

    Ruvi schrieb:

    Danke, das wusste ich in der Tat nicht, aber das gilt nur fuer den vector<bool> oder? Bei einem vector<int> bekomme ich doch so die direkte Speicheradresse der Nutzdaten, oder?

    Ja. Dieses ungewöhliche Verhalten ist einer der Gründe, wieso der vector<bool> solch einen schlechten Ruf besitzt.



  • Also ein Zeitstempel von HH:MM:SS kannst Du als Anzahl Sekunden seit 00:00:00 speichern. Der größte Wert ist dann 86400. Das passt nicht in 16 Bit, da hier der Wertebereich nur bis 65535 geht. Dafür brauchst Du also 17 Bit. Zwei Zeitstempel benötigen 34 Bit. Da könnte man aber ein Bit einsparen, indem man beide Zeitstempel kombiniert. Also t=t1*86400+t2. Dann bekommst Du t1 aus t/86400 und t2 aus t%86400 (modulo). Der Wertebereich geht bis 86400*86400=7464960000. Das passt schon mal in 33 Bit, da 2^33=8589934592 ist. Hier ist erst mal Schluss.

    Jetzt müsstest Du noch deine Applikation anschauen, ob wir nicht noch mehr Informationen verwerten können. Könnte es sein, dass immer t1<=t2 gilt? Wenn mit den Zeitstempeln ein Zeitraum angegeben ist, der nicht negativ sein kann, dann wäre das so. Damit kann man ein weiteres Bit einsparen und man käme dann mit 32 Bit und damit mit einem uint32_t aus.

    Eine andere Möglichkeit wären die bool Werte, die Du zusätzlich zu jedem Zeitstempelpaar speicherst. Sind es maximal 30, dann kannst Du mit ein wenig Bitschieberei die 30 Bit Informationen mit den 34 Bit Zeitstempeln relativ einfach zu einem 64 Bit Integer verwursteln. Oder Du verwendest die erste Variante, wo Du mit 33 Bit auskommst. Dann hast Du 31 Bit für die bool Werte.



  • Ruvi schrieb:

    vector <bool> vec;
    ...
    cout << &vec[0] << endl;
    cout << &vec[1] << endl;
    

    Wenn ich mich nicht verrechnet habe besteht ein Eintrag aus 24 bit also 3 Byte.

    here be dragons.

    vector<bool> ist kein vector, und &vec[0] ist daher auch nicht die adresse eines im vector gespeicherten bool s.



  • vector <bool> vec;

    Die Alternative ist std::bitset. In VS ist es aber mindestens so gross wie ein Register. Sicher wird fuer geringe Groessen auch std::vector<bool> einen fixen Wert erhalten, beispielsweise Registerbreite. Habe bei std::vector<bool> aber nicht nachgeschaut. Daher wirst du wohl eine eigene Loesung schaffen muessen. Weiterhin muss beachtet werden, dass bei eigenen Datenstrukturen der Kompiler durch padding den Zugriff optimieren darf. Also abschalten.

    Darueber hinaus sind 4GByte erstmal nicht schlimm, einfach genug verbauen und 64 Bit schreiben. Auch werden wahrscheinlich nicht alle Daten gleichzeitig benutzt, so dass ein intelligenterer Zugriff mehr bringt, als die vorgeschlagene Reduktion. Beispielweise kann fuer einen Zeitraum der Zeitpunkt+Distanz zum Ende gespeichert werden. Wenn durch den Kontext gegeben ist, dass die Distanz nicht groesser als 5000 Sekunden sein kann oder HH nie groesser als 24, kann das ins Speicherformat einfliessen.

    Insgesamt ist eine Halbierung des Speicherbedarf gefuehlsmaessig auch nicht der Bringer. Ob nun 2GByte oder 4GByte benutzt werden, ist in dieser Groessenordnung wohl unerheblich. 200 MByte im Vergleich zu 4GByte schon eher.

    Nur am Rande:

    Und in keinem Fall kann man die Adresse eines einzelnen Bits bekommen

    Fuer die immer beliebteren Arm-Architekturen stimmt diese Aussage nicht.



  • Und in keinem Fall kann man die Adresse eines einzelnen Bits bekommen

    Das stimmt natuerlich nicht! Der C++-Standard definiert nicht, was die smallest addressable unit of memory ist, er sagt nur, dass zumindest jedes byte eine unique address hat! Das bedeutet, es koennen selbst Bits eine unique address haben!!!

    Weiterhin muss beachtet werden, dass bei eigenen Datenstrukturen der Kompiler durch padding den Zugriff optimieren darf.

    Der Compiler darf nur den Zugriff erst optimieren wenn er auch das Padding auch in classes eingefuegt hat!!!!!



  • @11!elf: Koenntest du vielleicht weniger schreien, meine Augen sind schon ganz taub. Desweiteren sind Compiler manchmal sehr kindisch, gehen ihre eigenen Wege und halten sich nicht an "Vorschriften".

    Ich verstehe folgenden Satz nicht:

    Der Compiler darf nur den Zugriff erst optimieren wenn er auch das Padding auch in classes eingefuegt hat

    Also padding ist eine Zugriffsoptimierung. Der Kompiler darf also erst Padding einfuehren, wenn er Padding einfuehrt. Und wie ist das mit Safer Sex?



  • knivil schrieb:

    Nur am Rande:

    Und in keinem Fall kann man die Adresse eines einzelnen Bits bekommen

    Fuer die immer beliebteren Arm-Architekturen stimmt diese Aussage nicht.

    Hm... das geht wie? Ich kann mich so direkt jetzt an keine load oder store Instruction erinnern mit der man einzelne bits ansprechen kann.



  • arkot333 schrieb:

    Und in keinem Fall kann man die Adresse eines einzelnen Bits bekommen

    Das stimmt natuerlich nicht! Der C++-Standard definiert nicht, was die smallest addressable unit of memory ist, er sagt nur, dass zumindest jedes byte eine unique address hat! Das bedeutet, es koennen selbst Bits eine unique address haben!!!

    Der Standard sagt, dass Bytes eine Adresse haben. Ja, damit ist er theoretisch auch kompatibel mit eine hypothetischen Architektur, wo jedes Bit eine Adresse hat. Im Rahmen von Standard C++ sind Bits dennoch nicht adressierbar, selbst auf einer solchen Architektur, wenn sie existieren würde...



  • dot schrieb:

    Der Standard sagt, dass Bytes eine Adresse haben. Ja, damit ist er theoretisch auch kompatibel mit eine hypothetischen Architektur, wo jedes Bit eine Adresse hat. Im Rahmen von Standard C++ sind Bits dennoch nicht adressierbar, selbst auf einer solchen Architektur, wenn sie existieren würde...

    Wie man die Bitadressen bekommt ist selbstverständlich implementation-defined! Aber danach kann man sie wie jeden anderen Zeiger benutzen!!!



  • Wenn es darum geht, immer zwei Timestamps in 5 Byte unterzubringen, wuerde ich das etwa so machen:

    #include <cstdint>
    #include <iostream>
    
    class timestamps {
    public:
      timestamps(std::uint32_t first,
                 std::uint32_t second)
        : lower((first & 0x1ffff) | ((second & 0x7fff) << 17)),
          upper((second >> 15) & 0x03) { }
    
      std::uint32_t first () const { return lower & 0x1ffff; }
      std::uint32_t second() const { return (lower >> 17) | (upper << 15); }
    
    private:
      std::uint32_t lower;
      std::uint8_t  upper;
    } __attribute__((packed)); // WICHTIG: gcc-spezifisch. 
    
    int main() {
      timestamps test(81234, 85432);
    
      std::cout << test.first() << ", " << test.second() << '\n';
      std::cout << sizeof(test) << '\n';
    }
    

    Wenn du einen anderen Compiler als gcc unterstuetzen musst, schlag in dessen Doku nach, wie er packed structs handhabt. MSVC hat ein #pragma pack, wenn ich das richtig im Kopf habe.

    Was das Gerede um Bitadressen angeht:

    ISO/IEC 14882:2011 3.9.2 (3) schrieb:

    A valid value of an object pointer type represents either the address of a byte in memory (1.7) or a null pointer (4.10).

    Da ein Byte kein Bit sein kann (in ein Bit passt das basic execution character set nicht rein), kann man also keine Adressen von Bits haben.



  • arkot333 schrieb:

    dot schrieb:

    Der Standard sagt, dass Bytes eine Adresse haben. Ja, damit ist er theoretisch auch kompatibel mit eine hypothetischen Architektur, wo jedes Bit eine Adresse hat. Im Rahmen von Standard C++ sind Bits dennoch nicht adressierbar, selbst auf einer solchen Architektur, wenn sie existieren würde...

    Wie man die Bitadressen bekommt ist selbstverständlich implementation-defined! Aber danach kann man sie wie jeden anderen Zeiger benutzen!!!

    Nope, complete objects sind in C++ mindestens 1 Byte groß und damit kannst du in C++ niemals die Adresse eines Bit bestimmen, selbst wenn du eine Architektur erfindest, wo das möglich wäre...



  • cooky451 schrieb:

    Hm... das geht wie? Ich kann mich so direkt jetzt an keine load oder store Instruction erinnern mit der man einzelne bits ansprechen kann.

    Du darfst dir gerne das Programmierhandbuch durchlesen. Prinzipiell ist es ein Feature des memory controlers fuer bestimmte Bereiche des Speichers:

    Bit-banding maps a complete word of memory onto a single bit in the bit-band region. For example, writing to one of the alias words will set or clear the corresponding bit in the bitband region.

    D.h. du "schreibst" ein ganzes Byte und setzt ein Bit. Du arbeitest wie mit gewoehnlichen Bytes, es sind keine neuen Prozessorinstruktionen noetig. Sie werden nur vom Memory controller anders interpretiert.


Anmelden zum Antworten