<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style></head><body lang=EN-US link=blue vlink="#954F72"><div class=WordSection1><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Don’t worry about the time to append rather than pretend, it is not “exponential” nor even cubic.</p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>You are making a list of length in an N^2 algorithm. Appending to a list adds another tiny O(N^2) step, which is dominated by the main algorithm (also O(N^2), which both takes longer and evaluates vastly more values (failures as well as successes.)</p><p class=MsoNormal>Message: 3</p><p class=MsoNormal>Date: Thu, 21 Jan 2016 19:05:17 +0000</p><p class=MsoNormal>From: Rein Henrichs <rein.henrichs@gmail.com></p><p class=MsoNormal>To: The Haskell-Beginners Mailing List - Discussion of primarily</p><p class=MsoNormal> beginner-level topics related to Haskell <beginners@haskell.org>,</p><p class=MsoNormal> masonmlai@gmail.com</p><p class=MsoNormal>Subject: Re: [Haskell-beginners] program not running lazily</p><p class=MsoNormal>Message-ID:</p><p class=MsoNormal> <CAJp6G8zemeHpYwZ36ShMJ-m_BishVnUJpoqEmK=DosKHRVaqeg@mail.gmail.com></p><p class=MsoNormal>Content-Type: text/plain; charset="utf-8"</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>s/not/note, sorry</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>On Thu, Jan 21, 2016 at 10:42 AM Rein Henrichs <rein.henrichs@gmail.com></p><p class=MsoNormal>wrote:</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>> But not that doing so will cause the program to have an exponential</p><p class=MsoNormal>> runtime as each new ys must be repeatedly traversed to append a [y].. The</p><p class=MsoNormal>> alternative is to *unfold* your list by recursing on the right hand side of</p><p class=MsoNormal>> the (:) to add new elements.</p><p class=MsoNormal>><o:p> </o:p></p><p class=MsoNormal>> On Thu, Jan 21, 2016 at 5:43 AM Doug McIlroy <doug@cs.dartmouth.edu></p><p class=MsoNormal>> wrote:</p><p class=MsoNormal>><o:p> </o:p></p><p class=MsoNormal>>> Each time you find another good 9-mer, you add it to</p><p class=MsoNormal>>> the head of the list. This means that the ultimate</p><p class=MsoNormal>>> list will be in reverse order of discovery: the first element</p><p class=MsoNormal>>> to be printed is the last one to be found. To get</p><p class=MsoNormal>>> output in the order it was discovered, build the</p><p class=MsoNormal>>> output by ys++[y] rather than y:ys.</p><p class=MsoNormal>>> _______________________________________________</p><p class=MsoNormal>>> Beginners mailing list</p><p class=MsoNormal>>> Beginners@haskell.org</p><p class=MsoNormal>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</p><p class=MsoNormal>>><o:p> </o:p></p><p class=MsoNormal>><o:p> </o:p></p><p class=MsoNormal>-------------- next part --------------</p><p class=MsoNormal>An HTML attachment was scrubbed...</p><p class=MsoNormal>URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160121/9a99b2f6/attachment-0001.html></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>------------------------------</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Message: 4</p><p class=MsoNormal>Date: Thu, 21 Jan 2016 11:34:35 -0800</p><p class=MsoNormal>From: Mason Lai <masonmlai@gmail.com></p><p class=MsoNormal>To: Rein Henrichs <rein.henrichs@gmail.com>, doug@cs.dartmouth.edu</p><p class=MsoNormal>Cc: The Haskell-Beginners Mailing List - Discussion of primarily</p><p class=MsoNormal> beginner-level topics related to Haskell <beginners@haskell.org></p><p class=MsoNormal>Subject: Re: [Haskell-beginners] program not running lazily</p><p class=MsoNormal>Message-ID:</p><p class=MsoNormal> <CAH1iVpdf1tNsdHakTsM-1u4=2hu6GHpb47=gj+MZuxybUtb2Mw@mail.gmail.com></p><p class=MsoNormal>Content-Type: text/plain; charset="utf-8"</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I've changed the "if minimum < 3" line with an "any (< 3)" line. This has</p><p class=MsoNormal>sped up the performance to be good enough. (I assume that I have to</p><p class=MsoNormal>calculate the Lev. distance of all the 9-mers in order to take the minimum.</p><p class=MsoNormal>I really only care if any element has a Lev. distance less than three, so I</p><p class=MsoNormal>can stop when I find the first.) The rest of this discussion is purely for</p><p class=MsoNormal>fun.</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I've swapped "y:ys" for "ys ++ [y]", and while the output is reversed, I</p><p class=MsoNormal>don't appear to be able to take the first n elements still. I haven't timed</p><p class=MsoNormal>how long the program takes now to see if it blows up. Rein, I don't quite</p><p class=MsoNormal>understand your answer; I may need you to be more explicit if I don't</p><p class=MsoNormal>figure this out. Part of what confuses me is that the recursion takes place</p><p class=MsoNormal>in merge, and the (:) is in addInto. I think your comment has given me an</p><p class=MsoNormal>idea, so I'm going to take some time to play with this in the afternoon, so</p><p class=MsoNormal>I'll send an update tonight.</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Thanks for looking at this!</p><p class=MsoNormal>-- Mason</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>On Thu, Jan 21, 2016 at 11:05 AM, Rein Henrichs <rein.henrichs@gmail.com></p><p class=MsoNormal>wrote:</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>> s/not/note, sorry</p><p class=MsoNormal>><o:p> </o:p></p><p class=MsoNormal>> On Thu, Jan 21, 2016 at 10:42 AM Rein Henrichs <rein.henrichs@gmail.com></p><p class=MsoNormal>> wrote:</p><p class=MsoNormal>><o:p> </o:p></p><p class=MsoNormal>>> But not that doing so will cause the program to have an exponential</p><p class=MsoNormal>>> runtime as each new ys must be repeatedly traversed to append a [y].. The</p><p class=MsoNormal>>> alternative is to *unfold* your list by recursing on the right hand side of</p><p class=MsoNormal>>> the (:) to add new elements.</p><p class=MsoNormal>>><o:p> </o:p></p><p class=MsoNormal>>> On Thu, Jan 21, 2016 at 5:43 AM Doug McIlroy <doug@cs.dartmouth.edu></p><p class=MsoNormal>>> wrote:</p><p class=MsoNormal>>><o:p> </o:p></p><p class=MsoNormal>>>> Each time you find another good 9-mer, you add it to</p><p class=MsoNormal>>>> the head of the list. This means that the ultimate</p><p class=MsoNormal>>>> list will be in reverse order of discovery: the first element</p><p class=MsoNormal>>>> to be printed is the last one to be found. To get</p><p class=MsoNormal>>>> output in the order it was discovered, build the</p><p class=MsoNormal>>>> output by ys++[y] rather than y:ys.</p><p class=MsoNormal>>>> _______________________________________________</p><p class=MsoNormal>>>> Beginners mailing list</p><p class=MsoNormal>>>> Beginners@haskell.org</p><p class=MsoNormal>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</p><p class=MsoNormal>>>><o:p> </o:p></p><p class=MsoNormal>>><o:p> </o:p></p><p class=MsoNormal>-------------- next part --------------</p><p class=MsoNormal>An HTML attachment was scrubbed...</p><p class=MsoNormal>URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160121/15fe120e/attachment-0001.html></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>------------------------------</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Message: 5</p><p class=MsoNormal>Date: Fri, 22 Jan 2016 17:33:33 +1100</p><p class=MsoNormal>From: Thomas Koster <tkoster@gmail.com></p><p class=MsoNormal>To: beginners@haskell.org</p><p class=MsoNormal>Subject: [Haskell-beginners] Increasing capabilities dramatically</p><p class=MsoNormal> increases execution time</p><p class=MsoNormal>Message-ID:</p><p class=MsoNormal> <CAG1wH7DDYULMComW8QNntU4s6hcrhU53TAFywKfub+QqJi+BRQ@mail.gmail.com></p><p class=MsoNormal>Content-Type: text/plain; charset=UTF-8</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Hi friends,</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I have encountered a situation in a concurrent program where I see an</p><p class=MsoNormal>unexpected, dramatic increase in execution time when I add additional</p><p class=MsoNormal>capabilities. On a multi-core CPU, "-N1" is fastest by an order of</p><p class=MsoNormal>magnitude and the program increasingly slows for an increasing number</p><p class=MsoNormal>of capabilities (still fewer than the number of real cores, of</p><p class=MsoNormal>course).</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>My question is, why is this so and what can I do to improve this?</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Some details:</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I have a shared data structure which I call a "store", which is</p><p class=MsoNormal>basically a strict HashMap String Value. This structure is shared</p><p class=MsoNormal>between Haskell threads using an IORef/MVar pair:</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>data Store = Store (IORef (HashMap Key Value)) (MVar ())</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Focus on the IORef/MVar pair - the HashMap itself is not important. My</p><p class=MsoNormal>intention is that read-only transactions can take the pure value</p><p class=MsoNormal>straight from the IORef without blocking writers or other readers,</p><p class=MsoNormal>whereas mutating transactions (those that will update the IORef when</p><p class=MsoNormal>they complete) are serialized using the MVar. Alternatively, you can</p><p class=MsoNormal>regard the read-only transaction as working with a private snapshot of</p><p class=MsoNormal>the store that is discarded after it completes.</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>It is my hope that this technique will allow my program to exploit a</p><p class=MsoNormal>multi-core CPU by running several read-only transactions and at most</p><p class=MsoNormal>one mutating transaction in parallel. I am also assuming that this</p><p class=MsoNormal>technique is marginally more efficient than STM for this use case,</p><p class=MsoNormal>especially for write-heavy loads where I am assuming STM would waste</p><p class=MsoNormal>some time on retries (I did not test this).</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>-- | Execute a read-only transaction that returns a value.</p><p class=MsoNormal>withStore :: Store -> (HashMap Key Value -> a) -> IO a</p><p class=MsoNormal>withStore (Store ioref _) f = do</p><p class=MsoNormal> store <- readIORef ioref</p><p class=MsoNormal> return (f store)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>-- | Execute a transaction that updates the store and returns a value.</p><p class=MsoNormal>modifyStore :: Store -> (HashMap Key Value -> (HashMap Key Value, a)) -> IO a</p><p class=MsoNormal>modifyStore (Store ioref mvar) f =</p><p class=MsoNormal> modifyMVar mvar $ \ z -> do</p><p class=MsoNormal> store <- readIORef ioref</p><p class=MsoNormal> let (store', x) = f store</p><p class=MsoNormal> store' `seq` writeIORef ioref store'</p><p class=MsoNormal> return (z, x)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Stop me right here if this is a silly way to do this.</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I have a test that forks 4 threads that each increment a counter in</p><p class=MsoNormal>the store 100000 times, with the expectation that the final answer is</p><p class=MsoNormal>400000. I use the "async" package for this. This test is not</p><p class=MsoNormal>necessarily pathological. I expect simple operations like incrementing</p><p class=MsoNormal>counters and concatenating text to be typical transactions.</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> threads <- replicateM 4 $ async $</p><p class=MsoNormal> replicateM_ 100000 $</p><p class=MsoNormal> modifyStore store (...increment a counter...)</p><p class=MsoNormal> forM_ threads wait</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>In this test, while any thread is busy modifying the store, the other</p><p class=MsoNormal>three are blocked on the empty MVar, irrespective of how many</p><p class=MsoNormal>capabilities I have. Therefore, I expect the execution time with -N4</p><p class=MsoNormal>to be similar to -N1. I expect the only difference to be attributable</p><p class=MsoNormal>to the runtime's scheduling overheads, which I assume are relatively</p><p class=MsoNormal>insignificant. Instead, I see a dramatic increase in execution time</p><p class=MsoNormal>with increasing capabilities (typical measurements below).</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>By the way, I say I assume scheduling overheads are "relatively</p><p class=MsoNormal>insignificant" compared to incrementing the counter because in my</p><p class=MsoNormal>program, the counter is incremented by interpreting an imperative</p><p class=MsoNormal>EDSL, which I assume is relatively inefficient compared to e.g.</p><p class=MsoNormal>"succ", but perhaps I am mistaken. In a way, my whole question</p><p class=MsoNormal>probably centres around this assumption.</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I would be grateful is anyone can illuminate the reason for this</p><p class=MsoNormal>dramatic increase in execution time when I increase the number of</p><p class=MsoNormal>capabilities, and any hints on how I can mitigate it.</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I am using GHC 7.10.2 and compile with -O -threaded. All library</p><p class=MsoNormal>versions are as at Stackage LTS 3.2.</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>A typical measurement, with -N1:</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> Tot time (elapsed) Avg pause Max pause</p><p class=MsoNormal> Gen 0 516 colls, 0 par 0.000s 0.003s 0.0000s 0.0001s</p><p class=MsoNormal> Gen 1 2 colls, 0 par 0.000s 0.001s 0.0003s 0.0003s</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> TASKS: 4 (1 bound, 3 peak workers (3 total), using -N1)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> INIT time 0.000s ( 0.001s elapsed)</p><p class=MsoNormal> MUT time 0.136s ( 0.139s elapsed)</p><p class=MsoNormal> GC time 0.000s ( 0.003s elapsed)</p><p class=MsoNormal> EXIT time 0.000s ( 0.001s elapsed)</p><p class=MsoNormal> Total time 0.136s ( 0.144s elapsed)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>With -N2:</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> Tot time (elapsed) Avg pause Max pause</p><p class=MsoNormal> Gen 0 334 colls, 334 par 0.012s 0.006s 0.0000s 0.0001s</p><p class=MsoNormal> Gen 1 2 colls, 1 par 0.000s 0.000s 0.0002s 0.0003s</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> Parallel GC work balance: 39.33% (serial 0%, perfect 100%)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> TASKS: 6 (1 bound, 5 peak workers (5 total), using -N2)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> INIT time 0.000s ( 0.002s elapsed)</p><p class=MsoNormal> MUT time 2.032s ( 2.456s elapsed)</p><p class=MsoNormal> GC time 0.012s ( 0.007s elapsed)</p><p class=MsoNormal> EXIT time 0.000s ( 0.000s elapsed)</p><p class=MsoNormal> Total time 2.044s ( 2.465s elapsed)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>With -N4:</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> Tot time (elapsed) Avg pause Max pause</p><p class=MsoNormal> Gen 0 133 colls, 133 par 0.032s 0.005s 0.0000s 0.0001s</p><p class=MsoNormal> Gen 1 2 colls, 1 par 0.000s 0.001s 0.0003s 0.0003s</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> Parallel GC work balance: 41.33% (serial 0%, perfect 100%)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> TASKS: 10 (1 bound, 9 peak workers (9 total), using -N4)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> INIT time 0.000s ( 0.003s elapsed)</p><p class=MsoNormal> MUT time 3.516s ( 4.431s elapsed)</p><p class=MsoNormal> GC time 0.032s ( 0.005s elapsed)</p><p class=MsoNormal> EXIT time 0.000s ( 0.001s elapsed)</p><p class=MsoNormal> Total time 3.548s ( 4.439s elapsed)</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Thanks,</p><p class=MsoNormal>Thomas Koster</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>------------------------------</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Subject: Digest Footer</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>_______________________________________________</p><p class=MsoNormal>Beginners mailing list</p><p class=MsoNormal>Beginners@haskell.org</p><p class=MsoNormal>http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>------------------------------</p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>End of Beginners Digest, Vol 91, Issue 26</p><p class=MsoNormal>*****************************************</p><p class=MsoNormal><o:p> </o:p></p></div></body></html>