ある日のメモ

※途中にAIとの対話を含みます。

世界的にも有名なコンピュータサイエンティストであるアンドレイ・アレキサンドレスク（Andrei Alexandrescu）氏です。

彼が2020年にD言語の公式ブログに投稿した記事『Lomuto’s Comeback: Change-Free Sorting in C++ and D（ロムートの逆襲：C++とDにおけるブランチレス・ソート）』は、プログラミング界隈（RedditやHacker Newsなど）で大きな話題になりました。

あなたが先ほど挙げたOrson Peters氏のブログ記事（2022年）も、まさにこのアレキサンドレスク氏の2020年のアイデアをベースにして、さらに洗練・進化させたものです。

アレキサンドレスク氏が提唱した「世界最速のクイックソート」のアイデアの要点を分かりやすく解説します。

アレキサンドレスク氏のアイデアの核心

これまでクイックソートのパーティション（分割）といえば、「ホーア（Hoare）法が最強で、ロムート法は遅いから実用性なし」というのが数十年間、教科書通りの常識でした。

しかし、アレキサンドレスク氏は現代のCPUの特徴（分岐予測ペナルティ）に着目し、「あえて無駄なデータ移動（スワップ）が多いロムート法を『ブランチレス（条件分岐なし）』で実装すれば、ホーア法をぶち抜いて世界最速のソートが作れる」と主張したのです。

なぜロムート法を選んだのか？

ホーア法（両端から中央にスキャンする手法）は効率が良い反面、コードの構造上、どうしても条件分岐（if文）が多くなり、ブランチレス化するのが非常に困難でした。

一方で、ロムート法は「左から右へ一方向にスキャンするだけ」という単純な構造をしています。アレキサンドレスク氏は、この「一方向スキャン」こそが、CPUの条件分岐を消し去るのに完璧な構造であることを見抜きました。

具体的にどうやって「分岐」を消したのか？

通常、ロムート法では以下のような条件分岐を使います。

      C++
      // 従来のロムート法（遅い原因）

      if (array[i] < pivot) {

          swap(array[i], array[j]);

          j++;

      }

データがランダムだと、この if 文の予測が50%の確率で外れ、CPUの実行パイプラインがガタガタになります。

アレキサンドレスク氏は、これを以下のように書き換えました。

      C++
      // アレキサンドレスク氏のブランチレス・ロムート法

      bool less = array[i] < pivot;

      swap(array[i], array[j]); // 条件に関わらず常にスワップ（または移動）する！

      j += less;                 // 真（1）か偽（0）かをポインタにそのまま足す！

「ピボットより小さかろうが大きかろうが、とにかく毎回スワップの計算（条件付き移動指令：CMOVなど）を無理やり実行し、ポインタの進捗だけを 0 か 1 で制御する」という荒技です。

一見すると「条件を満たさない時まで無駄な計算をしていて遅そう」に見えますが、現代のCPUにおいては、「分岐予測ミスで何十サイクルも無駄にするくらいなら、毎回無駄な計算をストレートに実行した方が圧倒的に速い」のです。

結果：標準ライブラリ（std::sort）を圧倒

彼がこの「ブランチレス・ロムート法」をC++とD言語で実装し、C++の最高峰に最適化されている std::sort（インテルのリファレンス実装など）と比較したところ、ランダムなデータにおいて最大で2倍近く高速化するという驚異的な数値を叩き出しました。

この歴史の流れ

2020年（アレキサンドレスク氏）：
「ロムート法をブランチレスにしたら std::sort より速くなったぞ！」と発表。ただし、毎回スワップが発生するためメモリへの書き込みがまだ多かった。
2022年（Orson Peters氏 - 最初の質問の記事）：
「アレキサンドレスク氏のアイデアは素晴らしい。じゃあ、配列に1つ『空きスペース（ギャップ）』を作って玉突き移動にすれば、ブランチレスな上にスワップの無駄なメモリ書き込みまで減らせるから、もっと最速になる！」