CRoaring

Brüllend

Portable Roaring-Bitmaps in C (und C++) mit voller Unterstützung für Ihren Lieblings-Compiler (GNU GCC, LLVM's clang, Visual Studio, Apple Xcode, Intel oneAPI). In der Awesome C-Liste der Open-Source-C-Software enthalten.

Einführung

Bitsets, auch Bitmaps genannt, werden häufig als schnelle Datenstrukturen verwendet. Leider können sie zu viel Speicher verbrauchen. Zum Ausgleich verwenden wir häufig komprimierte Bitmaps.

Roaring-Bitmaps sind komprimierte Bitmaps, die herkömmliche komprimierte Bitmaps wie WAH, EWAH oder Concise tendenziell übertreffen. Sie werden von mehreren großen Systemen wie Apache Lucene und abgeleiteten Systemen wie Solr und Elasticsearch, Metamarkets' Druid, LinkedIn Pinot, Netflix Atlas, Apache Spark, OpenSearchServer, Cloud Torrent, Whoosh, InfluxDB, Pilosa, Bleve und Microsoft Visual Studio Team verwendet Services (VSTS) und Apache Kylin von eBay. Die CRoaring-Bibliothek wird in mehreren Systemen wie Apache Doris, ClickHouse, Redpanda und StarRocks verwendet. Die YouTube SQL Engine, Google Procella, verwendet Roaring-Bitmaps für die Indizierung.

Wir haben einen von Experten begutachteten Artikel zum Design und zur Bewertung dieser Bibliothek veröffentlicht:

• Roaring Bitmaps: Implementation of an Optimized Software Library, Software: Practice and Experience 48 (4), 2018 arXiv:1709.07821

Roaring-Bitmaps funktionieren in vielen wichtigen Anwendungen gut:

Verwenden Sie nach Möglichkeit Roaring für die Bitmap-Komprimierung. Verwenden Sie keine anderen Bitmap-Komprimierungsmethoden (Wang et al., SIGMOD 2017)

Für die Interoperabilität zwischen Implementierungen gibt es eine serialisierte Formatspezifikation. Daher ist es möglich, eine Roaring Bitmap aus C++ zu serialisieren, in Java zu lesen, zu ändern, wieder zu serialisieren und in Go und Python zu lesen.

Objektiv

Das Hauptziel des CRoaring besteht darin, eine leistungsstarke Low-Level-Implementierung bereitzustellen, die die Vorteile der neuesten Hardware voll ausnutzt. Roaring-Bitmaps sind bereits auf einer Vielzahl von Plattformen über Java-, Go-, Rust-Implementierungen verfügbar. CRoaring ist eine Bibliothek, die darauf abzielt, eine überlegene Leistung zu erzielen, indem sie nah an der neuesten Hardware bleibt.

(c) 2016-... Die CRoaring-Autoren.

Anforderungen

• Linux, macOS, FreeBSD, Windows (MSYS2 und Microsoft Visual Studio).
• Wir testen die Bibliothek mit ARM-, x64/x86- und POWER-Prozessoren. Wir unterstützen nur Little-Endian-Systeme (Big-Endian-Systeme sind verschwindend selten).
• Aktueller C-Compiler, der den C11-Standard unterstützt (GCC 7 oder besser, LLVM 8 oder besser (clang), Xcode 11 oder besser, Microsoft Visual Studio 2022 oder besser, Intel oneAPI Compiler 2023.2 oder besser), es gibt auch eine optionale C++-Klasse, die erforderlich ist ein C++-Compiler, der den C++11-Standard unterstützt.
• CMake (um zum Projekt beizutragen, können Benutzer auf Amalgamation/Unity-Builds zurückgreifen, wenn sie CMake nicht verwenden möchten).
• Das CMake-System geht davon aus, dass Git verfügbar ist.
• Unter x64-Systemen stellt die Bibliothek eine Laufzeitverteilung bereit, sodass optimierte Funktionen basierend auf den erkannten CPU-Funktionen aufgerufen werden. Es funktioniert mit GCC, clang (Version 9 und höher) und Visual Studio (2017 und höher). Andere Systeme (z. B. ARM) benötigen keinen Runtime-Dispatch.

Kaum jemand hat Zugriff auf ein echtes Big-Endian-System. Dennoch unterstützen wir Big-Endian-Systeme wie IBM s390x über Emulatoren – mit Ausnahme der IO-Serialisierung, die nur auf Little-Endian-Systemen unterstützt wird (siehe Problem 423).

Schnellstart

Die CRoaring-Bibliothek kann in einer einzigen Quelldatei zusammengefasst werden, was die Integration in andere Projekte erleichtert. Darüber hinaus kann die Leistung verbessert werden, indem der gesamte kritische Code in einer Kompilierungseinheit kompiliert werden kann. Die Begründung finden Sie in der SQLite-Dokumentation oder im entsprechenden Wikipedia-Eintrag. Benutzer, die diesen Weg wählen, müssen sich nicht auf das Build-System von CRoaring (basierend auf CMake) verlassen.

Wir bieten zusammengeführte Dateien als Teil jeder Veröffentlichung an.

Linux- oder macOS-Benutzer befolgen möglicherweise die folgenden Anweisungen, wenn sie einen aktuellen C- oder C++-Compiler und ein Standarddienstprogramm ( wget ) installiert haben.

1. Ziehen Sie die Bibliothek in ein Verzeichnis

    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
   

2. Erstellen Sie eine neue Datei mit dem Namen demo.c mit diesem Inhalt:

    #include 
   #include 
   #include "roaring.c"
   int main () {
       roaring_bitmap_t * r1 = roaring_bitmap_create ();
       for ( uint32_t i = 100 ; i < 1000 ; i ++ ) roaring_bitmap_add ( r1 , i );
       printf ( "cardinality = %dn" , ( int ) roaring_bitmap_get_cardinality ( r1 ));
       roaring_bitmap_free ( r1 );
   
       bitset_t * b = bitset_create ();
       for ( int k = 0 ; k < 1000 ; ++ k ) {
               bitset_set ( b , 3 * k );
       }
       printf ( "%zu n" , bitset_count ( b ));
       bitset_free ( b );
       return EXIT_SUCCESS ;
   }

3. Erstellen Sie eine neue Datei mit dem Namen demo.cpp mit diesem Inhalt:

   # 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 ;
   }

