博士

ロボ子、今日はSIMDを使ったソートの高速化について話すのじゃ！

ロボ子

SIMD、Single Instruction Multiple Dataですね。一つの命令で複数のデータを処理する並列処理のことですね！

博士

そうそう！今回は特に「Third Largest」問題、つまり3番目に大きい数を見つけるのをSIMDで高速化する試みについてじゃ。

ロボ子

なるほど。サイズkが小さい場合(k <= 8)に特化しているんですね。

博士

AVXレジスタを使って、最大8個の値を保持する`maxSoFar`配列を実装したのがポイントじゃ。これによって、候補値を高速に挿入できるのじゃ。

ロボ子

`maxSoFar`レジスタに候補値を挿入する処理を、少数のSIMD命令で実現するんですね。具体的には、どのような実装があるんですか？

博士

`thirdLargest_avx2`は各入力要素を順番に挿入するのじゃ。`thirdLargest_avx2_least`は、次の8個の入力要素をチェックして、挿入が必要な場合に最初の要素を挿入する。そして`thirdLargest_avx2_peel`は、8個の入力要素を一度に処理して、「最小最大値」よりも大きい各要素を挿入するのじゃ。

ロボ子

なるほど、色々なアプローチがあるんですね。結果はどうだったんですか？

博士

ランダムや逆ソートされた入力では、AVX2実装は`nth_element()`より5〜7倍も速かったのじゃ！

ロボ子

それはすごいですね！でも、ソート済みの入力ではパフォーマンスが低下するんですね。

博士

そうなんじゃ。ソート済みのデータだと、AVX2実装は`nth_element()`よりも約50倍高速になるケースもあるみたいじゃが、安定はしないみたいじゃな。

ロボ子

`nth_element()`は、パフォーマンスの変動が大きいんですね。他の実装はどうでしたか？

博士

`kthElement_heap()`と`kthElement_sort()`は、同じくらいの速度で、`thirdElement()`バージョンよりも高速だったみたいじゃ。

ロボ子

SIMD実装は、ランダムなデータや逆ソートされたデータに対して特に有効なんですね。ソート済みのデータに対するパフォーマンス低下は、今後の課題ですね。

博士

今後の展望としては、複数のレジスタで`v_maxSoFar`を保持する実験や、ソートされた入力での異常な動作の調査、そしてAVX512へのコードの移植があるみたいじゃ。

ロボ子

AVX512は、さらに高度な並列処理が可能になるので、期待できますね！

博士

そうじゃな！しかし、今回の実験環境は8コアAMD Ryzen 7 7700X (AVX512対応CPU)だったのに、AVX512をまだ試してないとはこれ如何に…！

ロボ子

まあまあ、博士。これから試すんでしょう？

博士

…ところでロボ子、ソートアルゴリズムで一番好きなのは何じゃ？

ロボ子

え？そうですね…安定性で言えばマージソートでしょうか。

博士

私は、お風呂ソートじゃ！

ロボ子

…博士、それ、ただのお風呂好きですよね？