思ったより(知ってるけど)知らないRustのイテレータと高階関数
こんにちは
こんにちはsaffronteaです。
FAST株式会社にてRustを使用してアプリケーション、APIなどのバックエンドの作成を行っています。
私はRustをかれこれ6~7年くらい使ってきていましたが、正直Iteratorをうまく扱えているとは言い難いなと思いつつ触っていました。
業務でRustコードを書くにあたって、より効率的で読みやすいコードを作っていくためには、
Iteratorをうまく使えるようになりたいなぁと感じたのでちゃんと調べてみることにしました。
まずはIteratorとはを振り返ろう
中を探っていく前に、まずイテレータについての基本概念を振り返ってみましょう。
Iteratorトレイトのdocs.rsには以下のように記載されています。
An iterator has a method, next, which when called, returns an Option<Item>. Calling next will return Some(Item) as long as there are elements, and once they’ve all been exhausted, will return None to indicate that iteration is finished. Individual iterators may choose to resume iteration, and so calling next again may or may not eventually start returning Some(Item) again at some point (for example, see TryIter).
すなわち、Iteratorとはnext()を持ちそれぞれの要素に同じItemの型を持つsize>=0の集合を指していることがわかります。
ここで重要なのはIteratorは0の長さもありうるということです。
以下のようなコードを試してみましょう。
fn main() {
let a : &[u8] = &[];
let mut a_iter = a.iter();
println!("{:?}",a_iter.size_hint());
println!("{:?}",a_iter.next());
}
出力は以下のようになるはずです。
(0, Some(0))
None
size_hint()はiterが持っているはずの長さを(usize,Option<usize>)で返してくれます。
(注:関数名が指すようにhintであり、unsafeでの境界チェックなどに使うと壊れる可能性があります)
今回の変数aは[]を示しているので、aの参照先スライスのイテレータであるa_iterのsizeは0になります。
そして次の要素がないイテレータはnext()でNoneを返すので、size=0のイテレータでnext()をするとNoneが返ってきます。このとき、a_iterは値を消費しているので、mutableにする必要があります。
ではコードを少し変えて、このようにするとどうなるでしょうか。
fn main() {
let a : &[u8] = &[1,2];
let mut a_iter = a.iter();
println!("{:?}",a_iter.size_hint());
println!("{:?}",a_iter.next());
println!("{:?}",a_iter.next());
println!("{:?}",a_iter.next());
}
出力は以下のようになるはずです。
(2, Some(2))
Some(1)
Some(2)
None
1個ずつ値が出てきてIteratorが消費されているのがわかりますね！
これによって、IteratorにできるものはnextがSomeを返す限り処理をすることで、指している先のリストが0であろうとなかろうと関係なくループを作ることができることがわかります。
高階関数と遅延評価の強さ
Rustはマルチパラダイム言語であり、完全では無いものの関数型言語のエッセンスが含まれています。
特に、Iteratorの仕組みには関数型の考えが多く使われています。
mapやfilterのような関数は他言語でも見られるので、馴染みのある方も多いと思いますが、これらは高階関数と呼ばれる関数群になります。
高階関数の定義は関数を受け取り、関数を返す関数です。イテレータであれば、Iteratorに対して関数を適用し、impl Iteratorを返す関数と言えます。
そして、これらの関数は終端操作がされるまで評価されません。これが遅延評価という概念になります。
RustはrustcがRustコードからLLVM IRに変換し、llvmがネイティブコードに変換するというフローでコンパイルされます。
これらの高階関数を用いた処理はRustコードからLLVM IRになるまでの間にmapやfilterなどの関数での関数は適切に合成され、
可能な限り少ないループ、もしくはループの展開という形でネイティブコードにコンパイルされることで最適化が行われます。
実際に見てみよう
ここまでは概念的な説明でしたが、これは何を意味しているかというと以下の利点があります:
- コンパイラにコードの意図を伝えることができる
- 人間が読むときに、ロジックとして明確である
- ループ内の副作用や状態変化を把握しやすくなる
簡単なforなどでは共に同じ最適化が働くのでほぼ差は現れませんが、
人間が(あまり考えず)手書きしたforループとコンパイラがコンテキストを把握できるmap->foldではmap->foldの方がうまく最適化できる可能性が上がります。
これを実例で説明します。
以下のような2つのコードがあるとします。
//for loop
for i in 1..10000{
if i%2 == 0 {
println!("{}",i);
}
}
// HOF pattern
(1..10000).filter(|i|i%2==0).for_each(|i|println!("{}",i))
これはreleaseビルドのx86_64のASMにすると以下のようになります。一部関係ない起動処理や関数は省略しています。
FORループ:
.LBB4_3:
incl %ebp
cmpl $10000, %ebp
je .LBB4_4
.LBB4_1:
movl %ebp, 4(%rsp)
testb $1, %bpl
jne .LBB4_3
leaq 4(%rsp), %rax
movq %rax, 8(%rsp)
movq %r15, 16(%rsp)
movq %r12, 24(%rsp)
movq $2, 32(%rsp)
movq $0, 56(%rsp)
movq %r13, 40(%rsp)
movq $1, 48(%rsp)
movq %rbx, %rdi
callq *%r14
jmp .LBB4_3
.LBB4_4:
addq $72, %rsp
popq %rbx
popq %r12
popq %r13
popq %r14
popq %r15
popq %rbp
retq
main:
pushq %rax
movq %rsi, %rcx
movslq %edi, %rdx
leaq playground::main(%rip), %rax
movq %rax, (%rsp)
leaq .Lanon.c1bf9e48a8946649a7f2975172157fc1.0(%rip), %rsi
movq %rsp, %rdi
xorl %r8d, %r8d
callq *std::rt::lang_start_internal@GOTPCREL(%rip)
popq %rcx
retq
イテレータパターン
.LBB4_3:
incl %ebp
cmpl $10000, %ebp
je .LBB4_4
.LBB4_1:
testb $1, %bpl
jne .LBB4_3
movl %ebp, 4(%rsp)
leaq 4(%rsp), %rax
movq %rax, 8(%rsp)
movq %r15, 16(%rsp)
movq %r12, 24(%rsp)
movq $2, 32(%rsp)
movq $0, 56(%rsp)
movq %r13, 40(%rsp)
movq $1, 48(%rsp)
movq %rbx, %rdi
callq *%r14
jmp .LBB4_3
.LBB4_4:
addq $72, %rsp
popq %rbx
popq %r12
popq %r13
popq %r14
popq %r15
popq %rbp
retq
main:
pushq %rax
movq %rsi, %rcx
movslq %edi, %rdx
leaq playground::main(%rip), %rax
movq %rax, (%rsp)
leaq .Lanon.c1bf9e48a8946649a7f2975172157fc1.0(%rip), %rsi
movq %rsp, %rdi
xorl %r8d, %r8d
callq *std::rt::lang_start_internal@GOTPCREL(%rip)
popq %rcx
retq
RustとLLVM IRによる適切な最適化が働いているので、目grepしても違いがわからないくらい同じですが1つ大きな違いを見つけることができます。
それが以下の部分です。
.LBB4_1:
movl %ebp, 4(%rsp)
testb $1, %bpl
jne .LBB4_3
leaq 4(%rsp), %rax
.LBB4_1:
testb $1, %bpl
jne .LBB4_3
movl %ebp, 4(%rsp)
leaq 4(%rsp), %rax
movq %rax, 8(%rsp)
movlは32bit=4byteの値をコピーする命令です。forでの記述ではtestbによる最下位bitの評価(=偶数判定)の前にmovlが発生することがわかります。
今回の命令の差によって発生する差は基本的には極小ですが、以上の例が示すようにイテレータパターンの方が最終的にどうロジックを扱うかをコンパイラが判定しやすくなり、
より複雑なループでもコンパイラが機械語のロジックを最適化する機会を与えることができます。
この差はforループだと変数iが発生するため、ライフタイムがループの終わりまであること、RustにおけるIteratorが遅延評価であることに起因します。
ここでは、for_eachという関数がIteratorの消費を行うことで実際の評価が発生します。それ以外には例えばcollectやfoldがこのような消費を行う関数にあたります。
先程のコード例を見て、もしかするとmapでprintlnすれば良いのでは？と思われた方もいるかもしれません。
これは実はうまくいきません。なぜならばmapだけではイテレータが実際に消費されないため、関数が評価されないのです。
実際に以下のような警告が出て、プログラムを実行しても何も表示されません。
warning: unused `Map` that must be used
--> src/main.rs:4:1
|
4 | (1..10000).filter(|i|i%2==0).map(|o|println!("{}",o));
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
= note: iterators are lazy and do nothing unless consumed
= note: `#[warn(unused_must_use)]` on by default
この遅延評価によって、コンパイル時にコンパイラが適切に関数を合成し意図をつかみながらプログラムを生成することができるのです。
先程のコードを思い出してみましょう。
(1..10000).filter(|i|i%2==0).for_each(|i|println!("{}",i))
このコードは、filterがi%2==0でないものは不要だということがコードとして明確であり、LLVMまでその意図が伝わっているのです。
そしてまた、人間も長大で複雑なforループを読む作業をせずとも、filterを見れば条件がわかり、mapを見れば処理がわかるという形にすることができるのです。
これが先程示した利点の以下の部分にあたります。
- コンパイラにコードの意図を伝えることができる
- 人間が読むときに、ロジックとして明確である
言語的にバグを減らす書き方を見てみよう
多くの方のRustを使い始めたり、興味を持った理由の一つがバグが少なくなるという謳い文句だと思います。
これはborrow-checkerによる所有権のコンパイル時チェックが大きな割合を占めていますが、
イテレータを高階関数で処理することでよりその恩恵を受けやすくなります。
以下のような例を考えてみましょう。
let mut v = vec![1, 2, 3];
for &x in v.iter() {
if x == 2 {
v.push(4); // エラー
}
}
このコードはエラーになってしまいます。iter()はmutableなイテレータではないからです。
では、これをiter_mut() にすれば良いかというと、同様にエラーになります。iter_mut() は全体を可変借用して要素への &mut を生成するため、
ループ内で v.push(...) しようとすると同じ理由で借用競合になります。
let mut v = vec![1, 2, 3];
for x in v.iter_mut() {
if *x == 2 {
v.push(4); // コンパイルエラー: cannot borrow `v` as mutable because it is also borrowed as mutable
}
}
これだけだとエラーがちょっと不思議な感じがしますが、高階関数のパターンで考えると当然に見えるようになります。
let mut vec= vec![1,2,3];
let v = vec.iter_mut().enumerate().for_each(|(i,v)|{
if *v == 2 {
vec.insert(i,4);
}
});
このコードを見たら問題がわかりやすくなります。
for_eachの実行中にVecが変更されてしまうと、イテレータの動作を言語として保証できません。
これが先程の3番の実例になります。
- ループ内の副作用や状態変化を把握しやすくなる
このコードは実際には以下のようなパターンで実装することができます。
- それぞれで新しいVecを生成して、flat化する
let v = vec![1,2,3];
let v = v.into_iter()
.flat_map(|x| if x == 2 { vec![x, 4] } else { vec![x] })
.collect();
-
clone()してコピーを参照する
let mut v = vec![1, 2, 3];
for x in v.clone() {
if x == 2 {
v.push(4);
}
}
- indexループを回す
let mut v = vec![1, 2, 3];
let mut i = 0;
while i < v.len() {
if v[i] == 2 {
v.push(4);
i += 1;
}
この3つのパターンにはいくつか違いがあります。
一つは1つ目のパターンはmutな変数が現れないという点です。
これによって変更を加えたい部分でしか変更が許可されないので、不意にVecを変えてしまってバグを引き起こす可能性をコードレベルで減らすことができます。2つめのパターンではmutableなvが最後に残るので、のちに不意にVecを操作してしまう可能性を残してしまいます。
もう一つは、Vecのコピーが発生するかどうかの点です。
一番下のパターンは同じVecに対してpushが走っているので、Vecそのもののコピーが発生しません。
理論的にはパフォーマンスはこのパターンが最も優れていますが、このようなパターンは境界チェックなどを正しく行う必要があり、注意が必要です。
全体の件数がどれくらいなのかによりますが、極限的にパフォーマンスを要求されたりunsafeな操作が必要でない限り避けた方が良いと思います。(このような書き方はほぼCと変わらないので、Cと同じパターンのバグを生み出す可能性があります)
まとめ
今回はIteratorとそれに関連する高階関数の概念についてかなり深いところを探ってみました。
実際にパフォーマンスチューニングをしてforを考えて書くのはかなり時間がかかり思考コストの高い作業になるので、高階関数とイテレータを組み合わせることで、チューニングをある程度コンパイラに任せるのがバランスの取れた選択だと感じました。
ファストは「ものづくりに誠実であれ。誇れる事業で天下を獲る、全員で。」を経営理念に掲げ、世界からできない理由をなくすためにサービスを展開する会社です。テックブログでは、ソフトウェアや技術にまつわる情報をお届けします。
Discussion