4. Kompilieren

    cc -o demo demo.c
   c++ -std=c++11 -o demopp demo.cpp
   

5. ./demo

    cardinality = 900
   1000
   

6. ./demopp

    cardinality = 900
   cardinality = 900
   

Verwendung von Roaring als CPM-Abhängigkeit

Wenn Sie CMake und CPM mögen, können Sie Ihrer CMakeLists.txt Datei nur ein paar Zeilen hinzufügen, um eine CRoaring Version zu erhalten. Weitere Einzelheiten finden Sie in unserer CPM-Demonstration.

 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)

Verwendung als CMake-Abhängigkeit mit FetchContent

Wenn Ihnen CMake gefällt, können Sie Ihrer CMakeLists.txt Datei nur ein paar Zeilen hinzufügen, um eine CRoaring Version zu erhalten. Weitere Einzelheiten finden Sie in unserer Demonstration.

Wenn Sie die CRoaring-Bibliothek lokal installiert haben, können Sie sie wie in diesem Beispiel mit find_package -Funktion von CMake verwenden:

 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 
#include " roaring/roaring.hh "
int main() {
  roaring::Roaring r1;
  for (uint32_t i = 100; i < 1000; i++) {
    r1.add(i);
  }
  std::cout << " cardinality = " << r1.cardinality() << std::endl;
  return 0;
}" )

