xeniumダウンロード - xeniumソースコードのダウンロード

xenium

C/C++

v0.0.2: Merge pull request #19 from rbalint

ダウンロード

ゼニウム

xenium は、同時データ構造とメモリ再利用アルゴリズムのコレクションを提供するヘッダーのみのライブラリです。データ構造はパラメータ化されており、さまざまな再利用スキームで使用できるようになります (STL でアロケータのカスタマイズが可能になるのと同様)。

ヘッダーのみ
高度にカスタマイズ可能
初期化コードは必要ありません
動的スレッド数をサポート (コンパイル時間の固定仕様なし)

ドキュメントに詳細が記載されています。

このプロジェクトは、https://github.com/mpoeter/emr にある私の以前の作品に基づいています。

使用例

# include < xenium/ramalhete_queue.hpp >
# include < xenium/reclamation/epoch_based.hpp >

struct msg { ... };

xenium::ramalhete_queue<
  std::unique_ptr<msg>,
  xenium::policy::reclaimer<xenium::reclamation::epoch_based<>>,
  xenium::policy::entries_per_node< 2048 >
> queue;

queue.push(std::make_unique<msg>());

std::unique_ptr<msg> data;
if (queue.try_pop(data)) {
    // do something with data
}

データ構造

現時点では、これまで再生スキームに重点が置かれていたため、提供されるデータ構造の数はかなり少ないです。ただし、近い将来さらにいくつかのデータ構造を追加する予定です。

michael_scott_queue - Michael と Scott [MS96] によって提案された、無制限のロックフリーのマルチプロデューサー/マルチコンシューマーキュー。
ramalhete_queue - Ramalhete [Ram16] によって提案された、高速で無制限のロックフリーのマルチプロデューサー/マルチコンシューマーキュー。
vyukov_bounded_queue - Vyukov [Vyu10] によって提案されたバージョンに基づく、制限されたマルチプロデューサー/マルチコンシューマー FIFO キュー。
kirsch_kfifo_queue - Kirsch らによって提案された無制限のマルチプロデューサー/マルチコンシューマー k-FIFO キュー。 [KLP13]。
kirsch_bounded_kfifo_queue - Kirsch らによって提案された、制限されたマルチプロデューサー/マルチコンシューマー k-FIFO キュー。 [KLP13]。
nikolaev_queue - Nikolaev [Nik19] によって提案された、無制限のマルチプロデューサー/マルチコンシューマーキュー。
nikolaev_bounded_queue - Nikolaev [Nik19] によって提案された、制限されたマルチプロデューサー/マルチコンシューマーキュー。
harris_michael_list_based_set - ソートされた一意のオブジェクトのセットを含むロックフリーのコンテナー。このデータ構造は、Harris [Har01] によるオリジナルの提案に基づいて構築された、Michael [Mic02] によって提案されたソリューションに基づいています。
harris_michael_hash_map - Harris [Har01] によるオリジナルの提案に基づいて構築された、Michael [Mic02] によって提案されたソリューションに基づくロックフリーのハッシュマップ。
chase_work_stealing_deque - Chase と Lev による提案に基づく作業盗用 deque [CL05]。
vyukov_hash_map - 更新操作にきめ細かいロックを使用する同時ハッシュマップ。この実装は、Vyukov [Vyu08] によって提案されたバージョンに大きく影響を受けています。
left_right - Ramalhete と Correia [RC15] によって提案された LeftRight アルゴリズムの汎用実装。
seqlock - シーケンスロックの実装 (「シーケンシャルロック」とも呼ばれます)。

再生計画

再利用スキームの実装は、Robison [Rob13] によって提案されたインターフェイスの適応バージョンに基づいています。

次の再利用スキームが実装されています。

lock_free_ref_count [Val95、MS95]
hazard_pointer [Mic04]
hazard_eras [RC17]
quiescent_state_based
generic_epoch_based - これは、いくつかの方法で構成できる一般化されたエポックベースのリクレイマーです。簡単にするために、次のエイリアスが対応する構成に対して事前定義されています。
- epoch_based [Fra04]
- new_epoch_based [HMBW07]
- debra [Bro15]
stamp_it [PT18a、PT18b]

建物

xenium はヘッダーのみのライブラリであるため、これを使用するには、インクルードディレクトリのリストに xenium フォルダーを含めるだけで十分です。他のサードパーティライブラリは必要ありません。ただし、実装では C++17 の機能が使用されるため、十分な C++17 サポートを備えたコンパイラーが必要です。次のコンパイラは CI ビルドで使用されているため、サポートされていることがわかっています。

gcc9
クラング10
Visual Studio 2019

単体テストにはgoogletestが必要で、ベンチマークにはtaocpp/jsonおよびtaocpp/config必要です。これらの依存関係はサブモジュールとして含まれているため、単体テストやベンチマークを次のように構築できます。

 git clone https://github.com/mpoeter/xenium.git && cd xenium
