Mehrere sehr kleine Integer in einem bool[] speichern



  • Hallo,

    ich arbeite an einem Programm das zig Millionen Objekte zum schnellen Zugriff im Speicher vorhalten muss. Diese Objekte bestehen jeweils aus einigen bool-Werten und zwei Zeitstempeln, die in der Form HH:MM:SS eingelesen werden und dann als seit 00:00:00 vergangene Sekunden (HH*3600+MM*60+SS) in einem uint32_t gespeichert werden.

    Bei ~500mio Datensätzen sind das in jedem Datensatz 2 * 32bit - macht insgesamt fast 4GB die im Speicher verbraucht werden. Das möchte ich gerne optimieren.

    Meine Idee bisher ist folgende: HH würde ein 5-bit-unsigned-Integer passen, MM und SS würden jeweils in ein 6-bit-unsigned-Integer passen. Das wäre ein tatsächlicher Platzbedarf von 34bit, fast um die Hälfte weniger als zuvor. Nur - wie speichere ich das? Wäre z.B. ein bool[34] hier eine Lösung? Belegt ein boolscher Wert tatsächlich nur ein bit im Speicher? Und wie konvertiere ich z.B. bool[0] bis bool[4] plattformunabhängig in einen normalen unsigned integer (bigendian vs little endian?)

    Vielen Dank für eure Tipps
    sagredo



  • Ich persoenlich kann dir nur sagen, dass ein Bool 8 Bit also 1 Byte gross ist.

    http://www.datasource.de/programmierung/tab33_cppdatentypen.html



  • Komprimiere doch den Speicher.



  • Ja, das war auch meine Befürchtung. Ich meine mich aber zu erinnern, dass vector<bool> so implementiert ist, dass ein 5 bools auch tatsächlich nur 5 bits belegen. Die Frage ist: wenn ich hier einen vector<bool> verwende, gewinne ich dann überhaupt was oder ist der Overhead so groß, dass ich am Ende evt sogar über den bisherigen 64bit lande?



  • Ich habe gerade mal nachgeguckt.
    Ich habe hier noch Visual Studio 2008 aber in meinem Compiler ist der Abstand im Speicher mehr als 1bit.

    vector <bool> vec;
    vec.push_back(true);
    vec.push_back(false);
    
    cout << vec[0] << endl;
    cout << vec[1] << endl << endl;
    
    cout << &vec[0] << endl;
    cout << &vec[1] << endl;
    

    Ausgabe:

    0
    1

    003BFD9C ( <-- Speicheradresse vec[0];
    003BFDB4 ( <-- Speicheradresse vec[1];

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


  • Mod

    Unter die 32 Bit je Zeitstempel bekommst du das auf üblichen Maschinen nicht wirklich, außer mit Verrenkungen. Ein relativ einfache Verrenkung wäre, es als HH, MM, SS mit je einem char zu speichern, womit du von 4 Byte auf 3 Byte kommst. Und dafür baut dir der Compiler anderswo wahrscheinlich wieder Füllbytes ein, weil 3 eine doofe Zahl ist, die zu keinem üblichen Alignment passt. Und unter 3 Byte kannst du gar nicht kommen, da die Information einfach 17 Bit groß ist und ein Computer nur ganze Bytes adressieren kann.

    Fragen die aufkommen:
    Wieso ist das überhaupt ein Problem? Der Zeitstempel macht doch sicherlich nur einen kleinen Teil der Gesamtdaten aus. Klingt nach einer unnötigen Optimierung.

    Dieser Zeitstempel ist relativ willkürlich an beiden Enden abgeschnitten. Der Tag scheint egal zu sein, Sekundenbruchteile ebenfalls. Könnte man da weiter abschneiden? Bloß auf 2 Sekunden genau? Oder in 12-Stunden Zyklen? Dann käme man auf 16 Bit Information und 2 Byte mag der Computer sehr viel lieber als 3 Byte. Da könnte man beide Zeitstempel in einen einzigen 4-Byte-Wert packen, was der Computer sehr gerne hat.


  • Mod

    @Ruvi und sagredo: Ihr habt da so einiges falsch verstanden. Kleinste Adressierungseinheit in einem Computer ist immer 1 Byte, per Definition des Bytes. Das heißt, jedes Datum hat immer mindestens 1 Byte, die Frage ist nur, ob man vielleicht mehrere Daten in ein Byte packen kann. vector<bool> macht das, Bitfields machen das, bitset macht das. Es gibt viele Möglichkeiten. Aber in allen Fällen gilt: Die Gesamtdatenmenge kommt immer noch in Einheiten von ganzen Bytes. Bei einigen dieser Datentypen (vector<bool>) sogar noch mit einigem Overhead. Und in keinem Fall kann man die Adresse eines einzelnen Bits bekommen, siehe oben. Das geht einfach nicht.
    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.



  • @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!!!


Log in to reply