Rustのイテレータ操作が一つのループになる様子を見る

背景

こういう記事があった

BiomeがforEachではなくfor...ofを推す理由を処理速度の観点から見る

（ここではforEachの是非は一旦おいておくとして）

配列に対してmapやfilterといった操作をメソッドチェーンで呼び出すと、呼び出しのたびに毎回配列を読むことになるので、for...ofを使って一重のみのループで処理したほうが速いことがある

下のmethodchain.tsみたいにやるよりも（チェーンがいくつも連なるのであれば）for-of.tsみたいに書いたほうが効率的では？という話

code:methodchain.ts

// xs: 0, 1, 2, 3, 4

const ys = xs

.map(x => x * 3)

.filter(x => x % 2 === 0);

// ys: 0, 6, 12

code:for-of.ts

// xs: 0, 1, 2, 3, 4

let ys: number[] = [];

for (const x of xs) {

if (triple % 2 === 0) {

ys.push(x * 3);

}

// ys: 0, 6, 12

動作を可視化してみる（TypeScript）

メソッドチェーン

mapが呼び出され、filterが呼び出される

code:methodchain.ts

const xs = ...Array(10).map((_, i) => i);

const ys = xs.map((i) => {

let triple = i * 3;

console.log(map: ${i} -> ${triple});

return triple;

})

.filter((i) => {

let predicate = i % 2 === 0;

console.log(filter: ${i} -> ${predicate});

return predicate;

});

console.log(ys);

code:result

map: 0 -> 0

map: 1 -> 3

map: 2 -> 6

map: 3 -> 9

map: 4 -> 12

map: 5 -> 15

map: 6 -> 18

map: 7 -> 21

map: 8 -> 24

map: 9 -> 27

filter: 0 -> true

filter: 3 -> false

filter: 6 -> true

filter: 9 -> false

filter: 12 -> true

filter: 15 -> false

filter: 18 -> true

filter: 21 -> false

filter: 24 -> true

filter: 27 -> false

0, 6, 12, 18, 24

for-of

mapとfilter（にあたる動作）が要素ごとに呼び出される

code:for-of.ts

const xs = ...Array(10).map((_, i) => i);

let ys: number[] = [];

for (const i of xs) {

let triple = i * 3;

console.log(map: ${i} -> ${triple});

if (triple % 2 === 0) {

console.log(filter: ${triple} -> true);

ys.push(triple);

} else {

console.log(filter: ${triple} -> false);

}

console.log(ys);

code:result

map: 0 -> 0

filter: 0 -> true

map: 1 -> 3

filter: 3 -> false

map: 2 -> 6

filter: 6 -> true

map: 3 -> 9

filter: 9 -> false

map: 4 -> 12

filter: 12 -> true

map: 5 -> 15

filter: 15 -> false

map: 6 -> 18

filter: 18 -> true

map: 7 -> 21

filter: 21 -> false

map: 8 -> 24

filter: 24 -> true

map: 9 -> 27

filter: 27 -> false

0, 6, 12, 18, 24

じゃあRustでメソッドチェーンを書いたらどうなるか

methodchain.tsと同じように書いて、printlnが呼び出される順番を見てみる

code:methodchain.rs

fn main() {

let v = (0..10).collect::<Vec<i32>>();

let s: Vec<i32> = v

.iter()

.map(|x| {

let triple = x * 3;

println!("map: {} -> {}", x, triple);

triple

})

.filter(|x| {

let is_even = x % 2 == 0;

println!("filter: {} -> {}", x, is_even);

is_even

})

.collect();

println!("s: {:?}", s);

}

code:result

map: 0 -> 0

filter: 0 -> true

map: 1 -> 3

filter: 3 -> false

map: 2 -> 6

filter: 6 -> true

map: 3 -> 9

filter: 9 -> false

map: 4 -> 12

filter: 12 -> true

map: 5 -> 15

filter: 15 -> false

map: 6 -> 18

filter: 18 -> true

map: 7 -> 21

filter: 21 -> false

map: 8 -> 24

filter: 24 -> true

map: 9 -> 27

filter: 27 -> false

s: 0, 6, 12, 18, 24

for-of.tsと同じ呼び出され方をしている

なぜこうなるのか

そもそもRustのiteratorは、最終的に一つのループを組み立てる記法である

直感的には複数のループを書いていても一つのループに変換される

ただ、一旦複数のループを作りそれをまとめるような最適化を行っているわけではない

最適化云々のレベルではなく記法・言語機能レベルの話

このような変換は、リストを多用する関数型言語では重要な最適化であるためそれなりに研究されているらしい

e.g. Haskellのfusion

参考

Rust's iterators optimize nicely—and contain a footgun | nicole@web

@blackenedgold: Rustが流行り出した初期の頃はこの話よくみたけど、最近これ系の記事あんまみないね。Rustのイテレータは最終的に1つのループになるよって話。

Rust's iterators optimize nicely—and contain a footgun | nicole@web

https://t.co/D9yUV5QuHW

@blackenedgold: このエントリでの話の掴みにされてるHaskellのfusionだけど、リストを多用する関数型言語では重要な最適化だからよく研究されているよ。特にHaskellだとlazyでpureだから色々やりやすい。

@blackenedgold: mapしてfilterをfilter_mapに書き換えるのはHaskellじゃないとダメかなと思ったけどstrictな戦略でもmapで_|_になるならfilter_mapでも_|_になるから別に変わらないか。

@blackenedgold: 最初読んでたときは気にならなかったけど改めて読むとloop fusionでこうなってるみたいな書き方が引っかかるな。そもそもiteratorは1つのループを書くための記法で一旦複数ループを作って最適化でまとめてる訳ではないよ。

@a4lg: @blackenedgold 一応お聞きすると、初期見たというお話はどちらでしょう？両方というのも十分あり得そうですが、その場合でも卵と鶏としての関係が気になりましたので……。

1. ループが1つになること

2. 直観的にはループが2つになりうること

@blackenedgold: @a4lg 両方ですね。一見複数のループを書いているようで一つのループを組み立てる記法だよという説明がよくある解説だと思います