<div>It is not obvious that semantics is preserved for optimisations which remove non-constants like</div><div><br></div><div>bar a b = a + b - a - b -- the RHS is should be optimized away to 0<br></div><div><br></div><div>
Calling bar undefined undefined throws an error, but the optimised bar would return 0.</div><br><div class="gmail_quote">On Sat, Jun 1, 2013 at 8:10 PM, Patrick Palka <span dir="ltr">&lt;<a href="mailto:patrick@parcs.ath.cx" target="_blank">patrick@parcs.ath.cx</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Yeah, I am going to use the MVar approach. Alternative implementations will be investigated if this approach happens to not scale well.</div>
<div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, May 31, 2013 at 9:10 AM, Thomas Schilling <span dir="ltr">&lt;<a href="mailto:nominolo@googlemail.com" target="_blank">nominolo@googlemail.com</a>&gt;</span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">[I&#39;ll be the mentor for this GSoC project.]<br>
<br>
I used the MVar approach a while ago and so did Simon Marlow&#39;s<br>
original solution.  Using MVars and Threads for this should scale well<br>
enough (1000s of modules) and be relatively straightforward.<br>
Error/exception handling could be a bit tricky, but you could use (or<br>
copy ideas from) the &#39;async&#39; package to deal with that.<br>
<span><font color="#888888"><br>
 / Thomas<br>
