futures-rsのjoin_allのパフォーマンス変遷
はじめに
Rustには非同期処理を扱うためのutilityとして、 futures-rs というライブラリがあります。
ある時社内で、このライブラリが提供しているjoin_allやtry_join_allに関する下記issueが話題に上がりました。
issueはtokio-rsに上げられていますが、実質的にはfutures-rsが提供している関数の内容になります。
このjoin_allやtry_join_allは実際に何箇所かで使用していたので、このissueに関して調べてみました。
※注)
このissueは少し前のもので、後述しますが最新版のfutures-rsにはこの課題を緩和するようなPRがすでに取り込まれて、v0.3.17でリリースされています。
join_allの実行モデル (v0.3.16以前)
join_allの復習になりますが、こいつは複数の Future を並行して実行し、すべての Future が完了するのを待つ関数です。イメージ的にはJavaScriptのPromise.all()に近しいと思います。
use futures::future::join_all;
async fn foo(i: u32) -> u32 { i }
let futures = vec![foo(1), foo(2), foo(3)];
let result = join_all(futures).await;
assert_eq!(result, [1, 2, 3]); // executed **only after** join_all completes
さて、ライブラリがこの挙動をどう実現しているか、実装もとてもシンプルで読みやすいので実際にコードを追ってみます。(version的には v0.3.16 で、後述する改善PRが入る前の最新版です)
join_allのエントリ
上記がjoin_allのエントリですが、最終的にはJoinAllというEnumを返しています。結論このJoinAllがFutureを実装しているので、こいつのpollがどういう実装になっているか見てあげれば良さそうです。
JoinAllのFuture実装
pollの実装を見ると、join_all()に渡したcollectionの1つ1つの要素をイテレーションして、それぞれのpollを実行しているのが分かります。最終的に、collectionに含まれる全てのFutureがReadyになった時はじめて、JoinAll自身もReadyを返して処理が終了します。
この実装によって、join_allには引数に渡すcollectionの要素数が大きくなった際に、下記のような課題感があったようです。[1]
-
ExecutorからJoinAllのpollが呼ばれた際に、毎回全ての要素のpollが呼ばれてしまう。 - (さらにtokioと組み合わせた場合、) cooperative task yieldingにより、
JoinAllの1度のpollでReadyにできるFutureの数が制限され、collectionの全てのFutureをReadyにするのに余計に時間がかかる
FuturesOrderedを使った改善 (v0.3.17以降)
上記のような課題感から、join_allには下記のようなPRが投げられました。(try_join_allも同様)
この変更により、join_allに渡されたcollectionの要素数が30より大きい場合、FuturesOrderedという非同期タスクキューのようなデータ構造を使うように変更されました。 [2]
FuturesOrderedは、キューに入れられたFutureを先頭から順番にpoll()していき、完了していればReadyを返すような挙動をします。以前の実装と比較すると、この実装はひとたびキューに入れられた要素がReadyになると、その要素は再びpollされることはないので、要素数が多い場合こっちの実装の方が遥かに効率的です。
0.3.17以降は、この修正が入ったjoin_allが提供されています。
まとめ
futures-rsクレートのjoin_allのちょっとした変遷を紹介しました。
最新のバージョンを使っていたり、少ない数のFutureを扱っているだけだったら大して問題にならないとは思いますが、かなり大きなオーダーのFutureをjoin_all等で待つみたいな処理を書いている場合は知っておいて損はないかなと思います。
-
FuturesOrderedとは別で、順序を保証しないFuturesUnorderedというデータ構造もあります。join_allの実装ではこっちのFuturesUnorderedでも良いのでは？と思ったのですが、FuturesOrderedではないといけない理由があるのかもしれないです。(詳しい方がいたら教えてください！) ↩︎
Discussion