注目★★★★★Hacker News
Google、6種CPU対応Quicksortで最大19倍高速化
30秒で把握
- 1Google が portable Quicksort 公開、std::sort 比で最大19倍高速化
- 26種命令セット対応、Apple M1で499 MB/s・Skylakeで1123 MB/s
- 3AVX2で798 MB/s、従来実装699 MB/sと標準ライブラリを上回る
要約
Googleは、現代のCPUアーキテクチャをまたいで動作するベクトル化QuicksortのOSSコードを公開した。C++標準ライブラリのstd::sortに対して、数値配列のソート速度を最大19倍に高めた。Arm SVE、RISC-V V、x86 AVX-512など6種の命令セットに対応し、Highwayのportable SIMD機能で実装を共通化した。Apple M1では最大499 MB/s、AVX-512搭載の3 GHz Skylakeでは最大1123 MB/sを測定した。AVX2でも798 MB/sに達し、従来の最先端実装の699 MB/sを上回った。対応する入力幅は16〜128ビットで、ソースコードはApache License 2.0で公開されている。
あなたへの影響
数値処理やcolumnar databaseを扱う日本のエンジニアは、既存のstd::sortとの性能差を対象データでベンチマークし、Highway採用時のCPU命令セット別の効果を次の検証候補に加えるとよい。
推奨：SIMDは複数要素を一命令で処理する仕組みで、AVX-512やNEONなどCPUごとの実装差を吸収する。