</font></span><div><div><br>
On 30 May 2013 18:51, Ryan Newton &lt;<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>&gt; wrote:<br>
&gt; What&#39;s the plan for what control / synchronization structures you&#39;ll use in<br>
&gt; part 2 of the plan to implement a parallel driver?<br>
&gt;<br>
&gt; Is the idea just to use an IO thread for each compile and block them on<br>
&gt; MVars when they encounter dependencies?  Or you can use a pool of worker<br>
&gt; threads and a work queue, and only add modules to the work queue when all<br>
&gt; their dependencies are met (limits memory use)... many options for executing<br>
&gt; a task DAG.  Fortunately the granularity is coarse.<br>
&gt;<br>
&gt;   -Ryan<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt; On Sun, Apr 21, 2013 at 10:34 PM, Patrick Palka &lt;<a href="mailto:patrick@parcs.ath.cx" target="_blank">patrick@parcs.ath.cx</a>&gt;<br>
&gt; wrote:<br>
&gt;&gt;<br>
&gt;&gt; Good points. I did not take into account whether proposal #2 may be worth<br>
&gt;&gt; it in light of -fllvm. I suppose that even if the LLVM codegen is able to<br>
&gt;&gt; perform similar optimizations, it would still be beneficial to implement<br>
&gt;&gt; proposal #2 as a core-to-core pass because the transformations it performs<br>
&gt;&gt; would expose new information to subsequent core-to-core passes. Also,<br>
&gt;&gt; Haskell has different overflow rules than C does (whose rules I assume<br>
&gt;&gt; LLVM&#39;s optimizations are modeled from): In Haskell, integer overflow is<br>
&gt;&gt; undefined for all integral types, whereas in C it&#39;s only undefined for<br>
&gt;&gt; signed integral types. This limits the number of optimizations a C-based<br>
&gt;&gt; optimizer can perform on unsigned arithmetic.<br>
&gt;&gt;<br>
&gt;&gt; I&#39;m not sure how I would break up the parallel compilation proposal into<br>
&gt;&gt; multiple self-contained units of work. I can only think of two units: making<br>
&gt;&gt; GHC thread safe, and writing the new parallel compilation driver. Other<br>
&gt;&gt; incidental units may come up during development (e.g. parallel compilation<br>
&gt;&gt; might exacerbate #4012), but I still feel that three months of full time<br>
&gt;&gt; work is ample time to complete the project, especially with existing<br>
&gt;&gt; familiarity with the code base.<br>
&gt;&gt;<br>
&gt;&gt; Thanks for the feedback.<br>
&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt; On Sun, Apr 21, 2013 at 5:55 PM, Carter Schonwald<br>
&gt;&gt; &lt;<a href="mailto:carter.schonwald@gmail.com" target="_blank">carter.schonwald@gmail.com</a>&gt; wrote:<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; Hey Patrick,<br>
&gt;&gt;&gt; both are excellent ideas for work that would be really valuable for the<br>
&gt;&gt;&gt; community!<br>
&gt;&gt;&gt; (independent of whether or not they can be made into GSOC sided chunks )<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; -------<br>
&gt;&gt;&gt; I&#39;m actually hoping to invest some time this summer investigating<br>
&gt;&gt;&gt; improving the numerics optimization story in ghc. This is in large part<br>
&gt;&gt;&gt; because I&#39;m writing LOTs of numeric codes in haskell presently (hopefully on<br>
&gt;&gt;&gt; track to make some available to the community ).<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; That said, its not entirely obvious (at least to me) what a tractable<br>
&gt;&gt;&gt; focused GSOC sized subset of the numerics optimization improvement would be,<br>
&gt;&gt;&gt; and that would have to also be a subset that has real performance impact and<br>
&gt;&gt;&gt; doesn&#39;t benefit from eg using -fllvm rather than -fasm .<br>
&gt;&gt;&gt; ---------<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; For helping pave the way to better parallel builds, what are some self<br>
&gt;&gt;&gt; contained units of work on ghc (or related work on cabal) that might be<br>
&gt;&gt;&gt; tractable over a summer? If you can put together a clear roadmap of &quot;work<br>
&gt;&gt;&gt; chunks&quot; that are tractable over the course of the summer, I&#39;d favor choosing<br>
&gt;&gt;&gt; that work, especially if you can give a clear outline of the plan per chunk<br>
&gt;&gt;&gt; and how to evaluate the success of each unit of work.<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; basically: while both are high value projects, helping improve the<br>
&gt;&gt;&gt; parallel build tooling (whether in performance or correctness or both!) has<br>
&gt;&gt;&gt; a more obvious scope of community impact, and if you can layout a clear plan<br>
&gt;&gt;&gt; of work that GHC folks agree with and seems doable, i&#39;d favor that project<br>
&gt;&gt;&gt; :)<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; hope this feedback helps you sort out project ideas<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; cheers<br>
&gt;&gt;&gt; -Carter<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; On Sun, Apr 21, 2013 at 12:20 PM, Patrick Palka &lt;<a href="mailto:patrick@parcs.ath.cx" target="_blank">patrick@parcs.ath.cx</a>&gt;<br>
&gt;&gt;&gt; wrote:<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; Hi,<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; I&#39;m interested in participating in the GSoC by improving GHC with one of<br>
&gt;&gt;&gt;&gt; these two features:<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; 1) Implement native support for compiling modules in parallel (see<br>
&gt;&gt;&gt;&gt; #910). This will involve making the compilation pipeline thread-safe,<br>
&gt;&gt;&gt;&gt; implementing the logic for building modules in parallel (with an emphasis on<br>
&gt;&gt;&gt;&gt; keeping compiler output deterministic), and lots of testing and<br>
&gt;&gt;&gt;&gt; benchmarking. Being able to seamlessly build modules in parallel will<br>
&gt;&gt;&gt;&gt; shorten the time it takes to recompile a project and will therefore improve<br>
&gt;&gt;&gt;&gt; the life of every GHC user.<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; 2) Improve existing constant folding, strength reduction and peephole<br>
&gt;&gt;&gt;&gt; optimizations on arithmetic and logical expressions, and optionally<br>
&gt;&gt;&gt;&gt; implement a core-to-core pass for optimizing nested comparisons (relevant<br>
&gt;&gt;&gt;&gt; tickets include #2132,#5615,#4101). GHC currently performs some of these<br>
&gt;&gt;&gt;&gt; simplifications (via its BuiltinRule framework), but there is a lot of room<br>
&gt;&gt;&gt;&gt; for improvement. For instance, the core for this snippet is essentially<br>
&gt;&gt;&gt;&gt; identical to the Haskell source:<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; foo :: Int -&gt; Int -&gt; Int -&gt; Int<br>
&gt;&gt;&gt;&gt; foo a b c = 10*((b+7+a+12+b+9)+4) + 5*(a+7+b+12+a+9) + 7 + b + c<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; Yet the RHS is actually equivalent to<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; 20*a + 26*b + c + 467<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; And:<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; bar :: Int -&gt; Int -&gt; Int<br>
&gt;&gt;&gt;&gt; bar a b = a + b - a - b -- the RHS is should be optimized away to 0<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; Other optimizations include: multiplication and division by powers of<br>
&gt;&gt;&gt;&gt; two should be converted to shifts; multiple plusAddr calls with constant<br>
&gt;&gt;&gt;&gt; operands should be coalesced into a single plusAddr call; floating point<br>
&gt;&gt;&gt;&gt; functions should be constant folded, etc..<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; GHC should be able to perform all these algebraic simplifications. Of<br>
&gt;&gt;&gt;&gt; course, emphasis should be placed on the correctness of such<br>
&gt;&gt;&gt;&gt; transformations. A flag for performing unsafe optimizations like assuming<br>
&gt;&gt;&gt;&gt; floating point arithmetic is associative and distributive should be added.<br>
&gt;&gt;&gt;&gt; This proposal will benefit anybody writing or using numerically intensive<br>
&gt;&gt;&gt;&gt; code.<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; I&#39;m wondering what the community thinks of these projects. Which project<br>
&gt;&gt;&gt;&gt; is a better fit for GSoC, or are both a good fit? Is a mentor willing to<br>
&gt;&gt;&gt;&gt; supervise one of these projects?<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; Thanks for your time.<br>
&gt;&gt;&gt;&gt; Patrick<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; (A little about myself: I&#39;m a Mathematics student in the US, and I&#39;ve<br>
&gt;&gt;&gt;&gt; been programming in Haskell for about 3.5 years. Having a keen interest in<br>
&gt;&gt;&gt;&gt; Haskell and compilers, I began studying the GHC source about 1 year ago and<br>
&gt;&gt;&gt;&gt; I&#39;ve since gotten a good understanding of its internals, contributing a few<br>
&gt;&gt;&gt;&gt; patches along the way.)<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; _______________________________________________<br>
&gt;&gt;&gt;&gt; Haskell-Cafe mailing list<br>
&gt;&gt;&gt;&gt; <a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
&gt;&gt;&gt;&gt; <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt; _______________________________________________<br>
&gt;&gt; Haskell-Cafe mailing list<br>
&gt;&gt; <a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
&gt;&gt; <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
&gt;&gt;<br>
&gt;<br>
</div></div></blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>Boris