Googleが初のベクター化Quicksortを公開、std::sortの最大19倍高速
Vectorized and performance-portable Quicksort
Googleは、SIMD命令を活用したポータブルなQuicksortをオープンソースで公開した。AVX2、AVX-512、Arm NEONなど6つの命令セットに対応し、C++のstd::sortと比べて9～19倍高速。Apple M1では最大499 MB/s、Skylakeでは1120 MB/sを達成し、既存のアーキテクチャ特化型ソートをも上回る。
以前はソートは高コストと考えられていた。単一CPUコアで1 GB/sのソートが可能になることで、どのような新しいアプリケーションや機能が開拓されるのか、興味は尽きない。
HNでの議論
29- zX41ZdbW
ここで見るのは奇妙だね、この記事はかなり古いよ。
pdqsort、vqsort、glide sort以降、現在の最先端はdriftsortとipnsortだ。
それらをClickHouseに統合した：https://github.com/ClickHouse/ClickHouse/pull/106650
- bee_rider
まあ、少し前に出たものだから、ちょっとふざけてもいいかな：
マージソートとヒープソートにはどこか美しさがある。名前が主なアイデアを教えてくれるし、仕組みもすぐに明らかだ。
一方、クイックソートには美しさのかけらもなく、唯一の取り柄（多くの場合に速いこと）にちなんで名付けられている。
- minitech
実際のタイトル：「Vectorized and performance-portable Quicksort」（2022年）。
実際に「初」と言える点：
> 幸いなことに、現代の命令セット（Arm SVE、RISC-V V、x86 AVX-512）には、パーティショニングに適した特別な命令が含まれている。yes/no値の別入力（要素がピボットより小さいかどうか）が与えられると、この「compress-store」命令は、対応する入力が「yes」である要素だけを連続したメモリに格納する。次にyes/no値を論理的に反転し、同じ命令を適用して要素を他のパーティションに書き込むことができる。この戦略はAVX-512固有のQuicksortで使われてきた。しかし、compress-storeを持たないAVX2などの他の命令セットはどうだろうか？先行研究では、permute命令を使ってこの命令をエミュレートする方法が示されている。
> 我々はこれらの技術を基盤として、3つのアーキテクチャにまたがる6つの命令セットにポータブルな、初のベクター化Quicksortを実現し、実際に従来のアーキテクチャ固有のソートを上回る性能を達成した。