RustがC++に速度で勝った話

C/C++からRustを呼ぶ

ベンチマークはC++で書かれているのですが、全部Rustに移植するのは大変ですし、そもそもベンチマークの中核関数以外はどうでもいいので、C++からRustを呼ぶことにします。
その方法についてはThe bookに書いてあります。

まず最初に、Rustのコードを吐く形式を

• 共有ライブラリ(.so)
• 静的ライブラリ(.a)

のどっちにするかの2択があります。
この場合、それぞれ書き方が異なりますし、コンパイルコマンドが異なります。また、一長一短で、

• 静的ライブラリにすると、Rustが要求する共有ライブラリを自力で調べてリンクしないといけないが、
• 共有ライブラリの場合は、ライブラリの探索パスを指定しなければならない

ので、お好みで、という感じだと思います（cargoとか使うとその辺り自動でやってくれそうですが、既存のMakefileに組み込むためになるべく素のコマンドを使いたかったのもあって、調べていません）。

加えて、crate_typeを指定する必要があります。これはソースの.rsに直接指定するか、代わりにコンパイル時のオプションで-crate-type=を指定することもできます。
これもどっちがいいかは、これも状況と好みで選ぶべきと思います（今回はソースコードに埋め込みました。

C/C++の配列を引数に渡す

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;
}

vectoradd

さて早速、共役勾配法を構成する計算のうち、一番わかり易い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++版と変わらない）ので、とりあえずの移植としてはこれで良しとします

他の関数も移植

しました。

• y += αx
• z = x – y
• r = x・y
• r = x・x
• y=x
• y = A x)

移植したので、早速時間計測してみました。

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は圧倒的に遅い！！

最適化オプション

遅い・・・と思ったちょうどその時、たまたま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全体を移植することにします

let v = vec![0f64, n];

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);
}

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]);
}

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);
}

$ ./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で反復していますが、ちゃんとイテレータとか使った方が速くなるのでは？と思ったので試してみます。

• add
• add_self
• sub
• dot
• dot_self
• copy

これを使っていて気づいたのは

• 複数のイテレータはzip()でまとめられるますが、3入力以上はzipを連結して(((a, b), c), d)みたいに「2要素タプルのタプルの・・・」としないといけない
• zip()の中身はイテレータでなくていい（IntoIteratorが実装されているものなら）
• zipされたイテレータは受け取ると参照が飛んでくるが、参照を外して受け取ることができて、このほうがすっきりする。ただし、もとの値を書き換える場合(dst)は無理）

です。一方、spmvをイテレータにしようとすると、data,columnを多次元配列にしなければならないので

• 1次元スライスを2次元に
• from_raw_partsで最初から多次元に

のどちらかができないとダメなんですが、どちらの方法も分からなかったので、やっていません。

実行結果は

$ ./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が使えるので、それを使います。

• copy (copy_from_slice)
• dot (fold)
• dot_self (fold)

結果は

$ ./ConjugateGradient
Generating Problem...
SequentialNative, PreProcess, 8.024, Solve, 1691.09, PostProcess, 1.403
Rust, PreProcess, 8.112, Solve, 1677.43, PostProcess, 1.467

なので、もうちょっと速くなった気持ちです。