BitMagic
v.7.13.4
BitMagic wurde als Algebra of Sets-Toolkit für den Informationsabruf entwickelt, hat sich jedoch derzeit zu einer allgemeineren Data Science-Komponentenbibliothek für speicherkompakte Strukturen und Algorithmen für prägnante Datenvektoren entwickelt. BitMagic implementiert komprimierte Bitvektoren und Container (Vektoren) basierend auf Ideen der Bit-Slicing-Transformation, der Rank-Select-Komprimierung und der logischen Berechnung auf speicherkomprimierten Modellen.
Alle Succicnt-Container von BitMagic sind serialisierbar (mit Komprimierung mithilfe modernster binärer interpolativer Codierung) für effiziente Speicherung und Netzwerkübertragung. Alle Container sind in komprimierter Form schnell durchsuchbar.
BitMagic bietet eine Reihe von Methoden und Tools zum Entwerfen Ihrer Anwendungen, um HPC-Techniken zu nutzen, um im laufenden Betrieb Speicher zu sparen (und so mehr Daten in einer Recheneinheit unterzubringen) und die Speicher- und Verkehrsmuster beim Speichern von Datenvektoren und -modellen in Dateien oder Objekten zu verbessern Speichern (SQL oder NoSQL), optimieren die Systembandbreite von Low-Level (CPU-Caches) bis hin zum Netzwerk- und Speicheraustausch.
BitMagic ermöglicht zwei große Klassen von Szenarien:
BitMagic wurde als Bausteine verwendet für:
Bitte besuchen Sie unsere Anwendungsfallhinweise: http://bitmagic.io/use-case.html
Die BitMagic-Bibliothek ist eine Hochleistungsbibliothek, die Optimierungen für verschiedene Plattformen und Build-Ziele implementiert:
BitMagic verwendet ein datenparalleles vektorisiertes Design mit dem Ziel, nicht nur die beste Single-Threaded-Leistung bereitzustellen, sondern auch hochparallele Berechnungen auf Systemen mit vielen Kernen zu ermöglichen.
BitMagic verwendet eine Reihe von Komprimierungsalgorithmen, Filtern und Transformationen, um den Speicherbedarf, die Speicherkosten und die Netzwerkdatenübertragung zu reduzieren. http://bitmagic.io/design.html
Bitte besuchen Sie unsere tech.notes: http://bitmagic.io/articles.html
BitMagic unterstützt die Neuinterpretation von Bitvektoren als Sammlungen nicht überlappender Bereiche von Einsen, flankiert von Nullen (zum Beispiel: 011110110). Reguläre Mengenfunktionen stellen Mengenschnitt-/Vereinigungs-Intervalloperationen bereit, implementieren einen Intervall-Iterator und suchen nach Intervallgrenzen. Bereiche und Intervalle sind in der Bioinformatik von großem Nutzen, da Genomdaten häufig als Koordinatenbereiche annotiert werden. BitMagic bietet Bausteine für effiziente Operationen an als Bitvektoren kodierten Intervallen (Intervallanfang/-ende finden, prüfen, ob der Bereich ein Intervall ist, Intervalle iterieren).
BitMagic implementiert logische Operationen für die dreiwertige Logik von Wahr/Falsch/Unbekannt (auch trinäre Logik, dreiwertig, ternär) in einer kompakten Zwei-Bit-Vektordarstellung und unterstützt Invertierungs-, UND- und ODER-Operationen gemäß Kleenes Definitionen. https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic
BitMagic nutzt das Konzept der zweistufigen Serialisierung-Deserialisierung. Der Fokus liegt auf einer schnellen Deserialisierung. BitMagic implementiert eine API für eine schnelle Vektorbereichs-Deserialisierung und Sammel-Deserialisierung komprimierter BLOBs. Die ultimative Funktion von BitMagic ist die Möglichkeit, mit komprimierten Daten zu arbeiten.
Dies ist der Hauptbetriebszustand im RAM, in dem Vektoren in speicherkompakter Form gehalten werden. Succinct ist KEINE Komprimierung. Es ist möglich, auf zufällige Elemente in Containern zuzugreifen, Blöcke zu dekodieren, Vektoren zu iterieren, Aktualisierungen vorzunehmen und Suchalgorithmen auszuführen. Stage One bietet eine transparente Nutzung, die Vektoren sehen STL sehr ähnlich. Succinct ist speicherkompakt, aber nicht vollständig komprimiert.
BitMagic kann alle Container und Vektoren mit zusätzlicher Komprimierung basierend auf Heuristik- und Codecblöcken serialisieren. Die Arbeitspferd-Codierungstechniken sind: Binary Interpolative Coding (BIC) und Elias Gamma.
BitMagic-Container werden als „sparse“-Vektoren bezeichnet, aber tatsächlich funktionieren ihre Komprimierungsschemata sowohl für spärliche als auch für dichte Daten gut.
BitMagic wird anhand eines Gov2-Benchmark-Sets aus invertierten Listen und einer Anzahl proprietärer Datensätze getestet. http://bitmagic.io/bm5-cmpr.html
Die Deserialisierung geht immer auf die erste Stufe zurück, sodass die Daten nicht vollständig dekodiert werden, sondern stattdessen
prägnant im RAM. Unser Ziel besteht hier darin, sowohl den Speicherbedarf der Anwendung zu reduzieren als auch die Deserialisierungslatenz zu verbessern. Dekomprimierungsalgorithmen unterstützen die Deserialisierung beliebiger Bereiche oder erfassen sogar die Deserialisierung von Elementen.
BitMagic unterstützt prägnante (speicherkompakte) Vektoren basierend auf der Bittranspositionstransformation
Auch bekannt als Bit-Plane-Komprimierung (BPC) (auch bekannt als Bit-Slicing) plus Rank-Select-Komprimierung. BitMagic-prägnante Vektoren werden etwas irreführend als „sparse“ bezeichnet, funktionieren aber für dichte Vektoren einwandfrei.
Die Bittransposition löst zwei Zwecke: Sie gibt ungenutzte Bitebenen frei und isoliert Regelmäßigkeit und Entropie in separate (spärliche) Bitvektoren. Die Komprimierung auf Bitebenen bietet sowohl eine überlegene Speicherleistung als auch eine schnelle Suche. Eines der Entwurfsziele besteht darin, indexfreie Suchen auf prägnanten Vektoren unter Verwendung schneller vektorisierter logischer Operationen durchzuführen.
Die prägnanten BitMagic-Vektoren sind in speicherkomprimierter Form indexfrei durchsuchbar. Es ist schnell!
Die prägnante bittransponierte Implementierung funktioniert sowohl für ganzzahlige Vektoren (mit oder ohne Vorzeichen) als auch für String-Vektoren. Es konkurriert mit anderen prägnanten Schemata wie Präfixbäumen. Prägnante Vektoren können sowohl sortiert als auch unsortiert sein. Die Idee hier ähnelt Apache Arrow-Parquet, geht jedoch mit Bitebenenkomprimierung und umfassender Nutzung der beschleunigten Rank-Select-Komprimierung noch einen Schritt weiter.
BitMagic unterstützt die Weiterentwicklung der Serialisierung (Protokoll) – wenn sich das Serialisierungsformat ändert, bleiben alte gespeicherte Daten für den neuen Code lesbar. Alter Code kann neue BLOBs NICHT lesen. BitMagic ändert die Hauptversionsnummer, wenn sich das Serialisierungsformat ändert.
BitMagic implementiert Speicherprofilierungsaufrufe für alle Vektoren. Jeder Vektor kann auf den Speicherbedarf abgetastet werden, sodass das System der obersten Ebene die Speicherverwaltung basierend auf der Laufzeitspeicherprofilierung anpassen kann. Ein typischer Anwendungsfall ist das Zwischenspeichern von Objekten im Speicher mit Komprimierung in den RAM und anschließender Verlagerung auf die Festplatte basierend auf Ressourcenverbrauch und Kosten (dynamisches Gleichgewicht von Nachfrage und Angebot).
Ja! BitMagic unterstützt 64-Bit und kann mit 32-Bit-Adressraum (weniger Overhead) oder vollem 64-Bit-Adressraum verwendet werden. Der 32-Bit-Adressraum ist der Standardmodus. 2^31-1 Elemente sollten gut für IR- und Data-Science-Systeme mit kurzer bis mittlerer Reichweite geeignet sein. Der 64-Bit-Adressmodus ist mit #define BM64ADDR oder #include „bm64.h“ verfügbar. Die aktuelle 64-Bit-Implementierung ermöglicht 2^48-1 Vektorelemente für große Systeme.
BitMagic kompiliert und arbeitet mit WebAssmbly (emscripten). Die neuesten Versionen enthalten mehrere plattformspezifische Optimierungen. Die Leistungszahlen liegen nahe an nativem Code ohne SIMD (manchmal auch Afster). Eine Beispielkompilierungszeile würde wie folgt aussehen:
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...
WebAssembly SIMD wird unterstützt, ist jedoch standardmäßig nicht aktiviert. Verwenden Sie: #define BMWASMSIMDOPT um es zu aktivieren. Emscripten-cmd-Beispiel:
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -msse4.2 -msimd128 -D BMWASMSIMDOPT -s WASM=1 -s DISABLE_EXCEPTION_CATCHING=0 -fno-rtti
Die aktuelle Implementierung verwendet SSE4.2-Transkompilierung (über intrinsische Funktionen), daher ist -msse4.2 erforderlich.
BitMagic unterstützt die ARM-CPU vollständig. Alle Versionen werden mit Raspberry Pi 4 einem Stresstest unterzogen. BitMagic implementiert einige algorithmische Optimierungen und Verbesserungen speziell für ARM (wie die Verwendung von LZCNT-Anweisungen). Prägnante BitMagic-Container können auf eingebetteten Systemen für Edge-Computing mit begrenzter Menge an verfügbarem Speicher sehr nützlich sein.
Arm Neon SIMD-Unterstützung ist verfügbar (über die SSE2NEON-Bibliothek).
BitMagic C++ ist eine reine Header-Bibliothek (einfach zu erstellen und in Ihrem Projekt zu verwenden) und wird mit einer Reihe von Beispielen geliefert. Es wird NICHT empfohlen, Tests als Codebeispiel zur Untersuchung der Bibliotheksnutzung zu verwenden. Tests veranschaulichen nicht die besten Nutzungsmuster und -modelle und sind oft absichtlich ineffizient.
API-Dokumentation und Beispiele: http://www.bitmagic.io/apis.html
Tutorial zur Mengenalgebra: http://bitmagic.io/set-algebra.html
Anwendungsfälle und Anwendungshinweise: http://bitmagic.io/use-case.html
Technische Hinweise zur Leistungsoptimierung: http://bitmagic.io/articles.html
Doxygen: http://bitmagic.io/doxygen/html/modules.html
Apache 2.0.
Wichtig! Wir bitten Sie, das BitMagic-Projekt in allen abgeleiteten Arbeiten oder unseren veröffentlichten Materialien ausdrücklich zu erwähnen. Eine ordnungsgemäße Referenz auf Ihrer Produkt-/Projektseite ist eine VORAUSSETZUNG für die Nutzung der BitMagic-Bibliothek.
Die BitMagic-Bibliothek legt großen Wert auf Codequalität und Testabdeckung.
Als Bausteine-Bibliothek muss BitMagic stabil und konform sein, um nützlich zu sein.
Wir verlassen uns nicht nur auf Unit-Tests, unsere Tests nutzen häufig „Chaos-Tests“ (auch Fuzzing genannt), bei denen Stresstests auf randomisierten, generierten Mengen und randomisierten Operationen basieren. Wir erstellen und führen regelmäßig Testanzüge für den Release- und Debug-Modus für verschiedene Kombinationen von SIMD-Optimierungen durch.
Die Ausführung aller Varianten von Test-Builds dauert Tage, daher kann nicht garantiert werden, dass der funktionierende Master-Zweig immer perfekt ist. Für die Produktion verwenden Sie bitte stabile Github-Release-Branches oder Distributionen von SourceForge: https://sourceforge.net/projects/bmagic/files/
GitHub-Master akzeptiert Patch-Anfragen. Unsere Verzweigungsrichtlinie sieht vor, dass der Master zwischen den Releases nicht als vollständig stabil betrachtet werden kann. (Für Produktionsstabilität verwenden Sie bitte Release-Versionen)
Benötigen Sie Hilfe bei Zuordnungen zu Python und anderen Sprachen (BitMagic verfügt über C-Bindungen)
BitMagic C++ ist ein reines Header-Softwarepaket und Sie können wahrscheinlich einfach die Quellen nehmen und sie direkt in Ihr Projekt einfügen. Alle Quellen/Header der C++-Bibliothek befinden sich im Verzeichnis src.
Wenn Sie jedoch unsere Makefiles verwenden möchten, müssen Sie die folgenden einfachen Anweisungen befolgen:
Wenden Sie einige Umgebungsvariablen an, indem Sie bmenv.sh im Stammverzeichnis des Projekts ausführen:
$ source ./bmenv.sh
(Bitte verwenden Sie „.“ „./bmenv.sh“, um die Root-Umgebungsvariable anzuwenden.)
Verwenden Sie GNU make (gmake), um die Installation zu erstellen.
$make rebuild
oder (DEBUG-Version)
$gmake DEBUG=YES rebuild
Der Standard-Compiler unter Unix und CygWin ist g++. Wenn Sie die Standardeinstellung ändern möchten, können Sie dies in makefile.in tun (sollte ziemlich einfach sein)
Wenn Sie die Cygwin-Installation verwenden, befolgen Sie bitte die allgemeinen Unix-Empfehlungen. MSVC – Lösung und Projekte sind über CMAKE verfügbar.
Xcode – Projektdateien sind über CMAKE verfügbar.
BitMagic-Bibliothek für C- und JNI-Zuordnungen.
Die BitMagic-Bibliothek ist für die Sprache C verfügbar (dies ist in Arbeit). Das Hauptziel von C Build besteht darin, BitMagic mit anderen Programmiersprachen zu verbinden. C-Build befindet sich im Unterverzeichnis „lang-maps“.
C-Build erstellt Versionen des BitMagic-Builds für SSE und AVX und fügt CPU-Identifikation hinzu, sodass das System der oberen Ebene dynamische CPU-Identifikation und Code-Versand unterstützen kann.
Der C-Build verwendet den C++-Compiler, jedoch kein RTTI, keine Ausnahmen (simuliert mit Weitsprung) und keine C++-Speicherverwaltung, sodass er C++-sprachenneutral und ohne Laufzeitabhängigkeiten ist. Algorithmen und Verhalten werden von C und C++ gemeinsam genutzt.
Aktueller Entwicklungsstand:
Die Python-Unterstützung steht noch aus und wir brauchen hier Hilfe. Wenn Sie sich für Python begeistern und glauben, dass Sie helfen können, wenden Sie sich bitte an: anatoliy.kuznetsov @ yahoo dot com
Die BitMagic-Bibliothek erfordert CXX-11. Es verwendet Bewegungssemantik, Noexept, Initialisierungslisten und Threads. Die nächste öffentliche Version wird CXX-17 verwenden (constexpr ifs usw.).
###Feinabstimmung und Optimierungen:
Alle BitMagic-Feinabstimmungsparameter werden durch die Präprozessordefinitionen (und Zielarch.-spezifischen Compilerschlüssel für die Codegenerierung) gesteuert.
| #definieren | Beschreibung | Breite |
|---|---|---|
| BMSSE2OPT | SSE2-Codeoptimierungen | 128-Bit |
| BMSSE42OPT | SSE4.2-Codeoptimierungen plus POPCNT, BSF usw | 128-Bit |
| BMAVX2OPT | AVX2-, POPCNT-, LZCNT-, BMI1- und BMI2-Optimierungen | 256-Bit |
| BMAVX512OPT | AVX-512, (experimentell) | 512-Bit |
| BMWASMSIMDOPT | WebAssembly SIMD-Optimierungen (über SSE4.2) | 128-Bit |
| DBMNEONOPT | Arm Neon SIMD-Optimierungen (über SSE2-Übersetzung) | 128-Bit |
####Einschränkungen:
SIMD-Optimierungsdefinitionen schließen sich gegenseitig aus, Sie können NICHT gleichzeitig BMSSE42OPT und BMAVX2OPT haben. Wählen Sie nur eine aus.
Die BM-Bibliothek unterstützt NICHT mehrere Codepfade und die Identifizierung von Laufzeit-CPUs. Sie müssen einen Build speziell für Ihr Zielsystem erstellen oder einen standardmäßigen portablen Build verwenden.
####Beispiele:
BitMagic-Beispiele und -Tests können mit GCC mithilfe der Cmd-Zeileneinstellungen erstellt werden:
make BMOPTFLAGS=-DBMAVX2OPT rebuild
oder
make BMOPTFLAGS=-DBMSSE42OPT rebuild
Es wendet automatisch den richtigen Satz von Compiler-Flags (GCC) für den Ziel-Build an.
CMAKE
cd build
cmake -DBMOPTFLAGS:STRING=BMSSE42OPT ..
make
ODER
cmake -DBMOPTFLAGS:STRING=BMAVX2OPT ..
Die BM-Bibliothek unterstützt das Schlüsselwort „restrict“. Einige Compiler (z. B. Intel C++) generieren besseren Code (Ladespeicher außerhalb der Reihenfolge), wenn das Schlüsselwort „restrict“ hilfreich ist. Diese Option ist standardmäßig deaktiviert, da die meisten C++-Compiler sie nicht unterstützen. Um es zu aktivieren, definieren Sie bitte BM_HASRESTRICT in Ihrem Projekt. Einige Compiler verwenden zu diesem Zweck das Schlüsselwort „__restrict“. Um dies zu korrigieren, definieren Sie das Makro BMRESTRICT, um das Schlüsselwort zu korrigieren.
Wenn Sie die BM-Bibliothek in einem „No-STL-Projekt“ (wie eingebetteten Systemen) verwenden möchten, definieren Sie BM_NO_STL.
Diese Regel gilt nur für die Kernmethoden bm::bvector<>. Hilfsalgorithmen, Beispiele usw. würden weiterhin STL verwenden.
Folgen Sie uns auf Twitter: https://twitter.com/bitmagicio
Vielen Dank, dass Sie die BitMagic-Bibliothek nutzen!
E-Mail: [email protected]
WEBSITE: http://bitmagic.io
GitHub: https://github.com/tlk00/BitMagic
