CRoaring
Version 4.2.1
Mapas de bits Roaring portátiles en C (y C++) con soporte completo para su compilador favorito (GNU GCC, LLVM's clang, Visual Studio, Apple Xcode, Intel oneAPI). Incluido en la lista Awesome C de software C de código abierto.
Los conjuntos de bits, también llamados mapas de bits, se utilizan comúnmente como estructuras de datos rápidas. Desafortunadamente, pueden utilizar demasiada memoria. Para compensar, utilizamos a menudo mapas de bits comprimidos.
Los mapas de bits rugientes son mapas de bits comprimidos que tienden a superar a los mapas de bits comprimidos convencionales como WAH, EWAH o Concise. Son utilizados por varios sistemas importantes como Apache Lucene y sistemas derivados como Solr y Elasticsearch, Metamarkets' Druid, LinkedIn Pinot, Netflix Atlas, Apache Spark, OpenSearchServer, Cloud Torrent, Whoosh, InfluxDB, Pilosa, Bleve, Microsoft Visual Studio Team. Services (VSTS) y Apache Kylin de eBay. La biblioteca CRoaring se utiliza en varios sistemas como Apache Doris, ClickHouse, Redpanda y StarRocks. El motor SQL de YouTube, Google Procella, utiliza mapas de bits Roaring para la indexación.
Publicamos un artículo revisado por pares sobre el diseño y evaluación de esta biblioteca:
Se ha descubierto que los mapas de bits rugientes funcionan bien en muchas aplicaciones importantes:
Utilice Roaring para la compresión de mapas de bits siempre que sea posible. No utilice otros métodos de compresión de mapas de bits (Wang et al., SIGMOD 2017)
Existe una especificación de formato serializado para la interoperabilidad entre implementaciones. Por lo tanto, es posible serializar un mapa de bits Roaring desde C++, leerlo en Java, modificarlo, volver a serializarlo y leerlo en Go y Python.
El objetivo principal de CRoaring es proporcionar una implementación de bajo nivel de alto rendimiento que aproveche al máximo el hardware más reciente. Los mapas de bits rugientes ya están disponibles en una variedad de plataformas a través de implementaciones de Java, Go, Rust... CRoaring es una biblioteca que busca lograr un rendimiento superior manteniéndose cerca del hardware más reciente.
(c) 2016-... Los autores CRoaring.
Casi nadie tiene acceso a un sistema big-endian real. Sin embargo, admitimos sistemas big-endian como IBM s390x a través de emuladores, excepto la serialización IO que solo se admite en sistemas little-endian (consulte el número 423).
La biblioteca CRoaring se puede fusionar en un único archivo fuente que facilita la integración en otros proyectos. Además, al permitir compilar todo el código crítico en una unidad de compilación, se puede mejorar el rendimiento. Para conocer el fundamento, consulte la documentación de SQLite o la entrada correspondiente de Wikipedia. Los usuarios que elijan esta ruta no necesitan depender del sistema de compilación de CRoaring (basado en CMake).
Ofrecemos archivos fusionados como parte de cada versión.
Los usuarios de Linux o macOS pueden seguir las siguientes instrucciones si tienen instalado un compilador C o C++ reciente y una utilidad estándar ( 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 con este contenido: #include demo.cpp con este contenido: # 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 le gustan CMake y CPM, puede agregar solo unas pocas líneas en su archivo CMakeLists.txt para obtener una versión CRoaring . Vea nuestra demostración de CPM para obtener más detalles.
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 le gusta CMake, puede agregar solo unas pocas líneas en su archivo CMakeLists.txt para obtener una versión CRoaring . Vea nuestra demostración para más detalles.
Si instaló la biblioteca CRoaring localmente, puede usarla con la función find_package de CMake como en este ejemplo:
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 Para generar los archivos combinados usted mismo, puede invocar un script bash...
./amalgamation.sh Si prefiere una salida silenciosa, puede utilizar el siguiente comando para redirigir stdout :
./amalgamation.sh > /dev/null (Los shells Bash son estándar en Linux y macOS. Los shells Bash están disponibles en Windows como parte del escritorio GitHub con el nombre Git Shell . Entonces, si ha clonado el repositorio CRoaring GitHub desde el escritorio GitHub, puede hacer clic derecho en CRoaring , seleccione Git Shell y luego ingrese los comandos anteriores).
No es necesario invocar el script en el directorio CRoaring. Puede invocarlo desde cualquier directorio donde desee que se escriban los archivos de fusión.
Generará tres archivos para usuarios de C: roaring.h , roaring.c y amalgamation_demo.c ... así como algunas breves instrucciones. El archivo amalgamation_demo.c es un ejemplo breve, mientras que roaring.h y roaring.c son archivos "amalgamados" (incluidos todos los archivos fuente y de encabezado del proyecto). ¡Esto significa que simplemente puedes copiar los archivos roaring.h y roaring.c en tu proyecto y estar listo para comenzar! ¡No es necesario crear una biblioteca! Consulte el archivo amalgamation_demo.c .
La interfaz C se encuentra en los archivos.
También tenemos una interfaz C++:
Algunos usuarios tienen que lidiar con grandes volúmenes de datos. Puede ser importante que estos usuarios conozcan las funciones addMany (C++) roaring_bitmap_or_many (C), ya que es mucho más rápido y económico agregar valores en lotes cuando sea posible. Además, puede ser útil llamar periódicamente a las funciones runOptimize (C++) o roaring_bitmap_run_optimize (C).
Disponemos de microbenchmarks construidos con Google Benchmarks. En Linux o macOS, puede ejecutarlos de la siguiente manera:
cmake -B build -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build build
./build/microbenchmarks/bench
De forma predeterminada, las herramientas de referencia seleccionan un conjunto de datos (por ejemplo, CRoaring/benchmarks/realdata/census1881 ). Tenemos varios conjuntos de datos y usted puede elegir otros:
./build/microbenchmarks/bench benchmarks/realdata/wikileaks-noquotes
Puede desactivar algunas funciones con el fin de realizar evaluaciones comparativas. Por ejemplo, suponiendo que tiene un procesador x64, puede comparar el código sin AVX-512 incluso si tanto su procesador como su compilador lo admiten:
cmake -B buildnoavx512 -D ROARING_DISABLE_AVX512=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build buildnoavx512
./buildnoavx512/microbenchmarks/bench
También puede realizar pruebas comparativas sin AVX o AVX-512:
cmake -B buildnoavx -D ROARING_DISABLE_AVX=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build buildnoavx
./buildnoavx/microbenchmarks/bench
Para los usuarios generales, CRoaring aplicaría el asignador predeterminado sin códigos adicionales. Pero también se proporciona un enlace de memoria global para aquellos que desean un asignador de memoria personalizado. Aquí hay un ejemplo:
#include Por defecto utilizamos:
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 ,
}; Requerimos que las funciones free / aligned_free sigan la convención C donde free(NULL) / aligned_free(NULL) no tienen ningún efecto.
Este ejemplo supone que se ha creado CRoaring y que se está vinculando con la biblioteca correspondiente. De forma predeterminada, CRoaring instalará sus archivos de encabezado en un directorio roaring . Si está trabajando desde el script de fusión, puede agregar la línea #include "roaring.c" si no está vinculando una biblioteca CRoaring prediseñada y reemplazar #include por #include "roaring.h" .
#include También admitimos mapas de bits comprimidos eficientes de 64 bits 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); La API es similar a los mapas de bits convencionales de 32 bits. Consulte el archivo de encabezado roaring64.h (compárelo con roaring.h ).
Admitimos conjuntos de bits convencionales (sin comprimir) como parte de la biblioteca.
Ejemplo sencillo:
bitset_t * b = bitset_create ();
bitset_set ( b , 10 );
bitset_get ( b , 10 ); // returns true
bitset_free ( b ); // frees memoryEjemplo más avanzado:
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_intersectEn algunos casos, es posible que desee convertir un mapa de bits Roaring en un conjunto de bits convencional (sin comprimir). De hecho, los conjuntos de bits tienen ventajas, como un mayor rendimiento de las consultas en algunos casos. El siguiente código ilustra cómo puede hacerlo:
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 ); Debe tener en cuenta que un conjunto de bits convencional ( bitset_t * ) puede utilizar mucha más memoria que un mapa de bits Roaring en algunos casos. Debe ejecutar pruebas comparativas para determinar si la conversión a un conjunto de bits tiene beneficios de rendimiento en su caso.
Este ejemplo supone que se ha creado CRoaring y que se está vinculando con la biblioteca correspondiente. De forma predeterminada, CRoaring instalará sus archivos de encabezado en un directorio roaring , por lo que es posible que deba reemplazar #include "roaring.hh" por #include . Si está trabajando desde el script de fusión, puede agregar la línea #include "roaring.c" si no está vinculando con una biblioteca prediseñada de 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 sigue el flujo de trabajo estándar de cmake. A partir del directorio raíz del proyecto (CRoaring), puedes hacer:
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
(Puede reemplazar el directorio build con cualquier otro nombre de directorio). De forma predeterminada, todas las pruebas se crean en todas las plataformas; para omitir la compilación y ejecución de pruebas, agregue -DENABLE_ROARING_TESTS=OFF a la línea de comando.
Como con todos los proyectos cmake , puede especificar los compiladores que desea usar agregando (por ejemplo) -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++ a la línea de comando cmake .
Si está utilizando clang o gcc y conoce su arquitectura de destino, puede configurar la arquitectura especificando -DROARING_ARCH=arch . Por ejemplo, si tiene muchos servidores pero el servidor más antiguo ejecuta la arquitectura Intel haswell , puede especificar - DROARING_ARCH=haswell . En tales casos, el binario producido se optimizará para procesadores que tengan las características de un proceso Haswell y es posible que no se ejecute en arquitecturas más antiguas. Puede encontrar la lista de valores de arquitectura válidos escribiendo man gcc .
mkdir -p build_haswell
cd build_haswell
cmake -DROARING_ARCH=haswell ..
cmake --build .
Para una versión de depuración, comenzando desde el directorio raíz del proyecto (CRoaring), intente
mkdir -p debug
cd debug
cmake -DCMAKE_BUILD_TYPE=Debug -DROARING_SANITIZE=ON ..
ctest
Para verificar que su código cumpla con la convención de estilo (asegúrese de que el clang-format esté instalado):
./tools/clang-format-check.sh
Para reformatear su código de acuerdo con la convención de estilo (asegúrese de que clang-format esté instalado):
./tools/clang-format.sh
Suponemos que tiene una PC con Windows común con al menos Visual Studio 2015 y un procesador x64.
Para compilar con al menos Visual Studio 2015 desde la línea de comando:
cmake esté disponible desde la línea de comando.VisualStudio .CRoaring en su lista de repositorios de GitHub y seleccionar Open in Git Shell , luego escribir cd VisualStudio en el shell recién creado.cmake -DCMAKE_GENERATOR_PLATFORM=x64 .. en el shell mientras esté en el repositorio VisualStudio . (Alternativamente, si desea crear una biblioteca estática, puede usar la línea de comando cmake -DCMAKE_GENERATOR_PLATFORM=x64 -DROARING_BUILD_STATIC=ON .. ...)RoaringBitmap.sln ). Abra este archivo en Visual Studio. Ahora debería poder construir el proyecto y ejecutar las pruebas. Por ejemplo, en la ventana Solution Explorer (disponible en el menú View ), haga clic derecho en ALL_BUILD y seleccione Build . Para probar el código, aún en la ventana Solution Explorer , seleccione RUN_TESTS y seleccione Build .Para compilar con al menos Visual Studio 2017 directamente en el IDE:
Visual C++ tools for CMake al instalar la carga de trabajo de desarrollo de C++ en Visual Studio.File > Open > Folder... para abrir la carpeta CRoaring.CMakeLists.txt en el directorio principal dentro Solution Explorer y seleccione Build para construir el proyecto.Select Startup Item... y elija una de las pruebas. Ejecute la prueba presionando el botón a la izquierda del menú desplegable.Tenemos optimizaciones específicas para AVX2 y AVX-512 en el código, y se activan dinámicamente según el hardware detectado en tiempo de ejecución.
conan ) Puedes instalar binarios prediseñados para roaring o compilarlos desde el código fuente usando Conan. Utilice el siguiente comando para instalar la última versión:
conan install --requires="roaring/[*]" --build=missing
Para obtener instrucciones detalladas sobre cómo utilizar Conan, consulte la documentación de Conan.
Los mantenedores de Conan y los contribuyentes de la comunidad mantienen actualizada la roaring receta de Conan. Si la versión no está actualizada, cree una incidencia o una solicitud de extracción en el repositorio de ConanCenterIndex.
vcpkg en Windows, Linux y macOS) Los usuarios de vcpkg en Windows, Linux y macOS pueden descargar e instalar roaring con un solo comando desde su shell favorito.
En Linux y macOS:
$ ./vcpkg install roaring
construirá e instalará roaring como una biblioteca estática.
En Windows (64 bits):
.vcpkg.exe install roaring:x64-windows
construirá e instalará roaring como una biblioteca compartida.
.vcpkg.exe install roaring:x64-windows-static
construirá e instalará roaring como una biblioteca estática.
Estos comandos también imprimirán instrucciones sobre cómo usar la biblioteca desde proyectos basados en MSBuild o CMake.
Si encuentra que la versión de roaring enviada con vcpkg está desactualizada, no dude en informarlo a la comunidad vcpkg ya sea enviando un problema o creando un PR.
Nuestro código AVX2 no utiliza números de punto flotante ni multiplicaciones, por lo que no está sujeto a la aceleración de frecuencia turbo en los procesadores Intel de muchos núcleos.
Nuestro código AVX-512 solo está habilitado en hardware reciente (Intel Ice Lake o mejor y AMD Zen 4) donde no se observa limitación de frecuencia específica de SIMD.
Al igual que, por ejemplo, los contenedores STL, la biblioteca CRoaring no tiene soporte de subprocesos integrado. Por lo tanto, cada vez que modifica un mapa de bits en un hilo, no es seguro consultarlo en otros. Sin embargo, puedes copiar un mapa de bits de forma segura y utilizar ambas copias.
