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)にすることで、改善しようとするのは危ういというのは言えるかと思います。

パーサコンビネータとPEGの違いについて

ちょっとTwitterの某所で議論を見かけたので、この辺の用語についてまとめておきたい気分です。

まず、パーサコンビネータ(Parser Combinator)というのは、パーサをオブジェクトないし関数ととらえて、パーサを組み合わせて複雑なパーザを組み合わせる技法の総称ってのが私の認識です。最もなナイーヴなパーサコンビネータを作ると、自然にPEG的な挙動になりますが、GLL Combinators なんてのもありますし、HaskellのParsecにしても、try使わないとPEG的な動作をするわけではないので、実用的にも理論的(?)にも、パーサコンビネータかPEGかは独立です。

次に、PEGが何かというと、「文法の表記法」と捉えられることが多いものの、これは一面でしかなくて、Parsing Expression Language(PEL)であるような言語のための形式文法と捉える方がシンプルかなと思います。BNFと違うのは、文脈自由文法という概念と、BNFという具体的な表記法(追記:この言い方は、厳密ではないです。正確には、文脈自由言語を表現可能な具体的な表記法と言うべきでしょうか)が別にあるのに対して、PEGは表記法でありそれ自体でも形式文法である(追記:PEGという名称が、形式文法としても、形式文法の表記法の意味でも用いられることがある、程度の意味です)、という点でしょうか。

ちなみに、BNFとPEGの違を端的に表す例としては、よくあるものだと、

a / ab

の受理言語は{a}になる(後の選択肢は試されない)なんてのがあります。BNFにおける a | ab だと、受理言語が {a, ab} になるのが、違う点です。

メモ書き程度の話で、あんまり当該文脈見てない人にわかりやすいように書いてないですが、参考になれば幸いです。

ついでに、その議論においてPrologが出てきましたが、Prologを使えば色々なパーザ書けるよってのは、自明なことであり、改めて論じるまでもないことな気がします(というのは、Prologプログラミング言語であって、計算能力はチューリング完全なので。もちろん、Definite Clause Grammarのような形で「より簡単に書ける」は真かもしれませんが)。

ウォーキング習慣さらに強化中

 最近、ほとんど毎日(例外は、雨の日と、朝早めに予定がある時くらい)、1時間約6km程度のウォーキングを実践しています。2月になってからでいうと、18日中15日はウォーキングしてるので、週5日以上歩いてる感じですね。

 1月よりさらにウォーキングの継続度合いが上がったわけですが(ちなみに、寒い時はウォーキング前にお風呂、寒くなくてもウォーキング後にお風呂は必ず入ってます)、主観的にはかなり色々な効用があるなと感じています。ざっと列挙するとこんな感じでしょうか。

生活が自然に朝型になる

 以前、朝型生活を意識しようとしてなかなか出来ませんでしたが、ほとんど毎日のようにウォーキングしていたら、自然と朝型生活になっていました。1月は、午前3時くらいまで起きていたい気分になる事が多かったのですが、今は、24時になると「あ、そろそろ寝る準備しないとなー」と自然と思考が切り替わる感じです。朝型生活を意識しようとしても出来ない人は(というのがまさに自分だったのですが)、歩く習慣から初めてみるといいのかもしれません。とはいえ、これが何ヶ月前からの蓄積か不明なので、すぐ成果が出るとは限らないですけど。

気分の変動幅が減る

 1月は家庭の事情が色々あり、あと、2月上旬もちょっと色々あったのですが、ここ1週間くらいは、割と日中も夜も含め、気分が穏やかで過ごせる日が明らかに増えました(というか、それ以前がそうでなかったので、冬季うつに近い状態だったのかも)。まあ、寝られても熟睡感が薄い日とかは時々あるんですが、そういうときでも「朝起きたら歩く」を実践してると、歩いた後には、割とへっちゃらになってたりします(もちろん、本当に睡眠不足の日は、結局、夜に疲労が押し寄せて来ますが)。

仕事やその他の活動のパフォーマンスが上がる(超主観的)

 1時間ウォーキングに費やすのは、クールダウンやお風呂タイムを含めると、1時間30くらいはそれにかけてる計算になりますけど、トータルで見ると日中の集中力はどう考えても上がってるし、「だるいから、この仕事、明日に回そう」と考えることが減ってて、トータルで見ると一日でこなせる仕事量は明らかに増えてます。

SNSをあんまり見なくなった

 これは気分良く過ごせる日が増えたのと関係してるのかもしれませんが、必要な情報を探す時はともかくとして、あんまりツイッター見てもしゃあないなあという気分に最近はなってて、それによって、ツイッターで変に暗い気分にならないという好循環が生まれてる感じです。だんだん、ツイッターに費やす時間は減っていると思うのですが、一方で「仲良く交流するツール」というツイッターの原初に立ち返った使い方が出来るようになったように感じています。

 というわけで、ウォーキングをひたすら繰り返している内に起きた変化について、ざっと書いてみました。1時間ってのは、人によってはやりすぎかもですが、(特に冬場は)歩いて悪いことはないと思うので、歩けてないなーって人は少しずつ歩いていくといい気がします。「運動しなきゃ……でも、運動出来てないな」って人の参考になればと思います。

 冬場は寒いので、屋外での運動はしづらいと思うのですが、朝方に氷点下行くような地域はともかくとして、そうでなければ、ウォーキング前にお風呂に入る、ご飯食べる、などなどして、身体の暖機運転を開始してから始めると、スムーズにウォーキング出来るってのが個人的な実感です。

最近のウォーキング

 去年の春ごろに、

kmizu.hatenablog.com

 なんてエントリを書いたりしましたが、それから約半年程度経ってどうなったかというと……とりあえず、習慣として歩くのが定着するようになりました。

 さすがに、毎日必ずウォーキングをする(例外は認めない)の部分は無理がありましたが、最近の実績で言えば、少ない時でも週に1回、多い時は週に4回程度は程度は歩くようになった感じです。

 特に冬場になってからというもの、日射量が減っているということもあるので、天気のいい日は出来るだけ歩くようにしています。やっぱり人間も動物というか、きちんと日の光を浴びて運動しないと不健康になるな、というのを最近実感しています。

ジョグ&ウォーク記録(2020/10/21)

今日は、目標として - いつもと全く違うコースを走る - ジョギングのみ(歩かない)

というのを掲げて走ってみましたが、気がついたらあっちこっち走ってて、10kmいってました。後半は完全にランナーズハイの勢いで走ってました。明日はさすがに足を休めようかなと思います。

ちょっと無茶だったと思うのですが(まだまだ運動不足なので)、おかげで、ジョギング時の姿勢や走法、呼吸の重要さを思い出した気がします。あと、運動を終えたあとの充実感もいつもと段違いですね(ランナーズハイの影響かも)。