Unduhan CRoaring - Unduhan kode sumber CRoaring

Bergemuruh

Bitmap Roaring portabel dalam C (dan C++) dengan dukungan penuh untuk kompiler favorit Anda (GNU GCC, dentang LLVM, Visual Studio, Apple Xcode, Intel oneAPI). Termasuk dalam daftar Awesome C perangkat lunak C sumber terbuka.

Perkenalan

Bitset, juga disebut bitmap, biasanya digunakan sebagai struktur data cepat. Sayangnya, mereka dapat menggunakan terlalu banyak memori. Untuk mengimbanginya, kita sering menggunakan bitmap terkompresi.

Bitmap menderu adalah bitmap terkompresi yang cenderung mengungguli bitmap terkompresi konvensional seperti WAH, EWAH, atau Ringkas. Mereka digunakan oleh beberapa sistem utama seperti Apache Lucene dan sistem turunannya seperti Solr dan Elasticsearch, Druid Metamarkets, LinkedIn Pinot, Netflix Atlas, Apache Spark, OpenSearchServer, Cloud Torrent, Whoosh, InfluxDB, Pilosa, Bleve, Microsoft Visual Studio Team Services (VSTS), dan Apache Kylin dari eBay. Library CRoaring digunakan di beberapa sistem seperti Apache Doris, ClickHouse, Redpanda, dan StarRocks. Mesin SQL YouTube, Google Procella, menggunakan bitmap Roaring untuk pengindeksan.

Kami menerbitkan artikel tinjauan sejawat tentang desain dan evaluasi perpustakaan ini:

Roaring Bitmap: Implementasi Perpustakaan Perangkat Lunak yang Dioptimalkan, Perangkat Lunak: Latihan dan Pengalaman 48 (4), 2018 arXiv:1709.07821

Bitmap menderu ternyata berfungsi dengan baik di banyak aplikasi penting:

Gunakan Roaring untuk kompresi bitmap bila memungkinkan. Jangan gunakan metode kompresi bitmap lainnya (Wang et al., SIGMOD 2017)

Ada spesifikasi format serial untuk interoperabilitas antar implementasi. Oleh karena itu, dimungkinkan untuk membuat serialisasi Roaring Bitmap dari C++, membacanya di Java, memodifikasinya, membuat serialisasi kembali dan membacanya di Go dan Python.

Tujuan

Tujuan utama CRoaring adalah untuk menyediakan implementasi tingkat rendah berkinerja tinggi yang sepenuhnya memanfaatkan perangkat keras terbaru. Bitmap menderu sudah tersedia di berbagai platform melalui implementasi Java, Go, Rust.... CRoaring adalah perpustakaan yang berupaya mencapai kinerja superior dengan tetap menggunakan perangkat keras terbaru.

Persyaratan

Linux, macOS, FreeBSD, Windows (MSYS2 dan Microsoft Visual studio).
Kami menguji perpustakaan dengan prosesor ARM, x64/x86 dan POWER. Kami hanya mendukung sistem little endian (sistem big endian semakin langka).
Kompiler C terbaru yang mendukung standar C11 (GCC 7 atau lebih baik, LLVM 8 atau lebih baik (dentang), Xcode 11 atau lebih baik, Microsoft Visual Studio 2022 atau lebih baik, Intel oneAPI Compiler 2023.2 atau lebih baik), ada juga kelas C++ opsional yang memerlukan kompiler C++ yang mendukung standar C++11.
CMake (untuk berkontribusi pada proyek, pengguna dapat mengandalkan amalgamasi/persatuan jika mereka tidak ingin menggunakan CMake).
Sistem CMake mengasumsikan bahwa git tersedia.
Pada sistem x64, perpustakaan menyediakan pengiriman runtime sehingga fungsi yang dioptimalkan dipanggil berdasarkan fitur CPU yang terdeteksi. Ia berfungsi dengan GCC, clang (versi 9 dan lebih tinggi) dan Visual Studio (2017 dan lebih tinggi). Sistem lain (misalnya ARM) tidak memerlukan pengiriman runtime.

