ビットマジック
v.7.13.4
BitMagic は、情報検索のための集合代数ツールキットとして作成されましたが、現在はメモリのコンパクトな構造と簡潔なデータ ベクトルのアルゴリズムのための、より一般的なデータ サイエンス コンポーネント ライブラリに進化しています。 BitMagic は、ビット スライス変換、ランク選択圧縮、メモリ圧縮モデル上の論理計算のアイデアに基づいて、圧縮されたビット ベクトルとコンテナ (ベクトル) を実装します。
すべての BitMagic の簡潔なコンテナは、効率的なストレージとネットワーク転送のためにシリアル化可能です (最先端のバイナリ補間コーディングを使用した圧縮を使用)。すべてのコンテナは圧縮形式で高速に検索できます。
BitMagic は、HPC 技術を使用してオンザフライでメモリを節約し (これにより、1 つのコンピューティング ユニットにより多くのデータを収めることができます)、データ ベクトルとモデルをファイルまたはオブジェクトに保存する際のストレージとトラフィック パターンを改善するアプリケーションを設計するためのメソッドとツールのセットを提供します。ストア (SQL または noSQL)、低レベル (CPU キャッシュ) からネットワークおよびストレージ交換に至るシステム帯域幅を最適化します。
BitMagic は、次の 2 つの大きなクラスのシナリオを容易にします。
BitMagic は以下の構成要素として使用されました。
ユースケースノートをご覧ください: http://bitmagic.io/use-case.html
BitMagic ライブラリは、さまざまなプラットフォームとビルド ターゲット向けの最適化を実装した高性能ライブラリです。
BitMagic は、最高のシングル スレッド パフォーマンスを提供するだけでなく、メニーコア システムでの高度な並列計算を容易にすることを目的として、データ並列ベクトル化設計を使用しています。
BitMagic は、一連の圧縮アルゴリズム、フィルター、変換を使用して、メモリ使用量、ストレージ コスト、ネットワーク データ転送を削減します。 http://bitmagic.io/design.html
弊社の tech.notes をご覧ください: http://bitmagic.io/articles.html
BitMagic は、0 が隣接する 1 の重複しない範囲のコレクションとしてのビット ベクトルの再解釈をサポートしています (例: 011110110)。通常の集合関数は、集合インターセクト/ユニオン区間演算を提供し、区間反復子を実装し、区間境界を検索します。ゲノミクス データには座標範囲として注釈が付けられることが多いため、範囲と間隔はバイオインフォマティクスで非常に役立ちます。 BitMagic は、ビットベクトルとしてエンコードされた間隔で効率的な操作を行うためのビルディング ブロックを提供します (間隔の開始/終了の検索、範囲が不規則かどうかの確認、間隔の反復)
BitMagic は、True/False/Unknown の 3 値論理 (三値論理、三価、三値) の論理演算をコンパクトな 2 ビット ベクトル表現で実装し、Kleene の定義に従って反転、AND、OR 演算をサポートします。 https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic
BitMagic は 2 段階のシリアル化と逆シリアル化の概念を使用します。焦点は高速な逆シリアル化です。 BitMagic は、ベクトル範囲の高速デシリアライゼーションと圧縮 BLOB の収集デシリアライゼーションのための API を実装しています。 BitMagic の究極の機能は、圧縮データを処理できることです。
これは主な RAM 内動作状態であり、ベクトルはメモリのコンパクトな形式に保たれます。簡潔は圧縮ではありません。コンテナ内のランダムな要素にアクセスし、ブロックをデコードし、ベクトルを反復し、更新し、検索アルゴリズムを実行することが可能です。 Stage One は透過的な使用を提供し、ベクトルは STL によく似ています。 succinct はメモリはコンパクトですが、完全には圧縮されていません。
BitMagic は、ヒューリスティックとコーデックのブロックに基づいて追加の圧縮を使用して、すべてのコンテナとベクターをシリアル化できます。主力のコーディング技術は、バイナリ補間コーディング (BIC) とエリアス ガンマです。
BitMagic コンテナは「スパース」ベクトルと呼ばれますが、実際、その圧縮スキームはスパース データとデンス データの両方に適しています。
BitMagic は、反転リストの Gov2 ベンチマーク セットと独自のデータ セットの数でテストされています。 http://bitmagic.io/bm5-cmpr.html
逆シリアル化は常にステージ 1 に戻るため、データは完全にはデコードされず、
RAM 内では簡潔です。ここでの目標は、アプリケーションのメモリ フットプリントを削減し、逆シリアル化のレイテンシーを改善することです。解凍アルゴリズムは、任意の範囲の逆シリアル化をサポートしたり、要素の逆シリアル化を収集したりすることもできます。
BitMagic は、ビット転置変換に基づいた簡潔な (メモリがコンパクトな) ベクトルをサポートします。
ビットプレーン圧縮 (BPC) (別名ビット スライシング) とランク選択圧縮とも呼ばれます。 BitMagic の簡潔なベクトルは、やや誤解を招くような「スパース」というラベルが付けられていますが、密なベクトルに対しては問題なく機能します。
ビット転置は 2 つの目的を解決します。未使用のビット プレーンを解放することと、規則性とエントロピーを別個の (疎な) ビット ベクトルに分離することです。ビットプレーンの圧縮により、優れたメモリパフォーマンスと高速検索の両方が実現します。設計目標の 1 つは、高速ベクトル化された論理演算を使用して、簡潔なベクトルでインデックスなしの検索を実行することです。
BitMagic の簡潔なベクトルは、メモリ圧縮形式でインデックスなしで検索可能です。速いですね！
簡潔なビット転置実装は、整数ベクトル (符号付きまたは符号なし) と文字列ベクトルの両方に対してうまく機能します。これは、プレフィックス ツリーなどの他の簡潔なスキームに匹敵します。簡潔なベクトルは、ソートすることも、ソートしないこともできます。ここでの考え方は Apache Arrow-Parquet に似ていますが、ビットプレーン圧縮と高速ランク選択圧縮の広範な使用によってさらに進化しています。
BitMagic はシリアル化 (プロトコル) の進化をサポートしています。シリアル化形式が変更されても、古い保存データは新しいコードで読み取ることができます。古いコードは新しい BLOB を読み取ることができません。 BitMagic では、シリアル化形式が変更されると、メジャー バージョン番号が変更されます。
BitMagic は、すべてのベクトルに対してメモリ プロファイリング呼び出しを実装します。任意のベクトルをメモリ フットプリント用にサンプリングできるため、最上位システムはランタイム メモリ プロファイリングに基づいてメモリ管理を適応させることができます。一般的な使用例は、オブジェクトのメモリ キャッシュを RAM に圧縮し、リソースの消費量とコスト (需要と供給の動的なバランス) に基づいてディスクに追い出すことです。
はい！ BitMagic は 64 ビットをサポートしており、32 ビット アドレス空間 (オーバーヘッドが少ない) または完全な 64 ビット アドレス空間で使用できます。 32 ビット アドレス空間はデフォルト モードです。2^31-1 要素は短距離から中距離の IR およびデータ サイエンス システムに適しています。 64 ビット アドレス モードは、#define BM64ADDR または #include "bm64.h" を使用して利用できます。現在の 64 ビット実装では、大規模システムに対して 2^48-1 のベクトル要素が可能です。
BitMagic は WebAssmbly (emscripten) をコンパイルして操作します。最新バージョンには、プラットフォームに固有の複数の調整が含まれています。パフォーマンスの数値は、SIMD なし (場合によっては SIMD 後) のネイティブ コードに近いです。サンプルのコンパイル行は次のようになります。
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...
WebAssembly SIMD はサポートされていますが、デフォルトではオンになっていません。 #define BMWASMSIMDOPTを使用して有効にします。 Emscripten コマンドの例:
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
現在の実装では SSE4.2 トランスコンパイル (組み込み経由) が使用されているため、 -msse4.2が必要です。
BitMagic は ARM CPU を完全にサポートしています。すべてのリリースは Raspberry Pi 4 でストレス テストされています。BitMagic は、ARM に固有のアルゴリズムの微調整と改善 (LZCNT 命令の使用など) を実装しています。 BitMagic の簡潔なコンテナは、利用可能なメモリ量が限られているエッジ コンピューティング用の組み込みシステムで非常に役立ちます。
Arm Neon SIMD サポートが利用可能です (SSE2NEON ライブラリ経由)。
BitMagic C++ はヘッダーのみのライブラリ (プロジェクトでの構築と使用が簡単) であり、サンプルのセットが付属しています。ライブラリの使用法を研究するためのコード例としてテストを使用することはお勧めしません。テストは最適な使用パターンやモデルを示すものではなく、多くの場合意図的に非効率的です。
API ドキュメントと例: http://www.bitmagic.io/apis.html
集合代数のチュートリアル: http://bitmagic.io/set-algebra.html
ユースケースとアプリケーションノート: http://bitmagic.io/use-case.html
パフォーマンスの最適化に関する技術ノート: http://bitmagic.io/articles.html
Doxygen: http://bitmagic.io/doxygen/html/modules.html
アパッチ2.0。
重要！派生著作物または当社の出版資料の中で BitMagic プロジェクトに明示的に言及するようお願いします。 BitMagic ライブラリを使用するには、製品/プロジェクト ページでの適切な参照が必須です。
BitMagic ライブラリは、コードの品質とテスト カバレッジに細心の注意を払っています。
ビルディング ブロック ライブラリとして BitMagic を使用するには、安定性と適合性が必要です。
私たちは単体テストだけに頼るのではなく、テストではランダム化された生成されたセットとランダム化された操作に基づいてストレス テストが行われる「カオス テスト」 (別名ファジング) がよく使用されます。 SIMD 最適化のさまざまな組み合わせに対して、リリース モードとデバッグ モードのテスト スーツを定期的に構築して実行します。
テスト ビルドのすべてのバリアントの実行には数日かかるため、動作する master ブランチが常に完璧であるとは限りません。運用環境の場合は、SourceForge の安定した github リリース ブランチまたはディストリビューションを使用してください: https://sourceforge.net/projects/bmagic/files/
GitHub マスターはパッチ リクエストを受け入れます。私たちの分岐ポリシーは、マスターがリリース間で完全に安定しているとは見なされないということです。 (運用の安定性を確保するには、リリース バージョンを使用してください)
Python やその他の言語へのマッピングについてサポートが必要です (BitMagic には C バインディングがあります)
BitMagic C++ はヘッダーのみのソフトウェア パッケージであり、おそらくソースを取得してプロジェクトに直接組み込むことができます。すべての C++ ライブラリのソース/ヘッダーは src ディレクトリにあります。
ただし、メイクファイルを使用したい場合は、次の簡単な手順に従う必要があります。
プロジェクトのルート ディレクトリで bmenv.sh を実行して、いくつかの環境変数を適用します。
$ source ./bmenv.sh
(ルート環境変数を適用するには「.」「./bmenv.sh」を使用してください)
GNU make (gmake) を使用してインストールをビルドします。
$make rebuild
または (デバッグバージョン)
$gmake DEBUG=YES rebuild
Unix および CygWin のデフォルトのコンパイラは g++ です。デフォルトを変更したい場合は、makefile.in で変更できます (非常に簡単に実行できるはずです)。
cygwin インストールを使用する場合は、一般的な Unix の推奨事項に従ってください。 MSVC - ソリューションとプロジェクトは CMAKE 経由で利用できます。
Xcode - プロジェクト ファイルは CMAKE 経由で入手できます。
C および JNI マッピング用の BitMagic ライブラリ。
BitMagic ライブラリは C 言語で利用できます (これは進行中です)。 C ビルドの主な目的は、BitMagic を他のプログラミング言語に橋渡しすることです。 C ビルドはサブディレクトリ「lang-maps」にあります。
C ビルドは、SSE および AVX 用の BitMagic ビルドのバージョンを作成し、CPU ID を追加するため、上位レベルのシステムは動的な CPU ID とコード ディスパッチをサポートできます。
C ビルドは C++ コンパイラを使用しますが、RTTI、例外 (ロング ジャンプでシミュレート)、および C++ メモリ管理を使用しないため、実行時の依存関係がなく、C++ 言語に中立です。アルゴリズムと動作は C と C++ で共有されます。
現在の開発状況:
Python のサポートは保留中なので、ここで助けが必要です。 Python に熱心で、手助けできると思われる場合は、anatoliy.kuznetsov @ yahoo dot com までご連絡ください。
BitMagic ライブラリには CXX-11 が必要です。移動セマンティクス、noexept、初期化リスト、スレッドを使用します。次の公開バージョンでは CXX-17 (constexpr ifs など) が使用されます。
###微調整と最適化:
すべての BitMagic 微調整パラメータは、プリプロセッサ定義 (およびコード生成用のターゲット アーキテクチャ固有のコンパイラ キー) によって制御されます。
| ＃定義する | 説明 | 幅 |
|---|---|---|
| BMSSE2OPT | SSE2 コードの最適化 | 128ビット |
| BMSSE42OPT | SSE4.2 コードの最適化と POPCNT、BSF など | 128ビット |
| BMAVX2OPT | AVX2、POPCNT、LZCNT、BMI1、BMI2の最適化 | 256ビット |
| BMAVX512OPT | AVX-512、(実験的) | 512ビット |
| BMWASMSIMDOPT | WebAssembly SIMD の最適化 (SSE4.2 経由) | 128ビット |
| DBMNEONOPT | Arm Neon SIMD の最適化 (SSE2 変換経由) | 128ビット |
####制限:
SIMD 最適化定義は相互に排他的であり、BMSSE42OPT と BMAVX2OPT を同時に使用することはできません。 1 つだけ選んでください。
BM ライブラリは、複数のコード パスとランタイム CPU の識別をサポートしていません。ターゲット システム専用にビルドするか、デフォルトのポータブル ビルドを使用する必要があります。
####例:
BitMagic のサンプルとテストは、コマンドライン設定を使用して GCC でビルドできます。
make BMOPTFLAGS=-DBMAVX2OPT rebuild
または
make BMOPTFLAGS=-DBMSSE42OPT rebuild
ターゲット ビルドに適切なコンパイラ (GCC) フラグのセットが自動的に適用されます。
CMAKE
cd build
cmake -DBMOPTFLAGS:STRING=BMSSE42OPT ..
make
または
cmake -DBMOPTFLAGS:STRING=BMAVX2OPT ..
BM ライブラリは「restrict」キーワードをサポートしており、一部のコンパイラ (インテル C++ など) は、restrict キーワードが役立つ場合に、より適切なコード (順序が崩れたロードストア) を生成します。ほとんどの C++ コンパイラはこのオプションをサポートしていないため、このオプションはデフォルトでオフになっています。これをオンにするには、プロジェクトで BM_HASRESTRICT を #define してください。一部のコンパイラは、この目的で「__restrict」キーワードを使用します。これを修正するには、BMRESTRICT マクロを定義してキーワードを修正します。
「非 STL プロジェクト」 (組み込みシステムなど) で BM ライブラリを使用したい場合は、BM_NO_STL を定義します。
このルールは、コアの bm::bvector<> メソッドにのみ適用されます。補助アルゴリズムやサンプルなどでは引き続き STL が使用されます。
Twitter でフォローしてください: https://twitter.com/bitmagicio
BitMagic ライブラリをご利用いただきありがとうございます。
電子メール: [email protected]
WEBサイト：http://bitmagic.io
GitHub: https://github.com/tlk00/BitMagic
