On Friday 10 August 2007 03:51:49 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).
Yes, the semantics of Haskell allow us to run pretty much any operation in parallel. However, the major problem is that lists are a fundamentally sequential data structure. It's quite expensive to chop up parts of a list to eg. send them to a parallel map function. I think the upcoming NDP arrays have a much better chance here.
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)
The program doesn't have much chance for parallelism as written. It uses the imperative ST monad and destructive update extensively. Spencer Janssen