Hampir tidak ada orang yang memiliki akses ke sistem big-endian yang sebenarnya. Meskipun demikian, Kami mendukung sistem big-endian seperti IBM s390x melalui emulator---kecuali untuk serialisasi IO yang hanya didukung pada sistem little-endian (lihat edisi 423).

Mulai Cepat

Pustaka CRoaring dapat digabungkan menjadi satu file sumber yang memudahkan integrasi ke proyek lain. Selain itu, dengan memungkinkan semua kode penting dikompilasi ke dalam satu unit kompilasi, kinerja dapat ditingkatkan. Untuk alasannya, silakan lihat dokumentasi SQLite, atau entri Wikipedia yang sesuai. Pengguna yang memilih rute ini, tidak perlu bergantung pada sistem build CRoaring (berdasarkan CMake).

Kami menawarkan file gabungan sebagai bagian dari setiap rilis.

Pengguna Linux atau macOS mungkin mengikuti petunjuk berikut jika mereka menginstal kompiler C atau C++ terbaru dan utilitas standar ( wget ).

Tarik perpustakaan ke dalam direktori

 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

Buat file baru bernama demo.c dengan konten ini:

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

Buat file baru bernama demo.cpp dengan konten ini:

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

Menyusun

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

./demo
```
 cardinality = 900
1000
```
./demopp
```
 cardinality = 900
cardinality = 900
```

Menggunakan Roaring sebagai ketergantungan CPM

Jika Anda menyukai CMake dan CPM, Anda dapat menambahkan beberapa baris saja di file CMakeLists.txt untuk mengambil rilis CRoaring . Lihat demonstrasi CPM kami untuk rincian lebih lanjut.

 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)

Menggunakan sebagai ketergantungan CMake dengan FetchContent

Jika Anda menyukai CMake, Anda dapat menambahkan beberapa baris saja di file CMakeLists.txt untuk mengambil rilis CRoaring . Lihat demonstrasi kami untuk rincian lebih lanjut.

Jika Anda menginstal pustaka CRoaring secara lokal, Anda dapat menggunakannya dengan fungsi find_package CMake seperti dalam contoh ini:

 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)

Penggabungan

Untuk membuat sendiri file gabungan, Anda dapat menjalankan skrip bash...

./amalgamation.sh

Jika Anda lebih memilih keluaran senyap, Anda dapat menggunakan perintah berikut untuk mengarahkan ulang stdout :

./amalgamation.sh > /dev/null

(Bash shell adalah standar di Linux dan macOS. Bash shell tersedia di Windows sebagai bagian dari GitHub Desktop dengan nama Git Shell . Jadi, jika Anda telah mengkloning repositori CRoaring GitHub dari dalam GitHub Desktop, Anda dapat mengklik kanan pada CRoaring , pilih Git Shell lalu masukkan perintah di atas.)

Tidak perlu menjalankan skrip di direktori CRoaring. Anda dapat menjalankannya dari direktori mana pun tempat Anda ingin file amalgamasi ditulis.

Ini akan menghasilkan tiga file untuk pengguna C: roaring.h , roaring.c dan amalgamation_demo.c ... serta beberapa instruksi singkat. File amalgamation_demo.c adalah contoh singkat, sedangkan roaring.h dan roaring.c adalah file "gabungan" (termasuk semua file sumber dan header untuk proyek). Ini berarti Anda cukup menyalin file roaring.h dan roaring.c ke dalam proyek Anda dan siap berangkat! Tidak perlu membuat perpustakaan! Lihat file amalgamation_demo.c .

API

Antarmuka C ditemukan di file

menderu.h,
menderu64.h.

Kami juga memiliki antarmuka C++:

menderu.hh,
menderu64map.hh.

Berurusan dengan volume besar

Beberapa pengguna harus berurusan dengan data dalam jumlah besar. Mungkin penting bagi pengguna ini untuk menyadari fungsi addMany (C++) roaring_bitmap_or_many (C) karena jauh lebih cepat dan ekonomis untuk menambahkan nilai dalam batch jika memungkinkan. Selain itu, memanggil fungsi runOptimize (C++) atau roaring_bitmap_run_optimize (C) secara berkala dapat membantu.