add_executable (repro main.cpp)
target_link_libraries (repro PUBLIC roaring::roaring)

Zusammenführen

Um die zusammengeführten Dateien selbst zu generieren, können Sie ein Bash-Skript aufrufen ...

./amalgamation.sh

Wenn Sie eine stille Ausgabe bevorzugen, können Sie stdout mit dem folgenden Befehl umleiten:

./amalgamation.sh > /dev/null

(Bash-Shells sind Standard unter Linux und macOS. Bash-Shells sind unter Windows als Teil des GitHub-Desktops unter dem Namen Git Shell verfügbar. Wenn Sie also das CRoaring -GitHub-Repository aus dem GitHub-Desktop heraus geklont haben, können Sie mit der rechten Maustaste auf CRoaring klicken , wählen Sie Git Shell aus und geben Sie dann die oben genannten Befehle ein.)

Es ist nicht erforderlich, das Skript im CRoaring-Verzeichnis aufzurufen. Sie können es von jedem Verzeichnis aus aufrufen, in das die Zusammenführungsdateien geschrieben werden sollen.

Es werden drei Dateien für C-Benutzer generiert: roaring.h , roaring.c und amalgamation_demo.c ... sowie einige kurze Anweisungen. Die Datei amalgamation_demo.c ist ein kurzes Beispiel, während roaring.h und roaring.c „zusammengeführte“ Dateien sind (einschließlich aller Quell- und Headerdateien für das Projekt). Das heißt, Sie können einfach die Dateien roaring.h und roaring.c in Ihr Projekt kopieren und schon kann es losgehen! Es ist nicht nötig, eine Bibliothek zu erstellen! Siehe die Datei amalgamation_demo.c .

API

Die C-Schnittstelle befindet sich in den Dateien

• brüllend.h,
• roaring64.h.

Wir haben auch eine C++-Schnittstelle:

• brüllend.hh,
• roaring64map.hh.

Umgang mit großen Volumina

Manche Nutzer müssen mit großen Datenmengen umgehen. Für diese Benutzer kann es wichtig sein, die Funktionen addMany (C++) roaring_bitmap_or_many (C) zu kennen, da es viel schneller und wirtschaftlicher ist, Werte nach Möglichkeit stapelweise hinzuzufügen. Darüber hinaus kann es hilfreich sein, regelmäßig die Funktionen runOptimize (C++) oder roaring_bitmap_run_optimize (C) aufzurufen.

Mikrobenchmarks durchführen

Wir haben Mikrobenchmarks mit den Google Benchmarks erstellt. Unter Linux oder macOS können Sie sie wie folgt ausführen:

 cmake -B build -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build build
./build/microbenchmarks/bench

Standardmäßig wählen die Benchmark-Tools einen Datensatz aus (z. B. CRoaring/benchmarks/realdata/census1881 ). Wir haben mehrere Datensätze und Sie können andere auswählen:

 ./build/microbenchmarks/bench benchmarks/realdata/wikileaks-noquotes

Für Benchmarking-Zwecke können Sie einige Funktionen deaktivieren. Angenommen, Sie verfügen über einen x64-Prozessor, könnten Sie den Code ohne AVX-512 vergleichen, selbst wenn sowohl Ihr Prozessor als auch Ihr Compiler dies unterstützen:

 cmake -B buildnoavx512 -D ROARING_DISABLE_AVX512=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build buildnoavx512
./buildnoavx512/microbenchmarks/bench

Sie können Benchmarks auch ohne AVX oder AVX-512 durchführen:

 cmake -B buildnoavx -D ROARING_DISABLE_AVX=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build buildnoavx
./buildnoavx/microbenchmarks/bench

Benutzerdefinierte Speicherzuweisungen

Für allgemeine Benutzer würde CRoaring die Standardzuordnung ohne zusätzliche Codes anwenden. Für diejenigen, die eine benutzerdefinierte Speicherzuweisung wünschen, wird jedoch auch ein globaler Speicher-Hook bereitgestellt. Hier ist ein Beispiel:

 #include 

