• BPnet
  • ビジネス
  • IT
  • テクノロジー
  • 医療
  • 建設・不動産
  • TRENDY
  • WOMAN
  • ショッピング
  • 転職
  • ナショジオ
  • 日経電子版
  • PR

  • PR

  • PR

  • PR

  • PR

本物のプログラマはHaskellを使う

第47回 領域漏れがあるプログラムを改良する

2011/06/01 ITpro

 前回は,GHCのヒープ・プロファイラを使って領域漏れが発生している個所を探す方法を紹介しました。もっとも,領域漏れの発生している個所を探すだけでは意味はありません。今回は,領域漏れの問題をどう解決するかを説明します。

関数内の値を正格評価する

 前回は,GHCのヒープ・プロファイラを使って,以下のプログラムに存在する領域漏れの問題を探りました。

main = print $ sum [0..1000000]

 ヒープ・プロファイラの結果から,領域漏れを起こしているデータはInteger型や「<base:Data.List.sat_s39p>」というクロージャで行われているリスト処理,そして遅延評価によって作成されるサンクから発生する,一度も使われないBLACKHOLEであることがわかりました。また,こうしたデータの領域漏れの原因が,main関数が呼び出しているsum関数,およびsum関数が呼び出しているfoldl関数にあることを突き止めました。

 では,sum関数やfoldl関数によって生じる領域漏れの問題を解決するにはどうすればよいでしょうか?

 領域漏れの原因は,遅延評価のために用意されたサンクです。したがって,遅延評価を特に必要としないプログラムでは,第9回で説明したseq関数や$!演算子,バン!パターンなどを使って,値を正格評価(先行評価)するようプログラムを書き換えれば問題を解決できます。

-- | A strict version of 'foldl'.
foldl'           :: (a -> b -> a) -> a -> [b] -> a
foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

{-# LANGUAGE BangPatterns #-}
foldl' f a []     = a
foldl' f a (x:xs) = let !a' = f a x in foldl' f a' xs

 正格評価版のfoldl関数であるfoldl'をこのように定義し,foldl'を使うようにsum関数を書き換えます。実際にはfoldl'はData.Listモジュールで提供されているので,インポートして利用できます。

import Data.List (foldl')
main = print $ sum' [0..1000000]

sum' :: (Num a) => [a] -> a
sum' = foldl' (+) 0

$ ghc  Lazy2.hs -fforce-recomp -O2
[1 of 1] Compiling Main             ( Lazy2.hs, Lazy2.o )
Linking Lazy2 ...

$ ./Lazy2
500000500000

 前回は,「-K100M」というオプションを指定することで,スタックに使用するメモリーを100Mバイトに拡張してプログラムを実行していました。正格評価に書き換えたプログラムでは,-K100Mオプションを指定しなくても,スタックがあふれることなくプログラムを実行できているのがわかります。

 なお,第8回第9回で説明したように,seq関数や$!演算子,バン!パターンでは,値はWHNFまでしか簡約されません。例えば,リストなどのデータ構造やデータ構造内の要素がすべて評価されるわけではありません。リストに対して正格評価を行っても,先頭の要素が評価されるだけで,残りの部分は遅延評価によって保留されてしまいます。

 このように,リストなどのデータ構造に対する正格評価では,遅延評価による評価の保留状態は解消しないため,領域漏れの問題を解決できません。第35回で説明したData.MapのMap型のように要素が正格評価されるデータ構造を使っていても,その中に格納されている要素がリストや第32回で説明したData.SeqのSeq型のように遅延評価されるデータ構造/データ型である場合には,同様の問題が生じます。

 この問題を解決するには,データ構造の中をたどっていき,すべての要素を正格評価する必要があります。具体的には,deepseqパッケージで提供されているNFDataクラスのrnfメソッドとdeepseq関数を利用するようにプログラムを変更します。

-- | 'deepseq': fully evaluates the first argument, before returning the
-- second.
--
-- The name 'deepseq' is used to illustrate the relationship to 'seq':
-- where 'seq' is shallow in the sense that it only evaluates the top
-- level of its argument, 'deepseq' traverses the entire data structure
-- evaluating it completely.
--
-- 'deepseq' can be useful for forcing pending exceptions,
-- eradicating space leaks, or forcing lazy I/O to happen.  It is
-- also useful in conjunction with parallel Strategies (see the
-- @parallel@ package).
--
-- There is no guarantee about the ordering of evaluation.  The
-- implementation may evaluate the components of the structure in
-- any order or in parallel.  To impose an actual order on
-- evaluation, use 'pseq' from "Control.Parallel" in the
-- @parallel@ package.
--
deepseq :: NFData a => a -> b -> b
deepseq a b = rnf a `seq` b

 deepseq関数は,第1引数として渡されたNFDataクラスのインスタンスである型の値を,NFDataクラスのrnfメソッドを使って正格評価します。第2引数として渡された値はそのまま返します。deepseq関数はseq関数を使って定義されており,「第1引数として渡された値がデータ構造である場合に,データ構造の中身まで正格評価する」こと以外の振る舞いはseq関数と同じです。したがって,seq関数の代わりにdeepseq関数を使うことで,データ構造を単に正格評価するのではなく,データ構造内のすべての要素を正格評価し,その結果を使って処理を行うようにプログラムを書き換えられます。

import Control.DeepSeq (deepseq, NFData(..))
import Data.List (foldl')

sum'' :: (Num a, NFData a) => [a] -> a
sum'' xs = xs `deepseq` foldl' (+) 0 xs

 NFDataクラスについては,第11回第43回のコラムを参照してください。

あなたにお薦め

連載新着

連載目次を見る

今のおすすめ記事

ITpro SPECIALPR

What’s New!

経営

アプリケーション/DB/ミドルウエア

クラウド

運用管理

設計/開発

サーバー/ストレージ

クライアント/OA機器

ネットワーク/通信サービス

セキュリティ

もっと見る