Googleがベクトル化Quicksortを公開、C++標準ライブラリの10倍高速化を実現
Googleが開発した高速ソートアルゴリズムの実装コードをオープンソース化。SIMD命令を活用し、現代的なCPUアーキテクチャ全体で移植性を保ちながら、標準ライブラリ比で約10倍の性能向上を達成した。
Googleは、C++の標準ライブラリ std::sort と比べて約10倍高速に配列をソートできるベクトル化Quicksortのオープンソースコードを公開した。この実装は、AVX2、AVX-512、Arm NEONを含むすべての現代的なCPUアーキテクチャ全体で移植性を持ちながら、既存の最先端のアーキテクチャ固有アルゴリズムをも上回る性能を発揮する。
SIMD命令による高速化
Googleの Brain Computer Architecture Research チームの Jan Wassenberg 氏らが開発したこの実装は、SIMD/ベクトル命令を活用することで飛躍的な性能向上を実現している。Quicksortにおいて、パーティショニング処理がCPU時間の大部分を占める点に着目し、現代的な命令セット（Arm SVE、RISC-V V、x86 AVX-512など）が備える圧縮・格納命令を活用した。
複数アーキテクチャでの性能測定
実装は Highway の移植可能 SIMD 関数を利用し、16～128ビット入力に対応している。その結果、プラットフォーム別に異なる性能を示した。Apple M1 では 32ビット数値に対して 499 MB/s、64ビット数値に対して 471 MB/s、128ビット数値に対して 466 MB/s を達成した。一方、3 GHz Skylake に AVX-512 を搭載した環境では、32ビット数値で 1123 MB/s、64ビット数値で 1119 MB/s、128ビット数値で 1120 MB/s に達し、AVX-512 は AVX2 比で 1.4～1.6 倍高速である。AVX2 環境では 798 MB/s を計測し、先行技術である AVX2 最適化版の 699 MB/s を上回った。
標準ライブラリと比較すると、32ビット数値で 58 MB/s、64ビット数値で 128 MB/s、128ビット数値で 117 MB/s の速度に対し、全体的には 9～19 倍の高速化を達成した。また、Highway を活用することで、プラットフォームごとに再実装する必要のない約 3000 行の C++ コードとなっている。
筆者の見立て
- ソートが高価な操作として扱われてきた点に着目し、この高速化により、新たなアプリケーションと機能が実現される可能性を示唆している。
- 単一 CPU コア上で 1 GB/s のソート速度を実現できることが、新たなアプリケーション実現の鍵になると論じている。
この記事は元記事の事実のみに基づいて自動生成されました。
出典
Google Open Source Blog「Vectorized and performance-portable Quicksort」https://opensource.googleblog.com/2022/06/Vectorized%20and%20performance%20portable%20Quicksort.html