CRoaring

CRoaring

Bitmaps Roaring portáteis em C (e C++) com suporte total para seu compilador favorito (GNU GCC, clang do LLVM, Visual Studio, Apple Xcode, Intel oneAPI). Incluído na lista Awesome C de software C de código aberto.

Introdução

Bitsets, também chamados de bitmaps, são comumente usados ​​como estruturas de dados rápidas. Infelizmente, eles podem usar muita memória. Para compensar, costumamos usar bitmaps compactados.

Roaring bitmaps são bitmaps compactados que tendem a superar os bitmaps compactados convencionais, como WAH, EWAH ou Concise. Eles são usados ​​por vários sistemas importantes, como Apache Lucene e sistemas derivados, como Solr e Elasticsearch, Metamarkets' Druid, LinkedIn Pinot, Netflix Atlas, Apache Spark, OpenSearchServer, Cloud Torrent, Whoosh, InfluxDB, Pilosa, Bleve, Microsoft Visual Studio Team Serviços (VSTS) e Apache Kylin do eBay. A biblioteca CRoaring é usada em diversos sistemas como Apache Doris, ClickHouse, Redpanda e StarRocks. O mecanismo SQL do YouTube, Google Procella, usa bitmaps Roaring para indexação.

Publicamos um artigo revisado por pares sobre o design e avaliação desta biblioteca:

• Roaring Bitmaps: Implementação de uma biblioteca de software otimizada, Software: prática e experiência 48 (4), 2018 arXiv:1709.07821

Descobriu-se que bitmaps incríveis funcionam bem em muitas aplicações importantes:

Use Roaring para compactação de bitmap sempre que possível. Não use outros métodos de compactação de bitmap (Wang et al., SIGMOD 2017)

Existe uma especificação de formato serializado para interoperabilidade entre implementações. Portanto, é possível serializar um Roaring Bitmap de C++, lê-lo em Java, modificá-lo, serializá-lo novamente e lê-lo em Go e Python.

Objetivo

O objetivo principal do CRoaring é fornecer uma implementação de alto desempenho e baixo nível que aproveite totalmente o hardware mais recente. Bitmaps incríveis já estão disponíveis em uma variedade de plataformas por meio de implementações Java, Go, Rust.... CRoaring é uma biblioteca que busca alcançar desempenho superior mantendo-se próximo do hardware mais recente.

(c) 2016-... Os autores do CRoaring.

Requisitos

• Linux, macOS, FreeBSD, Windows (MSYS2 e Microsoft Visual Studio).
• Testamos a biblioteca com processadores ARM, x64/x86 e POWER. Oferecemos suporte apenas a sistemas little endian (sistemas big endian são extremamente raros).
• Compilador C recente com suporte ao padrão C11 (GCC 7 ou melhor, LLVM 8 ou melhor (clang), Xcode 11 ou melhor, Microsoft Visual Studio 2022 ou melhor, Intel oneAPI Compiler 2023.2 ou melhor), há também uma classe C++ opcional que requer um compilador C++ que suporta o padrão C++11.
• CMake (para contribuir com o projeto, os usuários podem contar com compilações de amálgama/unidade se não desejarem usar o CMake).
• O sistema CMake assume que o git está disponível.
• Em sistemas x64, a biblioteca fornece despacho em tempo de execução para que funções otimizadas sejam chamadas com base nos recursos de CPU detectados. Funciona com GCC, clang (versão 9 e superior) e Visual Studio (2017 e superior). Outros sistemas (por exemplo, ARM) não precisam de despacho em tempo de execução.

Quase ninguém tem acesso a um sistema big endian real. No entanto, oferecemos suporte a sistemas big-endian, como IBM s390x, por meio de emuladores --- exceto para serialização IO, que é suportada apenas em sistemas little-endian (consulte a edição 423).

Início rápido

A biblioteca CRoaring pode ser reunida em um único arquivo fonte que facilita a integração em outros projetos. Além disso, ao tornar possível compilar todo o código crítico em uma unidade de compilação, pode melhorar o desempenho. Para saber a justificativa, consulte a documentação do SQLite ou a entrada correspondente da Wikipedia. Os usuários que escolhem esta rota não precisam depender do sistema de compilação do CRoaring (baseado em CMake).

