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