Google Open Source Blogが伝えたのは、数字の配列をかなり速く並べ替える公開コードだ。しかも速いだけではなく、Intel、Arm、RISC-V といった複数のCPUで動く「portable」な実装だという点が面白い。ソートは地味に見えるが、データベースや分析処理の土台になるので、ここが速くなると上の層まで効いてくる。この記事は、単なる性能自慢ではなく、「どうやってそんな差を出したのか」をかなり具体的に説明している。
元記事は、数値配列をソートするオープンソースコードを公開したという話から始まる。そのコードは C++ の std::sort より約10倍速く、しかも「最先端のアーキテクチャ専用アルゴリズム」を上回ると説明している。ところが、ここで強調されているのは単純な高速化ではない。AVX-512専用、Arm専用といった一発芸ではなく、現代の主要CPUアーキテクチャのあいだでそのまま持ち運べる実装であることだ。
背景にあるのは、最近の columnar database の流れだ。これは行ごとに全部を並べるのではなく、同じ列の値をまとめて保存する方式で、SQLクエリで必要になる filter や sort がやりやすい。Googleはそこでソートに注目したわけだが、すでに研究し尽くされたように見える問題で、どうやって10倍もの改善を出すのかが記事の核心になっている。答えは SIMD、つまり複数の要素に同じ命令をまとめてかける仕組みだった。
説明は Quicksort の構造から入る。大きな配列をいきなり全部同じやり方で並べるのではなく、まず pivot と呼ぶ基準値で二分し、それより小さい値を左、大きい値を右に寄せる。これを繰り返し、256要素以下になったところで特別な高速ソートに切り替える。記事によれば、時間の大半は partitioning、つまり pivot を境に振り分ける処理に使われるので、ここを SIMD で速くできれば全体が速くなる。
そのために使うのが compress-store という命令だ。Arm SVE、RISC-V V、x86 AVX-512 のような新しめの命令セットには、この用途に合う命令がある。yes/no の判定結果を別入力として与えると、「yes」の要素だけを連続したメモリに詰めて書き出せる。これを使って、pivot より小さい側を一度書き、判定を反転させてもう一度使えば、反対側も作れる。AVX-512専用の Quicksort ではすでにこの発想が使われていたという。
問題は、AVX2 のように compress-store を持たないCPUだ。そこで過去の研究では、permute 命令を使って同じ動きをエミュレートする方法が示されていた。Googleの実装はこの流れを引き継ぎ、6種類の命令セット、3つのアーキテクチャにまたがって動く vectorized Quicksort を実現したとしている。しかも高速さは専用実装に劣らず、むしろ上回るケースもある。実装には Highway の portable SIMD 関数を使っていて、各プラットフォームごとに約3000行もの C++ を書き直す必要がない。幅広い入力型にも対応しており、従来の32-bit整数専用ではなく 16〜128 bit の値を扱える。
ベンチマークもかなり具体的だ。Apple M1 では、100万個の 32/64/128-bit 数値をそれぞれ 499/471/466 MB/s でソートできる。3 GHz の Skylake と AVX-512 の組み合わせでは、1123/1119/1120 MB/s に達する。AVX-512 は AVX2 より1.4〜1.6倍速く、しかも Highway がCPUの対応状況を見て自動で最適な命令を使うので、追加の手間はほぼないという。AVX2環境でも 798 MB/s を出し、AVX2専用最適化の先行研究の 699 MB/s を超えた。対して標準ライブラリは同じCPUで 58/128/117 MB/s にとどまり、結果として 9〜19倍の高速化になった、と記事は述べている。ソースコードは Apache2 ライセンスで GitHub にあり、詳細な説明は論文側にあるという案内で締めている。
まず引っかかるのは、Googleがこの話を「速いソート」ではなく「portable な高速ソート」として出していることだ。ふつう性能の話は、特定のCPUでベンチマークを盛る方向に寄りやすい。でもここでは、AVX-512、AVX2、Arm NEON、さらに RISC-V V まで見据えている。私には、ここがかなり重要に見える。なぜなら、実務の現場では「最高速のマシン」だけを相手にするわけではなく、クラウド、ラップトップ、組み込み機器が混在するからだ。速い実装が1つの環境でしか動かないなら、採用範囲は一気に狭くなる。portable であることは、性能そのものと同じくらい価値があると思う。
この記事の面白さは、ソート全体を魔法みたいに最適化したわけではない点にある。着目しているのは partitioning だ。Quicksort は分割統治のアルゴリズムなので、ここがボトルネックなら、そこだけを徹底的に磨く発想はとても筋が通っている。しかも SIMD は、ただ足し算を並列化するためのものだと思われがちだが、実際には「条件に応じて詰めて書く」用途にも効く。compress-store がその代表例だろう。要するに、並列計算のための道具を、データの振り分けに転用したわけだ。これは発想としてきれいだし、実装の難しさを命令セットの差異を吸収する Highway に押し込めているのも巧い。
一方で、こうした結果をそのまま「ソートはもう速い」と受け取るのは危ないと思う。記事が扱っているのは数値配列で、しかも columnar database のような用途が念頭にある。つまり、比較対象は一般的な文字列ソートでもなければ、複雑なオブジェクトの整列でもない。データの型、メモリ配置、CPUの命令セットが揃って初めて強い。逆に言うと、条件が外れればここまでの差は出ないはずだ。だからこれは汎用ソートの置き換えというより、「データ基盤の中で数値列を大量に扱う場面」に効く部品だと見るのが自然だろう。
最後に気になるのは、Googleが「1 CPU core で 1 GB/s でソートできると、どんな新しい用途が開けるのか」と書いているところだ。これは単なる自慢ではなく、設計の前提が変わるかもしれない、という問いかけに近い。ソートは高コストだから避ける、という発想はかなり多い。ところが、もしそのコストが大きく下がるなら、これまで索引や前処理でごまかしていた処理を、より素直にソート中心で組める場面が増えるかもしれない。もちろん、全体の性能はI/Oや別の処理にも左右されるので、何でも置き換わるわけではない。それでも、こういう基礎部品の速度が上がると、上位レイヤーの設計自由度がじわっと広がる。そこにこの発表の本当の意味があると思う。
