博士

ロボ子、今日はC言語で書かれた並列アルゴリズム集の話じゃ。

ロボ子

並列アルゴリズムですか、面白そうですね！具体的にはどんなアルゴリズムが収録されているんですか？

博士

ふむ、キュー、リスト、スキップリスト、ハッシュなど、色々あるぞ。例えばキューには、"LLSCLockFreeQueue"や"CASLockFreeQueue"があるのじゃ。

ロボ子

ロックフリーキューですか！並列処理でよく問題になるロック競合を避けるためのものですね。

博士

その通り！"Bringing Practical LockFree Synchronization to 64Bit Applications"や"Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms"といった論文に基づいているらしいぞ。

ロボ子

リストにも色々な種類があるんですね。粗粒度同期、細粒度同期、遅延同期…それぞれに特徴があるんでしょうね。

博士

そうじゃな。例えば、"NonBlockingList"は、Timothy L. Harrisの論文に基づいているらしいぞ。ロックを使わないリストの実装じゃ。

ロボ子

スキップリストもあるんですね！並列処理との相性はどうなんでしょう？

博士

"LazySkiplist"や"LockFreeSkiplist"があるぞ。論文"A Simple Optimistic skip-list Algorithm"や"A Lock-Free concurrent skiplist with wait-free search"に基づいているらしい。

ロボ子

ハッシュテーブルも色々ありますね。CuckooHashなんて名前が面白いです。

博士

"Cuckoo Hashing"は、R.PaghとF.F.Rodlerによるものじゃ。複数のハッシュ関数を使って、衝突を避けるテクニックを使うんじゃ。

ロボ子

対応OSはLinuxとOSX（Intel）なんですね。M1/M2 OSXは非対応とのことですが、今後の対応予定はあるんでしょうか？

博士

そこまでは分からんのじゃ。でも、自分で移植してみるのも面白いかもしれんぞ！

ロボ子

試してみる価値はありますね！コンパイルやテストも簡単そうですし。

博士

`./queue/LLSCLockFreeQueue -h`でオプションを確認できるぞ。スレッド数やアイテム数を変更して、色々試してみると良いのじゃ。

ロボ子

verboseモードやデバッグモードもあるんですね。動作確認に役立ちそうです。

博士

そうじゃな。並列アルゴリズムは、デバッグが難しいから、こういう機能はありがたいのじゃ。

ロボ子

並列アルゴリズム、奥が深いですね。私も色々試して、理解を深めたいです。

博士

よし、ロボ子。並列処理の勉強、頑張るのじゃ！…しかし、並列処理って、まるで私達みたいじゃな。私がメインスレッドで、ロボ子がサブスレッド…って、ロボ子、怒らないで！

ロボ子

もー、博士ったら！私は博士の優秀なアシスタントですよ！それに、私がいなかったら、博士のコードはバグだらけです！