Lock Free Queue完成版

やっと負荷かけても落ちなくなった。

詳細書こうかと思ったけどめんどいので適当に概要…

結局、freed memoryを参照しても落ちないように自前でメモリ管理をやる必要があったというだけでした。そもそもせっかくLockFreeなコンテナなのに、メモリ管理がlockfreeじゃないとか悲しいしね。
あとは、CASが失敗したらちょっとwaitをかけて、他スレッドを優先させてやったりとか。こうした方がむしろパフォーマンスあがった。

実装はここらへんを見てください：
http://nyaxtstep.com/trac/libfecti/browser/trunk/fecti/Utility

FMTQueueとかFBlockMemoryAllocatorあたり

Queue実装の速度比較

左からNon-blocking Concurrent Queue, Two-lock Blocking Queue, std::queue + boost::mutexです。
縦は、３秒間に５スレッドで同時Push/Popしたカウント。Non-blockingは他の23倍ぐらいのパフォーマンスが出てる。

std::queue以外はLockFreeな固定メモリアロケータを使っていますが、なぜかstd::queueもTwo-lockも同じくらいの早さ。自作アロケータが重い疑惑。

しかし、こんなにLockがかち合う状況は現実的ではないので、Non-blockingの元ネタ論文に載っていたように、ある程度Waitを入れてループをまわす方が現実的な測定ができると思います。

テストプログラムは
http://nyaxtstep.com/trac/libfecti/browser/trunk/test/util_FMTQueue

ちょっとFAtomicIntegerの下書きがまざってて汚い。