BitMagic
v.7.13.4
BitMagic dibuat sebagai perangkat Aljabar Kumpulan untuk Pengambilan Informasi tetapi saat ini berkembang menjadi pustaka komponen Ilmu Data yang lebih umum untuk struktur kompak memori dan algoritme pada vektor data ringkas. BitMagic mengimplementasikan bit-vektor dan wadah (vektor) terkompresi berdasarkan ide transformasi bit-slicing, kompresi Rank-Select, dan komputasi logis pada model terkompresi memori.
Semua kontainer ringkas BitMagic dapat diserialkan (dengan kompresi menggunakan Pengodean Interpolatif Biner yang canggih) untuk penyimpanan dan transfer jaringan yang efisien. Semua kontainer dapat dicari dengan cepat dalam bentuk terkompresi.
BitMagic menawarkan serangkaian metode dan alat untuk merancang aplikasi Anda menggunakan teknik HPC untuk menghemat memori dengan cepat (sehingga dapat memuat lebih banyak data dalam satu unit komputasi), meningkatkan penyimpanan dan pola lalu lintas saat menyimpan vektor dan model data dalam file atau objek penyimpanan (SQL atau noSQL), mengoptimalkan bandwidth sistem dari tingkat rendah (cache CPU) hingga pertukaran jaringan dan penyimpanan.
BitMagic memfasilitasi dua kelas besar skenario:
BitMagic digunakan sebagai bahan penyusun untuk:
Silakan kunjungi catatan kasus penggunaan kami: http://bitmagic.io/use-case.html
Pustaka BitMagic adalah pustaka berkinerja tinggi, menerapkan pengoptimalan untuk berbagai platform dan membangun target:
BitMagic menggunakan desain vektorisasi data paralel dengan tujuan tidak hanya memberikan kinerja thread tunggal terbaik tetapi juga untuk memfasilitasi komputasi paralel tinggi pada sistem banyak inti.
BitMagic menggunakan serangkaian algoritme kompresi, filter, dan transformasi untuk mengurangi jejak memori, biaya penyimpanan, dan transfer data jaringan. http://bitmagic.io/design.html
Silakan kunjungi catatan teknologi kami: http://bitmagic.io/articles.html
BitMagic mendukung penafsiran ulang bit-vektor sebagai kumpulan rentang 1 yang tidak tumpang tindih yang diapit dengan 0 (misalnya: 011110110). Fungsi himpunan reguler menyediakan operasi intreval perpotongan / penyatuan himpunan, mengimplementasikan iterator interval, dan mencari batas interval. Rentang dan interval memiliki kegunaan besar dalam bioinformatika, karena data genomik sering kali dianotasi sebagai rentang koordinat. BitMagic menawarkan blok penyusun untuk operasi yang efisien pada interval yang dikodekan sebagai bit-vektor (temukan interval awal/akhir, periksa apakah rentang adalah inetrval, ulangi interval
BitMagic mengimplementasikan operasi logika untuk logika 3 nilai Benar/Salah/Tidak Diketahui (juga logika trivalen, trivalen, ternary) dalam representasi dua bit-vektor yang ringkas, mendukung operasi Pembalikan, DAN, ATAU mengikuti definisi Kleene. https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic
BitMagic menggunakan konsep serialisasi-deserialisasi dua tahap. Fokusnya adalah pada deserialisasi cepat. BitMagic mengimplementasikan API untuk deserialisasi rentang vektor cepat dan mengumpulkan deserialisasi BLOB terkompresi. Fitur utama BitMagic adalah kemampuan untuk bekerja dengan data terkompresi.
Ini adalah keadaan operasional utama dalam RAM, di mana vektor disimpan dalam bentuk memori yang ringkas. Ringkas BUKAN kompresi. Dimungkinkan untuk mengakses elemen acak dalam wadah, memecahkan kode blok, mengulangi vektor, membuat pembaruan, menjalankan algoritma pencarian. Tahap Satu menawarkan penggunaan transparan, vektornya terlihat seperti STL. Ringkas adalah memori yang ringkas tetapi tidak terkompresi sepenuhnya.
BitMagic dapat membuat serialisasi semua container dan vektor dengan kompresi tambahan berdasarkan blok heuristik dan codec. Teknik pengkodean pekerja keras adalah: Binary Interpolative Coding (BIC) dan Elias Gamma.
Kontainer BitMagic disebut vektor "jarang" namun kenyataannya skema kompresinya bekerja dengan baik untuk data yang jarang dan padat.
BitMagic diuji pada kumpulan daftar terbalik dan jumlah kumpulan data kepemilikan yang menjadi patokan Gov2. http://bitmagic.io/bm5-cmpr.html
Deserialisasi selalu kembali ke Tahap Satu, sehingga data tidak sepenuhnya didekodekan melainkan didekodekan
ringkas dalam RAM. Tujuan kami di sini adalah mengurangi jejak memori aplikasi dan meningkatkan latensi deserialisasi. Algoritma dekompresi mendukung deserialisasi rentang sewenang-wenang atau bahkan mengumpulkan deserialisasi elemen.
BitMagic mendukung vektor ringkas (memori ringkas) berdasarkan transformasi transposisi bit
juga dikenal sebagai bit-plane compression (BPC) (alias bit-slicing) ditambah kompresi Rank-Select. Vektor ringkas BitMagic diberi label "jarang" yang agak menyesatkan tetapi berfungsi dengan baik untuk vektor padat.
Transposisi bit memecahkan dua tujuan: membebaskan dataran bit yang tidak terpakai dan mengisolasi keteraturan dan entropi menjadi vektor-bit yang terpisah (jarang). Kompresi pada bit-plane menawarkan kinerja memori superior dan pencarian cepat. Salah satu tujuan desain untuk melakukan pencarian bebas indeks pada vektor ringkas menggunakan operasi logika vektor cepat.
Vektor ringkas BitMagic dapat dicari tanpa indeks dalam bentuk terkompresi memori. Ini cepat!
Implementasi transposisi bit yang ringkas berfungsi dengan baik untuk vektor bilangan bulat (bertanda tangan atau tidak bertanda tangan) serta vektor string. Ini menyaingi skema ringkas lainnya seperti pohon awalan. Vektor ringkas dapat diurutkan dan tidak diurutkan. Idenya di sini mirip dengan Apache Arrow-Parquet, tetapi dibutuhkan lebih jauh dengan kompresi bit-plane dan penggunaan ekstensif kompresi Rank-Select yang dipercepat.
BitMagic mendukung evolusi serialisasi (protokol) - jika format serialisasi berubah, data lama yang disimpan tetap dapat dibaca oleh kode baru. Kode lama TIDAK akan bisa membaca BLOB baru. BitMagic mengubah nomor versi utama ketika format serialisasi berubah.
BitMagic mengimplementasikan panggilan profil memori untuk semua vektor. Vektor apa pun dapat diambil sampelnya untuk jejak memori sehingga sistem tingkat atas dapat mengadaptasi pengelolaan memori berdasarkan pembuatan profil memori waktu proses. Kasus penggunaan yang umum adalah cache memori objek dengan kompresi ke RAM dan kemudian dikeluarkan ke disk berdasarkan konsumsi sumber daya dan biaya (keseimbangan dinamis antara permintaan dan penawaran).
Ya! BitMagic mendukung 64-bit, dapat digunakan dengan ruang alamat 32-bit (lebih sedikit overhead) atau ruang alamat 64-bit penuh. Ruang alamat 32-bit adalah mode default. Elemen 2^31-1 harus cocok untuk sistem IR dan ilmu data jarak pendek hingga menengah. Mode alamat 64-bit tersedia menggunakan #define BM64ADDR atau #include "bm64.h". Implementasi 64-bit saat ini memungkinkan 2^48-1 elemen vektor untuk sistem skala besar.
BitMagic mengkompilasi dan bekerja dengan WebAssmbly (emscripten). Versi terbaru mencakup beberapa penyesuaian, khusus untuk platform tersebut. Angka kinerja mendekati kode asli tanpa SIMD (terkadang setelahnya). Contoh baris kompilasi akan terlihat seperti:
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...
SIMD WebAssembly didukung tetapi tidak AKTIF secara default. Gunakan: #define BMWASMSIMDOPT untuk mengaktifkannya. Contoh cmd tertulis:
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -msse4.2 -msimd128 -D BMWASMSIMDOPT -s WASM=1 -s DISABLE_EXCEPTION_CATCHING=0 -fno-rtti
Implementasi saat ini menggunakan trans-kompilasi SSE4.2 (melalui intrinsik), jadi -msse4.2 diperlukan.
BitMagic sepenuhnya mendukung CPU ARM. Semua rilis diuji stres dengan Raspberry Pi 4. BitMagic mengimplementasikan beberapa penyesuaian algoritmik dan peningkatan khusus untuk ARM (seperti penggunaan instruksi LZCNT). Kontainer ringkas BitMagic bisa sangat berguna pada sistem tertanam untuk komputasi edge dengan jumlah memori yang tersedia terbatas.
Dukungan Arm Neon SIMD tersedia (melalui perpustakaan SSE2NEON).
BitMagic C++ adalah pustaka header saja (mudah dibuat dan digunakan dalam proyek Anda) dan dilengkapi dengan serangkaian contoh. TIDAK disarankan untuk menggunakan tes sebagai contoh kode untuk mempelajari penggunaan perpustakaan. Pengujian tidak menggambarkan pola dan model penggunaan terbaik dan sering kali sengaja dibuat tidak efisien.
Dokumentasi dan contoh API: http://www.bitmagic.io/apis.html
Tutorial Aljabar Himpunan: http://bitmagic.io/set-algebra.html
Kasus Penggunaan dan Catatan Aplikasi: http://bitmagic.io/use-case.html
Catatan teknis tentang optimalisasi kinerja: http://bitmagic.io/articles.html
Doksigen: http://bitmagic.io/doxygen/html/modules.html
Apache 2.0.
Penting! Kami meminta Anda untuk secara eksplisit menyebutkan proyek BitMagic dalam karya turunan apa pun atau materi yang kami terbitkan. Referensi yang tepat pada halaman produk/proyek Anda adalah PERSYARATAN untuk menggunakan Perpustakaan BitMagic.
Pustaka BitMagic memberikan perhatian serius pada kualitas kode dan cakupan pengujian.
Sebagai perpustakaan blok penyusun, BitMagic harus stabil dan sesuai agar dapat berguna.
Kami tidak mengandalkan pengujian unit saja, pengujian kami sering kali menggunakan "pengujian kekacauan" (alias fuzzing) di mana pengujian stres didasarkan pada kumpulan yang dihasilkan secara acak dan operasi yang diacak. Kami secara teratur membuat dan menjalankan pengujian untuk mode Rilis dan Debug untuk berbagai kombinasi pengoptimalan SIMD.
Semua varian uji coba membutuhkan waktu berhari-hari untuk dijalankan, sehingga cabang master yang berfungsi TIDAK dijamin sempurna sepanjang waktu. Untuk produksi silakan gunakan cabang atau distribusi rilis github yang stabil dari SourceForge: https://sourceforge.net/projects/bmagic/files/
Master GitHub menerima permintaan patch Kebijakan percabangan kami adalah bahwa master tidak dapat dianggap sepenuhnya stabil di antara rilis. (untuk stabilitas produksi silakan gunakan versi rilis)
Butuh bantuan dengan pemetaan ke Python dan bahasa lain (BitMagic memiliki binding C)
BitMagic C++ adalah paket perangkat lunak khusus header dan Anda mungkin dapat mengambil sumbernya dan langsung memasukkannya ke dalam proyek Anda. Semua sumber/header perpustakaan C++ ada di direktori src.
Namun jika Anda ingin menggunakan makefile kami, Anda harus mengikuti instruksi sederhana berikutnya:
Terapkan beberapa variabel lingkungan dengan menjalankan bmenv.sh di direktori root proyek:
$ source ./bmenv.sh
(silakan gunakan "." "./bmenv.sh" untuk menerapkan variabel lingkungan root)
gunakan GNU make (gmake) untuk membangun instalasi.
$make rebuild
atau (versi DEBUG)
$gmake DEBUG=YES rebuild
Kompiler default di Unix dan CygWin adalah g++. Jika Anda ingin mengubah default, Anda dapat melakukannya di makefile.in (seharusnya cukup mudah dilakukan)
Jika Anda menggunakan instalasi cygwin harap ikuti rekomendasi umum Unix. MSVC - solusi dan proyek tersedia melalui CMAKE.
Xcode - file proyek tersedia melalui CMAKE.
Pustaka BitMagic untuk pemetaan C dan JNI.
Perpustakaan BitMagic tersedia untuk bahasa C (ini sedang dalam proses). Tujuan utama dari C build adalah untuk menjembatani BitMagic ke bahasa pemrograman lain. C build ada di subdirektori "lang-maps".
C build membuat versi BitMagic build untuk SSE dan AVX dan menambahkan identifikasi CPU, sehingga sistem tingkat atas dapat mendukung identifikasi CPU dinamis dan pengiriman kode.
C build menggunakan kompiler C++, tetapi tidak menggunakan RTTI, pengecualian (disimulasikan dengan lompat jauh) dan manajemen memori C++, sehingga bahasa C++ netral, tanpa ketergantungan runtime. Algoritma dan perilaku digunakan bersama antara C dan C++.
Keadaan perkembangan saat ini:
Dukungan Python masih menunggu keputusan dan kami memerlukan bantuan di sini. Jika Anda antusias dengan Python dan merasa dapat membantu, silakan hubungi: anatoliy.kuznetsov @ yahoo dot com
Perpustakaan BitMagic membutuhkan CXX-11. Ia menggunakan semantik pemindahan, noexept, daftar inisialisasi, utas. Versi publik berikutnya akan menggunakan CXX-17 (constexpr ifs, dll).
###Penyempurnaan dan pengoptimalan:
Semua parameter penyempurnaan BitMagic dikontrol oleh definisi praprosesor (dan kunci kompiler khusus lengkungan target untuk pembuatan kode).
| #mendefinisikan | Keterangan | Lebar |
|---|---|---|
| BMSSE2OPT | Optimasi kode SSE2 | 128-bit |
| BMSSE42OPT | Optimasi kode SSE4.2 ditambah POPCNT, BSF, dll | 128-bit |
| BMAVX2OPT | Optimasi AVX2, POPCNT, LZCNT, BMI1, BMI2 | 256-bit |
| BMAVX512OPT | AVX-512, (percobaan) | 512-bit |
| BMWASMSIMDOPT | Pengoptimalan SIMD WebAssembly (melalui SSE4.2) | 128-bit |
| DBMNEONOPT | Optimasi Arm Neon SIMD (melalui terjemahan SSE2) | 128-bit |
####Batasan:
Definisi optimasi SIMD saling eksklusif, Anda TIDAK dapat memiliki BMSSE42OPT dan BMAVX2OPT secara bersamaan. Pilih satu saja.
Pustaka BM TIDAK mendukung banyak jalur kode dan identifikasi CPU runtime. Anda harus membangun secara khusus untuk sistem target Anda atau menggunakan build portabel default.
####Contoh:
Contoh dan pengujian BitMagic dapat dibuat dengan GCC menggunakan pengaturan baris cmd:
make BMOPTFLAGS=-DBMAVX2OPT rebuild
atau
make BMOPTFLAGS=-DBMSSE42OPT rebuild
Ini secara otomatis menerapkan kumpulan tanda compiler (GCC) yang tepat untuk build target.
CMAKE
cd build
cmake -DBMOPTFLAGS:STRING=BMSSE42OPT ..
make
ATAU
cmake -DBMOPTFLAGS:STRING=BMAVX2OPT ..
Pustaka BM mendukung kata kunci "batasi", beberapa kompiler (misalnya Intel C++) menghasilkan kode yang lebih baik (penyimpanan beban rusak) ketika kata kunci pembatasan membantu. Opsi ini dimatikan secara default karena sebagian besar kompiler C++ tidak mendukungnya. Untuk MENGAKTIFKANnya, harap #define BM_HASRESTRICT di proyek Anda. Beberapa kompiler menggunakan kata kunci "__restrict" untuk tujuan ini. Untuk memperbaikinya, tentukan makro BMRESTRICT untuk memperbaiki kata kunci.
Jika Anda ingin menggunakan perpustakaan BM dalam "proyek tanpa STL" (seperti sistem tertanam) tentukan BM_NO_STL.
Aturan ini hanya berlaku untuk metode inti bm::bvector<>. Algoritme tambahan, contoh, dll masih menggunakan STL.
Ikuti kami di Twitter: https://twitter.com/bitmagicio
Terima kasih telah menggunakan perpustakaan BitMagic!
email: [email protected]
Situs WEB: http://bitmagic.io
GitHub: https://github.com/tlk00/BitMagic