int main (){
    // define with your own memory hook
    roaring_memory_t my_hook { my_malloc , my_free ...};
    // initialize global memory hook
    roaring_init_memory_hook ( my_hook );
    // write you code here
    ...
}

Standardmäßig verwenden wir:

 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 ,
};

Wir verlangen, dass die Funktionen free / aligned_free der C-Konvention folgen, wobei free(NULL) / aligned_free(NULL) keine Wirkung haben.

Beispiel (C)

In diesem Beispiel wird davon ausgegangen, dass CRoaring erstellt wurde und Sie eine Verknüpfung mit der entsprechenden Bibliothek herstellen. Standardmäßig installiert CRoaring seine Header-Dateien in einem roaring -Verzeichnis. Wenn Sie mit dem Zusammenführungsskript arbeiten, können Sie die Zeile #include "roaring.c" hinzufügen, wenn Sie nicht mit einer vorgefertigten CRoaring-Bibliothek verknüpfen, und #include durch #include "roaring.h" ersetzen. .

 #include 
#include 
#include 
#include 

bool roaring_iterator_sumall ( uint32_t value , void * param ) {
    * ( uint32_t * ) param += value ;
    return true;  // iterate till the end
}

int main () {
    // create a new empty bitmap
    roaring_bitmap_t * r1 = roaring_bitmap_create ();
    // then we can add values
    for ( uint32_t i = 100 ; i < 1000 ; i ++ ) roaring_bitmap_add ( r1 , i );
    // check whether a value is contained
    assert ( roaring_bitmap_contains ( r1 , 500 ));
    // compute how many bits there are:
    uint32_t cardinality = roaring_bitmap_get_cardinality ( r1 );
    printf ( "Cardinality = %d n" , cardinality );

    // if your bitmaps have long runs, you can compress them by calling
    // run_optimize
    uint32_t expectedsizebasic = roaring_bitmap_portable_size_in_bytes ( r1 );
    roaring_bitmap_run_optimize ( r1 );
    uint32_t expectedsizerun = roaring_bitmap_portable_size_in_bytes ( r1 );
    printf ( "size before run optimize %d bytes, and after %d bytesn" ,
           expectedsizebasic , expectedsizerun );

    // create a new bitmap containing the values {1,2,3,5,6}
    roaring_bitmap_t * r2 = roaring_bitmap_from ( 1 , 2 , 3 , 5 , 6 );
    roaring_bitmap_printf ( r2 );  // print it

    // we can also create a bitmap from a pointer to 32-bit integers
    uint32_t somevalues [] = { 2 , 3 , 4 };
    roaring_bitmap_t * r3 = roaring_bitmap_of_ptr ( 3 , somevalues );

    // we can also go in reverse and go from arrays to bitmaps
    uint64_t card1 = roaring_bitmap_get_cardinality ( r1 );
    uint32_t * arr1 = ( uint32_t * ) malloc ( card1 * sizeof ( uint32_t ));
    assert ( arr1 != NULL );
    roaring_bitmap_to_uint32_array ( r1 , arr1 );
    roaring_bitmap_t * r1f = roaring_bitmap_of_ptr ( card1 , arr1 );
    free ( arr1 );
    assert ( roaring_bitmap_equals ( r1 , r1f ));  // what we recover is equal
    roaring_bitmap_free ( r1f );

    // we can go from arrays to bitmaps from "offset" by "limit"
    size_t offset = 100 ;
    size_t limit = 1000 ;
    uint32_t * arr3 = ( uint32_t * ) malloc ( limit * sizeof ( uint32_t ));
    assert ( arr3 != NULL );
    roaring_bitmap_range_uint32_array ( r1 , offset , limit , arr3 );
    free ( arr3 );

    // we can copy and compare bitmaps
    roaring_bitmap_t * z = roaring_bitmap_copy ( r3 );
    assert ( roaring_bitmap_equals ( r3 , z ));  // what we recover is equal
    roaring_bitmap_free ( z );

    // we can compute union two-by-two
    roaring_bitmap_t * r1_2_3 = roaring_bitmap_or ( r1 , r2 );
    roaring_bitmap_or_inplace ( r1_2_3 , r3 );

    // we can compute a big union
    const roaring_bitmap_t * allmybitmaps [] = { r1 , r2 , r3 };
    roaring_bitmap_t * bigunion = roaring_bitmap_or_many ( 3 , allmybitmaps );
    assert (
        roaring_bitmap_equals ( r1_2_3 , bigunion ));  // what we recover is equal
    // can also do the big union with a heap
    roaring_bitmap_t * bigunionheap =
        roaring_bitmap_or_many_heap ( 3 , allmybitmaps );
    assert ( roaring_bitmap_equals ( r1_2_3 , bigunionheap ));

    roaring_bitmap_free ( r1_2_3 );
    roaring_bitmap_free ( bigunion );
    roaring_bitmap_free ( bigunionheap );

    // we can compute intersection two-by-two
    roaring_bitmap_t * i1_2 = roaring_bitmap_and ( r1 , r2 );
    roaring_bitmap_free ( i1_2 );

    // we can write a bitmap to a pointer and recover it later
    uint32_t expectedsize = roaring_bitmap_portable_size_in_bytes ( r1 );
    char * serializedbytes = malloc ( expectedsize );
    // When serializing data to a file, we recommend that you also use
    // checksums so that, at deserialization, you can be confident
    // that you are recovering the correct data.
    roaring_bitmap_portable_serialize ( r1 , serializedbytes );
    // Note: it is expected that the input follows the specification
    // https://github.com/RoaringBitmap/RoaringFormatSpec
    // otherwise the result may be unusable.
    // The 'roaring_bitmap_portable_deserialize_safe' function will not read
    // beyond expectedsize bytes.
    // We also recommend that you use checksums to check that serialized data corresponds
    // to the serialized bitmap. The CRoaring library does not provide checksumming.
    roaring_bitmap_t * t = roaring_bitmap_portable_deserialize_safe ( serializedbytes , expectedsize );
    if ( t == NULL ) { return EXIT_FAILURE ; }
    const char * reason = NULL ;
    // If your input came from an untrusted source, then you need to validate the
    // resulting bitmap. Failing to do so could lead to undefined behavior, crashes and so forth.
    if (! roaring_bitmap_internal_validate ( t , & reason )) {
        return EXIT_FAILURE ;
    }
    // At this point, the bitmap is safe.
    assert ( roaring_bitmap_equals ( r1 , t ));  // what we recover is equal
    roaring_bitmap_free ( t );
    // we can also check whether there is a bitmap at a memory location without
    // reading it
    size_t sizeofbitmap =
        roaring_bitmap_portable_deserialize_size ( serializedbytes , expectedsize );
    assert ( sizeofbitmap ==
           expectedsize );  // sizeofbitmap would be zero if no bitmap were found
    // We can also read the bitmap "safely" by specifying a byte size limit.
    // The 'roaring_bitmap_portable_deserialize_safe' function will not read
    // beyond expectedsize bytes.
    // We also recommend that you use checksums to check that serialized data corresponds
    // to the serialized bitmap. The CRoaring library does not provide checksumming.
    t = roaring_bitmap_portable_deserialize_safe ( serializedbytes , expectedsize );
    if ( t == NULL ) {
        printf ( "Problem during deserialization.n" );
        // We could clear any memory and close any file here.
        return EXIT_FAILURE ;
    }
    // We can validate the bitmap we recovered to make sure it is proper.
    // If the data came from an untrusted source, you should call
    // roaring_bitmap_internal_validate.
    const char * reason_failure = NULL ;
    if (! roaring_bitmap_internal_validate ( t , & reason_failure )) {
        printf ( "safely deserialized invalid bitmap: %sn" , reason_failure );
        // We could clear any memory and close any file here.
        return EXIT_FAILURE ;
    }
    assert ( roaring_bitmap_equals ( r1 , t ));  // what we recover is equal
    roaring_bitmap_free ( t );

    free ( serializedbytes );

    // we can iterate over all values using custom functions
    uint32_t counter = 0 ;
    roaring_iterate ( r1 , roaring_iterator_sumall , & counter );

    // we can also create iterator structs
    counter = 0 ;
    roaring_uint32_iterator_t * i = roaring_iterator_create ( r1 );
    while ( i -> has_value ) {
        counter ++ ;  // could use    i->current_value
        roaring_uint32_iterator_advance ( i );
    }
    // you can skip over values and move the iterator with
    // roaring_uint32_iterator_move_equalorlarger(i,someintvalue)

    roaring_uint32_iterator_free ( i );
    // roaring_bitmap_get_cardinality(r1) == counter

    // for greater speed, you can iterate over the data in bulk
    i = roaring_iterator_create ( r1 );
    uint32_t buffer [ 256 ];
    while ( 1 ) {
        uint32_t ret = roaring_uint32_iterator_read ( i , buffer , 256 );
        for ( uint32_t j = 0 ; j < ret ; j ++ ) {
            counter += buffer [ j ];
        }
        if ( ret < 256 ) {
            break ;
        }
    }
    roaring_uint32_iterator_free ( i );

    roaring_bitmap_free ( r1 );
    roaring_bitmap_free ( r2 );
    roaring_bitmap_free ( r3 );
    return EXIT_SUCCESS ;
}