Oferecemos arquivos agrupados como parte de cada versão.

Os usuários de Linux ou macOS podem seguir as instruções a seguir se tiverem um compilador C ou C++ recente instalado e um utilitário padrão ( wget ).

1. Puxe a biblioteca em um diretório

    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. Crie um novo arquivo chamado demo.c com este conteúdo:

    #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. Crie um novo arquivo chamado demo.cpp com este conteúdo:

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

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

5. ./demo

    cardinality = 900
   1000
   

6. ./demopp

    cardinality = 900
   cardinality = 900
   

Usando Roaring como uma dependência de CPM

Se você gosta de CMake e CPM, você pode adicionar apenas algumas linhas em seu arquivo CMakeLists.txt para obter uma versão CRoaring . Veja nossa demonstração de CPM para mais detalhes.

 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)

Usando como dependência do CMake com FetchContent

Se você gosta do CMake, pode adicionar apenas algumas linhas ao seu arquivo CMakeLists.txt para obter uma versão CRoaring . Veja nossa demonstração para mais detalhes.

Se você instalou a biblioteca CRoaring localmente, poderá usá-la com a função find_package do CMake como neste exemplo:

 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)

Amalgamando

Para gerar você mesmo os arquivos amalgamados, você pode invocar um script bash...

./amalgamation.sh

Se preferir uma saída silenciosa, você pode usar o seguinte comando para redirecionar stdout :

./amalgamation.sh > /dev/null

(Os shells Bash são padrão no Linux e no macOS. Os shells Bash estão disponíveis no Windows como parte do GitHub Desktop sob o nome Git Shell . Portanto, se você clonou o repositório CRoaring GitHub de dentro do GitHub Desktop, você pode clicar com o botão direito em CRoaring , selecione Git Shell e insira os comandos acima.)

Não é necessário invocar o script no diretório CRoaring. Você pode invocá-lo de qualquer diretório onde deseja que os arquivos de fusão sejam gravados.

Ele irá gerar três arquivos para usuários C: roaring.h , roaring.c e amalgamation_demo.c ... bem como algumas breves instruções. O arquivo amalgamation_demo.c é um exemplo curto, enquanto roaring.h e roaring.c são arquivos "amalgamados" (incluindo todos os arquivos de origem e de cabeçalho do projeto). Isso significa que você pode simplesmente copiar os arquivos roaring.h e roaring.c para o seu projeto e estar pronto para começar! Não há necessidade de produzir uma biblioteca! Consulte o arquivo amalgamation_demo.c .

API

A interface C é encontrada nos arquivos

• rugindo.h,
• rugindo64.h.

Também temos uma interface C++:

• rugindo.hh,
• rugindo64map.hh.

Lidando com grandes volumes

Alguns usuários precisam lidar com grandes volumes de dados. Pode ser importante que esses usuários estejam cientes das funções addMany (C++) roaring_bitmap_or_many (C), pois é muito mais rápido e econômico adicionar valores em lotes quando possível. Além disso, chamar periodicamente as funções runOptimize (C++) ou roaring_bitmap_run_optimize (C) pode ajudar.

Executando microbenchmarks

Temos microbenchmarks construídos com os Benchmarks do Google. No Linux ou macOS, você pode executá-los da seguinte forma:

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

Por padrão, as ferramentas de benchmark escolhem um conjunto de dados (por exemplo, CRoaring/benchmarks/realdata/census1881 ). Temos vários conjuntos de dados e você pode escolher outros:

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

Você pode desativar algumas funcionalidades para fins de benchmarking. Por exemplo, supondo que você tenha um processador x64, você pode comparar o código sem o AVX-512, mesmo que tanto o processador quanto o compilador o suportem:

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

Você também pode fazer benchmark sem AVX ou AVX-512:

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

Alocadores de memória personalizados

