tag:blogger.com,1999:blog-7094652.post7833750806448105225..comments2024-03-23T14:36:09.980+00:00Comments on Neil Mitchell's Blog (Haskell etc): Optimisation with ContinuationsNeil Mitchellhttp://www.blogger.com/profile/13084722756124486154noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-7094652.post-69775213668959423852014-08-16T22:22:49.065+01:002014-08-16T22:22:49.065+01:00Sébastien: forkIO is cheap in terms of computation...Sébastien: forkIO is cheap in terms of computation time, and thread stacks are small if you never do any meaningful work on them. Shake is in the rare position of having a lot of queued threads, each of which did a reasonable amount of work, and will again in the future - a worst case for the Haskell RTS.<br /><br />Exceptions did turn out to be the hardest bit of the project, and I did end up including an exception handling bit, and some resource finalisation code. Thanks for the link, I'll have a read, and I'm also intending to post my notes on what ended up with in the end. My finalisers were quite neat (but not very advanced). My exception handlers on the continuation threads were complex, powerful, and seem a bit inelegant.<br />Neil Mitchellhttps://www.blogger.com/profile/13084722756124486154noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-34227401124480208672014-08-16T10:38:58.902+01:002014-08-16T10:38:58.902+01:00I thought also forkIO would be so cheap already th...I thought also forkIO would be so cheap already that you wouldn't have to resort to CPS in Haskell.<br /><br />This reminds me of a project I did in Scala a few years ago to support user-level green threads. Scala being impure, CPS with effects can be directly expressed as:<br />(a => ()) => ()<br /><br />To cope with user-level threads and exceptions, the signature had to be changed to:<br />((t, a) => ()) => ()<br />Where t is a user-level thread. It is used to schedule back continuations sequentially (only for processing results!) and it acts also as an escape hatch in case of exception by implementing the function to handle them:<br />Exception => ().<br /><br />After, I went on adding automatic resource control, and so on... If you are curious about it, the details are explained in the paper here:<br />https://github.com/molecule-labs/molecule#publication<br />(see section 3: Monadic User-Level Threads, code is on github too)<br /><br />Getting the details rights was tricky and I would love to see if it can be expressed in a better way.<br /><br />Side remark: I would call the operator something else because a parallel operator should really return both results: IO a -> IO b -> IO (a, b)Sébastien Bocqhttps://www.blogger.com/profile/17382572962250062819noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-52836357299778900672014-07-04T15:59:16.159+01:002014-07-04T15:59:16.159+01:00This observation – that running the continuation o...This observation – that running the continuation on the first thread to complete lets you use one less thread – is very similar to how the work-stealing scheduler in Cilk works. There we want to run both pieces of work to completion, but the first thread to finish wants to go off and find other work to do. So we actually steal the continuation of pending work.J-W Maessenhttps://www.blogger.com/profile/01577860012705910561noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-84881570986254351202014-07-04T12:37:33.609+01:002014-07-04T12:37:33.609+01:00It's been too long ago to remember the details...It's been too long ago to remember the details.<br /><br />I mostly did it because that was the most understandable way to design it. Actually, I looked at Max's Openshake and couldn't really make sense of it's inner workings. So, after thinking about how it should work conceptually, explicitly enumerating the states each Action could be in seemed to be the way that seemed to be easiest to follow (also for potential contributors).<br /><br />I don't think I ever finished the code. Looking through the code, exceptions handling was never fully implemented, so I don't know if it can be made to work correctly.<br /><br />The key driver is https://github.com/nominolo/cake/blob/master/src/Development/Cake/Core.hs#L460<br /><br />Maybe you can see some fatal flaw in it :)Thomas Schillinghttps://www.blogger.com/profile/04274984206279511399noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-78355063461724001832014-07-04T11:50:08.823+01:002014-07-04T11:50:08.823+01:00Thomas: Very interesting to see. Did it work in pr...Thomas: Very interesting to see. Did it work in practice? How did you cope with exceptions? Any general hardwon advice?Neil Mitchellhttps://www.blogger.com/profile/13084722756124486154noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-58135651853218623212014-07-04T11:14:51.474+01:002014-07-04T11:14:51.474+01:00When I built my clone of Shake (that was shortly b...When I built my clone of Shake (that was shortly before you published your personal rewrite) I ended up using an explicit data type to represent the current state of a rule. Some of those did include a continuation.<br /><br />https://github.com/nominolo/cake/blob/master/src/Development/Cake/Core.hs#L732Thomas Schillinghttps://www.blogger.com/profile/04274984206279511399noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-19155373129415786822014-06-30T21:59:41.321+01:002014-06-30T21:59:41.321+01:00C a is a type alias for (a -> IO ()) -> IO (...C a is a type alias for (a -> IO ()) -> IO (), so you can rewrite it as:<br /><br />parallel :: C a -> C a -> (a -> IO ()) -> IO ()<br /><br />Now you can see where the k comes from.Neil Mitchellhttps://www.blogger.com/profile/13084722756124486154noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-80920475614106063332014-06-30T21:42:49.131+01:002014-06-30T21:42:49.131+01:00Is this type signature messed up? It looks like it...Is this type signature messed up? It looks like it's missing the type for k to me: <br /><br />parallel :: C a -> C a -> C a<br />parallel t1 t2 k = do ...<br />Anonymousnoreply@blogger.com