No Such Blog or Diary

ghc6.8.2がaptでインストールできるのだけどControl.Parallelの在り処が分からない．libghc6-parallel-dev とかいうパッケージがあるのが普通な気もするけど見当たらない．しょうがないのでaptで入れるのは諦めて自前で6.8.3をコンパイルしていれた．

でもquicksortが速くならない…

Control.Parallel の par を使うと第一引数を別スレッドで評価してくれる（かも）．ということで，試した．

import Control.Parallel
 
homP op f x = h x
  where
    h [a] = f a
    h (a:x) = fa `par` (hx `seq` (fa `op` hx))
     where fa = f a
           hx = h x
 
mapP f = homP (++) (\x->[f x])
 
chunk n [] = []
chunk n x = take n x:chunk n (drop n x)
 
split p x = chunk (div (length x + p - 1) p) x
mapS f dxs = mapP (map f) dxs
reduceS op dxs = homP op (foldl1 op) dxs
 
 
main = print $ reduceS(+) $ mapS f $ split 32 [1..10000]
 
f n = fib 16
 
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

基本，split でチャンクに切り分けて，homP で各チャンクに対する計算を並列評価する．

par の型は a -> b -> b で，デフォルトだと最初の引数を完全に無視する．んで，コンパイルというかリンク時に -threaded をつけてやると別スレッドでの並列評価を試みるコードになってくれるらしい．あと，実行時に +RST -N2 とかやって， N オプションで生成するネイティブスレッドの数を指定する．

とりあえず上のコードを デュアルコアで動かしたら 2.5 秒が 1.5 秒になる程度の効果が現れた．確かに並列で評価してくれているらしい．

ちなみに，

main = print $ sum $ concat $ mapS f $ split 32 [1..10000]

としてあげると並列計算の効果が全く現れない．sum の計算が concat の結果を頭から消費していく形なので，前のチャンクの結果が sum で消費しつくされてからしか次のチャンクの評価が起こらない．なので，mapS f での各チャンクに対する map f の評価が逐次的にしか起きてくれず，並列計算にならない．と思う．とりあえず遅延評価があると思ったより面倒だなぁ．

existential type でバインドされてて外側からは見えない型が二つあって，それらが同じ型である場合しか考えたくないのだがコンパイラにはそんなこと分からず…　動かん．そこの型を明示的に持てばこの部分だけは問題解決するが他の部分で…　とりあえず計算のシミュレートさえ出来れば良いのでトリックでごまかす．

data と newtype の宣言で deriving つけたらインスタンスが自動生成されることを始めて知った…　Eq、Ord、Enum、 Bounded、Show、 Read に対して使えるようでかなり手間が省ける．

C++ のソースからコメントだけを抜き出したい衝動に駆られたのでおもむろに Haskell で実装．やはり簡単なプログラムの実装は Haskell のほうが簡単だ…

 -- Extract C++ comments from stdin
import List
import System
 
 -- for C-style comments, i.e. /* comments... */
judgeC (t,c) (c1,c2,c3) 
    = if t==0 && c2=='/' && c3=='*' then (1,0) 
      else if t==1 && c1=='*' && c2=='/' && c > 2 then (0,0) 
           else (t,c+1)
 
 -- for C++-style comments, i.e. /* comments... */ or // comment... \n
judgeCXX (t,c) (c1,c2,c3) 
    = if t==0 && c2=='/' && c3=='/' then (2,0) 
      else if t==2 && c2=='\n' then (0,0) 
           else judgeC (t,c) (c1,c2,c3) 
 
unfilterComments x judge =
    let dx = (zip3 (" "++init x) x (tail x++" ")) 
        cms = scanl judge (0,0) dx
        cms' = zipWith (\(c1,_) (c2,_) -> c1 > 0 || c2 > 0) cms (tail cms)
    in map (\(x,c) -> x) (filter (\(_,c) -> c) (zip x cms'))
 
main = getArgs >>= 
       (\args -> getContents >>=
        (\x -> putStr (unfilterComments x
                       (if not (args ==[]) && head args == "-c" 
                        then judgeC else judgeCXX))))

Haskell の多倍長演算の中身は GMP だったのねと．GHC をコンパイルして初めて気づいた．ほんと，どうでもいいことだ…