Para usuários gerais, CRoaring aplicaria o alocador padrão sem códigos extras. Mas o gancho de memória global também é fornecido para aqueles que desejam um alocador de memória personalizado. Aqui está um exemplo:

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

Por padrão usamos:

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

Exigimos que as funções free / aligned_free sigam a convenção C onde free(NULL) / aligned_free(NULL) não têm efeito.

Exemplo (C)

Este exemplo pressupõe que o CRoaring foi compilado e que você está vinculando à biblioteca correspondente. Por padrão, o CRoaring instalará seus arquivos de cabeçalho em um diretório roaring . Se você estiver trabalhando a partir do script de fusão, poderá adicionar a linha #include "roaring.c" se não estiver vinculando a uma biblioteca CRoaring pré-construída e substituir #include por #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 ;
}

Bitmaps Roaring compactados de 64 bits (C)

Também oferecemos suporte a bitmaps compactados eficientes de 64 bits em 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);

A API é semelhante aos bitmaps convencionais de 32 bits. Consulte o arquivo de cabeçalho roaring64.h (compare com roaring.h ).

Bitsets convencionais (C)

Oferecemos suporte a bitsets de convenção (não compactados) como parte da biblioteca.

Exemplo simples:

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

Exemplo mais avançado:

 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

Em alguns casos, você pode querer converter um bitmap Roaring em um bitset convencional (descompactado). Na verdade, os bitsets têm vantagens, como desempenho de consulta mais alto em alguns casos. O código a seguir ilustra como você pode fazer isso:

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

Você deve estar ciente de que um bitset de convenção ( bitset_t * ) pode usar muito mais memória do que um bitmap Roaring em alguns casos. Você deve executar benchmarks para determinar se a conversão para um bitset traz benefícios de desempenho no seu caso.

Exemplo (C++)

Este exemplo pressupõe que o CRoaring foi compilado e que você está vinculando à biblioteca correspondente. Por padrão, CRoaring instalará seus arquivos de cabeçalho em um diretório roaring , então você pode precisar substituir #include "roaring.hh" por #include . Se você estiver trabalhando a partir do script de fusão, poderá adicionar a linha #include "roaring.c" se não estiver vinculando a uma biblioteca pré-construída 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;
}

Construindo com cmake (Linux e macOS, os usuários do Visual Studio devem ver abaixo)

CRoaring segue o fluxo de trabalho padrão do cmake. A partir do diretório raiz do projeto (CRoaring), você pode fazer:

 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

(Você pode substituir o diretório build por qualquer outro nome de diretório.) Por padrão, todos os testes são construídos em todas as plataformas, para pular a construção e a execução de testes, adicione -DENABLE_ROARING_TESTS=OFF à linha de comando.

Tal como acontece com todos os projetos cmake , você pode especificar os compiladores que deseja usar adicionando (por exemplo) -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++ à linha de comando cmake .

Se você estiver usando clang ou gcc e conhece sua arquitetura de destino, poderá definir a arquitetura especificando -DROARING_ARCH=arch . Por exemplo, se você tiver muitos servidores, mas o servidor mais antigo estiver executando a arquitetura Intel haswell , você poderá especificar - DROARING_ARCH=haswell . Nesses casos, o binário produzido será otimizado para processadores com características de um processo haswell e não poderá ser executado em arquiteturas mais antigas. Você pode descobrir a lista de valores de arquitetura válidos digitando man gcc .

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

Para uma versão de depuração, começando no diretório raiz do projeto (CRoaring), tente

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

Para verificar se o seu código obedece à convenção de estilo (certifique-se de que clang-format esteja instalado):

 ./tools/clang-format-check.sh

Para reformatar seu código de acordo com a convenção de estilo (certifique-se de que clang-format esteja instalado):

 ./tools/clang-format.sh

Construindo (Visual Studio no Windows)

Presumimos que você tenha um PC Windows comum com pelo menos Visual Studio 2015 e um processador x64.

Para compilar com pelo menos o Visual Studio 2015 na linha de comando:

