CRoaring
Version 4.2.1
お気に入りのコンパイラ (GNU GCC、LLVM の Clang、Visual Studio、Apple Xcode、Intel oneAPI) を完全にサポートする、C (および C++) のポータブル Roaring ビットマップ。オープンソース C ソフトウェアの Awesome C リストに含まれています。
ビットセット (ビットマップとも呼ばれます) は、高速データ構造として一般に使用されます。残念ながら、メモリを過剰に使用する可能性があります。これを補うために、圧縮されたビットマップがよく使用されます。
Roaring ビットマップは、WAH、EWAH、Concise などの従来の圧縮ビットマップよりも優れたパフォーマンスを発揮する傾向のある圧縮ビットマップです。これらは、Apache Lucene などのいくつかの主要システムや、Solr や Elasticsearch、Metamarkets の Druid、LinkedIn Pinot、Netflix Atlas、Apache Spark、OpenSearchServer、Cloud Torrent、Whoosh、InfluxDB、Pilosa、Bleve、Microsoft Visual Studio Team などの派生システムで使用されています。サービス (VSTS)、および eBay の Apache Kylin。 CRoaring ライブラリは、Apache Doris、ClickHouse、Redpanda、StarRocks などのいくつかのシステムで使用されています。 YouTube SQL エンジンである Google Procella は、インデックス作成に Roaring ビットマップを使用します。
このライブラリの設計と評価に関する査読済みの記事を公開しました。
Roaring ビットマップは、多くの重要なアプリケーションでうまく機能することがわかっています。
ビットマップ圧縮には可能な限り Roaring を使用してください。他のビットマップ圧縮方法は使用しないでください (Wang et al.、SIGMOD 2017)
実装間の相互運用性のためにシリアル化された形式の仕様があります。したがって、C++ から Roaring Bitmap をシリアル化し、Java で読み取り、変更し、再度シリアル化し、Go と Python で読み取ることが可能です。
CRoaring の主な目標は、最新のハードウェアを最大限に活用する高性能の低レベル実装を提供することです。 Roaring ビットマップは、Java、Go、Rust などの実装を通じて、さまざまなプラットフォームですでに利用可能です。 CRoaring は、最新のハードウェアに近づき、優れたパフォーマンスの実現を目指すライブラリです。
(c) 2016-...CRoaring 著者。
実際のビッグエンディアン システムにアクセスできる人はほとんどいません。それにもかかわらず、リトル エンディアン システムでのみサポートされる IO シリアル化を除き、エミュレータを通じて IBM s390x などのビッグ エンディアン システムをサポートします (問題 423 を参照)。
CRoaring ライブラリは 1 つのソース ファイルに統合できるため、他のプロジェクトへの統合が容易になります。さらに、すべての重要なコードを 1 つのコンパイル単位にコンパイルできるようにすることで、パフォーマンスを向上させることができます。理論的根拠については、SQLite のドキュメント、または対応する Wikipedia エントリを参照してください。このルートを選択するユーザーは、CRoaring のビルド システム (CMake ベース) に依存する必要はありません。
各リリースの一部として統合されたファイルを提供します。
Linux または macOS ユーザーは、最新の C または C++ コンパイラがインストールされており、標準ユーティリティ ( wget ) がインストールされている場合は、次の手順に従うことができます。
wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.c
wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.h
wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.hh
demo.cという名前の新しいファイルを作成します。 #include demo.cppという名前の新しいファイルを作成します。 # include < iostream >
# include " roaring.hh " // the amalgamated roaring.hh includes roaring64map.hh
# include " roaring.c "
int main () {
roaring::Roaring r1;
for ( uint32_t i = 100 ; i < 1000 ; i++) {
r1. add (i);
}
std::cout << " cardinality = " << r1. cardinality () << std::endl;
roaring::Roaring64Map r2;
for ( uint64_t i = 18000000000000000100ull ; i < 18000000000000001000ull ; i++) {
r2. add (i);
}
std::cout << " cardinality = " << r2. cardinality () << std::endl;
return 0 ;
} cc -o demo demo.c
c++ -std=c++11 -o demopp demo.cpp
./demo cardinality = 900
1000
./demopp cardinality = 900
cardinality = 900
CMake と CPM が気に入っている場合は、 CMakeLists.txtファイルに数行追加するだけでCRoaringリリースを入手できます。詳細については、CPM のデモをご覧ください。
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)CMake が気に入った場合は、 CMakeLists.txtファイルに数行を追加するだけでCRoaringリリースを入手できます。詳細については、デモをご覧ください。
CRoaring ライブラリをローカルにインストールした場合は、次の例のように CMake のfind_package関数でそれを使用できます。
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 結合されたファイルを自分で生成するには、bash スクリプトを呼び出すことができます...
./amalgamation.shサイレント出力を希望する場合は、次のコマンドを使用してstdoutリダイレクトできます。
./amalgamation.sh > /dev/null (Bash シェルは、Linux および macOS では標準です。Bash シェルは、Windows ではGit Shellという名前で GitHub デスクトップの一部として利用できます。したがって、GitHub デスクトップ内からCRoaring GitHub リポジトリのクローンを作成した場合は、 CRoaringを右クリックできます、 Git Shellを選択し、上記のコマンドを入力します。)
CRoaring ディレクトリ内のスクリプトを呼び出す必要はありません。これは、統合ファイルを書き込む任意のディレクトリから呼び出すことができます。
C ユーザー向けに、 roaring.h 、 roaring.c 、 amalgamation_demo.cという 3 つのファイルと、いくつかの簡単な手順が生成されます。 amalgamation_demo.cファイルは短い例ですが、 roaring.hとroaring.cは「結合された」ファイル (プロジェクトのすべてのソース ファイルとヘッダー ファイルを含む) です。つまり、ファイルroaring.hとroaring.cプロジェクトにコピーするだけで準備完了です。ライブラリを作成する必要はありません。 amalgamation_demo.cファイルを参照してください。
C インターフェイスはファイル内にあります。
C++ インターフェイスもあります。
一部のユーザーは大量のデータを処理する必要があります。可能であればバッチで値を追加するほうがはるかに高速で経済的であるため、これらのユーザーはaddMany (C++) のroaring_bitmap_or_many (C) 関数を認識することが重要になる場合があります。さらに、 runOptimize (C++) 関数またはroaring_bitmap_run_optimize (C) 関数を定期的に呼び出すと効果がある場合があります。
Google ベンチマークを使用して構築されたマイクロベンチマークがあります。 Linux または macOS では、次のように実行できます。
cmake -B build -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build build
./build/microbenchmarks/bench
デフォルトでは、ベンチマーク ツールは 1 つのデータ セットを選択します (例: CRoaring/benchmarks/realdata/census1881 )。いくつかのデータセットがあり、他のデータセットを選択することもできます。
./build/microbenchmarks/bench benchmarks/realdata/wikileaks-noquotes
ベンチマークの目的で一部の機能を無効にすることができます。たとえば、x64 プロセッサを使用していると仮定すると、プロセッサとコンパイラの両方が AVX-512 をサポートしている場合でも、AVX-512 を使用せずにコードのベンチマークを実行できます。
cmake -B buildnoavx512 -D ROARING_DISABLE_AVX512=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build buildnoavx512
./buildnoavx512/microbenchmarks/bench
AVX または AVX-512 を使用せずにベンチマークを実行することもできます。
cmake -B buildnoavx -D ROARING_DISABLE_AVX=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build buildnoavx
./buildnoavx/microbenchmarks/bench
一般ユーザーの場合、CRoaring は追加のコードなしでデフォルトのアロケーターを適用します。ただし、カスタム メモリ アロケータが必要な場合は、グローバル メモリ フックも提供されます。以下に例を示します。
#include デフォルトでは以下を使用します。
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 ,
}; free / aligned_free関数は、 free(NULL) / aligned_free(NULL)が影響を及ぼさない C 規約に従う必要があります。
この例では、CRoaring が構築されており、対応するライブラリに対してリンクしていることを前提としています。デフォルトでは、CRoaring はそのヘッダー ファイルをroaringディレクトリにインストールします。アマルガム スクリプトから作業している場合、事前に構築された CRoaring ライブラリにリンクしていない場合は#include "roaring.c"という行を追加し、 #include を#include "roaring.h"に置き換えることができます。 。
#include C での効率的な 64 ビット圧縮ビットマップもサポートしています。
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 は従来の 32 ビット ビットマップと同様です。ヘッダー ファイルroaring64.hを参照してください ( roaring.hと比較してください)。
ライブラリの一部として規約ビットセット (非圧縮) をサポートします。
簡単な例:
bitset_t * b = bitset_create ();
bitset_set ( b , 10 );
bitset_get ( b , 10 ); // returns true
bitset_free ( b ); // frees memoryより高度な例:
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場合によっては、Roaring ビットマップを従来の (非圧縮) ビットセットに変換したい場合があります。実際、ビットセットには、場合によってはクエリのパフォーマンスが向上するなどの利点があります。次のコードは、その方法を示しています。
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 );場合によっては、規約ビットセット ( bitset_t * ) が Roaring ビットマップよりも多くのメモリを使用する可能性があることに注意してください。ベンチマークを実行して、ビットセットへの変換によってパフォーマンス上の利点があるかどうかを判断する必要があります。
この例では、CRoaring が構築されており、対応するライブラリに対してリンクしていることを前提としています。デフォルトでは、CRoaring はヘッダー ファイルをroaringディレクトリにインストールするため、 #include "roaring.hh"を#include に置き換える必要がある場合があります。アマルガム スクリプトから作業している場合、CRoaring の事前構築済みライブラリに対してリンクしていない場合は、 #include "roaring.c"という行を追加できます。
# include < iostream >
# include " roaring.hh "
using namespace roaring ;
int main () {
Roaring r1;
for ( uint32_t i = 100 ; i < 1000 ; i++) {
r1. add (i);
}
// check whether a value is contained
assert (r1. contains ( 500 ));
// compute how many bits there are:
uint32_t cardinality = r1. cardinality ();
// if your bitmaps have long runs, you can compress them by calling
// run_optimize
uint32_t size = r1. getSizeInBytes ();
r1. runOptimize ();
// you can enable "copy-on-write" for fast and shallow copies
r1. setCopyOnWrite ( true );
uint32_t compact_size = r1. getSizeInBytes ();
std::cout << " size before run optimize " << size << " bytes, and after "
<< compact_size << " bytes. " << std::endl;
// create a new bitmap with varargs
Roaring r2 = Roaring::bitmapOf ( 5 , 1 , 2 , 3 , 5 , 6 );
r2. printf ();
printf ( " n " );
// create a new bitmap with initializer list
Roaring r2i = Roaring::bitmapOfList ({ 1 , 2 , 3 , 5 , 6 });
assert (r2i == r2);
// we can also create a bitmap from a pointer to 32-bit integers
const uint32_t values[] = { 2 , 3 , 4 };
Roaring r3 ( 3 , values);
// we can also go in reverse and go from arrays to bitmaps
uint64_t card1 = r1. cardinality ();
uint32_t *arr1 = new uint32_t [card1];
r1. toUint32Array (arr1);
Roaring r1f (card1, arr1);
delete[] arr1;
// bitmaps shall be equal
assert (r1 == r1f);
// we can copy and compare bitmaps
Roaring z (r3);
assert (r3 == z);
// we can compute union two-by-two
Roaring r1_2_3 = r1 | r2;
r1_2_3 |= r3;
// we can compute a big union
const Roaring *allmybitmaps[] = {&r1, &r2, &r3};
Roaring bigunion = Roaring::fastunion ( 3 , allmybitmaps);
assert (r1_2_3 == bigunion);
// we can compute intersection two-by-two
Roaring i1_2 = r1 & r2;
// we can write a bitmap to a pointer and recover it later
uint32_t expectedsize = r1. getSizeInBytes ();
char *serializedbytes = new char [expectedsize];
r1. write (serializedbytes);
// readSafe will not overflow, but the resulting bitmap
// is only valid and usable if the input follows the
// Roaring specification: https://github.com/RoaringBitmap/RoaringFormatSpec/
Roaring t = Roaring::readSafe (serializedbytes, expectedsize);
assert (r1 == t);
delete[] serializedbytes;
// we can iterate over all values using custom functions
uint32_t counter = 0 ;
r1.iterate(
[]( uint32_t value, void *param) {
*( uint32_t *)param += value;
return true ;
},
&counter);
// we can also iterate the C++ way
counter = 0 ;
for (Roaring::const_iterator i = t. begin (); i != t. end (); i++) {
++counter;
}
// counter == t.cardinality()
// we can move iterators to skip values
const uint32_t manyvalues[] = { 2 , 3 , 4 , 7 , 8 };
Roaring rogue ( 5 , manyvalues);
Roaring::const_iterator j = rogue. begin ();
j. equalorlarger ( 4 ); // *j == 4
return EXIT_SUCCESS;
}
CRoaring は標準の cmake ワークフローに従います。プロジェクト (CRoaring) のルート ディレクトリから始めて、次のことができます。
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
( buildディレクトリは他のディレクトリ名に置き換えることができます。) デフォルトでは、すべてのテストはすべてのプラットフォームでビルドされます。テストのビルドと実行をスキップするには、コマンド ラインに-DENABLE_ROARING_TESTS=OFFを追加します。
すべてのcmakeプロジェクトと同様に、(たとえば) -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++ cmakeコマンド ラインに追加することで、使用するコンパイラを指定できます。
Clang または GCC を使用していて、ターゲット アーキテクチャがわかっている場合は、 -DROARING_ARCH=archを指定してアーキテクチャを設定できます。たとえば、多数のサーバーがあり、最も古いサーバーが Intel haswellアーキテクチャを実行している場合は、 - DROARING_ARCH=haswellを指定できます。このような場合、生成されたバイナリは haswell プロセスの特性を持つプロセッサ向けに最適化され、古いアーキテクチャでは動作しない可能性があります。 man gccと入力すると、有効なアーキテクチャ値のリストを確認できます。
mkdir -p build_haswell
cd build_haswell
cmake -DROARING_ARCH=haswell ..
cmake --build .
デバッグ リリースの場合は、プロジェクトのルート ディレクトリ (CRoaring) から開始して、次のことを試してください。
mkdir -p debug
cd debug
cmake -DCMAKE_BUILD_TYPE=Debug -DROARING_SANITIZE=ON ..
ctest
コードがスタイル規則に従っていることを確認するには ( clang-formatがインストールされていることを確認してください):
./tools/clang-format-check.sh
スタイル規則に従ってコードを再フォーマットするには ( clang-formatがインストールされていることを確認してください):
./tools/clang-format.sh
ここでは、少なくとも Visual Studio 2015 と x64 プロセッサを搭載した一般的な Windows PC を使用していることを前提としています。
コマンド ラインから Visual Studio 2015 以上を使用してビルドするには:
cmake使用できるようにするように依頼してください。VisualStudioなどのサブディレクトリを作成します。CRoaringを右クリックし、 Open in Git Shellを選択し、新しく作成したシェルにcd VisualStudioと入力します。VisualStudioリポジトリ内で、シェルにcmake -DCMAKE_GENERATOR_PLATFORM=x64 ..と入力します。 (あるいは、静的ライブラリをビルドする場合は、コマンド ラインcmake -DCMAKE_GENERATOR_PLATFORM=x64 -DROARING_BUILD_STATIC=ON ..を使用することもできます。)RoaringBitmap.sln )。このファイルを Visual Studio で開きます。これで、プロジェクトをビルドしてテストを実行できるようになります。たとえば、 Solution Explorerウィンドウ ( Viewメニューから利用可能) で、 ALL_BUILDを右クリックし、 Buildを選択します。コードをテストするには、 Solution ExplorerウィンドウでRUN_TESTSを選択し、 Buildを選択します。少なくとも Visual Studio 2017 を使用して IDE で直接ビルドするには:
Visual C++ tools for CMake選択します。File > Open > Folder...を使用して CRoaring フォルダーを開きます。Solution Explorer内の親ディレクトリにあるCMakeLists.txtを右クリックし、 [ビルド] を選択してプロジェクトをBuildします。Select Startup Item...メニューをドロップし、テストの 1 つを選択します。ドロップダウンの左側にあるボタンを押してテストを実行します。コードには AVX2 および AVX-512 に固有の最適化があり、実行時に検出されたハードウェアに基づいて動的に最適化されます。
conanの使い方） roaring用に事前にビルドされたバイナリをインストールすることも、Conan を使用してソースからビルドすることもできます。最新バージョンをインストールするには、次のコマンドを使用します。
conan install --requires="roaring/[*]" --build=missing
コナンの使用方法の詳細については、コナンのドキュメントを参照してください。
roaringコナンのレシピは、コナンのメンテナーとコミュニティの貢献者によって最新の状態に保たれています。バージョンが古い場合は、ConanCenterIndex リポジトリで問題を作成するか、プル リクエストを作成してください。
vcpkgの使用) Windows、Linux、macOS 上の vcpkg ユーザーは、お気に入りのシェルから 1 つのコマンドでroaringダウンロードしてインストールできます。
Linux および macOS の場合:
$ ./vcpkg install roaring
roaring静的ライブラリとしてビルドしてインストールします。
Windows (64 ビット) の場合:
.vcpkg.exe install roaring:x64-windows
共有ライブラリとしてroaringビルドしてインストールします。
.vcpkg.exe install roaring:x64-windows-static
roaring静的ライブラリとしてビルドしてインストールします。
これらのコマンドは、MSBuild または CMake ベースのプロジェクトからライブラリを使用する方法に関する指示も出力します。
vcpkgに同梱されているroaringのバージョンが古いことに気付いた場合は、問題を送信するか PR を作成して、 vcpkgコミュニティに遠慮なく報告してください。
当社の AVX2 コードは浮動小数点数や乗算を使用しないため、メニーコア Intel プロセッサ上のターボ周波数スロットルの影響を受けません。
当社の AVX-512 コードは、SIMD 固有の周波数スロットルが観察されない最近のハードウェア (Intel Ice Lake 以降および AMD Zen 4) でのみ有効です。
たとえば、STL コンテナーと同様、CRoaring ライブラリにはスレッド サポートが組み込まれていません。したがって、あるスレッドでビットマップを変更するたびに、他のスレッドでそれをクエリするのは安全ではありません。ただし、ビットマップを安全にコピーし、両方のコピーを使用することはできます。