git submodule update --init --recursive
mkdir build && cd build
cmake ..
make gtest
make benchmark

参考文献

[兄15]	トレバー・アレクサンダー・ブラウン。ロックフリーのデータ構造のためにメモリを再利用する: より良い方法が必要です。分散コンピューティングの原則 (PODC) に関する 2015 ACM シンポジウムの議事録、261 ～ 270 ページ。 ACM、2015 年。
【CL05】	デビッド・チェイスとヨッシ・レフ動的な循環ワークスチールデキュー。『アルゴリズムとアーキテクチャの並列処理に関する第 17 回 ACM シンポジウム (SPAA)』の議事録、21 ～ 28 ページ。 ACM、2005 年。
【フラ04】	キア・フレイザー。実質的なロックフリー。博士論文、ケンブリッジ大学コンピュータ研究所、2004 年。
[ハル01]	ティモシー・L・ハリス。ノンブロッキングリンクリストの実用的な実装。第 15 回分散コンピューティング国際会議 (DISC) の議事録、300 ～ 314 ページ。シュプリンガー・フェルラーク、2001 年。
【HMBW07】	トーマス E. ハート、ポール E. マッケニー、アンジェラデムケブラウン、ジョナサンウォルポール。ロックレス同期のためのメモリ再利用のパフォーマンス。並列および分散コンピューティングのジャーナル、67(12):1270–1285、2007。
[KLP13]	クリストフ・キルシュ、マイケル・リッパウツ、ハンネス・パイヤー。高速かつスケーラブルな、ロックフリーの k-FIFO キュー。『並列コンピューティング技術に関する国際会議 (PaCT) の議事録』、208 ～ 223 ページ、Springer-Verlag、2013 年。
【マイク02】	メイジド・M・マイケル。高性能の動的ロックフリーハッシュテーブルとリストベースのセット。『並列アルゴリズムとアーキテクチャに関する第 14 回年次 ACM シンポジウム (SPAA)』の議事録、73 ～ 82 ページ。 ACM、2002 年。
【マイク04】	メイジド・M・マイケル。ハザードポインタ: ロックのないオブジェクトに対する安全なメモリ再利用。並列および分散システムに関する IEEE トランザクション、15(6):491–504、2004。
[MS95]	メイジド・M・マイケルとマイケル・L・スコット。ロックフリーのデータ構造のメモリ管理方法を修正。技術レポート、ロチェスター大学、1995 年。
[MS96]	メイジド・M・マイケルとマイケル・L・スコット。シンプル、高速、実用的なノンブロッキングおよびブロッキング同時キューアルゴリズム。分散コンピューティングの原則 (PODC) に関する第 15 回年次 ACM シンポジウムの議事録、267 ～ 275 ページ。 ACM、1996年。
[ニック19]	Ruslan Nikolaev スケーラブルでポータブル、メモリ効率の高いロックフリーの FIFO キュー。第 33 回分散コンピューティング国際シンポジウム (DISC) の議事録、2019 年。
[PT18a]	マヌエル・ピーターとイェスパー・ラーソン・トレフ。簡単な発表: Stamp-it、C++ メモリモデルにおけるスレッド効率の高い同時メモリ再利用スキーム。アルゴリズムとアーキテクチャの並列処理に関する第 30 回 ACM シンポジウム (SPAA) の議事録、355 ～ 358 ページ。 ACM、2018年。
[PT18b]	マヌエル・ピーターとイェスパー・ラーソン・トレフ。 Stamp-it は、C++ メモリモデルにおけるスレッド効率の高い同時メモリ再利用スキームです。技術レポート、2018年。
[ラム16]	ペドロ・ラマルヘテ。 FAAArrayQueue - MPMC ロックフリーキュー (パート 4/4)。ブログ、2016 年 11 月。
【RC15】	ペドロ・ラマリヘテとアンドレイア・コレイア。 Left-Right - 待機なしの Population Oblivious Read を使用した同時実行制御手法。 2015 年 10 月
[RC17]	ペドロ・ラマリヘテとアンドレイア・コレイア。簡単なお知らせ: ハザード時代 - ノンブロッキングメモリ再利用。『アルゴリズムとアーキテクチャの並列処理に関する第 29 回 ACM シンポジウム (SPAA)』の議事録、367 ～ 369 ページ。 ACM、2017年。
[ロブ13]	アーチ・D・ロビソン。同時コンテナで安全に破棄するためのポリシーベースの設計。 C++ 標準委員会の論文、2013 年。
【ヴァル95】	ジョン・D・ヴァロワ。ロックフリーのデータ構造。博士論文、レンセラー工科大学、1995 年。
【Vyu08】	ドミトリー・ヴュコフ。スケーラブルなハッシュマップ。 Google グループの投稿、2008 年。
【Vyu10】	ドミトリー・ヴュコフ。シンプルで効率的な境界付き MPMC キュー。 Google グループの投稿、2010 年。