Komprimierte 64-Bit-Roaring-Bitmaps (C)

Wir unterstützen auch effiziente 64-Bit-komprimierte Bitmaps in 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);

Die API ähnelt den herkömmlichen 32-Bit-Bitmaps. Bitte beachten Sie die Header-Datei roaring64.h (vergleichen Sie mit roaring.h ).

Konventionelle Bitsätze (C)

Wir unterstützen konventionelle Bitsätze (unkomprimiert) als Teil der Bibliothek.

Einfaches Beispiel:

 bitset_t * b = bitset_create ();
bitset_set ( b , 10 );
bitset_get ( b , 10 ); // returns true
bitset_free ( b ); // frees memory

Fortgeschritteneres Beispiel:

 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_intersect

In einigen Fällen möchten Sie möglicherweise eine Roaring-Bitmap in einen herkömmlichen (unkomprimierten) Bitsatz konvertieren. Tatsächlich haben Bitsätze in einigen Fällen Vorteile, wie z. B. eine höhere Abfrageleistung. Der folgende Code veranschaulicht, wie Sie dies tun können:

 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 );

Sie sollten sich darüber im Klaren sein, dass ein Konventionsbitset ( bitset_t * ) in manchen Fällen viel mehr Speicher beanspruchen kann als eine Roaring-Bitmap. Sie sollten Benchmarks durchführen, um festzustellen, ob die Konvertierung in ein Bitset in Ihrem Fall Leistungsvorteile bringt.