Menjalankan microbenchmark

Kami memiliki microbenchmark yang dibuat dengan Google Benchmarks. Di Linux atau macOS, Anda dapat menjalankannya sebagai berikut:

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

Secara default, alat benchmark mengambil satu kumpulan data (misalnya, CRoaring/benchmarks/realdata/census1881 ). Kami memiliki beberapa kumpulan data dan Anda dapat memilih yang lain:

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

Anda dapat menonaktifkan beberapa fungsi untuk tujuan pembandingan. Misalnya, dengan asumsi Anda memiliki prosesor x64, Anda dapat melakukan benchmark kode tanpa AVX-512 meskipun prosesor dan kompiler Anda mendukungnya:

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

Anda juga dapat melakukan benchmark tanpa AVX atau AVX-512:

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

Pengalokasi memori khusus

Untuk pengguna umum, CRoaring akan menerapkan pengalokasi default tanpa kode tambahan. Namun kaitan memori global juga disediakan bagi mereka yang menginginkan pengalokasi memori khusus. Berikut ini contohnya:

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

Secara default kami menggunakan:

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

Kami mengharuskan fungsi free / aligned_free mengikuti konvensi C di mana free(NULL) / aligned_free(NULL) tidak berpengaruh.

Contoh (C)

Contoh ini mengasumsikan bahwa CRoaring telah dibuat dan Anda menautkan ke perpustakaan yang sesuai. Secara default, CRoaring akan menginstal file headernya di direktori roaring . Jika Anda bekerja dari skrip amalgamasi, Anda dapat menambahkan baris #include "roaring.c" jika Anda tidak menautkan ke pustaka CRoaring bawaan dan mengganti #include dengan #include "roaring.h" .

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

Bitmap Roaring 64-bit terkompresi (C)

Kami juga mendukung bitmap terkompresi 64-bit yang efisien di 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);

API ini mirip dengan bitmap 32-bit konvensional. Silakan lihat file header roaring64.h (bandingkan dengan roaring.h ).

Bitset konvensional (C)

Kami mendukung bitset konvensi (tidak terkompresi) sebagai bagian dari perpustakaan.

Contoh sederhana:

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

Contoh lebih lanjut:

 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

Dalam beberapa kasus, Anda mungkin ingin mengubah bitmap Roaring menjadi bitset konvensional (tidak terkompresi). Memang benar, bitset memiliki kelebihan seperti kinerja kueri yang lebih tinggi dalam beberapa kasus. Kode berikut mengilustrasikan bagaimana Anda dapat melakukannya:

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

Anda harus menyadari bahwa bitset konvensi ( bitset_t * ) mungkin menggunakan lebih banyak memori daripada bitmap Roaring dalam beberapa kasus. Anda harus menjalankan tolok ukur untuk menentukan apakah konversi ke bitset memiliki manfaat kinerja dalam kasus Anda.

Contoh (C++)

Contoh ini mengasumsikan bahwa CRoaring telah dibuat dan Anda menautkan ke perpustakaan yang sesuai. Secara default, CRoaring akan menginstal file headernya di direktori roaring sehingga Anda mungkin perlu mengganti #include "roaring.hh" dengan #include . Jika Anda bekerja dari skrip amalgamasi, Anda dapat menambahkan baris #include "roaring.c" jika Anda tidak menautkan ke perpustakaan bawaan 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;
}

Membangun dengan cmake (Linux dan macOS, pengguna Visual Studio harus melihatnya di bawah)

CRoaring mengikuti alur kerja cmake standar. Mulai dari direktori root proyek (CRoaring), Anda dapat melakukan:

 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

(Anda dapat mengganti direktori build dengan nama direktori lainnya.) Secara default, semua pengujian dibuat di semua platform, untuk melewati pengujian pembuatan dan menjalankan, tambahkan -DENABLE_ROARING_TESTS=OFF ke baris perintah.

Seperti semua proyek cmake , Anda dapat menentukan kompiler yang ingin Anda gunakan dengan menambahkan (misalnya) -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++ ke baris perintah cmake .

