On Sun, Nov 2, 2008 at 12:42 PM, T Willingham wrote:

On Sun, Nov 2, 2008 at 6:44 PM, Bulat Ziganshin wrote:

...

...

What would it take to implement a -j equivalent for, say, GHC? Or if this is not possible, what is wrong with my reasoning?

problem is that make have rather large pices of work which it can run parallel. if ghc will try to parallel every machine operation, it will pend more time maintaining these jobs. 'par' is just the way to tell GHC "this part of job is large enough"

Right, but couldn't the Haskell complier+runtime discover "rather large pieces of work"?

Perhaps, but not easily. Especially if it can be done statically, there is plenty of research to be done in this area. Haskell is rather different from make. The graph of a lambda calculus program is not nearly as transparent as the graph of a makefile -- *especially* considering lazy evaluation. For example, you might think: map (+1) [1..10000000] Is a "rather large piece of work", but if it is then applied to "take 4", that is no longer true. We don't want to be futilely spinning our processor computing this. So my guess is that there are some cases, in the same way as strictness analysis, where you can identify these, but there are many cases which are much more subtle and hard to identify automatically. But I am no expert in the area. Luke

Hello T, Monday, November 3, 2008, 3:42:49 AM, you wrote:

On Sun, Nov 2, 2008 at 6:44 PM, Bulat Ziganshin wrote:

...

...

What would it take to implement a -j equivalent for, say, GHC? Or if this is not possible, what is wrong with my reasoning?

problem is that make have rather large pices of work which it can run parallel. if ghc will try to parallel every machine operation, it will pend more time maintaining these jobs. 'par' is just the way to tell GHC "this part of job is large enough"

Right, but couldn't the Haskell complier+runtime discover "rather large pieces of work"?

are you ever herd about "halting problem"? it's imposible in general case and i doubt how far it may be done on practice. in general, it looks close to really compute the function (and you still need to know its actual input params!) anyway it's not done and i don't heard about researches in this direction -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

On Tue, Nov 4, 2008 at 7:34 PM, Chad Scherrer wrote:

T Willingham writes:

...

I am thinking of our troglodytic friend 'make', which will run (for example) 4 parallel jobs when given the option "make -j4". Even 'rake', the ruby version of make, now has a branch (called drake) which does the parallel -j option.

...

From the replies I've seen about this, I think it's been interpreted as asking whether ghc could compile a given program so that it will execute in parallel. In general that's a hard problem.

On the other hand, it should be really straightforward (in principle, I mean) to get something going like ghc --make -j4 Foo.hs similar to your make example, so that compile time could be reduced, while the execution could either be sequential or parallel. I don't think there's anything like this yet (is there?).

Does anyone have any thought what it would take to get this going?

Chad

I believe that's the one of the points of the hbuild project (see http://hackage.haskell.org/trac/hackage/wiki/HBuild). Alex

Bulat Ziganshin wrote:

Hello Chad,

Wednesday, November 5, 2008, 6:34:01 AM, you wrote:

...

ghc --make -j4 Foo.hs

afair, it was implemented and not shown speed improvements. ask Simon

We did get speed improvements, it was the main case study for the initial implementation of shared-memory parallelism in GHC. See http://www.haskell.org/~simonmar/bib/multiproc05_abstract.html However, due to the way GHC is structured internally (it has some global caches updated using unsafePerformIO!) the parallel make implementation was quite fragile, and wasn't suitable for incorporating into GHC proper. It's certainly possible, but we need to think carefully about how to make these caches multi-thread-safe. Cheers, Simon