CRoaring
Version 4.2.1
Переносимые растровые изображения Roaring на C (и C++) с полной поддержкой вашего любимого компилятора (GNU GCC, clang LLVM, Visual Studio, Apple Xcode, Intel oneAPI). Включен в список программного обеспечения C с открытым исходным кодом Awesome C.
Битовые наборы, также называемые растровыми изображениями, обычно используются в качестве быстрых структур данных. К сожалению, они могут использовать слишком много памяти. Чтобы компенсировать это, мы часто используем сжатые растровые изображения.
Ревущие растровые изображения — это сжатые растровые изображения, которые имеют тенденцию превосходить по производительности обычные сжатые растровые изображения, такие как WAH, EWAH или Consized. Они используются несколькими основными системами, такими как Apache Lucene и производными системами, такими как Solr и Elasticsearch, Metamarkets Druid, LinkedIn Pinot, Netflix Atlas, Apache Spark, OpenSearchServer, Cloud Torrent, Whoosh, InfluxDB, Pilosa, Bleve, Microsoft Visual Studio Team. Services (VSTS) и Apache Kylin от eBay. Библиотека CRoaring используется в нескольких системах, таких как Apache Doris, ClickHouse, Redpanda и StarRocks. SQL-движок YouTube, Google Procella, использует для индексации растровые изображения Roaring.
Мы опубликовали рецензируемую статью о дизайне и оценке этой библиотеки:
Ревущие растровые изображения хорошо работают во многих важных приложениях:
По возможности используйте Roaring для сжатия растровых изображений. Не используйте другие методы сжатия растровых изображений (Ванг и др., 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 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 локально, вы можете использовать ее с функцией 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 Чтобы самостоятельно сгенерировать объединенные файлы, вы можете вызвать сценарий bash...
./amalgamation.sh Если вы предпочитаете тихий вывод, вы можете использовать следующую команду для перенаправления stdout :
./amalgamation.sh > /dev/null (Оболочки Bash являются стандартными для Linux и macOS. Оболочки Bash доступны в Windows как часть рабочего стола GitHub под названием Git Shell . Поэтому, если вы клонировали репозиторий CRoaring GitHub из рабочего стола GitHub, вы можете щелкнуть правой кнопкой мыши 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 Benchmarks. В 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 По умолчанию мы используем:
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 на #include "roaring.h" .
#include Мы также поддерживаем эффективные 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 * ) в некоторых случаях может использовать гораздо больше памяти, чем растровое изображение Roaring. Вам следует провести тесты, чтобы определить, имеет ли преобразование в битовый набор преимущества в производительности в вашем случае.
В этом примере предполагается, что CRoaring собран и вы подключаете соответствующую библиотеку. По умолчанию CRoaring установит свои заголовочные файлы в каталог roaring , поэтому вам может потребоваться заменить #include "roaring.hh" на #include . Если вы работаете со сценарием объединения, вы можете добавить строку #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 . В таких случаях созданный двоичный файл будет оптимизирован для процессоров, имеющих характеристики процесса 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++ в 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
Подробные инструкции по использованию Conan можно найти в документации Conan.
Рецепт roaring Конана постоянно обновляется сопровождающими Conan и участниками сообщества. Если версия устарела, создайте проблему или запрос на извлечение в репозитории 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 , отправив сообщение о проблеме или создав PR.
Наш код AVX2 не использует числа с плавающей запятой или умножения, поэтому он не подлежит турборегулированию частоты на многоядерных процессорах Intel.
Наш код AVX-512 включен только на новейшем оборудовании (Intel Ice Lake или новее и AMD Zen 4), где не наблюдается регулирования частоты, специфичного для SIMD.
Как, например, контейнеры STL, библиотека CRoaring не имеет встроенной поддержки потоков. Таким образом, всякий раз, когда вы изменяете растровое изображение в одном потоке, запрашивать его в других потоках небезопасно. Однако вы можете безопасно скопировать растровое изображение и использовать обе копии.
