よくあるベンチマークを調べたい
κeenです。よくある言語同士や言語実装同士の速さの比較に使われるベンチマークが実際にどんなところの性能を調べているのかを理解してないので軽く調べてみます。
色々調べようかと思ったんですが、一番よく見るのはComputer Language Benchmarks Gameの結果かなと思うのでここで使われているベンチマーク10種について調べていきます。 調べるとはいっても説明を読んで、ベンチマークに使われてるプログラムを読んで感想を言っていくだけです。実際にプロファイルをとってどこがボトルネックになるとかまではやらずに想像で喋ってるので参考程度に見ていって下さい。
fannkuch-redux
fannkuch-reduxは数字列を操作するプログラムです。
求める計算は以下です
- ${1,\cdots,n}$の並べ替えを受け取る 例: ${4,2,1,5,3}$
- 最初の要素を見て（ここでは4）、先頭からその数の要素分だけ順序を反転させる: ${5,1,2,4,3}$
- これを先頭の要素が1になるまで繰り返す: ${3,4,2,1,5}$ → ${2,4,3,1,5}$ → ${4,2,3,1,5}$ → ${1,3,2,4,5}$
- 何回反転させたかを数える: 5
- 以下のどちらかの式でチェックサムを計算する（どちらでも等価）:
- $checksum = checksum + (\mathrm{if};{}permutation\_index;\mathrm{is};\mathrm{even};\mathrm{then};{}flips\_count;\mathrm{else}-flips\_count)$
- $checksum = checksum + (toggle\_sign_{-1\_1} * flips\_count)$
- これを全ての $1$ から $n$ までの数の並べ替えで計算する
- チェックサムと、最大の反転回数を出力する
個々の数字列に対しては並列に計算できるので、処理系の並列計算能力や配列操作、場合によっては数値の扱いあたりが効いてきそうですね。
因みにこれはベンチマーク用のプログラムみたいで、あんまり意味のあることはしてなさそうです。fannkuchはパンケーキ（ホットケーキ）の意味で、ホットケーキを裏返すのを繰り返してる…らしいです。
n-body
n-bodyは木星型惑星の軌道を計算するプログラムです。木星型惑星は太陽系でいうと木星、土星、天王星、海王星です。日本語でも普通にN体問題で知られていますね。
プログラムの中身はそこまで難しいものではなく、主にループと浮動小数点数計算で構成されています。 ベンチマークプログラムとして浮動小数点数計算がメインなので数値計算屋さんの戦場になっておりSIMD命令などを使った最適化の戦いが繰り広げられています。 SIMDを使えない言語ではシンプルな演算の性能のベンチマークになるようです。
spectal-norm
spectral-normは行列のスペクトルノルムの近似値をべき乗法で計算するプログラムです。スペクトルノルムについてはWikipediaの行列ノルムのページや特異値のページも参考にして下さい。 計算の元になる行列の要素は以下の式で与えられています。
\[ a_{ij} = \frac{1}{(i+j)(i+j+1)/2+i+1} \]
添字を渡されたらどんなサイズの行列でも要素を計算できるのでベンチマーク向けにサイズを増やすのに向いてます。
具体的なスペクトルノルムの計算は $A^TA$ を20回掛けて求めています。
行列計算なので粗粒度並列性（≒スレッド）と細粒度並列性（≒SIMD）の両方が使えるところであり、かつキャッシュの有効活用なんかも重要なのでそれぞれを使える/使えないが大きく点数に響きます。
mandelbrot
mandelbrotはマンデルブロ集合を描画するプログラムです。マンデルブロ集合は投げ付けたら痛そうなアレですね。
画素ごとの計算が可能で自由な並列化ができるのでそのあたりの速さが必要そうです。あと地味にバイナリデータを出力するのでバイナリデータの出入力が弱いとマイナスポイントかもしれません。
pidigits
pidigitsは円周率πの10進表記を求め、表示するプログラムです。アルゴリズムに指定があります。内部で多倍長整数を使うので多倍長整数ライブラリの出来の良さが効いてきます。
regex-redux
regex-reduxは正規表現でDNA列のフォーマットのFASTAを処理するプログラムです。
入力の改行を正規表現処理したり、特定の塩基列とその逆相補配列をさがしたり、特定のパターンを置き換えたりします。
正規表現エンジンの速度や文字列確保の効率などが効いてきます。
fasta
fastaは先述のDNA列のフォーマットであるFASTAを生成するプログラムで、アルゴリズムに指定があります。DNA列を繰り返したりランダム生成したりします。
ループの中で分岐や（プログラムの作りによっては）文字列確保をするので基礎スペックが効いてきます。ランダムとはいってもアルゴリズム指定があり、結果の一致も求められるのですが、工夫すると並列化もできるようなので並列化性能も効くみたいです。
k-nucleotide
k-nucleotideはハッシュマップを使ってFASTAフォーマットで与えられる塩基を数えるプログラムです。各塩基の単体、2つ組の全てのカウントを出力し、3、4、6、12、18つ組の全てをカウントして特定の組のカウントを出力することが求められます。
ハッシュマップ自作が認められない、容量も手動確保せずに自動スケーリングに任せるなどの制約があり、組み込み/ライブラリのハッシュマップの速度を競う内容になっています。
reverse-complement
reverse-complementはFASTAフォーマットで与えられたDNAの逆相補配列を出力するプログラムです。アルゴリズムの指定があり、入力を1行ずつ自動バッファリングに任せて読み込むなどの制約があります。
ナイーブな出入力の速度と反転に必要な文字列処理が効いてくるベンチマークになります。…が、入力と反転処理を並行でやるために工夫したり反転操作は上手くスレッド並列やSIMD化したりもできるので、やっぱり並列処理に強い言語が強くなります。
binary-trees
binary-treesは完全二分木を操作するプログラムです。アロケーションに指定があり、最低でも参照実装のプログラムと同じ回数だけのアロケーションが求められます。また、独自のメモリ管理手段を用意することは禁止されています。
アロケーションに指定がある通り、メモリの扱いが効いてくるベンチマークです。あと地味にポインタを行ったり来たりするのでポインタの効率が悪いとマイナスポイントになります。アロケーションの指定で自作アロケータは禁止されているものの、外部ライブラリのアロケータを使うのは許されているようで、そういった手動メモリ管理ができる言語が大幅に有利になっています。
ざっと眺めてみましたが、結構大変ですね。前半で数値計算が多くて「大丈夫か？」とも思ったのですが後半で文字列処理やハッシュマップ、メモリアロケーションなどが登場したのでそれなりにバランスの取れたベンチマークなんじゃないでしょうか。
余談ですがベンチマークスイートのネタとしてypsilonのベンチマークなんかもあったのですが、大変なのでやめました。
とりあえず個人的にはどんなベンチマークを取ってるのか納得できたのですっきりしました。