Jika Anda menggunakan clang atau gcc dan mengetahui arsitektur target, Anda dapat mengatur arsitektur dengan menentukan -DROARING_ARCH=arch . Misalnya, jika Anda memiliki banyak server tetapi server tertua menjalankan arsitektur Intel haswell , Anda dapat menentukan - DROARING_ARCH=haswell . Dalam kasus seperti itu, biner yang dihasilkan akan dioptimalkan untuk prosesor yang memiliki karakteristik proses haswell dan mungkin tidak berjalan pada arsitektur lama. Anda dapat mengetahui daftar nilai arsitektur yang valid dengan mengetik man gcc .

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

Untuk rilis debug, mulai dari direktori root proyek (CRoaring), coba

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

Untuk memeriksa apakah kode Anda mematuhi konvensi gaya (pastikan clang-format diinstal):

 ./tools/clang-format-check.sh

Untuk memformat ulang kode Anda sesuai dengan konvensi gaya (pastikan clang-format diinstal):

 ./tools/clang-format.sh

Bangunan (Visual Studio di bawah Windows)

Kami berasumsi bahwa Anda memiliki PC Windows umum dengan setidaknya Visual Studio 2015, dan prosesor x64.

Untuk membangun dengan setidaknya Visual Studio 2015 dari baris perintah:

Ambil kode CRoaring dari GitHub, misalnya dengan mengkloningnya menggunakan GitHub Desktop.
Instal CMake. Saat Anda menginstalnya, pastikan untuk meminta agar cmake tersedia dari baris perintah.
Buat subdirektori dalam CRoaring, seperti VisualStudio .
Menggunakan shell, buka direktori yang baru dibuat ini. Misalnya, dalam GitHub Desktop, Anda dapat mengklik kanan CRoaring di daftar repositori GitHub Anda, dan memilih Open in Git Shell , lalu ketik cd VisualStudio di shell yang baru dibuat.
Ketik cmake -DCMAKE_GENERATOR_PLATFORM=x64 .. di shell saat berada di repositori VisualStudio . (Atau, jika Anda ingin membangun perpustakaan statis, Anda dapat menggunakan baris perintah cmake -DCMAKE_GENERATOR_PLATFORM=x64 -DROARING_BUILD_STATIC=ON .. .)
Perintah terakhir ini membuat file solusi Visual Studio di direktori yang baru dibuat (misalnya, RoaringBitmap.sln ). Buka file ini di Visual Studio. Anda sekarang seharusnya dapat membangun proyek dan menjalankan pengujian. Misalnya, di jendela Solution Explorer (tersedia dari menu View ), klik kanan ALL_BUILD dan pilih Build . Untuk menguji kode, masih di jendela Solution Explorer , pilih RUN_TESTS dan pilih Build .

Untuk membangun dengan setidaknya Visual Studio 2017 langsung di IDE:

Ambil kode CRoaring dari GitHub, misalnya dengan mengkloningnya menggunakan GitHub Desktop.
Pilih Visual C++ tools for CMake saat menginstal Beban Kerja Pengembangan C++ dalam Visual Studio.
Dalam Visual Studio gunakan File > Open > Folder... untuk membuka folder CRoaring.
Klik kanan pada CMakeLists.txt di direktori induk dalam Solution Explorer dan pilih Build untuk membangun proyek.
Untuk pengujian, pada toolbar Standar, letakkan menu Select Startup Item... dan pilih salah satu pengujian. Jalankan pengujian dengan menekan tombol di sebelah kiri dropdown.

Kami memiliki pengoptimalan khusus untuk AVX2 dan AVX-512 dalam kodenya, dan pengoptimalan tersebut diubah secara dinamis berdasarkan perangkat keras yang terdeteksi saat runtime.

Penggunaan (Menggunakan `conan` )

Anda dapat menginstal binari yang sudah dibuat sebelumnya untuk roaring atau membuatnya dari sumber menggunakan Conan. Gunakan perintah berikut untuk menginstal versi terbaru:

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

Untuk petunjuk rinci tentang cara menggunakan Conan, silakan merujuk ke dokumentasi Conan.

