Benchmarks GameのRust vs C++をスクレイピングして決着をつける

はじめに

注意: この記事はRust贔屓とスクレイピングの練習でできています。

Benchmarks Gameとはプログラミング言語の速度を比較するサイトです。
プログラミング言語の速さに興味がある方ならご存知でしょう。
このサイトのトップに2019年2月の現在書いている通り、現実のプログラムの動作はベンチマークとかなり異なるのですがベンチマークジャンキーには関係ないことです。
現実は置いておいてここのデータを元にRust vs C++に決着をつけましょう。

この記事を書くきっかけとなったのは久しぶりにRust vs C++を見ると、ずっとちょい負けしていたRustがついにC++を超えているように見えたからです。
表の見方を説明しておきますと、secsが実行時間、memが使用メモリ、busyがCPU時間です (多分) 。gzはわかりません。
secs, mem, busyの小ささが概ね高速、省メモリ、省CPUに対応しています。
とりあえずsecsに注目してみましょう。
勝ち負けの数を比べると6勝4敗でRustの勝ち越しです。
しかし、もし辛勝6と大敗4だとしたら勝ったとは言えないでしょう。
平均を計算して決着をつけなければなりません。
ということでまずデータをスクレイピングしていきます。
スクレイピングのコードなんて興味ないという方は[データの処理][#データの処理]へ飛んでください。

まとまったソースコードはリポジトリにあります。
動作はPython3.8で確認しています。

スクレイピング

事前にbeautifulsoup4とlxmlをインストールしておいてください。
この表現で合っているのか自信がないですが、beautifulsoup4とlxmlはそれぞれHTMLのパースのフロントエンドとバックエンドです。

インポートは次のようになります。

from urllib.request import urlopen
from bs4 import BeautifulSoup

そしてまずHTMLをダウンロードしてBeutifulSoupオブジェクトに変換します。

rust_gpp_url = 'https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/rust-gpp.html'
with urlopen(rust_gpp_url) as f:
    # lxmlでないと閉じタグを省略しているbenchmarksgameのHTMLをパースできない
    soup = BeautifulSoup(f, 'lxml')

そしてRust vs C++のソースをグッと睨むと、tbodyの中に各ベンチマークが入っていることがわかるので、頑張って数値を取り出します。

tbodies = soup.find_all('tbody')
# 最後のテーブルは処理系の情報なので取り除く
tbodies = tbodies[:-1]

secs_table = {'Rust': [], 'C++': []}
for tbody in tbodies:
    trs = tbody.find_all('tr')
    # 3, 4番目のtr要素がそれぞれRust, C++のベンチマークである
    rust, cpp = trs[2], trs[3]
    # その中のtd要素の2-5番目がそれぞれsecs, mem, gz, busyである
    secs = rust.find_all('td')[1].string
    secs_table['Rust'].append(float(secs))
    secs = cpp.find_all('td')[1].string
    secs_table['C++'].append(float(secs))

print(secs_table)

データの処理

取り出した数値から平均を計算します。
ここで秒数の平均を取るのはあまりいい方法とは言えないでしょう。
おそらく各問題のスケールが均一になっていません。
というわけで問題毎にRustの秒数とC++の秒数の比の平均や中央値を計算することになります。
しかしこの際にも注意すべきことがあり、通常の平均 (相加平均) を取るのは不自然だということです。
例えばRustが問題1, 2にそれぞれ2, 2秒かかり, C++が2, 4秒かかっている場合、Rust / C++ の平均は

$$
\frac{2 / 2 + 2 / 4}{2} = \frac{3}{4}
$$

ですが、C++ / Rust の平均は

$$
\frac{2 / 2 + 4 / 2}{2} = \frac{3}{2}
$$

となりC++から見るとRustは3/4倍の時間で問題を解くことができるが、Rustから見るとC++は3/2倍の時間がかかるというように、変なことになっています。
比のように積や逆数を考えるのが自然な対象に関しては、相乗平均を考えるのが自然です。
定義を確認しておくと、$a_0, a_1, ..., a_{n - 1}$の通常の平均 (相加平均) は

$$
\frac{a_0 + a_1 + \dots + a_{n - 1}}{n}
$$

であるのに対し、相乗平均は

$$
\sqrt[n]{a_0 a_1 \dots a_{n - 1}}
$$

というようにちょうど足し算をかけ算にし、$n$分の$1$を$n$乗根に変えたような形をしています。
計算するコードは次のようになります。

print('C++ / Rust')

for (key, rust_values), cpp_values in zip(table['Rust'].items(), table['C++'].values()):
    n = len(rust_values)
    # 中央値の計算のために収集する
    ratios = []
    mean = 1.0
    for rust_value, cpp_value in zip(rust_values, cpp_values):
        ratio = cpp_value / rust_value
        ratios.append(ratio)
        mean *= ratio
    mean **= 1 / n
    print(f'{key.ljust(4)} - mean: {mean:.2f}', end=', ')

    ratios.sort()
    if n % 2 == 1:
        median = ratios[n // 2]
    else:
        # 中央値が2つある場合はそれらの相乗平均を取る
        median = (ratios[n // 2 - 1] * ratios[n // 2]) ** (1 / 2)
    print(f'median: {median:.2f}')

実行結果:

C++ / Rust
secs - mean: 1.10, median: 1.02
mem  - mean: 1.09, median: 1.11
gz   - mean: 0.95, median: 1.02
busy - mean: 1.08, median: 1.05

Rustのほうが1割近く速いです。
流石に勝ちすぎな気がするのでRustが大差をつけている問題のreverse-complementを過去のものと照らし合わせるとC++が省メモリと引き換えにかなり遅くなっているようです。(Rustがk-nucleotideで大差をつけられるのはいつもどおりのようでした)
そこでreverse-complement抜きで計算すると次のようになります。

C++ / Rust
secs - mean: 0.99, median: 1.02
mem  - mean: 1.17, median: 1.24
gz   - mean: 0.99, median: 1.10
busy - mean: 1.03, median: 1.05

完全勝利とはいきませんでしたが、これならもうC++よりちょっと遅いとは言えないのではないでしょうか。
そしてもう一度確認しておきますが今はRustが明確に速いです。
せっかくだから配慮前の結果をもう一度確認しておきましょう。

C++ / Rust
secs - mean: 1.10, median: 1.02
mem  - mean: 1.09, median: 1.11
gz   - mean: 0.95, median: 1.02
busy - mean: 1.08, median: 1.05

結論

Pythonの勝ち

蛇足

途中でこの記事で使っているのはPythonだけだと気づいて結論を差し替えました。

そういえば、いつの間にかRust vs Clangというのができていて、RustとC clangを比較できるようになっていました。
同じLLVMバックエンド同士ならならC相手でも圧勝です。
まあGCCバックエンドを持たないのがRustなのですが。