3. vector<bool> serialisieren

vector<bool> serialisieren

  • E

    Ich habe ein vector<bool> mit ca. 2*10^11 Bits (also x64-Anwendung) und möchte dies daher möglichst rasch aus einer einzigen Datei xyz.dat serialisieren (in beide Richtungen), finde dazu nichts Brauchbares im Netz. Bietet C++ 11 hier etwas Raffiniertes? Die rechnerische Erzeugung der 200 Mrd. Bits benötigt z.Z. (single-threaded) noch 52 min., das Laden von Festplatte sollte also rascher erfolgen.

    0
  • ?

    Also ~25GB Daten wenn ich richtig gerechnet habe? Für dein Problem ist mir nichts aus der STL bekannt und mich würde auch wundern wenn es dort sowas gibt. Also wirst wohl selbst immer 8 Bit nehmen müssen, zu einem Byte zusammen setzen und in eine Datei schreiben. Wird vermutlich nicht super schnell aber der Flaschenhals is vermutlich eh die Festplatte (außer du hast jetzt noch ein super schnelles Speichersystem). Brauchst du denn wirklich die Funktionalität von vector<bool> ? Ginge nicht auch ein vector<uint8_t> , wo du dir die Bit selbst raus ziehst wenn man gerade die Bit-Darstellung braucht?

    0
  • E

    Nein, unbedingt die bittable aus Effizienzgründen im Zugriff.

    0

  • 😮
    Bei solchen Mengen würde ich über Kompression nachdenken.

    0
  • E

    Das geht m.E. nicht, jedes Bit repräsentiert Primzahl ja/nein im Zahlenraum bis z.B. 2*10^11 (RAM-abhängig, passt zu 32 GB).

    0
  • ?

    Bei solchen Mengen würde ich über die Benutzung der STXXL (Standard Template Library for Extra Large Data Sets) nachdenken.

    0
  • ?

    Ist es dabei nicht eher problematisch dafür einen so so langen Speicherblock zu bekommen?

    0

  • Es gibt darauf keine Antwort, denn wie std::vector<bool> seine Daten ablegt ist implementationsspezifisch. Wenn du es fuer eine spezielle Implementation machen willst, ist es das einfachste den vector zu analysieren und dann mit fixen offsets und casts zu arbeiten. Oder eine eigene Implementation der Datenstruktur.

    0
  • Mod

    Jo, selber implementieren und das underlying array als char -Array in eine Datei schieben. Am Besten mit den C-Funktionen.

    0
  • F

    Erhard Henkes schrieb:

    Nein, unbedingt die bittable aus Effizienzgründen im Zugriff.

    Wenn du Wert auf Effizenz legst, und mit derart vielen simpel strukturierten Daten hantieren musst, könnte sich eventuell lohnen, das Bitset als Memory Mapped File vorzuhalten. Boost bietet da was Portables (habe damit selbst allerdings noch keine Erfahrungen gesammelt):

    http://www.boost.org/doc/libs/1_58_0/libs/iostreams/doc/classes/mapped_file.html

    So eine Variante hätte ein paar Vorteile:

    - Der User braucht nicht unbedingt 32GiB RAM, lediglich der virtuelle Addressraum sollte gross genug sein (also 64-Bit-Anwendung).
    - Laden/Speichern/Caching macht das Betriebssystem.
    - "Zero Copy" beim lesen/schreiben.
    - Datei ist wie zusammenhängeder Arbeitsspeicher addressierbar (via char* ).

    Man könnte sogar so verwegen sein, und einen std::vector<bool> via placement new (und eigenem Allocator) in der Datei konstruieren. Ich würde allerdings wie Arcoth eher dazu raten, das selbst auf einem char -Array zu implementieren, damit man eine portable Datenstruktur hat. Ein std::vector<bool> würde dann nämlich auch das "Dateiformat" Implementations-Abhängig machen. D.h. man kann die Datei wahrscheinlich nur "laden", wenn man exakt die selbe Standardbibliothek verwendet (und wenn man Pech hat müssen auch Compiler-Version/Flags, Debug/Release-Versionen der Standard-Lib, etc. übereinstimmen).

    Finnegan

    0
  • R

    Das geht m.E. nicht, jedes Bit repräsentiert Primzahl ja/nein im Zahlenraum bis z.B. 2*10^11

    Versteh ich das richtig ?
    Du willst für die info ob ne Zahl von 0 - 2 * 10^11 ne Primzahl ist, in nem vector<bool> oder ähnliches speichern ?

    ehrlich, wenn du den Speicher dafür nicht am Stück bekommst, bzw zwischenspeichern(platte) musst, geht dir jeglicher vorteil des Arrays verloren.
    200 * 10^9 < 2^38
    für die bitmask brauchtest also 2^34 byte ^^
    16 GB nur für die Bitmask ?

    Machts dann ned Sinn den lookup gleich auf nen Baum zu legen ?
    also in nen std::set<int64_t> und darauf bauen das der B-Baum lookup schneller ist also wie jegliches gerödel was brauchst um diese überdimensinale Bitmask zu verwalten ? Und dabei noch ne menge Speicher sparst (zumindest wenn die Primzahlen speicherst und nicht die "nicht Primzahlen" ^^)

    Ciao ...

    0
  • E

    Ich habe mit einem std::unordered_set<uint64_t> begonnen (unordered_set hat etwas schnelleren find-Zugriff als set) und via File auf Platte ausgetauscht. Das braucht aber zuviel Speicher im RAM. Man kommt damit bei 32 GB RAM auf meinem PC bis in die Gegend von 5 Milliarden. Mit vector<bool> schafft man immerhin etwas mehr als 200 Mrd. (braucht 25 Mrd. byte).
    Hat mich auch verwundert.

    Vgl.: http://www.michael-holzapfel.de/themen/primzahlen/pz-anzahl.htm
    1.000.000.000 50.847.534
    10.000.000.000 455.052.511
    Mit 8 byte pro Primzahl kommt man da schnell hoch im RAM, da unordered_set einen gigantischen overhead besitzt). Vector<bool> dagegen ist heute wirklich "lean". Dafür fehlt eine eingebaute Serialisierung (man kann die Bits nur als echte ASCII Zahlen in den Stream schieben).

    0

  • Bau dir doch nen Wrapper um nen vector<char>.

    0
  • ?

    DocShoe schrieb:

    Bau dir doch nen Wrapper um nen vector<char>.

    Du meintest vector<uint8_t>

    0
  • F

    RHBaum schrieb:

    Machts dann ned Sinn den lookup gleich auf nen Baum zu legen ?
    also in nen std::set<int64_t> und darauf bauen das der B-Baum lookup schneller ist also wie jegliches gerödel was brauchst um diese überdimensinale Bitmask zu verwalten ? Und dabei noch ne menge Speicher sparst (zumindest wenn die Primzahlen speicherst und nicht die "nicht Primzahlen" ^^)

    In dem Zahlenbereich kann man etwa zwischen 7 und 8 Milliarden Primzahlen erwarten. Selbst wenn man diese maximal speichereffizient in einer Dictionary-Datenstruktur untergebracht bekommt (also 8 Byte je Primzahl), dann benötigt man dafür schon etwa doppelt so viel Speicher wie für das Bitset. Wenn noch zusätzlicher Speicherbedarf für z.B. eine Baumstruktur hinzukommen, sieht es da wohl noch deutlich schlechter aus. Ich denke so ein Bitset ist schon eine ganz gute wahl für das spezifische Problem. Es hat ausserdem den Vorteil, dass man es für Einzelabfragen direkt adressieren kann. Das ist mindestens so gut wie eine Hash-Map, und muss auch nicht "rödeln" wenn das Bitset in einer Datei liegt. Für eine Einzelabfrage kann man direkt in O(1) an die richtige Dateiposition springen - im Gegensatz zum B-Baum, der dafür O(log(n)) Zugriffe braucht. Bei Bereichs-Abfragen (z.B. "gib mir mal alle Primzahlen in [a, b]") könnte allerdings der Baum wieder glänzen.

    Für Punkt-Abfragen würde ich aus dem Bauch heraus tippen, dass eine "Memory Mapped" Bitset nur schwer zu schlagen sein wird 😃

    Finnegan

    0
  • E

    Ich denke so ein Bitset ist schon eine ganz gute wahl für das spezifische Problem.

    Ich weiß es, weil ich es vergleichend ausprobiert habe.

    "Memory Mapped" Bitset

    Kannst Du mir da einen Link auf ein Beispiel geben? Habe ich bisher noch nicht gebraucht. Klingt interessant für den Austausch mit dem File. Ansonsten baue ich mir wirklich einen wrapper um vector<uint8_t> oder vector<uint64_t> (weiß nicht, was schneller läuft).

    unordered_set<uint64_t> primzahlen; // so fing ich an 
