BitMagique
v.7.13.4
BitMagic a été créé en tant que boîte à outils d'algèbre des ensembles pour la recherche d'informations, mais a actuellement évolué vers une bibliothèque de composants de science des données plus générale pour les structures compactes de mémoire et les algorithmes sur des vecteurs de données succincts. BitMagic implémente des vecteurs de bits compressés et des conteneurs (vecteurs) basés sur des idées de transformation de découpage de bits, de compression Rank-Select et de calcul logique sur des modèles compressés en mémoire.
Tous les conteneurs succincts BitMagic sont sérialisables (avec compression utilisant un codage interpolatif binaire de pointe) pour un stockage et un transfert réseau efficaces. Tous les conteneurs peuvent être recherchés rapidement sous forme compressée.
BitMagic propose des ensembles de méthodes et d'outils pour concevoir vos applications afin d'utiliser les techniques HPC pour économiser de la mémoire à la volée (et ainsi pouvoir insérer plus de données dans une unité de calcul), améliorer les modèles de stockage et de trafic lors du stockage de vecteurs de données et de modèles dans des fichiers ou des objets. (SQL ou noSQL), optimisez la bande passante des systèmes depuis le bas niveau (caches CPU) jusqu'à l'échange de réseau et de stockage.
BitMagic facilite deux grandes classes de scénarios :
BitMagic a été utilisé comme élément de base pour :
Veuillez consulter nos notes de cas d'utilisation : http://bitmagic.io/use-case.html
La bibliothèque BitMagic est une bibliothèque hautes performances, implémentant des optimisations pour une variété de plates-formes et de cibles de build :
BitMagic utilise une conception vectorisée de données parallèles dans le but non seulement de fournir les meilleures performances monothread, mais également de faciliter le calcul hautement parallèle sur des systèmes à plusieurs cœurs.
BitMagic utilise une suite d'algorithmes de compression, de filtres et de transformations pour réduire l'empreinte mémoire, les coûts de stockage et le transfert de données réseau. http://bitmagic.io/design.html
Veuillez visiter nos notes techniques : http://bitmagic.io/articles.html
BitMagic prend en charge la réinterprétation des vecteurs de bits sous forme de collections de plages de 1 ne se chevauchant pas flanquées de 0 (par exemple : 011110110). Les fonctions d'ensemble régulières fournissent des opérations d'intervalle d'intersection/union d'ensemble, implémentent un itérateur d'intervalle et recherchent les limites d'intervalle. Les plages et les intervalles sont d'une grande utilité en bioinformatique, car les données génomiques sont souvent annotées sous forme de plages de coordonnées. BitMagic propose des éléments de base pour des opérations efficaces sur des intervalles codés sous forme de vecteurs binaires (trouver le début/la fin de l'intervalle, vérifier si la plage est une valeur inentrval, itérer les intervalles
BitMagic implémente des opérations logiques pour la logique à 3 valeurs Vrai/Faux/Inconnu (également logique trivalente, trivalente, ternaire) dans une représentation compacte à deux vecteurs binaires, prenant en charge les opérations Inverser, ET ou OU suivant les définitions de Kleene. https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic
BitMagic utilise le concept de sérialisation-désérialisation en deux étapes. L'accent est mis sur la désérialisation rapide. BitMagic implémente une API pour une désérialisation rapide de la plage vectorielle et rassemble la désérialisation des BLOB compressés. La fonctionnalité ultime de BitMagic est la capacité de travailler avec des données compressées.
Il s'agit du principal état opérationnel de la RAM, dans lequel les vecteurs sont conservés sous forme mémoire compacte. Succinct n’est PAS une compression. Il est possible d'accéder à des éléments aléatoires dans des conteneurs, de décoder des blocs, d'itérer des vecteurs, d'effectuer des mises à jour, d'exécuter des algorithmes de recherche. Stage One offre une utilisation transparente, ses vecteurs ressemblent beaucoup à STL. Succinct est une mémoire compacte mais pas entièrement compressée.
BitMagic peut sérialiser tous les conteneurs et vecteurs avec une compression supplémentaire basée sur des blocs d'heuristiques et de codecs. Les techniques de codage les plus performantes sont : le codage interpolatif binaire (BIC) et Elias Gamma.
Les conteneurs BitMagic sont appelés vecteurs « clairsemés », mais en fait, ses schémas de compression fonctionnent bien pour les données clairsemées et denses.
BitMagic est testé sur l'ensemble de référence Gov2 de listes inversées et de nombre d'ensembles de données propriétaires. http://bitmagic.io/bm5-cmpr.html
La désérialisation revient toujours à la première étape, donc les données ne sont pas complètement décodées mais plutôt
succinct en RAM. Notre objectif ici est à la fois de réduire l’empreinte mémoire des applications et d’améliorer la latence de désérialisation. Les algorithmes de décompression prennent en charge la désérialisation de plages arbitraires ou même rassemblent la désérialisation d'éléments.
BitMagic prend en charge les vecteurs succincts (mémoire compacte) basés sur la transformation de transposition de bits
également connue sous le nom de compression par plan de bits (BPC) (alias bit-slicing) plus compression Rank-Select. Les vecteurs succints BitMagic étiquetés de manière quelque peu trompeuse « clairsemés », mais ils fonctionnent très bien pour les vecteurs denses.
La transposition de bits répond à deux objectifs : libérer les bits bruts inutilisés et isoler la régularité et l'entropie dans des vecteurs de bits séparés (clairsemés). La compression sur les plans de bits offre à la fois des performances de mémoire supérieures et une recherche rapide. L'un des objectifs de conception consiste à effectuer des recherches sans index sur des vecteurs succincts à l'aide d'opérations logiques vectorisées rapides.
Les vecteurs succincts BitMagic sont consultables sans index sous forme compressée en mémoire. C'est rapide !
L'implémentation succincte de transposition de bits fonctionne bien pour les vecteurs entiers (signés ou non signés) ainsi que pour les vecteurs de chaînes. Il rivalise avec d’autres schémas succincts comme les arbres de préfixes. Les vecteurs succincts peuvent être à la fois triés et non triés. L'idée ici est similaire à celle d'Apache Arrow-Parquet, mais elle va plus loin avec la compression par plan de bits et l'utilisation intensive de la compression accélérée Rank-Select.
BitMagic prend en charge l'évolution de la sérialisation (protocole) : si le format de sérialisation change, les anciennes données enregistrées restent lisibles par le nouveau code. L'ancien code ne pourra PAS lire les nouveaux BLOB. BitMagic change le numéro de version majeure lorsque le format de sérialisation change.
BitMagic implémente des appels de profilage de mémoire pour tous les vecteurs. N'importe quel vecteur peut être échantillonné pour l'empreinte mémoire afin que le système de niveau supérieur puisse adapter la gestion de la mémoire en fonction du profilage de la mémoire d'exécution. Le cas d'utilisation typique est le cache mémoire d'objets avec compression dans la RAM, puis expulsion vers le disque en fonction de la consommation et des coûts des ressources (équilibre dynamique entre l'offre et la demande).
Oui! BitMagic prend en charge 64 bits et peut être utilisé avec un espace d'adressage de 32 bits (moins de surcharge) ou un espace d'adressage complet de 64 bits. L'espace d'adressage de 32 bits est le mode par défaut. Les éléments 2 ^ 31-1 devraient convenir aux systèmes IR et de science des données à courte et moyenne portée. Le mode d'adresse 64 bits est disponible en utilisant #define BM64ADDR ou #include "bm64.h". L'implémentation actuelle de 64 bits autorise 2 ^ 48-1 éléments vectoriels pour les systèmes à grande échelle.
BitMagic compile et fonctionne avec WebAssmbly (emscripten). Les dernières versions incluent plusieurs ajustements spécifiques à la plate-forme. Les chiffres de performances sont proches du code natif sans SIMD (parfois après). Un exemple de ligne de compilation ressemblerait à :
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...
WebAssembly SIMD est pris en charge mais il n'est pas activé par défaut. Utilisez : #define BMWASMSIMDOPT pour l'activer. Exemple de cmd Emscript :
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
L'implémentation actuelle utilise la trans-compilation SSE4.2 (via des intrinsèques), donc -msse4.2 est nécessaire.
BitMagic prend entièrement en charge le processeur ARM. Toutes les versions sont testées sous contrainte avec Raspberry Pi 4. BitMagic implémente quelques ajustements algorithmiques et améliorations spécifiques à ARM (comme l'utilisation de l'instruction LZCNT). Les conteneurs succincts BitMagic peuvent être très utiles sur les systèmes embarqués pour l'informatique de pointe avec une quantité de mémoire disponible limitée.
La prise en charge Arm Neon SIMD est disponible (via la bibliothèque SSE2NEON).
BitMagic C++ est une bibliothèque d'en-tête uniquement (facile à créer et à utiliser dans votre projet) et elle est livrée avec un ensemble d'exemples. Il n'est PAS conseillé d'utiliser des tests comme exemple de code pour étudier l'utilisation de la bibliothèque. Les tests n’illustrent pas les meilleurs modèles et modèles d’utilisation et sont souvent intentionnellement inefficaces.
Documentation et exemples d'API : http://www.bitmagic.io/apis.html
Tutoriel d'algèbre des ensembles : http://bitmagic.io/set-algebra.html
Cas d'utilisation et notes d'application : http://bitmagic.io/use-case.html
Notes techniques sur l'optimisation des performances : http://bitmagic.io/articles.html
Doxygen : http://bitmagic.io/doxygen/html/modules.html
Apache2.0.
Important! Nous vous demandons de mentionner explicitement le projet BitMagic dans tout travail dérivé ou nos documents publiés. Une référence appropriée sur votre page produit/projet est une EXIGENCE pour utiliser la bibliothèque BitMagic.
La bibliothèque BitMagic accorde une attention particulière à la qualité du code et à la couverture des tests.
En tant que bibliothèque de blocs de construction, BitMagic doit être stable et conforme pour être utile.
Nous ne nous appuyons pas uniquement sur les tests unitaires, nos tests utilisent souvent des « tests de chaos » (alias fuzzing) où les tests de résistance sont basés sur des ensembles générés et randomisés et des opérations randomisées. Nous construisons et exécutons régulièrement des combinaisons de tests pour les modes Release et Debug pour diverses combinaisons d'optimisations SIMD.
Toutes les variantes des versions de test prennent des jours à s'exécuter, donc la branche principale fonctionnelle n'est PAS garantie d'être parfaite à tout moment. Pour la production, veuillez utiliser les branches ou distributions stables de Github de SourceForge : https://sourceforge.net/projects/bmagic/files/
Le maître GitHub accepte les demandes de correctifs. Notre politique de branchement est que le maître ne peut pas être considéré comme totalement stable entre les versions. (pour la stabilité de la production, veuillez utiliser les versions release)
Besoin d'aide pour les mappages vers Python et d'autres langages (BitMagic a des liaisons C)
BitMagic C++ est un progiciel uniquement en-tête et vous pouvez probablement simplement prendre les sources et les insérer directement dans votre projet. Toutes les sources/en-têtes de la bibliothèque C++ se trouvent dans le répertoire src.
Cependant, si vous souhaitez utiliser nos makefiles, vous devez suivre les instructions simples suivantes :
Appliquez quelques variables d'environnement en exécutant bmenv.sh dans le répertoire racine du projet :
$ source ./bmenv.sh
(veuillez utiliser "." "./bmenv.sh" pour appliquer la variable d'environnement racine)
utilisez GNU make (gmake) pour créer l'installation.
$make rebuild
ou (version DEBUG)
$gmake DEBUG=YES rebuild
Le compilateur par défaut sous Unix et CygWin est g++. Si vous souhaitez modifier la valeur par défaut, vous pouvez le faire dans makefile.in (cela devrait être assez facile à faire)
Si vous utilisez l'installation de Cygwin, veuillez suivre les recommandations générales d'Unix. MSVC - la solution et les projets sont disponibles via CMAKE.
Xcode - les fichiers de projet sont disponibles via CMAKE.
Bibliothèque BitMagic pour les mappages C et JNI.
La bibliothèque BitMagic est disponible pour le langage C (c'est un travail en cours). L'objectif principal de la version C est de relier BitMagic à d'autres langages de programmation. La build C se trouve dans le sous-répertoire "lang-maps".
La version C crée des versions de la version BitMagic pour SSE et AVX et ajoute l'identification du processeur, afin que le système de niveau supérieur puisse prendre en charge l'identification dynamique du processeur et la répartition du code.
La version C utilise le compilateur C++, mais n'utilise pas RTTI, les exceptions (simulées avec un saut en longueur) et la gestion de la mémoire C++, elle est donc neutre en termes de langage C++, sans dépendances d'exécution. Les algorithmes et les comportements sont partagés entre C et C++.
État actuel du développement :
Le support de Python est en attente et nous avons besoin d'aide ici. Si vous êtes enthousiasmé par Python et pensez pouvoir aider, veuillez contacter : anatoliy.kuznetsov @ yahoo dot com
La bibliothèque BitMagic nécessite CXX-11. Il utilise la sémantique de déplacement, les noexepts, les listes d'initialisation et les threads. La prochaine version publique utilisera CXX-17 (constexpr ifs, etc.).
###Réglage fin et optimisations :
Tous les paramètres de réglage fin de BitMagic sont contrôlés par les définitions du préprocesseur (et par les clés de compilateur spécifiques à l'arch cible pour la génération de code).
| #définir | Description | Largeur |
|---|---|---|
| BMSSE2OPT | Optimisations du code SSE2 | 128 bits |
| BMSSE42OPT | Optimisations du code SSE4.2 plus POPCNT, BSF, etc. | 128 bits |
| BMAVX2OPT | Optimisations AVX2, POPCNT, LZCNT, BMI1, BMI2 | 256 bits |
| BMAVX512OPT | AVX-512, (expérimental) | 512 bits |
| BMWASMSIMDOPT | Optimisations WebAssembly SIMD (via SSE4.2) | 128 bits |
| DBMNEONOPT | Optimisations Arm Neon SIMD (via la traduction SSE2) | 128 bits |
####Limites:
Les définitions d'optimisation SIMD s'excluent mutuellement, vous ne pouvez PAS avoir BMSSE42OPT et BMAVX2OPT en même temps. Choisissez-en un seul.
La bibliothèque BM ne prend PAS en charge plusieurs chemins de code ni l'identification du processeur d'exécution. Vous devez créer spécifiquement pour votre système cible ou utiliser la version portable par défaut.
####Exemples :
Des exemples et des tests BitMagic peuvent être créés avec GCC à l'aide des paramètres de la ligne cmd :
make BMOPTFLAGS=-DBMAVX2OPT rebuild
ou
make BMOPTFLAGS=-DBMSSE42OPT rebuild
Il applique automatiquement le bon ensemble d'indicateurs du compilateur (GCC) pour la version cible.
CMAKE
cd build
cmake -DBMOPTFLAGS:STRING=BMSSE42OPT ..
make
OU
cmake -DBMOPTFLAGS:STRING=BMAVX2OPT ..
La bibliothèque BM prend en charge le mot-clé "restrict", certains compilateurs (par exemple Intel C++) génèrent un meilleur code (stockages de chargement dans le désordre) lorsque le mot-clé restrict est utile. Cette option est désactivée par défaut car la plupart des compilateurs C++ ne la prennent pas en charge. Pour l'activer, veuillez #define BM_HASRESTRICT dans votre projet. Certains compilateurs utilisent le mot-clé "__restrict" à cet effet. Pour le corriger, définissez la macro BMRESTRICT pour corriger le mot-clé.
Si vous souhaitez utiliser la bibliothèque BM dans un "projet sans STL" (comme les systèmes embarqués), définissez BM_NO_STL.
Cette règle s'applique uniquement aux méthodes principales bm::bvector<>. Les algorithmes auxiliaires, les exemples, etc. utiliseraient toujours STL.
Suivez-nous sur Twitter : https://twitter.com/bitmagicio
Merci d'utiliser la bibliothèque BitMagic !
e-mail : [email protected]
Site WEB : http://bitmagic.io
GitHub : https://github.com/tlk00/BitMagic
