<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi all,<div><br></div><div>I'm experimenting a bit with the parallelization capabilities of Haskell.</div><div>What I am trying to do is to process in parallel all the lines of a text file, calculating the edit distance of each of these lines with a given string.</div><div>This is my testing code:</div><div><br></div><div><br></div><div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; "><span style="color: #0000c4">import</span> System.IO</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; "><span style="color: #0000c4">import</span> Control.Monad</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; "><span style="color: #0000c4">import</span> Control.Parallel</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; "><span style="color: #0000c4">import</span> Control.Parallel.Strategies</div><div><br></div><div><font class="Apple-style-span" face="Monaco" size="3"><span class="Apple-style-span" style="font-size: 11px;">edist :: String -> String -> Int</span></font></div><div><font class="Apple-style-span" face="Monaco" size="3"><span class="Apple-style-span" style="font-size: 11px;">-- edist calculates the edit distance of 2 strings</span></font></div><div><font class="Apple-style-span" face="Monaco" size="3"><span class="Apple-style-span" style="font-size: 11px;">-- see for example <span class="Apple-style-span" style="font-family: Helvetica; font-size: 12px; "><a href="http://www.csse.monash.edu.au/~lloyd/tildeFP/Haskell/1998/Edit01/">http://www.csse.monash.edu.au/~lloyd/tildeFP/Haskell/1998/Edit01/</a></span></span></font></div><div><font class="Apple-style-span" face="Monaco" size="3"><span class="Apple-style-span" style="font-size: 11px;"><br></span></font></div></div><div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; ">getLines :: FilePath <span style="color: #0000c4">-></span> IO [Int]</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; color: rgb(128, 64, 64); "><span style="color: #000000">getLines = liftM ((parMap rnf (edist </span><span style="">longString</span><span style="color: #000000">)) . </span><span style="color: #40c0c0">lines</span><span style="color: #000000">) . </span><span style="color: #40c0c0">readFile</span></div><div><font class="Apple-style-span" color="#40C0C0" face="Monaco" size="3"><span class="Apple-style-span" style="font-size: 11px;"><br></span></font></div><div><font class="Apple-style-span" color="#40C0C0" face="Monaco" size="3"><span class="Apple-style-span" style="font-size: 11px;"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; ">main :: IO ()</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; ">main = <span style="color: #0000c4">do</span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; "><span class="Apple-tab-span" style="white-space:pre"> </span>list <- getLines <span style="color: #804040">"input.txt"<span class="Apple-style-span" style="color: rgb(64, 192, 192); "><span style="color: #000000"><span class="Apple-tab-span" style="white-space:pre"></span></span></span></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; "><span style="color: #804040"><span class="Apple-style-span" style="color: rgb(64, 192, 192); "><span style="color: #000000"><span class="Apple-tab-span" style="white-space:pre"> </span></span>mapM_<span style="color: #000000"> ( </span>putStrLn<span style="color: #000000"> . </span>show<span style="color: #000000"> ) list</span></span></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; ">I am testing this code in a 2xQuadCore linux (Ubuntu 8.10) machine (8 cores in total).</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; ">The code has been compiled with</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; ">ghc --make -threaded mytest.hs</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; ">I've been trying input files of different lengths, but the more cores I try to use, the worst performance I am getting.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; ">Here are some examples:</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; "># input.txt -> 10 lines (strings) of ~1200 letters each</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; ">$ time ./mytest +RTS -N1 > /dev/null </div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; "><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; ">real<span class="Apple-tab-span" style="white-space:pre"> </span>0m4.775s</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; ">user<span class="Apple-tab-span" style="white-space:pre"> </span>0m4.700s</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal Monaco; min-height: 15px; ">sys<span class="Apple-tab-span" style="white-space:pre"> </span>0m0.080s</div><div><br></div><div>$ time ./mytest +RTS -N4 > /dev/null</div><div><br></div><div><div>real<span class="Apple-tab-span" style="white-space:pre"> </span>0m6.272s</div><div>user<span class="Apple-tab-span" style="white-space:pre"> </span>0m8.220s</div><div>sys<span class="Apple-tab-span" style="white-space:pre"> </span>0m0.290s</div><div><br></div><div>$ time ./mytest +RTS -N8 > /dev/null</div><div><br></div><div><div>real<span class="Apple-tab-span" style="white-space:pre"> </span>0m7.090s</div><div>user<span class="Apple-tab-span" style="white-space:pre"> </span>0m10.960s</div><div>sys<span class="Apple-tab-span" style="white-space:pre"> </span>0m0.400s</div><div><br></div><div># input.txt -> 100 lines (strings) of ~1200 letters each</div><div>$ time ./mytest +RTS -N1 > /dev/null</div><div><br></div><div><div>real<span class="Apple-tab-span" style="white-space:pre"> </span>0m49.854s</div><div>user<span class="Apple-tab-span" style="white-space:pre"> </span>0m49.730s</div><div>sys<span class="Apple-tab-span" style="white-space:pre"> </span>0m0.120s</div><div><br></div><div>$ time ./mytest +RTS -N4 > /dev/null</div><div><br></div><div><div>real<span class="Apple-tab-span" style="white-space:pre"> </span>1m11.303s</div><div>user<span class="Apple-tab-span" style="white-space:pre"> </span>1m36.210s</div><div>sys<span class="Apple-tab-span" style="white-space:pre"> </span>0m1.070s</div><div><br></div></div><div>$ time ./mytest +RTS -N8 > /dev/null</div><div><br></div><div><div>real<span class="Apple-tab-span" style="white-space:pre"> </span>1m19.488s</div><div>user<span class="Apple-tab-span" style="white-space:pre"> </span>2m6.250s</div><div>sys<span class="Apple-tab-span" style="white-space:pre"> </span>0m1.270s</div><div><br></div></div><div><br></div><div>What is going wrong in this code? Is this a problem of the "grain size" of the parallelization?</div><div>Any help / advice would be very welcome,<span class="Apple-tab-span" style="white-space:pre"></span></div><div><br></div><div>M;<span class="Apple-tab-span" style="white-space:pre"></span></div><div><span class="Apple-tab-span" style="white-space:pre"> </span><br></div></div></div></div></div></span></font></div></div></body></html>