• Obtenha o código CRoaring do GitHub, por exemplo, clonando-o usando o GitHub Desktop.
• Instale o CMake. Ao instalá-lo, certifique-se de solicitar que o cmake seja disponibilizado na linha de comando.
• Crie um subdiretório dentro do CRoaring, como VisualStudio .
• Usando um shell, vá para este diretório recém-criado. Por exemplo, no GitHub Desktop, você pode clicar com o botão direito em CRoaring na lista de repositórios do GitHub e selecionar Open in Git Shell e digitar cd VisualStudio no shell recém-criado.
• Digite cmake -DCMAKE_GENERATOR_PLATFORM=x64 .. no shell enquanto estiver no repositório VisualStudio . (Alternativamente, se você deseja construir uma biblioteca estática, você pode usar a linha de comando cmake -DCMAKE_GENERATOR_PLATFORM=x64 -DROARING_BUILD_STATIC=ON .. .)
• Este último comando criou um arquivo de solução do Visual Studio no diretório recém-criado (por exemplo, RoaringBitmap.sln ). Abra este arquivo no Visual Studio. Agora você deve conseguir construir o projeto e executar os testes. Por exemplo, na janela Solution Explorer (disponível no menu View ), clique com o botão direito em ALL_BUILD e selecione Build . Para testar o código, ainda na janela Solution Explorer , selecione RUN_TESTS e selecione Build .

Para compilar com pelo menos o Visual Studio 2017 diretamente no IDE:

• Obtenha o código CRoaring do GitHub, por exemplo, clonando-o usando o GitHub Desktop.
• Selecione o componente opcional Visual C++ tools for CMake ao instalar a carga de trabalho de desenvolvimento C++ no Visual Studio.
• No Visual Studio, use File > Open > Folder... para abrir a pasta CRoaring.
• Clique com o botão direito em CMakeLists.txt no diretório pai no Solution Explorer e selecione Build para compilar o projeto.
• Para testar, na barra de ferramentas Padrão, solte o menu Select Startup Item... e escolha um dos testes. Execute o teste pressionando o botão à esquerda do menu suspenso.

Temos otimizações específicas para AVX2 e AVX-512 no código, e elas são ativadas dinamicamente com base no hardware detectado em tempo de execução.

Uso (usando conan )

Você pode instalar binários pré-construídos para roaring ou construí-los a partir do código-fonte usando Conan. Use o seguinte comando para instalar a versão mais recente:

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

Para obter instruções detalhadas sobre como usar o Conan, consulte a documentação do Conan.

A receita roaring do Conan é mantida atualizada pelos mantenedores do Conan e colaboradores da comunidade. Se a versão estiver desatualizada, crie um problema ou solicitação pull no repositório ConanCenterIndex.

Uso (usando vcpkg no Windows, Linux e macOS)

Os usuários do vcpkg no Windows, Linux e macOS podem baixar e instalar roaring com um único comando de seu shell favorito.

No Linux e macOS:

 $ ./vcpkg install roaring

irá construir e instalar roaring como uma biblioteca estática.

No Windows (64 bits):

 .vcpkg.exe install roaring:x64-windows

irá construir e instalar roaring como uma biblioteca compartilhada.

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

irá construir e instalar roaring como uma biblioteca estática.

Esses comandos também imprimirão instruções sobre como usar a biblioteca de projetos baseados em MSBuild ou CMake.

Se você achar que a versão do roaring fornecida com vcpkg está desatualizada, sinta-se à vontade para denunciá-la à comunidade vcpkg enviando um problema ou criando um PR.

Limitação relacionada ao SIMD

Nosso código AVX2 não usa números de ponto flutuante ou multiplicações, portanto, não está sujeito a aceleração de frequência turbo em processadores Intel de vários núcleos.

Nosso código AVX-512 só é habilitado em hardware recente (Intel Ice Lake ou superior e AMD Zen 4) onde a aceleração de frequência específica do SIMD não é observada.

Segurança do fio

Como, por exemplo, contêineres STL, a biblioteca CRoaring não possui suporte integrado a threads. Assim, sempre que você modifica um bitmap em um thread, não é seguro consultá-lo em outros. No entanto, você pode copiar um bitmap com segurança e usar ambas as cópias