Article

2019年9月18日

今日も「1マイクロ秒でも速いソフトウェア」を目指している皆様、こんにちは。

フィックスターズでは、CまたはC++を仕事に使うことが圧倒的に多いですが、1年前に社内勉強会で「C/C++の後継になりうる」と噂のRustを取り上げました。
その時に「Rustで書き直したらC++で書いたやつより速くなった」というネタを発表したのですが、先日ネットワークドライバを様々な言語で実装したRustはCに比べてわずかに遅かったという話を見かけた(日本語記事も参照)ので、自分の発表内容を思い返すついでにブログでご紹介します。

TL;DR

共役勾配法のベンチマークを実行したら

  • C++:1686[ms]
  • Rust:1675[ms]

で、必ずC++よりRustの方が速かった(わずかに)。

概要

共役勾配法とは、線形方程式の求解手法で、以下のような単純な線形代数操作でのみ構成されています。

  • 疎行列・ベクトル積
  • ベクトルの加減算
  • ベクトルの内積

詳しくはググるなりウィキペディアを参照してもらうなりするとして、とても単純なので、今回元にするベンチマークではいろんな環境での結果が試されています

元々がC++で書かれていたので、これをRustに移植して、Rustの勉強をしつつ「RustはC++並に速い」という世の中の噂(?)を検証してみようというのが今回の趣旨です。

なお、最初に書いた通り、これは1年前の発表内容であり、Rustはとても進化が速いので、現在では少しズレていることが書かれているかもしれません。
また、勉強会で自分が勉強しながら書いたり調べたりしたコードなので、あまり洗練されていなかったり、もしかすると間違っているかもしれません。もしそれらを見つけたらぜひコメントを下さい。

準備(Rust環境の設定)

環境構築はLinuxの場合、まず、curl https://sh.rustup.rs -sSf | shを実行し、1(Proceed with installation)を選びます。
その後、source $HOME/.cargo/envをすれば完了です。簡単ですね!

なお、今回は以下のような環境で準備&速度計測しました

OS
Ubuntu 16.04.6 LTS
CPU
Intel Core i9 7900X
Memory
DDR4-2666 16GB x 4 (64GB)
Clang
v8.0.1
Rustc
v1.37.0
ソースコード
ConjugateGradient (c3946cc31607ba5168eb1e331506683d805c1ea4)

(2019/09/19 10:00追記)なおここでの処理時間計測結果は、内容の確認と新しいコンパイラでの結果比較もかねて、1年前のものではなく執筆時点での再測定結果に更新しています。

とりあえず移植する

C/C++からRustを呼ぶ

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

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

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

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

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

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

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

共有ライブラリにする場合

Rust(rust.rs)
#![crate_type = "cdylib"] // dylibでも動くが無駄な情報がついてくるのでcdylibの方がいい

#[no_mangle]
pub extern fn func()
{
	println!("Hello, world! [from Rust]");
}
C++(main.cpp)
#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]

静的ライブラリにする場合

Rust(rust.rs)
#![crate_type = "staticlib"]

#[no_mangle]
pub extern fn func()
{
	println!("Hello, world! [from Rust]");
}
C++(main.cpp)
共有ライブラリと同じ
コンパイル&実行方法
$ rustc func.rs
$ g++ main.cpp -lfunc -L.
$ ./a.out
Hello, world! [from C++]
Hello, world! [from Rust]

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

C/C++では「ポインタ」と「長さ」で配列を扱うので、Rustにもその情報しか渡せません。

Rustでは、The bookにある通り、以下のようにポインタを扱うことができます。

  • ptr : *const Tconst T* ptr
  • ptr : *mut TT* 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++版と変わらない)ので、とりあえずの移植としてはこれで良しとします

他の関数も移植

しました。

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

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な機能だったりするのでとりあえず無視します)。

  • Vec: 可変長配列。C++のstd::vector?
  • Box: 固定長配列(ただし長さはコンパイル時定数)。C++でnew std::arrayするみたいな
  • Slice: 厳密には配列ではなく、いわゆる「ビュー」。

Sliceは先に説明した通りです。ということで、VecかBoxかですが、Boxは作る時に「スタックに置いてからヒープにコピー」するらしく、それは流石に避けたいです(処理速度的に無駄なことはしたくない)。
ということでVecしか選択肢がなく、

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

としました。
ただ、本当は可変長じゃないのでVecより素朴な(速い?)ものが欲しいです。何か良いのがあれば教えてください(MR送ってもらえるとなお嬉しいです!)。

SliceもVecも同列に扱いたい

というわけで、

  • 外から渡された配列はSlice
  • 内部のはVec

という状況になり、引数に渡す時に型が違うのが面倒になってしまいました。

こういう時、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` is not implemented for `&[f64]`)。
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で反復していますが、ちゃんとイテレータとか使った方が速くなるのでは?と思ったので試してみます。

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

  • 複数のイテレータは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の差は大きくなった気がします?

用意されているイテレータ操作関数を使う

内積と複製については、それぞれ、foldcopy_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++に速度で勝った話」でした。

やり残したこととしては

  • spmvもRustっぽく書く
  • Rustでもスレッド並列化(rayonなど)してOpenMPと対戦

です。いつかやりたいと思います&誰かぜひやってください。

追試結果のご紹介(2019/09/19 10:00追記)

早速、追試をしていただいたようでありがとうございます!(こういうスピード感でマサカリ投げ合うのが現代の醍醐味ですね)。
以下、私が把握している限りをご紹介します。ほかに「こういうのありましたよ」というのがあれば、コメント欄等でぜひ教えてください

Tags

About Author

YOSHIFUJI Naoki

yoshifujiです。計算力学的なプログラムを高速化することが得意です。プログラミング自体はチョットダケワカリマス。 Twitter: https://twitter.com/LWisteria

2 Comments

Leave a Comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

Recent Comments

Social Media