Resep Conan roaring terus diperbarui oleh pengelola Conan dan kontributor komunitas. Jika versinya sudah kedaluwarsa, silakan buat masalah atau tarik permintaan pada repositori ConanCenterIndex.

Penggunaan (Menggunakan `vcpkg` di Windows, Linux dan macOS)

Pengguna vcpkg di Windows, Linux dan macOS dapat mengunduh dan menginstal roaring dengan satu perintah dari shell favorit mereka.

Di Linux dan macOS:

 $ ./vcpkg install roaring

akan membangun dan menginstal roaring sebagai perpustakaan statis.

Di Windows (64-bit):

 .vcpkg.exe install roaring:x64-windows

akan membangun dan menginstal roaring sebagai perpustakaan bersama.

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

akan membangun dan menginstal roaring sebagai perpustakaan statis.

Perintah ini juga akan mencetak instruksi tentang cara menggunakan perpustakaan dari proyek berbasis MSBuild atau CMake.

Jika Anda menemukan versi roaring yang dikirimkan bersama vcpkg sudah kedaluwarsa, jangan ragu untuk melaporkannya ke komunitas vcpkg dengan mengirimkan masalah atau dengan membuat PR.

Pembatasan terkait SIMD

Kode AVX2 kami tidak menggunakan angka floating-point atau perkalian, sehingga tidak tunduk pada pelambatan frekuensi turbo pada prosesor Intel banyak inti.

Kode AVX-512 kami hanya diaktifkan pada perangkat keras terbaru (Intel Ice Lake atau lebih baik dan AMD Zen 4) di mana pembatasan frekuensi khusus SIMD tidak diamati.

Keamanan benang

Seperti, misalnya, kontainer STL, perpustakaan CRoaring tidak memiliki dukungan thread bawaan. Jadi, setiap kali Anda memodifikasi bitmap di satu thread, tidak aman untuk menanyakannya di thread lain. Namun, Anda dapat menyalin bitmap dengan aman dan menggunakan kedua salinan tersebut

Memperluas

CRoaring

Bergemuruh

Perkenalan

Tujuan

Persyaratan

Mulai Cepat

Menggunakan Roaring sebagai ketergantungan CPM

Menggunakan sebagai ketergantungan CMake dengan FetchContent

Penggabungan

API

Berurusan dengan volume besar

Menjalankan microbenchmark

Pengalokasi memori khusus

Contoh (C)

Bitmap Roaring 64-bit terkompresi (C)

Bitset konvensional (C)

Contoh (C++)

Membangun dengan cmake (Linux dan macOS, pengguna Visual Studio harus melihatnya di bawah)

Bangunan (Visual Studio di bawah Windows)

Penggunaan (Menggunakan `conan` )

Penggunaan (Menggunakan `vcpkg` di Windows, Linux dan macOS)

Pembatasan terkait SIMD

Keamanan benang

libmem

glfm

RetrOS 32

mdns

lz4

arcan

chat.petals.dev

GPT Prompt Templates

GPTyped

libmem

RetrOS 32

glfm

termwind

slugify

laravel firebase

CRoaring

Bergemuruh

Perkenalan

Tujuan

Persyaratan

Mulai Cepat

Menggunakan Roaring sebagai ketergantungan CPM

Menggunakan sebagai ketergantungan CMake dengan FetchContent

Penggabungan

API

Berurusan dengan volume besar

Menjalankan microbenchmark

Pengalokasi memori khusus

Contoh (C)

Bitmap Roaring 64-bit terkompresi (C)

Bitset konvensional (C)

Contoh (C++)

Membangun dengan cmake (Linux dan macOS, pengguna Visual Studio harus melihatnya di bawah)

Bangunan (Visual Studio di bawah Windows)

Penggunaan (Menggunakan conan )

Penggunaan (Menggunakan vcpkg di Windows, Linux dan macOS)

Pembatasan terkait SIMD

Keamanan benang

Penggunaan (Menggunakan `conan` )

Penggunaan (Menggunakan `vcpkg` di Windows, Linux dan macOS)