本日、C++ std::sort の約10倍の速度で数値配列をソートでき、最先端のアーキテクチャ固有アルゴリズムを上回りながら、すべての現代的なCPUアーキテクチャにポータブルなオープンソースコードを公開します。以下で、これをどのように達成したかを説明します。

まず、背景から。最近、特定の列のすべての値を連続して格納するカラムナデータベースへの傾向があります。これは、レコードまたは「行」のすべてのフィールドを次のレコードの前に格納するのとは対照的です。これは、SQLクエリの重要な構成要素であるフィルタリングやソートにおいて高速になる可能性があります。したがって、私たちはこのデータレイアウトに焦点を当てます。

ソートは広く研究されていることを考えると、どうすれば10倍の高速化を見つけられるのでしょうか？答えはSIMD/ベクトル命令にあります。これらは、単一の命令で複数の独立した要素に対して操作を実行します。たとえば、AVX-512命令セットを使用する場合は一度に16個のfloat32を操作し、Arm NEONでは4個を操作します。

SIMDにすでに精通している方は、スーパーコンピュータ、機械学習アプリケーションの線形代数、ビデオ処理、またはJPEG XLなどの画像コーデックで使用されていると聞いたことがあるかもしれません。しかし、SIMD操作が独立した要素のみを扱う場合、隣接する配列要素を再配置するソートをどのように行うのでしょうか？たとえば、256要素の配列をソートする特別な方法があると想像してください。次に、より大きな配列をソートするためのクイックソートアルゴリズムは、それを2つのサブ配列に分割することで構成されます。「ピボット」値（理想的には中央値）より小さいものと、その他すべてです。次に、サブ配列が最大256要素になるまで再帰し、これらのソートに特別な方法を使用します。分割はCPU時間の大部分を占めるため、SIMDを使用して高速化できれば、高速なソートが得られます。

幸いなことに、現代の命令セット（Arm SVE、RISC-V V、x86 AVX-512）には、分割に適した特別な命令が含まれています。はい/いいえ値の別の入力（要素がピボットより小さいかどうか）が与えられると、この「コンプレスストア」命令は、対応する入力が「はい」である要素のみを連続メモリに格納します。次に、はい/いいえ値を論理的に否定し、命令を再度適用して要素を他のパーティションに書き込むことができます。この戦略は、AVX-512固有のクイックソートで使用されています。しかし、コンプレスストアを持たないAVX2などの他の命令セットはどうでしょうか？以前の研究では、置換命令を使用してこの命令をエミュレートする方法が示されています。私たちはこれらの技術に基づいて、3つのアーキテクチャにわたる6つの命令セットにポータブルな最初のベクトル化クイックソートを実現し、実際に以前のアーキテクチャ固有のソートを上回っています。

私たちの実装はHighwayのポータブルSIMD関数を使用しているため、各プラットフォーム用に約3,000行のC++を再実装する必要はありません。Highwayは利用可能な場合はコンプレスストアを使用し、そうでない場合は同等の置換命令を使用します。以前の最先端技術—これも32ビット整数に固有でした—とは対照的に、私たちは16〜128ビット入力の全範囲をサポートしています。単一のポータブル実装にもかかわらず、AVX2、AVX-512（Intel Skylake）、Arm NEON（Apple M1）の両方で記録的な速度に達しています。100万個の32/64/128ビット数値の場合、Apple M1で実行される私たちのコードは、499/471/466 MB/sの速度でソートされた出力を生成できます。AVX-512を搭載した3 GHz Skylakeでは、速度は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倍の高速化を実現しました。

以前は、ソートは高コストと考えられていました。単一のCPUコアで1 GB/sでソートできることで、どのような新しいアプリケーションと機能が解き放たれるかを見ることに興味があります。Apache2ライセンスのソース...