Beispiel (C++)

In diesem Beispiel wird davon ausgegangen, dass CRoaring erstellt wurde und Sie eine Verknüpfung mit der entsprechenden Bibliothek herstellen. Standardmäßig installiert CRoaring seine Header-Dateien in einem roaring -Verzeichnis, daher müssen Sie möglicherweise #include "roaring.hh" durch #include ersetzen. Wenn Sie mit dem Zusammenführungsskript arbeiten, können Sie die Zeile #include "roaring.c" hinzufügen, wenn Sie nicht mit einer vorgefertigten CRoaring-Bibliothek verknüpfen.

# 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;
}

Erstellen mit cmake (Linux und macOS, Visual Studio-Benutzer sollten siehe unten)

CRoaring folgt dem standardmäßigen cmake-Workflow. Ausgehend vom Stammverzeichnis des Projekts (CRoaring) können Sie Folgendes tun:

 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

(Sie können das build -Verzeichnis durch einen beliebigen anderen Verzeichnisnamen ersetzen.) Standardmäßig werden alle Tests auf allen Plattformen erstellt. Um das Erstellen und Ausführen von Tests zu überspringen, fügen Sie -DENABLE_ROARING_TESTS=OFF zur Befehlszeile hinzu.

Wie bei allen cmake Projekten können Sie die Compiler angeben, die Sie verwenden möchten, indem Sie (zum Beispiel) -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++ zur cmake -Befehlszeile hinzufügen.

