CRoaring
Version 4.2.1
Bitmaps Roaring portables en C (et C++) avec prise en charge complète de votre compilateur préféré (GNU GCC, clang de LLVM, Visual Studio, Apple Xcode, Intel oneAPI). Inclus dans la liste Awesome C des logiciels open source C.
Les bitsets, également appelés bitmaps, sont couramment utilisés comme structures de données rapides. Malheureusement, ils peuvent utiliser trop de mémoire. Pour compenser, nous utilisons souvent des bitmaps compressés.
Les bitmaps rugissants sont des bitmaps compressés qui ont tendance à surpasser les bitmaps compressés conventionnels tels que WAH, EWAH ou Concise. Ils sont utilisés par plusieurs systèmes majeurs tels qu'Apache Lucene et des systèmes dérivés tels que Solr et Elasticsearch, Metamarkets' Druid, LinkedIn Pinot, Netflix Atlas, Apache Spark, OpenSearchServer, Cloud Torrent, Whoosh, InfluxDB, Pilosa, Bleve, Microsoft Visual Studio Team. Services (VSTS) et Apache Kylin d'eBay. La bibliothèque CRoaring est utilisée dans plusieurs systèmes tels que Apache Doris, ClickHouse, Redpanda et StarRocks. Le moteur SQL YouTube, Google Procella, utilise des bitmaps Roaring pour l'indexation.
Nous avons publié un article évalué par des pairs sur la conception et l'évaluation de cette bibliothèque :
Les bitmaps rugissants fonctionnent bien dans de nombreuses applications importantes :
Utilisez Roaring pour la compression bitmap autant que possible. N'utilisez pas d'autres méthodes de compression bitmap (Wang et al., SIGMOD 2017)
Il existe une spécification de format sérialisé pour l'interopérabilité entre les implémentations. Par conséquent, il est possible de sérialiser un Roaring Bitmap à partir de C++, de le lire en Java, de le modifier, de le sérialiser et de le lire en Go et Python.
L'objectif principal de CRoaring est de fournir une implémentation de bas niveau hautes performances qui tire pleinement parti du matériel le plus récent. Les bitmaps rugissants sont déjà disponibles sur diverses plates-formes via des implémentations Java, Go, Rust.... CRoaring est une bibliothèque qui cherche à obtenir des performances supérieures en restant proche du matériel le plus récent.
(c) 2016-... Les auteurs CRoaring.
Presque personne n’a accès à un véritable système big-endian. Néanmoins, nous prenons en charge les systèmes big-endian tels que IBM s390x via des émulateurs --- à l'exception de la sérialisation IO qui n'est prise en charge que sur les systèmes small-endian (voir numéro 423).
La bibliothèque CRoaring peut être fusionnée en un seul fichier source, ce qui facilite son intégration dans d'autres projets. De plus, en permettant de compiler tout le code critique dans une seule unité de compilation, cela peut améliorer les performances. Pour la justification, veuillez consulter la documentation SQLite ou l'entrée Wikipédia correspondante. Les utilisateurs qui choisissent cette voie n'ont pas besoin de s'appuyer sur le système de construction de CRoaring (basé sur CMake).
Nous proposons des fichiers fusionnés dans le cadre de chaque version.
Les utilisateurs de Linux ou de macOS peuvent suivre les instructions suivantes s'ils disposent d'un compilateur C ou C++ récent installé et d'un utilitaire standard ( wget ).
wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.c
wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.h
wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.hh
demo.c avec ce contenu : #include demo.cpp avec ce contenu : # include < iostream >
# include " roaring.hh " // the amalgamated roaring.hh includes roaring64map.hh
# include " roaring.c "
int main () {
roaring::Roaring r1;
for ( uint32_t i = 100 ; i < 1000 ; i++) {
r1. add (i);
}
std::cout << " cardinality = " << r1. cardinality () << std::endl;
roaring::Roaring64Map r2;
for ( uint64_t i = 18000000000000000100ull ; i < 18000000000000001000ull ; i++) {
r2. add (i);
}
std::cout << " cardinality = " << r2. cardinality () << std::endl;
return 0 ;
} cc -o demo demo.c
c++ -std=c++11 -o demopp demo.cpp
./demo cardinality = 900
1000
./demopp cardinality = 900
cardinality = 900
Si vous aimez CMake et CPM, vous pouvez ajouter seulement quelques lignes dans votre fichier CMakeLists.txt pour récupérer une version CRoaring . Consultez notre démonstration CPM pour plus de détails.
cmake_minimum_required ( VERSION 3.10)
project (roaring_demo
LANGUAGES CXX C
)
set (CMAKE_CXX_STANDARD 17)
set (CMAKE_C_STANDARD 11)
add_executable (hello hello.cpp)
# You can add CPM.cmake like so:
# mkdir -p cmake
# wget -O cmake/CPM.cmake https://github.com/cpm-cmake/CPM.cmake/releases/latest/download/get_cpm.cmake
include (cmake/CPM.cmake)
CPMAddPackage(
NAME roaring
GITHUB_REPOSITORY "RoaringBitmap/CRoaring"
GIT_TAG v2.0.4
OPTIONS "BUILD_TESTING OFF"
)
target_link_libraries (hello roaring::roaring) Si vous aimez CMake, vous pouvez ajouter seulement quelques lignes dans votre fichier CMakeLists.txt pour récupérer une version CRoaring . Voir notre démonstration pour plus de détails.
Si vous avez installé la bibliothèque CRoaring localement, vous pouvez l'utiliser avec la fonction find_package de CMake comme dans cet exemple :
cmake_minimum_required ( VERSION 3.15)
project (test_roaring_install VERSION 0.1.0 LANGUAGES CXX C)
set (CMAKE_CXX_STANDARD 11)
set (CMAKE_CXX_STANDARD_REQUIRED ON )
set (CMAKE_C_STANDARD 11)
set (CMAKE_C_STANDARD_REQUIRED ON )
find_package (roaring REQUIRED)
file (WRITE main.cpp "
#include Pour générer vous-même les fichiers fusionnés, vous pouvez appeler un script bash...
./amalgamation.sh Si vous préférez une sortie silencieuse, vous pouvez utiliser la commande suivante pour rediriger stdout :
./amalgamation.sh > /dev/null (Les shells Bash sont standard sous Linux et macOS. Les shells Bash sont disponibles sous Windows dans le cadre du bureau GitHub sous le nom Git Shell . Donc, si vous avez cloné le référentiel CRoaring GitHub depuis le bureau GitHub, vous pouvez cliquer avec le bouton droit sur CRoaring , sélectionnez Git Shell , puis entrez les commandes ci-dessus.)
Il n'est pas nécessaire d'invoquer le script dans le répertoire CRoaring. Vous pouvez l'invoquer à partir de n'importe quel répertoire dans lequel vous souhaitez que les fichiers de fusion soient écrits.
Il générera trois fichiers pour les utilisateurs C : roaring.h , roaring.c et amalgamation_demo.c ... ainsi que quelques brèves instructions. Le fichier amalgamation_demo.c est un court exemple, tandis que roaring.h et roaring.c sont des fichiers "fusionnés" (y compris tous les fichiers sources et d'en-tête du projet). Cela signifie que vous pouvez simplement copier les fichiers roaring.h et roaring.c dans votre projet et être prêt à partir ! Pas besoin de produire une bibliothèque ! Voir le fichier amalgamation_demo.c .
L'interface C se trouve dans les fichiers
Nous disposons également d'une interface C++ :
Certains utilisateurs doivent gérer de gros volumes de données. Il peut être important que ces utilisateurs connaissent les fonctions addMany (C++) roaring_bitmap_or_many (C) car il est beaucoup plus rapide et économique d'ajouter des valeurs par lots lorsque cela est possible. De plus, appeler périodiquement les fonctions runOptimize (C++) ou roaring_bitmap_run_optimize (C) peut aider.
Nous disposons de microbenchmarks construits avec les Google Benchmarks. Sous Linux ou macOS, vous pouvez les exécuter comme suit :
cmake -B build -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build build
./build/microbenchmarks/bench
Par défaut, les outils de référence sélectionnent un ensemble de données (par exemple, CRoaring/benchmarks/realdata/census1881 ). Nous disposons de plusieurs ensembles de données et vous pouvez en choisir d’autres :
./build/microbenchmarks/bench benchmarks/realdata/wikileaks-noquotes
Vous pouvez désactiver certaines fonctionnalités à des fins d'analyse comparative. Par exemple, en supposant que vous disposez d'un processeur x64, vous pouvez comparer le code sans AVX-512 même si votre processeur et votre compilateur le prennent en charge :
cmake -B buildnoavx512 -D ROARING_DISABLE_AVX512=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build buildnoavx512
./buildnoavx512/microbenchmarks/bench
Vous pouvez également effectuer une analyse comparative sans AVX ou AVX-512 :
cmake -B buildnoavx -D ROARING_DISABLE_AVX=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build buildnoavx
./buildnoavx/microbenchmarks/bench
Pour les utilisateurs généraux, CRoaring appliquerait l'allocateur par défaut sans codes supplémentaires. Mais un hook de mémoire global est également fourni pour ceux qui souhaitent un allocateur de mémoire personnalisé. Voici un exemple :
#include Par défaut nous utilisons :
static roaring_memory_t global_memory_hook = {
. malloc = malloc ,
. realloc = realloc ,
. calloc = calloc ,
. free = free ,
. aligned_malloc = roaring_bitmap_aligned_malloc ,
. aligned_free = roaring_bitmap_aligned_free ,
}; Nous exigeons que les fonctions free / aligned_free suivent la convention C où free(NULL) / aligned_free(NULL) n'ont aucun effet.
Cet exemple suppose que CRoaring a été construit et que vous établissez un lien avec la bibliothèque correspondante. Par défaut, CRoaring installera ses fichiers d'en-tête dans un répertoire roaring . Si vous travaillez à partir du script de fusion, vous pouvez ajouter la ligne #include "roaring.c" si vous n'établissez pas de lien avec une bibliothèque CRoaring prédéfinie et remplacer #include par #include "roaring.h" .
#include Nous prenons également en charge les bitmaps compressés 64 bits efficaces en C :
roaring64_bitmap_t *r2 = roaring64_bitmap_create();
for ( uint64_t i = 100 ; i < 1000 ; i++) roaring64_bitmap_add(r2, i);
printf ( " cardinality (64-bit) = %d n " , ( int ) roaring64_bitmap_get_cardinality(r2));
roaring64_bitmap_free (r2); L'API est similaire aux bitmaps 32 bits conventionnels. Veuillez consulter le fichier d'en-tête roaring64.h (à comparer avec roaring.h ).
Nous prenons en charge les jeux de bits de convention (non compressés) dans le cadre de la bibliothèque.
Exemple simple :
bitset_t * b = bitset_create ();
bitset_set ( b , 10 );
bitset_get ( b , 10 ); // returns true
bitset_free ( b ); // frees memoryExemple plus avancé :
bitset_t * b = bitset_create ();
for ( int k = 0 ; k < 1000 ; ++ k ) {
bitset_set ( b , 3 * k );
}
// We have bitset_count(b) == 1000.
// We have bitset_get(b, 3) is true
// You can iterate through the values:
size_t k = 0 ;
for ( size_t i = 0 ; bitset_next_set_bit ( b , & i ); i ++ ) {
// You will have i == k
k += 3 ;
}
// We support a wide range of operations on two bitsets such as
// bitset_inplace_symmetric_difference(b1,b2);
// bitset_inplace_symmetric_difference(b1,b2);
// bitset_inplace_difference(b1,b2);// should make no difference
// bitset_inplace_union(b1,b2);
// bitset_inplace_intersection(b1,b2);
// bitsets_disjoint
// bitsets_intersectDans certains cas, vous souhaiterez peut-être convertir un bitmap Roaring en un jeu de bits conventionnel (non compressé). En effet, les bitsets présentent des avantages tels que des performances de requête plus élevées dans certains cas. Le code suivant illustre comment procéder :
roaring_bitmap_t * r1 = roaring_bitmap_create ();
for ( uint32_t i = 100 ; i < 100000 ; i += 1 + ( i % 5 )) {
roaring_bitmap_add ( r1 , i );
}
for ( uint32_t i = 100000 ; i < 500000 ; i += 100 ) {
roaring_bitmap_add ( r1 , i );
}
roaring_bitmap_add_range ( r1 , 500000 , 600000 );
bitset_t * bitset = bitset_create ();
bool success = roaring_bitmap_to_bitset ( r1 , bitset );
assert ( success ); // could fail due to memory allocation.
assert ( bitset_count ( bitset ) == roaring_bitmap_get_cardinality ( r1 ));
// You can then query the bitset:
for ( uint32_t i = 100 ; i < 100000 ; i += 1 + ( i % 5 )) {
assert ( bitset_get ( bitset , i ));
}
for ( uint32_t i = 100000 ; i < 500000 ; i += 100 ) {
assert ( bitset_get ( bitset , i ));
}
// you must free the memory:
bitset_free ( bitset );
roaring_bitmap_free ( r1 ); Vous devez être conscient qu'un jeu de bits de convention ( bitset_t * ) peut utiliser beaucoup plus de mémoire qu'un bitmap Roaring dans certains cas. Vous devez exécuter des tests de performance pour déterminer si la conversion en un jeu de bits présente des avantages en termes de performances dans votre cas.
Cet exemple suppose que CRoaring a été construit et que vous établissez un lien avec la bibliothèque correspondante. Par défaut, CRoaring installera ses fichiers d'en-tête dans un répertoire roaring , vous devrez donc peut-être remplacer #include "roaring.hh" par #include . Si vous travaillez à partir du script de fusion, vous pouvez ajouter la ligne #include "roaring.c" si vous n'établissez pas de lien avec une bibliothèque prédéfinie CRoaring.
# include < iostream >
# include " roaring.hh "
using namespace roaring ;
int main () {
Roaring r1;
for ( uint32_t i = 100 ; i < 1000 ; i++) {
r1. add (i);
}
// check whether a value is contained
assert (r1. contains ( 500 ));
// compute how many bits there are:
uint32_t cardinality = r1. cardinality ();
// if your bitmaps have long runs, you can compress them by calling
// run_optimize
uint32_t size = r1. getSizeInBytes ();
r1. runOptimize ();
// you can enable "copy-on-write" for fast and shallow copies
r1. setCopyOnWrite ( true );
uint32_t compact_size = r1. getSizeInBytes ();
std::cout << " size before run optimize " << size << " bytes, and after "
<< compact_size << " bytes. " << std::endl;
// create a new bitmap with varargs
Roaring r2 = Roaring::bitmapOf ( 5 , 1 , 2 , 3 , 5 , 6 );
r2. printf ();
printf ( " n " );
// create a new bitmap with initializer list
Roaring r2i = Roaring::bitmapOfList ({ 1 , 2 , 3 , 5 , 6 });
assert (r2i == r2);
// we can also create a bitmap from a pointer to 32-bit integers
const uint32_t values[] = { 2 , 3 , 4 };
Roaring r3 ( 3 , values);
// we can also go in reverse and go from arrays to bitmaps
uint64_t card1 = r1. cardinality ();
uint32_t *arr1 = new uint32_t [card1];
r1. toUint32Array (arr1);
Roaring r1f (card1, arr1);
delete[] arr1;
// bitmaps shall be equal
assert (r1 == r1f);
// we can copy and compare bitmaps
Roaring z (r3);
assert (r3 == z);
// we can compute union two-by-two
Roaring r1_2_3 = r1 | r2;
r1_2_3 |= r3;
// we can compute a big union
const Roaring *allmybitmaps[] = {&r1, &r2, &r3};
Roaring bigunion = Roaring::fastunion ( 3 , allmybitmaps);
assert (r1_2_3 == bigunion);
// we can compute intersection two-by-two
Roaring i1_2 = r1 & r2;
// we can write a bitmap to a pointer and recover it later
uint32_t expectedsize = r1. getSizeInBytes ();
char *serializedbytes = new char [expectedsize];
r1. write (serializedbytes);
// readSafe will not overflow, but the resulting bitmap
// is only valid and usable if the input follows the
// Roaring specification: https://github.com/RoaringBitmap/RoaringFormatSpec/
Roaring t = Roaring::readSafe (serializedbytes, expectedsize);
assert (r1 == t);
delete[] serializedbytes;
// we can iterate over all values using custom functions
uint32_t counter = 0 ;
r1.iterate(
[]( uint32_t value, void *param) {
*( uint32_t *)param += value;
return true ;
},
&counter);
// we can also iterate the C++ way
counter = 0 ;
for (Roaring::const_iterator i = t. begin (); i != t. end (); i++) {
++counter;
}
// counter == t.cardinality()
// we can move iterators to skip values
const uint32_t manyvalues[] = { 2 , 3 , 4 , 7 , 8 };
Roaring rogue ( 5 , manyvalues);
Roaring::const_iterator j = rogue. begin ();
j. equalorlarger ( 4 ); // *j == 4
return EXIT_SUCCESS;
}
CRoaring suit le flux de travail cmake standard. A partir du répertoire racine du projet (CRoaring), vous pouvez faire :
mkdir -p build
cd build
cmake ..
cmake --build .
# follow by 'ctest' if you want to test.
# you can also type 'make install' to install the library on your system
# C header files typically get installed to /usr/local/include/roaring
# whereas C++ header files get installed to /usr/local/include/roaring
(Vous pouvez remplacer le répertoire build par n'importe quel autre nom de répertoire.) Par défaut, tous les tests sont construits sur toutes les plates-formes, pour ignorer la construction et l'exécution des tests, ajoutez -DENABLE_ROARING_TESTS=OFF à la ligne de commande.
Comme pour tous les projets cmake , vous pouvez spécifier les compilateurs que vous souhaitez utiliser en ajoutant (par exemple) -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++ à la ligne de commande cmake .
Si vous utilisez clang ou gcc et que vous connaissez votre architecture cible, vous pouvez définir l'architecture en spécifiant -DROARING_ARCH=arch . Par exemple, si vous disposez de plusieurs serveurs mais que le serveur le plus ancien exécute l'architecture Intel haswell , vous pouvez spécifier - DROARING_ARCH=haswell . Dans de tels cas, le binaire produit sera optimisé pour les processeurs ayant les caractéristiques d'un processus Haswell et ne pourra pas fonctionner sur des architectures plus anciennes. Vous pouvez connaître la liste des valeurs d'architecture valides en tapant man gcc .
mkdir -p build_haswell
cd build_haswell
cmake -DROARING_ARCH=haswell ..
cmake --build .
Pour une version de débogage, en partant du répertoire racine du projet (CRoaring), essayez
mkdir -p debug
cd debug
cmake -DCMAKE_BUILD_TYPE=Debug -DROARING_SANITIZE=ON ..
ctest
Pour vérifier que votre code respecte la convention de style (assurez-vous que clang-format est installé) :
./tools/clang-format-check.sh
Pour reformater votre code selon la convention de style (assurez-vous que clang-format est installé) :
./tools/clang-format.sh
Nous supposons que vous disposez d'un PC Windows commun avec au moins Visual Studio 2015 et un processeur x64.
Pour compiler avec au moins Visual Studio 2015 à partir de la ligne de commande :
cmake soit disponible à partir de la ligne de commande.VisualStudio .CRoaring dans votre liste de référentiels GitHub et sélectionner Open in Git Shell , puis taper cd VisualStudio dans le shell nouvellement créé.cmake -DCMAKE_GENERATOR_PLATFORM=x64 .. dans le shell lorsque vous êtes dans le référentiel VisualStudio . (Alternativement, si vous souhaitez créer une bibliothèque statique, vous pouvez utiliser la ligne de commande cmake -DCMAKE_GENERATOR_PLATFORM=x64 -DROARING_BUILD_STATIC=ON .. .)RoaringBitmap.sln ). Ouvrez ce fichier dans Visual Studio. Vous devriez maintenant pouvoir créer le projet et exécuter les tests. Par exemple, dans la fenêtre Solution Explorer (disponible dans le menu View ), cliquez avec le bouton droit sur ALL_BUILD et sélectionnez Build . Pour tester le code, toujours dans la fenêtre Solution Explorer , sélectionnez RUN_TESTS et sélectionnez Build .Pour compiler avec au moins Visual Studio 2017 directement dans l'EDI :
Visual C++ tools for CMake lors de l’installation de la charge de travail de développement C++ dans Visual Studio.File > Open > Folder... pour ouvrir le dossier CRoaring.CMakeLists.txt dans le répertoire parent dans Solution Explorer et sélectionnez Build pour créer le projet.Select Startup Item... et choisissez l'un des tests. Exécutez le test en appuyant sur le bouton à gauche de la liste déroulante.Nous avons des optimisations spécifiques à AVX2 et AVX-512 dans le code, et elles sont activées dynamiquement en fonction du matériel détecté au moment de l'exécution.
conan ) Vous pouvez installer des binaires prédéfinis pour roaring ou les créer à partir des sources à l'aide de Conan. Utilisez la commande suivante pour installer la dernière version :
conan install --requires="roaring/[*]" --build=missing
Pour des instructions détaillées sur l'utilisation de Conan, veuillez vous référer à la documentation de Conan.
La recette roaring de Conan est tenue à jour par les responsables de Conan et les contributeurs de la communauté. Si la version est obsolète, veuillez créer un problème ou une pull request sur le référentiel ConanCenterIndex.
vcpkg sous Windows, Linux et macOS) Les utilisateurs de vcpkg sous Windows, Linux et macOS peuvent télécharger et installer roaring avec une seule commande à partir de leur shell préféré.
Sous Linux et macOS :
$ ./vcpkg install roaring
construira et installera roaring en tant que bibliothèque statique.
Sous Windows (64 bits) :
.vcpkg.exe install roaring:x64-windows
construira et installera roaring en tant que bibliothèque partagée.
.vcpkg.exe install roaring:x64-windows-static
construira et installera roaring en tant que bibliothèque statique.
Ces commandes imprimeront également des instructions sur la façon d'utiliser la bibliothèque à partir de projets basés sur MSBuild ou CMake.
Si vous trouvez que la version de roaring fournie avec vcpkg est obsolète, n'hésitez pas à la signaler à la communauté vcpkg soit en soumettant un problème, soit en créant un PR.
Notre code AVX2 n'utilise pas de nombres à virgule flottante ni de multiplications, il n'est donc pas soumis à une limitation de fréquence turbo sur les processeurs Intel multicœurs.
Notre code AVX-512 n'est activé que sur le matériel récent (Intel Ice Lake ou supérieur et AMD Zen 4) où la limitation de fréquence spécifique au SIMD n'est pas observée.
Comme, par exemple, les conteneurs STL, la bibliothèque CRoaring n'a pas de support de thread intégré. Ainsi, chaque fois que vous modifiez un bitmap dans un thread, il est dangereux de l'interroger dans d'autres. Cependant, vous pouvez copier un bitmap en toute sécurité et utiliser les deux copies
