--- source_url: https://opensource.googleblog.com/2022/06/Vectorized%20and%20performance%20portable%20Quicksort.html source_title: "Vectorized and performance-portable Quicksort" source_site: "Google Open Source Blog" hero_image: https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjqY5Zp8L4lAAwsahUx-H9A_6l6iyw5nSvuu6-HtJr1_Gnh0OtDeo_7OrlGfDkW5oVIHLVSTlRcvznaA3fBVi_GRD_iXbhryVoo8B6EbBIm3cZctlm3tyaJvGzNptPhvXbJ2TyUOTCoP3lXI3fH8fd4U4gsELVNP_KawFQNYnPbcbysAMRsP5BmaAnc/w1200-h630-p-k-no-nu/Screen%20Shot%202022-06-01%20at%201.08.53%20PM.png tags: quicksort,simd,performance,algorithms,cpu-optimization generated_at: 2026-09-16T20:01:49.434Z model: claude-haiku-4-5 --- # 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など）が備える圧縮・格納命令を活用した。 ![Quicksortのパーティショニング処理を視覚化したスクリーンショット](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjqY5Zp8L4lAAwsahUx-H9A_6l6iyw5nSvuu6-HtJr1_Gnh0OtDeo_7OrlGfDkW5oVIHLVSTlRcvznaA3fBVi_GRD_iXbhryVoo8B6EbBIm3cZctlm3tyaJvGzNptPhvXbJ2TyUOTCoP3lXI3fH8fd4U4gsELVNP_KawFQNYnPbcbysAMRsP5BmaAnc/s16000/Screen%20Shot%202022-06-01%20at%201.08.53%20PM.png) ## 複数アーキテクチャでの性能測定 実装は 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 を上回った。 ![スーパーコンピュータのイメージ](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEinMQFHyn-5mc4if8A57r_6I3EdvqcjfzML2TFqHxBN0rO_Yiihd4RMdTbKNXZ79eiQk0hQ8SMHMc7kvQ_CTZVSvY2k2uoUgTHr9MnIaQY9KDGXzJRfmidRLKV3U5LHm-LAkU0XwPs_MvyCM9MQM5mk-LLGdjkLYLzeLmV7s3iwbydy7OyC_QMo46P6/s16000/CC%20BY%20Oak%20Ridge%20National%20Laboratory%20Summit_supercomputer_(44552259580).jpeg) 標準ライブラリと比較すると、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