Wenn Sie clang oder gcc verwenden und Ihre Zielarchitektur kennen, können Sie die Architektur festlegen, indem Sie -DROARING_ARCH=arch angeben. Wenn Sie beispielsweise viele Server haben, der älteste Server jedoch die Intel- haswell -Architektur ausführt, können Sie - DROARING_ARCH=haswell angeben. In solchen Fällen wird die erzeugte Binärdatei für Prozessoren mit den Eigenschaften eines Haswell-Prozesses optimiert und läuft möglicherweise nicht auf älteren Architekturen. Sie können die Liste der gültigen Architekturwerte herausfinden, indem Sie man gcc eingeben.

 mkdir -p build_haswell
cd build_haswell
cmake -DROARING_ARCH=haswell ..
cmake --build .

Versuchen Sie es für eine Debug-Version, beginnend im Stammverzeichnis des Projekts (CRoaring).

 mkdir -p debug
cd debug
cmake -DCMAKE_BUILD_TYPE=Debug -DROARING_SANITIZE=ON ..
ctest

So überprüfen Sie, ob Ihr Code der Stilkonvention entspricht (stellen Sie sicher, dass das clang-format installiert ist):

 ./tools/clang-format-check.sh

So formatieren Sie Ihren Code gemäß der Stilkonvention neu (stellen Sie sicher, dass das clang-format installiert ist):

 ./tools/clang-format.sh

Erstellen (Visual Studio unter Windows)

Wir gehen davon aus, dass Sie einen gängigen Windows-PC mit mindestens Visual Studio 2015 und einem x64-Prozessor haben.

So erstellen Sie mit mindestens Visual Studio 2015 über die Befehlszeile:

• Holen Sie sich den CRoaring-Code von GitHub, indem Sie ihn beispielsweise mit GitHub Desktop klonen.
• Installieren Sie CMake. Stellen Sie bei der Installation sicher, dass cmake über die Befehlszeile verfügbar gemacht wird.
• Erstellen Sie in CRoaring ein Unterverzeichnis, z. B. VisualStudio .
• Gehen Sie mit einer Shell in dieses neu erstellte Verzeichnis. Beispielsweise können Sie in GitHub Desktop mit der rechten Maustaste auf CRoaring in Ihrer GitHub-Repository-Liste klicken, Open in Git Shell auswählen und dann cd VisualStudio in die neu erstellte Shell eingeben.
• Geben Sie cmake -DCMAKE_GENERATOR_PLATFORM=x64 .. in die Shell ein, während Sie sich im VisualStudio -Repository befinden. (Wenn Sie alternativ eine statische Bibliothek erstellen möchten, können Sie die Befehlszeile cmake -DCMAKE_GENERATOR_PLATFORM=x64 -DROARING_BUILD_STATIC=ON .. verwenden.)
• Dieser letzte Befehl erstellte eine Visual Studio-Lösungsdatei im neu erstellten Verzeichnis (z. B. RoaringBitmap.sln ). Öffnen Sie diese Datei in Visual Studio. Sie sollten nun in der Lage sein, das Projekt zu erstellen und die Tests auszuführen. Klicken Sie beispielsweise im Solution Explorer Fenster (verfügbar im Menü „ View “) mit der rechten Maustaste auf ALL_BUILD und wählen Sie Build aus. Um den Code zu testen, wählen Sie immer noch im Solution Explorer Fenster RUN_TESTS und dann Build aus.

