I/O がボトルネックではなくなりましたか?

2022 年 11 月 27 日

最近のベン・ホイト ブログ投稿を公開しました 一般に信じられていることに反して、ストリームから単語の出現頻度を数えるなどの典型的なプログラミング面接の問題のボトルネックは I/O ではないと主張しています。シーケンシャル読み取り速度は大幅に進歩しましたが、CPU 速度は停滞しています。

シーケンシャル読み取りは確かに信じられないほど高速です。 Ben Hoyt の投稿でリンクされているのと同じ方法を使用すると、次のようになります。 1.6GB/秒 コールド キャッシュでのシーケンシャル読み取り、および 12.8GB/秒 ウォーム キャッシュ上 (5 つのベスト)。

しかし、シングルスレッドでも 1.6 GB/s の速度で単語頻度をカウントできるはずですよね。

(せっかちな人のために: コードは GitHub で入手可能。）

最適化された C 実装

Ben Hoyt のブログでは、 以前の投稿 これには、単語頻度カウンターの高速な C バージョンが含まれています。コンパイルしました optimized.c GCC 12 で、使用 -O3 -march=native フラグを設定し、425MB の入力ファイル (欽定訳聖書 100 部) で実行しました。

結果は驚くほど悪いものでした。

$ time ./optimized  /dev/null

real    0m1.525s
user    0m1.477s
sys     0m0.048s

それだけです 278MB/秒 ウォームキャッシュ上。

ベクトル化

コードを見ると、ホット ループの 1 つに早期終了を含む多くの分岐があり、コンパイラーのベクトル化を妨げていることがわかりました。

for (; i if (c >= 'A' && c 
    hash *= FNV_PRIME;
    hash ^= (uint64_t)c;
}

パフォーマンスを向上させるための最初の試みは、次のようにこの小文字のロジックをループの外に移動することでした。

for (int i = 0; i = 'A' && buf[i] 

This simple change improved performance to 330 MB/s (using clang for better vectorization). Funnily enough, just adding these 3 lines before the loop, without deleting the original code gives comparable speed; strictly more work, but branch prediction does its job. Still, it's about a factor 5 away from cold cache sequential read speed.

Trying a simpler problem
At this point I thought it was unlikely I could squeeze a lot of performance out of the word frequency counter. Sure, there are cache misses in the hash map, so maybe it could be optimized for better cache locality of common words. Or potentially short words can benefit from perfect hashing on the stack. But what will that give? Another 20%?
Instead, let's look at an informative baseline. Just count words without keeping track of frequencies; no tedious hash maps.

In fact there's a program for that: wc -w. Such a single-purpose tool must be fast, right?

$ time wc -w  /dev/null 

real    0m1.758s
user    0m1.718s
sys     0m0.040s

予想外に性能がひどい…。 245.2MB/秒。なぜ？まあ、マニュアルページには、別のことをしていると書かれています。 Ben Hoyt コードは次の部分のみを分割します。 ' ' 空白、一方 wc 用途 ' '、 '\n'、 '\t'、 ...ロケール固有の文字も含まれます。




単語カウントはどれくらい早くできるでしょうか？
過去 10 年間でディスク速度が追いついたという前提がある場合、実際にはその期間の新しい CPU 機能を使用する必要があります。それは基本的に、すべてのものをベクトル化することを意味します。 AVX2 はすでに 10 年近く前のものです。 2017年にAVX-512が一般向けに入手可能になりましたが、私はznver2を使用しているので、AVX2に固執します。
残念ながら、コンパイラは単語数の自動ベクトル化に苦労しています。おそらく、これはベン・ホイト氏の主張の要点を証明しているでしょう。ディスクは「無料で」桁違いに速くなりましたが、現代のコンパイラは魔法のように桁違いに速くマシンコードを生成できるわけではありません。分岐のあるスカラー プログラムをベクトル化されたマシン コードに変換するのは非常に困難です。
マスク
単語数の一部は簡単に自動ベクトル化できます。簡単にするために、16 個の連続文字を格納できる 128 ビットのレジスタ サイズがあると仮定します。空白を事前にレジスタにブロードキャストし、単一の実行を行うことで、空白を見つけるのは簡単です。 VPCMPEQB 比較演算:
       | 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 |
input: | h o w   m a n y   w o r d s   a | r e   h e r e ?
 mask: | 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 |

しかし、ベクトル レジスタにマスクを取得した後、どうやって単語を数えるのでしょうか?私が考えることができる唯一のことは、 バイトマスクの移動 で見たトリック コスモポリタン libc  strlen 実装。関連する指示 PMOVMSKB ロングビットマスクを32ビットに移動します intそして、いつものようにちょっとしたトリックを行います。
ちょっとしたトリック
よくあるちょっとしたコツは何ですか？有力な候補者の一人は、 最初のセットを検索 または ffs つまり、ちょっとしたトリックを正しく理解するのがどれほど面倒かを考えると、これは素晴らしい名前です。この命令は、次のように設定されたビットを反復するために使用できます。
#include 

int main() {
    int mask = 0b0100000100001000;
    int prev = 0;
    while (mask) {
        int curr = __builtin_ffs(mask);
        if (curr > prev + 1)
            printf("Word start at %d\n", curr);
        prev = curr;
        if (curr == 32) // don't ask, sigh.
            break;
        mask = (mask >> curr) 
    }
}

上記のマスクの例に対応して、以下が出力されます。
Word start at 4
Word start at 9
Word start at 15

それをまとめる
結局、このコードを明示的に使用して作成しました immintrin.h それはまったく恐ろしい経験です。次回は高レベルの API を使用します (以前は、Julia REPL で対話的に物事をベクトル化してとても楽しかったです) VectorizationBase.jl）。しかし、少なくとも私は、生成されたマシンコードをある程度制御できるように感じました。
256 ビット レジスタを備えた AVX2 を使用すると、データを 32 ビットに揃える必要があり、私はそれを実行しました (もちろん、最初に台無しにしないわけにはいきません)。ブロードキャストされたすべての空白文字を保持するために、レジスターのうち 6 つを予約しました。次に、ベクトル化されたループを明示的に 4 回展開したため、各反復で 128 バイトのデータが処理されます。
オフバイワンのバグを修正するには非常に時間がかかりましたが、最終的には、コンピューター上のゼロではない量のテキスト ファイルに対してテストして、なんとか動作するプログラムを入手することができました。
$ ./wc-avx2 
So, how fast?!
$ time ./wc-avx2 
That comes down to 1.45 GB/s (on a warm cache).
Sigh. So hand-optimized, single-threaded word count is only getting about 11% of the sequential disk read speed. And on a cold cache?
$ sysctl -w vm.drop_caches=3
$ time ./wc-avx2 
Still more time in user than sys :(. So yeah, maybe the disk speed has caught up statement is indeed true.
Get the code
I've put my code up on GitHub. If you know better bit-tricks, feel free to submit a pull request.