CRoaring
Version 4.2.1
صور نقطية Roaring محمولة بلغة C (وC++) مع دعم كامل للمترجم المفضل لديك (GNUGC وLLVM's clang وVisual Studio وApple Xcode وIntel oneAPI). تم تضمينه في قائمة Awesome C لبرامج C مفتوحة المصدر.
تُستخدم مجموعات البت، والتي تسمى أيضًا الصور النقطية، بشكل شائع كهياكل بيانات سريعة. لسوء الحظ، يمكنهم استخدام الكثير من الذاكرة. للتعويض، غالبًا ما نستخدم الصور النقطية المضغوطة.
الصور النقطية الصاخبة هي صور نقطية مضغوطة تميل إلى التفوق على الصور النقطية المضغوطة التقليدية مثل 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)، وApache Kylin من موقع eBay. تُستخدم مكتبة CRoaring في عدة أنظمة مثل Apache Doris، وClickHouse، وRedpanda، وStarRocks. يستخدم محرك YouTube SQL، Google Procella، الصور النقطية الهادرة للفهرسة.
قمنا بنشر مقالة تمت مراجعتها من قبل النظراء حول تصميم وتقييم هذه المكتبة:
تم اكتشاف أن الصور النقطية الهادرة تعمل بشكل جيد في العديد من التطبيقات المهمة:
استخدم Roaring لضغط الصور النقطية كلما أمكن ذلك. لا تستخدم طرقًا أخرى لضغط الصور النقطية (Wang et al., SIGMOD 2017)
توجد مواصفات تنسيق متسلسلة لقابلية التشغيل البيني بين التطبيقات. وبالتالي، من الممكن إجراء تسلسل لصورة Roaring Bitmap من C++، وقراءتها في Java، وتعديلها، وإعادة تسلسلها وقراءتها في Go وPython.
الهدف الأساسي من CRoaring هو توفير تنفيذ عالي المستوى ومنخفض المستوى يستفيد بشكل كامل من أحدث الأجهزة. الصور النقطية الصاخبة متاحة بالفعل على مجموعة متنوعة من الأنظمة الأساسية من خلال تطبيقات Java وGo وRust.... CRoaring هي مكتبة تسعى إلى تحقيق أداء فائق من خلال البقاء على مقربة من أحدث الأجهزة.
(ج) 2016-... المؤلفون الزاحفون.
لا يكاد أي شخص لديه حق الوصول إلى نظام حقيقي كبير. ومع ذلك، فإننا ندعم الأنظمة ذات النهاية الكبيرة مثل IBM s390x من خلال المحاكيات --- باستثناء تسلسل الإدخال والإخراج الذي يتم دعمه فقط على الأنظمة ذات النهاية الصغيرة (راجع الإصدار 423).
يمكن دمج مكتبة CRoaring في ملف مصدر واحد مما يسهل التكامل في المشاريع الأخرى. علاوة على ذلك، من خلال إتاحة تجميع كل التعليمات البرمجية المهمة في وحدة تجميع واحدة، يمكن تحسين الأداء. لمعرفة الأساس المنطقي، يرجى الاطلاع على وثائق SQLite، أو إدخال ويكيبيديا المقابل. لا يحتاج المستخدمون الذين يختارون هذا المسار إلى الاعتماد على نظام إنشاء 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 <stdio.h>
#include <stdlib.h>
#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 ;
}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 . راجع عرضنا التوضيحي للتكلفة لكل ألف ظهور لمزيد من التفاصيل.
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 محليًا، فيمكنك استخدامها مع وظيفة find_package الخاصة بـ CMake كما في هذا المثال:
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 <iostream>
#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)لإنشاء الملفات المدمجة بنفسك، يمكنك استدعاء برنامج نصي bash...
./amalgamation.sh إذا كنت تفضل الإخراج الصامت، فيمكنك استخدام الأمر التالي لإعادة توجيه stdout :
./amalgamation.sh > /dev/null (تعد قذائف Bash قياسية في نظامي Linux وmacOS. وتتوفر قذائف Bash في نظام التشغيل Windows كجزء من GitHub Desktop تحت اسم Git Shell . لذا، إذا قمت باستنساخ مستودع CRoaring GitHub من داخل GitHub Desktop، فيمكنك النقر بزر الماوس الأيمن على CRoaring ، حدد Git Shell ثم أدخل الأوامر المذكورة أعلاه.)
ليس من الضروري استدعاء البرنامج النصي في دليل CRoaring. يمكنك استدعاؤه من أي دليل تريد كتابة ملفات الدمج فيه.
سيقوم بإنشاء ثلاثة ملفات لمستخدمي C: roaring.h و roaring.c و amalgamation_demo.c ... بالإضافة إلى بعض التعليمات المختصرة. يعد الملف 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
افتراضيًا، تقوم أدوات قياس الأداء باختيار مجموعة بيانات واحدة (على سبيل المثال، CRoaring/benchmarks/realdata/census1881 ). لدينا العديد من مجموعات البيانات ويمكنك اختيار مجموعات أخرى:
./build/microbenchmarks/bench benchmarks/realdata/wikileaks-noquotes
يمكنك تعطيل بعض الوظائف لغرض قياس الأداء. على سبيل المثال، بافتراض أن لديك معالج x64، يمكنك قياس الكود بدون 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 <roaring.h>
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
...
}بشكل افتراضي نستخدم:
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 اصطلاح C حيث لا يكون free(NULL) / aligned_free(NULL) أي تأثير.
يفترض هذا المثال أنه تم إنشاء CRoaring وأنك تقوم بالارتباط بالمكتبة المقابلة. بشكل افتراضي، سيقوم CRoaring بتثبيت ملفات الرأس الخاصة به في دليل roaring . إذا كنت تعمل من خلال البرنامج النصي للدمج، فيمكنك إضافة السطر #include "roaring.c" إذا لم تكن ترتبط بمكتبة CRoaring سابقة الإنشاء واستبدال #include <roaring/roaring.h> بـ #include "roaring.h" .
#include <roaring/roaring.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
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 ;
}نحن ندعم أيضًا الصور النقطية المضغوطة الفعالة 64 بت في لغة 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) الصور النقطية التقليدية ذات 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 * ) قد تستخدم ذاكرة أكبر بكثير من الصورة النقطية الهادرة في بعض الحالات. يجب عليك تشغيل معايير لتحديد ما إذا كان التحويل إلى مجموعة بت له فوائد الأداء في حالتك.
يفترض هذا المثال أنه تم إنشاء CRoaring وأنك تقوم بالارتباط بالمكتبة المقابلة. افتراضيًا، سيقوم CRoaring بتثبيت ملفات الرأس الخاصة به في دليل roaring لذا قد تحتاج إلى استبدال #include "roaring.hh" بـ #include <roaring/roaring.hh> . إذا كنت تعمل من خلال البرنامج النصي للدمج، فيمكنك إضافة السطر #include "roaring.c" إذا لم تكن ترتبط بمكتبة CRoaring التي تم إنشاؤها مسبقًا.
# include < iostream >
# include " roaring.hh "
using namespace roaring ;
int main () {
Roaring r1;
for ( uint32_t i = 100 ; i < 1000 ; i++) {
r1. add (i);
}
// check whether a value is contained
assert (r1. contains ( 500 ));
// compute how many bits there are:
uint32_t cardinality = r1. cardinality ();
// if your bitmaps have long runs, you can compress them by calling
// run_optimize
uint32_t size = r1. getSizeInBytes ();
r1. runOptimize ();
// you can enable "copy-on-write" for fast and shallow copies
r1. setCopyOnWrite ( true );
uint32_t compact_size = r1. getSizeInBytes ();
std::cout << " size before run optimize " << size << " bytes, and after "
<< compact_size << " bytes. " << std::endl;
// create a new bitmap with varargs
Roaring r2 = Roaring::bitmapOf ( 5 , 1 , 2 , 3 , 5 , 6 );
r2. printf ();
printf ( " n " );
// create a new bitmap with initializer list
Roaring r2i = Roaring::bitmapOfList ({ 1 , 2 , 3 , 5 , 6 });
assert (r2i == r2);
// we can also create a bitmap from a pointer to 32-bit integers
const uint32_t values[] = { 2 , 3 , 4 };
Roaring r3 ( 3 , values);
// we can also go in reverse and go from arrays to bitmaps
uint64_t card1 = r1. cardinality ();
uint32_t *arr1 = new uint32_t [card1];
r1. toUint32Array (arr1);
Roaring r1f (card1, arr1);
delete[] arr1;
// bitmaps shall be equal
assert (r1 == r1f);
// we can copy and compare bitmaps
Roaring z (r3);
assert (r3 == z);
// we can compute union two-by-two
Roaring r1_2_3 = r1 | r2;
r1_2_3 |= r3;
// we can compute a big union
const Roaring *allmybitmaps[] = {&r1, &r2, &r3};
Roaring bigunion = Roaring::fastunion ( 3 , allmybitmaps);
assert (r1_2_3 == bigunion);
// we can compute intersection two-by-two
Roaring i1_2 = r1 & r2;
// we can write a bitmap to a pointer and recover it later
uint32_t expectedsize = r1. getSizeInBytes ();
char *serializedbytes = new char [expectedsize];
r1. write (serializedbytes);
// readSafe will not overflow, but the resulting bitmap
// is only valid and usable if the input follows the
// Roaring specification: https://github.com/RoaringBitmap/RoaringFormatSpec/
Roaring t = Roaring::readSafe (serializedbytes, expectedsize);
assert (r1 == t);
delete[] serializedbytes;
// we can iterate over all values using custom functions
uint32_t counter = 0 ;
r1.iterate(
[]( uint32_t value, void *param) {
*( uint32_t *)param += value;
return true ;
},
&counter);
// we can also iterate the C++ way
counter = 0 ;
for (Roaring::const_iterator i = t. begin (); i != t. end (); i++) {
++counter;
}
// counter == t.cardinality()
// we can move iterators to skip values
const uint32_t manyvalues[] = { 2 , 3 , 4 , 7 , 8 };
Roaring rogue ( 5 , manyvalues);
Roaring::const_iterator j = rogue. begin ();
j. equalorlarger ( 4 ); // *j == 4
return EXIT_SUCCESS;
}
يتبع CRoaring سير عمل 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 . في مثل هذه الحالات، سيتم تحسين الملف الثنائي المُنتج للمعالجات التي تتمتع بخصائص عملية هاسويل وقد لا تعمل على بنيات أقدم. يمكنك معرفة قائمة القيم المعمارية الصالحة عن طريق كتابة 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
نحن نفترض أن لديك جهاز كمبيوتر مشتركًا يعمل بنظام Windows ومزودًا ببرنامج Visual Studio 2015 على الأقل ومعالج x64.
للإنشاء باستخدام Visual Studio 2015 على الأقل من سطر الأوامر:
cmake من سطر الأوامر.VisualStudio .CRoaring في قائمة مستودعات GitHub، وتحديد Open in Git Shell ، ثم اكتب cd VisualStudio في الصدفة المنشأة حديثًا.cmake -DCMAKE_GENERATOR_PLATFORM=x64 .. في الصدفة أثناء وجودك في مستودع VisualStudio . (بدلاً من ذلك، إذا كنت ترغب في إنشاء مكتبة ثابتة، فيمكنك استخدام سطر الأوامر 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 عند تثبيت C++ Development Workload داخل Visual Studio.File > Open > Folder... لفتح مجلد CRoaring.CMakeLists.txt في الدليل الأصلي داخل Solution Explorer وحدد Build لإنشاء المشروع.Select Startup Item... واختر أحد الاختبارات. قم بإجراء الاختبار بالضغط على الزر الموجود على يسار القائمة المنسدلة.لدينا تحسينات خاصة بـ AVX2 وAVX-512 في التعليمات البرمجية، ويتم تشغيلها ديناميكيًا بناءً على الأجهزة المكتشفة في وقت التشغيل.
conan ) يمكنك تثبيت الثنائيات المعدة مسبقًا roaring أو إنشائها من المصدر باستخدام Conan. استخدم الأمر التالي لتثبيت أحدث إصدار:
conan install --requires="roaring/[*]" --build=missing
للحصول على تعليمات مفصلة حول كيفية استخدام كونان، يرجى الرجوع إلى وثائق كونان.
يتم تحديث وصفة كونان roaring من قبل المشرفين على كونان والمساهمين في المجتمع. إذا كان الإصدار قديمًا، فيرجى إنشاء مشكلة أو سحب طلب في مستودع ConanCenterIndex.
vcpkg على أنظمة التشغيل Windows وLinux وmacOS) يمكن لمستخدمي vcpkg على أنظمة التشغيل Windows وLinux وmacOS تنزيل وتثبيت 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.
إذا وجدت أن إصدار roaring الذي تم شحنه مع vcpkg قديم، فلا تتردد في إبلاغ مجتمع vcpkg به إما عن طريق إرسال مشكلة أو عن طريق إنشاء علاقات عامة.
لا يستخدم كود AVX2 الخاص بنا أرقام الفاصلة العائمة أو الضرب، لذا فهو لا يخضع لاختناق التردد التوربيني في معالجات Intel متعددة النواة.
يتم تمكين رمز AVX-512 الخاص بنا فقط على الأجهزة الحديثة (Intel Ice Lake أو أفضل وAMD Zen 4) حيث لا يتم ملاحظة اختناق التردد الخاص بـ SIMD.
مثل حاويات STL، على سبيل المثال، لا تحتوي مكتبة CRoaring على دعم لمؤشر الترابط المضمن. ومن ثم، كلما قمت بتعديل صورة نقطية في أحد المواضيع، فمن غير الآمن الاستعلام عنها في موضوعات أخرى. ومع ذلك، يمكنك نسخ صورة نقطية بأمان واستخدام كلا النسختين
