[Haskell-cafe] Haskell vs GC'd imperative languages, threading, parallelizeability (is that a word? :-D )

[Stefan O'Rear]

On Fri, Aug 10, 2007 at 04:51:49PM +0800, Hugh Perkins wrote:
> Well, managed to shave 25% of C# execution time by writing my own bit
> array.  For now, I will concede that, under the conditions of the shoot,
> bitarrays in c# are slower than bitarrays in Haskell.  I'll let you know if
> I get any new ideas on this.
>
> Getting back to the original problem, which is: threading.  Donald, one of
> the things that is very interesting about Haskell is it's potential for
> automatic threading, ie you write a trivial algorithm that looks like it
> runs in a single thread, and the runtime splits it across multiple cores
> automatically.
>
> It's fairly safe to say that maps, foldrs, foldls, and their derivatives are
> safe to parallelize?  (For example, hand-waving argument, a foldr of (/) on
> [1,5,7,435,46,2] can be split into a foldr on [1,5,7] and a foldr on
> [435,46,2], then their results combined).

Not really, because Haskell isn't powerful enough to express the fact
that (/) is associative.  (It isn't, but I'm ignoring that fact since
I'm pretty sure it's beside the point).  It is possible to do it using
an explicit foldb, however, and to a 1st approximation this is what lies
behind NDP.

On the other hand, division is *much* faster than sparking threads,
especially once factors invisible in the code (eg, cache-line ping-pong
on scheduler data structures) is taken into account.  In the past,
optimistic researchers have developed automatic parallelisation
algorithms.  The best of these were several times slower than decent
sequential algorithms.

The explicit case, using `par` or equivalent, is more interesting.
`par` gives you enough control to implement efficient threading, but is
semantically extremely lightweight - you can ignore par using the rule x
`par` y === y.  Adding or removing par following that rule cannot
possibly introduce bugs, far better than the equivalent situation with
global mutable data and forkIO!

> To what extent is the technology you are using in your algorithm
> parallizable?  (I actually cant tell, it's a genuine question).  In the case
> that it is parallelizable, to what extent is it trivial for a runtime to
> know this?  (Again, I dont have enough information to tell)

Something tells me the To: field of your message doesn't correspond
with the person you're actually addressing :)

Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070810/63f20d8e/attachment.bin