So erstellen Sie mit mindestens Visual Studio 2017 direkt in der IDE:

• Holen Sie sich den CRoaring-Code von GitHub, indem Sie ihn beispielsweise mit GitHub Desktop klonen.
• Wählen Sie die optionale Komponente Visual C++ tools for CMake aus, wenn Sie den C++-Entwicklungsworkload in Visual Studio installieren.
• Verwenden Sie in Visual Studio File > Open > Folder... um den CRoaring-Ordner zu öffnen.
• Klicken Sie mit der rechten Maustaste auf CMakeLists.txt im übergeordneten Verzeichnis im Solution Explorer und wählen Sie Build aus, um das Projekt zu erstellen.
• Zum Testen öffnen Sie in der Standardsymbolleiste das Menü Select Startup Item... und wählen Sie einen der Tests aus. Führen Sie den Test durch, indem Sie auf die Schaltfläche links neben dem Dropdown-Menü klicken.

Wir haben Optimierungen speziell für AVX2 und AVX-512 im Code, und diese werden dynamisch basierend auf der erkannten Hardware zur Laufzeit umgesetzt.

Verwendung (Verwendung von conan )

Sie können vorgefertigte Binärdateien für roaring installieren oder sie mit Conan aus dem Quellcode erstellen. Verwenden Sie den folgenden Befehl, um die neueste Version zu installieren:

 conan install --requires="roaring/[*]" --build=missing

Detaillierte Anweisungen zur Verwendung von Conan finden Sie in der Conan-Dokumentation.

Das roaring Conan-Rezept wird von Conan-Betreuern und Community-Mitwirkenden auf dem neuesten Stand gehalten. Wenn die Version veraltet ist, erstellen Sie bitte einen Issue oder Pull Request im ConanCenterIndex-Repository.

Verwendung (Verwendung von vcpkg unter Windows, Linux und macOS)

vcpkg-Benutzer unter Windows, Linux und macOS können roaring mit einem einzigen Befehl von ihrer Lieblings-Shell herunterladen und installieren.

Unter Linux und macOS:

 $ ./vcpkg install roaring

wird roaring als statische Bibliothek erstellen und installieren.

Unter Windows (64-Bit):

 .vcpkg.exe install roaring:x64-windows

wird roaring als gemeinsam genutzte Bibliothek erstellen und installieren.

 .vcpkg.exe install roaring:x64-windows-static

wird roaring als statische Bibliothek erstellen und installieren.

Diese Befehle geben auch Anweisungen zur Verwendung der Bibliothek aus MSBuild- oder CMake-basierten Projekten aus.

Wenn Sie feststellen, dass die mit vcpkg gelieferte Version von roaring veraltet ist, können Sie dies gerne der vcpkg -Community melden, indem Sie entweder ein Problem einreichen oder eine PR erstellen.

SIMD-bedingte Drosselung

Unser AVX2-Code verwendet keine Gleitkommazahlen oder Multiplikationen und unterliegt daher nicht der Turbofrequenzdrosselung auf Intel-Prozessoren mit vielen Kernen.

Unser AVX-512-Code ist nur auf neuerer Hardware (Intel Ice Lake oder besser und AMD Zen 4) aktiviert, bei der keine SIMD-spezifische Frequenzdrosselung beobachtet wird.

Thread-Sicherheit

Wie beispielsweise STL-Container verfügt die CRoaring-Bibliothek über keine integrierte Thread-Unterstützung. Wenn Sie also eine Bitmap in einem Thread ändern, ist es unsicher, sie in anderen Threads abzufragen. Sie können jedoch problemlos eine Bitmap kopieren und beide Kopien verwenden