【Rust】ArcとStringのclone()、速いのはどっち?
ArcやRcといえば、Cell/RefCellやMutex/RwLockと組み合わせて複数の参照先から値を共有しつつ変更も行えるという、&mutの制約を突破するためのものとして語られる事が多いような気がしますが、今回は純粋なデータ共有としてのArc/Rcについて考えていってみたいと思います。
そもそもArc/Rcとは?
なにやらややこしそうな気配がしますが、冷静に見ると原理は結構単純です。
Rustの変数には所有権というものがあり、一つのデータを保持できるのは基本的には一つの変数のみです。
&を使った借用は複数作ることができますが、借用はその名の通り、値を借りているだけという扱いなので、オリジナルの変数が先に消滅するような場合ですと、Borrow checkerに叱られてコンパイルエラーになります。
このBorrow checkerの監視をかいくぐっていろんなところに借用を作るのは至難の業です。
structに借用を渡すような事をしようものなら、かなり窮屈なプログラミングを強いられることになります。
それを避ける方法の一つが、Arc/Rcを使ったデータ共有となります。
// 借用をstructのメンバに含める場合。fugaはHogeより長生きでなければならない
struct Hoge<'a>{
fuga:&'a Fuga
}
// Rcを使った場合。fugaの寿命を考えなくてよい。
struct Hoge{
fuga:Rc<Fuga>
}
Rcを使う場合ですと、Rcのデータが複製される度にRc内部の参照カウンタが一つ増えます。
いろんなところで複製しまくると、そのカウンタは複製した分だけ増えます。
そして、スコープを抜けるなどして、Rcがドロップされる度に、カウンタが減ります。
そうして、最終的にカウンタが0になると、Rcそのものが消滅します。
どういう事が、実際のコードを見てみましょう。※わかりやすいようにスコープを付けてます。
struct Fuga{
}
struct Hoge{
fuga:Rc<Fuga>
}
struct Hugo{
fuga:Option<Rc<Fuga>>
}
{
let mut hugo=Hugo{fuga:None};
{
let fuga=Rc::new(Fuga::new()); //この時点では参照カウンタが1
hugo.fuga=Some(Rc::clone(&fuga)); //// Rc::cloneで複製される。参照カウンタは2になる
{
let hoge=Hoge{fuga: Rc::clone(&fuga)}; //さらに複製。参照カウンタは3になる
{
let fuga2=Rc::clone(&fuga); //さらに複製。参照カウンタは4になる
} //このスコープを抜けると参照カウンタは3に
} // 参照カウンタ2
} // 参照カウンタ1。最初に作ったfugaがドロップしてもhugo内のfugaは生存している
}//ここを抜けるとhugoも消滅し、fugaの参照カウンタは0になり、ドロップされる
このように、Rcを使う事で、Borrow checkerを気にすることなく、データの共有が可能になります。
ArcとRcの違い
並列処理や非同期処理で使う場合はArcでなければならない、シングルスレッドで使う場合はRcでもおけまる、と覚えておけば間違いありません。
なお、ArcはRcに比べて遅いといわれています。しかし、私が実際に試してみる限りでは速度差は感じられず、後述しますが、今回の調査の方法ではArcの方が速いまでありました。
普通に値のclone()ではダメなのか?
Arc/Rcを使う場合の目的は、普通の借用だとBorrow chekerに追跡が厳しいから使う、というケースが多いと思います。
ただし、Borrow chekerを避けるだけであれば、借用ではなく値のcloneを持たせてしまうという手段があります。むしろprimitiveな型の場合はそうするのが自然です。
しかし、VecやStringなどのデータ量が多くなることが予測される場合、毎回cloneしていてはメモリコピーの負荷が高くなり、Arc/Rcの方が速度面で有利なのではなかろうか?と思うのですが、Arc/Rcはそれなりに負荷が高いようで、逆に重くなるのでは?という懸念もあります。
という事で、前置きが長くなりましたが、今回はこの辺りが実際にどうなのか?というのを検証していってみたいと思います。
実際に試してみる
以下の簡単なコードで試してみることにしました。
#[test]
fn test_arc() {
let a = Arc::new("hoge".to_string());
let mut b=vec![];
for _ in 0..10000000{
b.push(Arc::clone(&a));
}
}
#[test]
fn test_rc() {
let a = Rc::new("hoge".to_string());
let mut b=vec![];
for _ in 0..10000000{
b.push(Rc::clone(&a));
}
}
#[test]
fn test_str() {
let a = "hoge".to_string();
let mut b=vec![];
for _ in 0..10000000{
b.push(a.clone());
}
}
#[test]
fn test_str2() {
let mut b=vec![];
for _ in 0..10000000{
b.push("hoge".to_string());
}
}
test実行でfinishedタイムを見るだけいうという雑な測り方ですが、下記のような結果になりました。
関数 | finished time |
---|---|
test_arc | 0.21s |
test_rc | 0.24s |
test_str | 0.70s |
test_str2 | 0.95s |
Arcの方がRcより速いです。これはちょっと想定外でした。
おそらく実行環境のCPUやメモリ速度によって変わるのではないかなと思います。
Arc/RcのClone(=参照カウンタのインクリメント)と、Stringを都度生成する場合の速度差は見ての通り、まぁまぁの差がありました。
ついでに、test_strとtest_str2の差ですが、
これはString::clone()と&str::to_string()の差という事で、どうやら&strからto_stringするよりも、Stringを単純に複製する方が速いという結果になりました。to_stringの方はメモリコピー以外の何らかの処理が入っているという事だと思います。
まとめ
この実験結果により、(少なくとも私の実行環境では)容量の大きい値は複製(メモリコピー)よりもArc/Rcの方が高速である、と判断してよいかと思います。
当然ながら複数のデータが同一の文字列を内包するという状況でなければ意味はないですが、例えばHTMLやXMLのような構造化されたテキストデータをパースするような処理であれば同一文字列を値として持ちまわるケースも出てくるかもしれません。
ただし、見ての通り、速度差としては1回あたりの処理で比べると僅差でしかありません。ループの回数を多くしているので大きな差があるようにも見えますが、複製を配列に入れるだけなどというコードは実際には存在せず、他の処理にもっと時間がかかるはずですので、全体から見ると極めて些細なものではあると思います。
コードのメンテナンス性とのトレードオフとしては悩ましい程度の差ではありますが、少しでも高速化したい場合の対策としては取り入れてもよいかな、と思います。
Discussion
ベンチマークはリリースビルドで行うべきでしょう。「Rustのベンチマークでこれが遅い」という記事は時々見かけますが、そのほとんどでデバッグビルドを計測していました。
安定化されていないのでnightlyでしか使えないのですが、
cargo bench
でそれぞれを計測したところ、という結果になりました。
cargo bench
はデフォルトでリリースビルドを計測するようになっていますが、cargo bench --profile=dev
で実行すると、という結果になります。これは記事の傾向と近いですね
コメントありがとうございます。
最適化によって結構差がありますね。
貴重な検証結果を投稿いただきありがとうございます。参考になります。