fstream myPrimesDatabase;
uint64_t j;
myPrimesDatabase.open("myPrimesDatabase.dat", fstream::in | fstream::binary);
//cout << "Primzahlen werden aus der Datei geladen ..." << endl;
while (!myPrimesDatabase.eof())
{
  myPrimesDatabase.read((char*)&j, sizeof(j));
  //cout << j << " ";
  primzahlen.insert(j);
}
myPrimesDatabase.close();

    Bei 8 Byte muss man weniger read aufrufen als bei einem Byte Größe. Vielleicht sollte man das sogar für das read noch größer basteln mit einer wrapper-class. Kenne mich da nicht gut aus mit Optimieren.

    0

  • Normalerweise macht man dann eine reserve auf die Groesse und dann ein einziges read aus der Datei.

    0
  • ?

    TGGC schrieb:

    Normalerweise macht man dann eine reserve auf die Groesse und dann ein einziges read aus der Datei.

    Du meinst wohl resize. Außerdem hat das Beispiel gerade irgendwie gar nichts mehr mit Bitmasken zu tun. Wenn man dann einen vector<uint8_t> oder vector<uint64_t> hat kann man alles in einer read Anweisung laden, wie TGGC schon sagte. Noch ein Vorschlag um Platz zu sparen wenn du das nicht eh schon gemacht hast: Alle geraden Zahlen würde ich gar nicht in die Bitmaske aufnehmen. Dann braucht man nur die hälfte Speicherplatz und bei ~25GB die im RAM liegen/aus einer Datei geladen sollen wäre das schon sinnvoll.

    0
  • F

    Erhard Henkes schrieb:

    "Memory Mapped" Bitset

    Kannst Du mir da einen Link auf ein Beispiel geben? Habe ich bisher noch nicht gebraucht. Klingt interessant für den Austausch mit dem File. Ansonsten baue ich mir wirklich einen wrapper um vector<uint8_t> oder vector<uint64_t> (weiß nicht, was schneller läuft).

    Ich bezog mich damit auf meinen vorangenagenen Beitrag. Konkreten Beispiel-Code habe ich dafür leider nicht, nur den den Doku-Link aus der iostreams-Bibliothek von Boost, in der das "Memory Mapping" für Dateien portabel implementiert ist:

    http://www.boost.org/doc/libs/1_58_0/libs/iostreams/doc/classes/mapped_file.html

    Das Ganze setzt also voraus, dass du ein wenig experimentierfreudig bist und die Muße hast dich durch die Doku zu arbeiten - der Dateizugriff läuft dabei etwas anders als das klassische open/read/write ab, und es ist nicht Teil der Standardbibliothek - du brauchst also Boost dafür 😃

    Nur für den Fall, dass dir nicht ganz klar sein sollte, was es mit dem "Memory Mapping" auf sich hat:
    Es handelt sich dabei um eine die Betriebssystem-Funktion, die auch bei Auslagerungsdateien/Swapspeicher zum Einsatz kommt. Dabei wird eine Datei in den Virtuellen Addressraum (also den "RAM") "abgebildet". Der Zugriff auf den Dateiinhalt erfolgt dabei über einen simplen char* (siehe boost::iostreams::mapped_file::data() ), der auf einen Speicherbereich von der Größe der gemappten Datei zeigt. Das Lesen/Schreiben der Daten wird dabei transparent vom Betriebssystem übernommen (inklusive effizentem Caching der Daten). Das einzige was man dabei selbst macht, ist in den Speicherbereich auf den der char* zeigt zu schreiben bzw. davon zu lesen (bzw. darin deine Bits zu "schubsen"). Speicherseiten, die nicht im physischen RAM vorliegen, werden dabei vom OS aus der Datei geladen, und gleichzeitig Seiten aus dem physischen Speicher in die Datei "ausgelagert", bzw. zurückgeschrieben.

    Ich habe wie schonmal erwähnt selbst noch nicht mit mapped_file gearbeitet, deswegen die Warnung von wegen "experimentierfreudig". Ich denke aber, dass das für deine Datenmassen ein schöner Anwendungsfall für ein solches Memory Mapping sind:
    Deine Datenstruktur ist simpel genug, um sie mal eben "roh" in einen char* "reinschreiben" zu können, und es gibt dir mit überschaubarem Aufwand die Flexibilität, die Daten dank OS eben nicht alle im physischen Arbeitsspeicher vorhalten zu müssen.
    Dennoch kann man mit den Daten arbeiten, als lägen sie dort.

    Finnegan

    0
  • E

    Alle geraden Zahlen würde ich gar nicht in die Bitmaske aufnehmen.

    Super Idee!

    0
  • ?

    Erhard Henkes schrieb:

    Alle geraden Zahlen würde ich gar nicht in die Bitmaske aufnehmen.

    Super Idee!

    Genausowenig die Zahlen, die durch 3 teilbar sind.

    Der Index für n ist dann n-n/2-n/3+n/6.

    Und dann natürlich auch für 5, 7, 11 und 13, musst von Hand schauen, wann aufhören.

    0
Anmelden zum Antworten