kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

メモリ使用量の削減のために遅延リストを使うのは(多くの場合)アンチパターン

 こんばんは。ちょっと久しぶりにScalaの記事を書いてみようと思い立って、こうやって記事を書くことにしました。

 といっても、タイトルがほとんど全てを表しているのですけど。

 最近のプログラミング言語のいくつかは、俗に遅延リストと称される機能を持っています。HaskellListがデフォルトで非正格(というか、評価が非正格なので、Listもそうなる)のは有名ですし、Clojureにも標準で遅延シーケンスがあります。そして、今回ネタにするScalaも、遅延リスト相当の型が標準ライブラリで提供されています(Scala 2.12ではStream、2.13からはLazyListに改名)。以下では、Scala 2.13の場合に、LazyListをメモリ節約のために使って、ハマる例を紹介します(実際のプロダクションコードで見たのを元に、minimalにしたものです)。

def doHeavyJob(queue: JobQueue): JobResult = {
  val jobs: LazyList[Job] = queue.dequeueAllJobs()// JobQueueからLazyListとしてJobのシーケンスを取得
  val results: LazyList[JobResult] = jobs.map(doJob) //  各々のJobに対してdoJobを実行 
  results.foldLeft(emptyJob)(composeJobs) // JobResultのシーケンスから、結果を計算
}

 ここで、引数queue 自体が保持している(かもしれない)LazyListについては一端考えないことにします。さて、ここで、コードの作成者がわざわざJobのシーケンスをLazyListで表現したのには訳があって、一言でいうと、LazyListで保持することによって、jobs.size に比例する量のメモリを使用しないで良いと考えたようです。

 この誤解は遅延リストの初心者にしばしば見られるものなのですが、一言で言うと大抵の場合それはアンチパターンなので止めよう、ということです。この場合ですと、もちろん、doHeavyJobの呼び出しが終われば、LazyListのために利用したメモリはGC対象になるのですが、foldLeft内でLazyListの中身が評価されると、jobsのサイズに比例した量のメモリが必要になります。jobs.sizeの値が小さければ(あるいはjobsの保持する個々のJobのサイズが小さければ)問題ないのですが、そうでない場合、コード作成者の目論見は大外れに終わり、場合によっては予期しないOutOfMemoryErrorに遭遇する羽目になります。

 そして、このような場合、同じ遅延リストは二度以上再利用されないので、以下のようにIteratorを用いたコードに書き直す事ができます。

def doHeavyJob(queue: JobList): JobResult = {
  val jobs: Iterator[Job] = queue.dequeueAllJobs.iterator // JobQueueからLazyListとしてJobのシーケンスを取得
  val results: Iterator[JobResult] = jobs.map(doJob) //  各々のJobに対してdoJobを実行 
  results.foldLeft(emptyJob)(composeJobs) // JobResultのシーケンスから、結果を計算
}

 こうしてあげれば、doHeavyJobの実行途中でも、jobsのサイズに比例した量のメモリは必要になりません(というのは、Iteratorだと一度しかたどられないので、foldLeftでも一定のメモリしか必要としないわけです)。

 もちろん、すべての場合に遅延リストを使うべきでない、とまでは言えませんが、メモリ使用量が多そうな処理を遅延リスト(ScalaだとLazyList)にすることで、改善しようとするのは危ういというのは言えるかと思います。