このブログは、株式会社フィックスターズのエンジニアが、あらゆるテーマについて自由に書いているブログです。
今日も「1マイクロ秒でも速いソフトウェア」を目指している皆様、こんにちは。
フィックスターズでは、CまたはC++を仕事に使うことが圧倒的に多いですが、1年前に社内勉強会で「C/C++の後継になりうる」と噂のRustを取り上げました。
その時に「Rustで書き直したらC++で書いたやつより速くなった」というネタを発表したのですが、先日ネットワークドライバを様々な言語で実装したらRustはCに比べてわずかに遅かったという話を見かけた(日本語記事も参照)ので、自分の発表内容を思い返すついでにブログでご紹介します。
共役勾配法のベンチマークを実行したら
で、必ずC++よりRustの方が速かった(わずかに)。
共役勾配法とは、線形方程式の求解手法で、以下のような単純な線形代数操作でのみ構成されています。
詳しくはググるなりウィキペディアを参照してもらうなりするとして、とても単純なので、今回元にするベンチマークではいろんな環境での結果が試されています。
元々がC++で書かれていたので、これをRustに移植して、Rustの勉強をしつつ「RustはC++並に速い」という世の中の噂(?)を検証してみようというのが今回の趣旨です。
なお、最初に書いた通り、これは1年前の発表内容であり、Rustはとても進化が速いので、現在では少しズレていることが書かれているかもしれません。
また、勉強会で自分が勉強しながら書いたり調べたりしたコードなので、あまり洗練されていなかったり、もしかすると間違っているかもしれません。もしそれらを見つけたらぜひコメントを下さい。
環境構築はLinuxの場合、まず、curl https://sh.rustup.rs -sSf | sh
を実行し、1(Proceed with installation)を選びます。
その後、source $HOME/.cargo/env
をすれば完了です。簡単ですね!
なお、今回は以下のような環境で準備&速度計測しました
(2019/09/19 10:00追記)なおここでの処理時間計測結果は、内容の確認と新しいコンパイラでの結果比較もかねて、1年前のものではなく執筆時点での再測定結果に更新しています。
ベンチマークはC++で書かれているのですが、全部Rustに移植するのは大変ですし、そもそもベンチマークの中核関数以外はどうでもいいので、C++からRustを呼ぶことにします。
その方法についてはThe bookに書いてあります。
まず最初に、Rustのコードを吐く形式を
のどっちにするかの2択があります。
この場合、それぞれ書き方が異なりますし、コンパイルコマンドが異なります。また、一長一短で、
ので、お好みで、という感じだと思います(cargoとか使うとその辺り自動でやってくれそうですが、既存のMakefileに組み込むためになるべく素のコマンドを使いたかったのもあって、調べていません)。
加えて、crate_typeを指定する必要があります。これはソースの.rsに直接指定するか、代わりにコンパイル時のオプションで-crate-type=
を指定することもできます。
これもどっちがいいかは、これも状況と好みで選ぶべきと思います(今回はソースコードに埋め込みました。
#![crate_type = "cdylib"] // dylibでも動くが無駄な情報がついてくるのでcdylibの方がいい
#[no_mangle]
pub extern fn func()
{
println!("Hello, world! [from Rust]");
}
#include <iostream>
extern "C" void func();
int main()
{
std::cout << "Hello, world! [from C++]" << std::endl;
func();
return 0;
}
$ rustc func.rs
$ g++ main.cpp -lfunc -L. -Xlinker -rpath -Xlinker .
$ ./a.out
Hello, world! [from C++]
Hello, world! [from Rust]
#![crate_type = "staticlib"]
#[no_mangle]
pub extern fn func()
{
println!("Hello, world! [from Rust]");
}
$ rustc func.rs
$ g++ main.cpp -lfunc -L.
$ ./a.out
Hello, world! [from C++]
Hello, world! [from Rust]
C/C++では「ポインタ」と「長さ」で配列を扱うので、Rustにもその情報しか渡せません。
Rustでは、The bookにある通り、以下のようにポインタを扱うことができます。
ptr : *const T
⇔ const T* ptr
ptr : *mut T
⇔ T* ptr
しかしそのままだと配列アクセスみたいにはできないので、ここでstd::slice::from_raw_parts
を使って、スライスを作ります。
#[no_mangle]
pub extern fn func(x_ptr : *const f64, n : usize)
{
let x = unsafe{std::slice::from_raw_parts(x_ptr, n)};
println!("{}/{}", x[0], n);
}
#include <iostream>
#include <memory>
extern "C" void func(const double*, std::size_t);
int main()
{
constexpr auto N = std::size_t(10);
auto a = std::make_unique<double[]>(N);
a[0] = 0.12345;
func(a, N);
return 0;
}
さて早速、共役勾配法を構成する計算のうち、一番わかり易いy = x + βyを最初に移植してみます
static void Add(Problem::VectorT& y, const Problem::VectorT& x, const double beta)
{
const auto n = y.N;
for(auto i = decltype(n)(0); i < n; i++)
{
const auto x_i = x[i];
const auto y_i0 = y[i];
const auto y_i = x_i + beta * y_i0;
y[i] = y_i;
}
}
#[no_mangle]
pub extern fn Add(y_ptr : *mut f64, x_ptr : *const f64, n : usize, beta : f64)
{
let x = unsafe{std::slice::from_raw_parts(x_ptr, n)};
let y = unsafe{std::slice::from_raw_parts_mut(y_ptr, n)};
for i in 0..n
{
y[i] = x[i] + beta * y[i]
}
}
スライスを作る時、後から書き換えるものについてはstd::slice::from_raw_parts_mut
になることに注意が必要です。
移植した後実行すると、残差の収束状況が
0, 0.0462883
1, 0.0154017
2, 0.0109386
3, 0.0121484
4, 0.0169089
5, 0.0222516
6, 0.0279979
7, 0.0365326
8, 0.0449547
9, 0.0549113
10, 0.0666704
11, 0.0736913
12, 0.0814898
13, 0.0947444
14, 0.0994545
15, 0.0993077
16, 0.105784
17, 0.112494
18, 0.114861
19, 0.121114
20, 0.126522
21, 0.13164
22, 0.138759
23, 0.139927
24, 0.138921
25, 0.14813
26, 0.155181
27, 0.152352
28, 0.15514
29, 0.160411
30, 0.159579
31, 0.161631
32, 0.168127
33, 0.171606
34, 0.176357
35, 0.178426
36, 0.176112
37, 0.17939
38, 0.185836
39, 0.184756
40, 0.187017
41, 0.193864
42, 0.192611
43, 0.190431
44, 0.195028
45, 0.197859
46, 0.197548
47, 0.199383
48, 0.198936
49, 0.199582
50, 0.204465
と表示され、C++と変わらないことが確認できます(※問題の性質上、50回程度では残差は減りません)。
あまりRustらしい書き方とは言えませんが、結果は合ってる(C++版と変わらない)ので、とりあえずの移植としてはこれで良しとします
しました。
移植したので、早速時間計測してみました。
SequentialNative, PreProcess, 8.384, Solve, 1769.87, PostProcess, 1.765
Rust, PreProcess, 8.275, Solve, 55706.9, PostProcess, 1.306
表示されている数字は、左から順に前処理にかかった時間、求解本体の時間、後処理の時間です。
つまり、C++版は1.8[s]でしたが、Rust版は55[s]かかっていることになります。
Rustは圧倒的に遅い!!
ということでRustはC++に比べて遅い、とかいうと流石にそんなことはないはずなので、高速化します。
遅い・・・と思ったちょうどその時、たまたまTwitterに「Rust最適化入門 1. 最適化オプションをつけているか確認する」と流れてきました。なるほど。
で、最適化オプション自体は色々あるようですが、とりあえず-C opt-level=3 -C debug_assertions=no
で良さそうです。
ということでつけてみました。結果、
SequentialNative, PreProcess, 8.539, Solve, 1794.23, PostProcess, 1.639
Rust, PreProcess, 8.569, Solve, 1808.4, PostProcess, 1.42
ということで、C++は1794[ms]、Rustは1808[ms]で、ほとんどC++版と同じ時間になりました(ちょっとだけ負けてますが)。
ちょっとだけ遅いのは、呼び出しコストでは?(あと、全体最適化もかけづらいし)ということで、Solve全体を移植することにします
共役勾配法では内部の計算でしか使わないベクトルというのが3つあって、それをどうするか?という話です。
(動的な大規模)配列は、C++では「ポインタ」(と長さ)でしかないんですが、Rustではいくつかあるので、どれがいいかなと調べてみると、概ね3通りあるようです(他にもありますが、unstableな機能だったりするのでとりあえず無視します)。
Sliceは先に説明した通りです。ということで、VecかBoxかですが、Boxは作る時に「スタックに置いてからヒープにコピー」するらしく、それは流石に避けたいです(処理速度的に無駄なことはしたくない)。
ということでVecしか選択肢がなく、
let v = vec![0f64, n];
としました。
ただ、本当は可変長じゃないのでVecより素朴な(速い?)ものが欲しいです。何か良いのがあれば教えてください(MR送ってもらえるとなお嬉しいです!)。
というわけで、
という状況になり、引数に渡す時に型が違うのが面倒になってしまいました。
こういう時、C++ではテンプレートの出番なので、Rustの場合はトレイト境界を使うことになります。
今回やりたいことは[]でのアクセスで、これはstd::ops::Index
が該当します。
ここで、結果をf64で取得したいので、Associated Type
を指定することで可能になります。つまり、以下のような感じになります。
fn func<T>(v: T) -> f64 where
T : std::ops::Index<usize, Output=f64>
{
let a = v[0];
return a;
}
fn main()
{
let v = vec![1f64; 10];
let r = func(v);
println!("{}", r);
}
と、言うことでVecはこれでいいんですが、なぜかSliceはstd::ops::Indexを実装してないと怒られることに気づきました(the trait `std::ops::Index
)。
s[i]でアクセスできるんだから、Indexを実装していないわけないはず。。というかリファレンス見ると実装されてそうなのに・・・。
ということで、諦めて、VecはSliceにして、引数は全部Sliceで渡すことにしました。
fn func(v: &[f64]) -> f64
{
let a = v[3];
return a;
}
fn main()
{
let v = vec![1f64; 10];
let s = &v[..];
let r = func(s);
println!("{}", r);
println!("{}", s[3]);
}
というところまで書いて、実は最初のは書き方が間違っているんだと社内Slackのrustチャンネルで教えてもらいました。
トレイト境界には暗黙的にSizedが含まれるため、SizedでないSliceは渡せなかっただけだったようです。
ということで、?Sizedをつければよかったです。
fn func<T>(v: &T) -> f64 where
T : std::ops::Index<usize, Output=f64> + ?Sized
{
let a = v[3];
return a;
}
fn main()
{
let v = vec![1f64; 10];
let r = func(&v);
println!("{}", r);
}
ということで、これで使えるのですが、まぁとりあえずSliceのままでも不便しなかったので、以降はSliceを使い続けます。
書き直した結果、
$ ./ConjugateGradient
Generating Problem...
SequentialNative, PreProcess, 8.1, Solve, 1768.39, PostProcess, 1.4
Rust, PreProcess, 8.353, Solve, 1823.39, PostProcess, 1.295
これだけではやっぱりまだちょっと遅いです。
今の実装のままだと、Vecの生成、つまりメモリ確保をSolveの中でやっていますが、C++では前処理でやっていてSolve時間に含まれず比べるにはちょっと不公平です。
ということで、外でやることにしたい・・・んですが、やり方が思いつかないので、普通に外から渡すようにしました。
$ ./ConjugateGradient
Generating Problem...
SequentialNative, PreProcess, 8.106, Solve, 1802.42, PostProcess, 1.325
Rust, PreProcess, 8.288, Solve, 1812.75, PostProcess, 1.634
あんまり変わりませんでした・・・。
Rustは配列アクセスする時に境界チェックをするので、そのオーバーヘッドを気にしてみます。
ベクトルの加減算(いわゆるBLAS Level1)は全部範囲内であることはコード上明らかなので、ここはコンパイラがチェックを外してくれているはずと信じます。
ということで、問題は疎行列ベクトル積なので、ここはget_unchecked()
を使います。
fn func(v: &[f64]) -> f64 where
{
let a = unsafe{ *v.get_unchecked(3) };
return a;
}
fn main()
{
let v = vec![1f64; 10];
let s = &v[..];
let r = func(s);
println!("{}", r);
}
これによってunsafeになることが注意です。やってみました結果、
$ ./ConjugateGradient
Generating Problem...
SequentialNative, PreProcess, 8.232, Solve, 1685.91, PostProcess, 1.455
Rust, PreProcess, 8.022, Solve, 1675.32, PostProcess, 1.429
C++に勝ったぞ!!!!!!
※このベンチマークは、実行順とかではあまり結果に差がない(メモリキャッシュどうこうの影響はあまりない)ことが経験的にわかっていて、実際に何回か繰り返したりC++(SequentialNative)と順番を入れ替えたりしても必ずわずかに勝つので、本当に勝ったらしい。
ここまでのコードは、C++を普通に移植してfor iで反復していますが、ちゃんとイテレータとか使った方が速くなるのでは?と思ったので試してみます。
これを使っていて気づいたのは
(((a, b), c), d)
みたいに「2要素タプルのタプルの・・・」としないといけないです。一方、spmvをイテレータにしようとすると、data,columnを多次元配列にしなければならないので
のどちらかができないとダメなんですが、どちらの方法も分からなかったので、やっていません。
実行結果は
$ ./ConjugateGradient
Generating Problem...
SequentialNative, PreProcess, 8.024, Solve, 1681.53, PostProcess, 1.475
Rust, PreProcess, 8.114, Solve, 1674.95, PostProcess, 1.422
となって、そもそも元の実行時間にブレはあるんですが、C++とRustの差は大きくなった気がします?
内積と複製については、それぞれ、fold
とcopy_from_slice
が使えるので、それを使います。
結果は
$ ./ConjugateGradient
Generating Problem...
SequentialNative, PreProcess, 8.024, Solve, 1691.09, PostProcess, 1.403
Rust, PreProcess, 8.112, Solve, 1677.43, PostProcess, 1.467
なので、もうちょっと速くなった気持ちです。
ということで、全部まとめるとこんな感じです
やったこと | C++版[ms] | Rust版[ms] | 短縮時間[ms] | 加速率 |
---|---|---|---|---|
各関数の移植 | 1770 | 55707 | -53937 | 3.2% |
最適化オプション | 1794 | 1808 | -14 | 99.2% |
全体移植 | 1802 | 1823 | -21 | 98.8% |
外部でメモリ確保 | 1802 | 1813 | -11 | 99.4% |
配列境界チェック | 1686 | 1675 | +11 | 100.7% |
イテレータ | 1682 | 1675 | +7 | 100.4% |
イテレータ操作関数 | 1691 | 1677 | +14 | 100.8% |
実行毎に数十msはブレるので、元のC++実装に対しての時間で比較して見ると、最適化オプションと配列境界チェックの除去が効いているように見えます。
そして先述の通り、RustとC++で実行順を入れ替えたり何度か実行しても、最終的に必ず(わずかに)Rustの方が時間短かったので、(2019/09/20:45追記)「計測誤差ではないの?」という問い合わせを内外から多数受けたので、(先述の通り経験的に計測誤差でないことは明らかではあるんですが経験者でない人向けの)分かりやすい証拠としてC++とRustそれぞれ単体を100回ずつ計測した結果を置いておきます。分布から分かる通り、検定などするまでもなく有意にRustの方が時間が短いことが分かります。また、C++側は元のナイーブな実装のままなので、高速化の余地(例えばrestrict)は十分にあります。ここでは「手軽にやった時に」を想定しており、その条件では結論として「RustでC++に速度で勝った話」でした。
やり残したこととしては
です。いつかやりたいと思います&誰かぜひやってください。
早速、追試をしていただいたようでありがとうございます!(こういうスピード感でマサカリ投げ合うのが現代の醍醐味ですね)。
以下、私が把握している限りをご紹介します。ほかに「こういうのありましたよ」というのがあれば、コメント欄等でぜひ教えてください
https://qiita.com/ACUVE/items/598cecf687cb771f7242
この記事どうでしょう。