On 8/10/07, Donald Bruce Stewart wrote:

http://shootout.alioth.debian.org/gp4/benchmark.php?test=nsievebits&lang=all

The GHC-compiled entry comes in at 1.2x C++, which I'm quite happy with. Strangely, despite your assertions, the C# entry lags well down the list.

Yeah, you somehow managed to slip around their rules without them noticing ;-) They specify to use a bit array, but you dont ;-) Bit arrays are optimal for space, but can be really slow.

On 8/10/07, Donald Bruce Stewart wrote:

It's using bit arrays.

Well I'm a total Haskell newbie, and you're using Haskell to write imperative code, so it's really hard for me to read, but looking at your code, you have: (IOUArray Int Bool) -- an array of Bool Bool is a 32-bit value in Haskell AFAIK? (or possibly a machine-dependent sized value, but certainly not a bit?)

On 8/10/07, Donald Bruce Stewart wrote:

No, STUArray s Int Bool is a bit array. Look at the space use. Or try replacing Bool with Word32, and see what happens.

Fair enough. Well, the mono example in the shootout is lacking quite a few optimizations, eg its using the builtin BitArray (slowww....), and it's not checking for the value of the bits before writing them. I dont quite get as fast as your ghc version (yet ;-) ), but its within 10% on my machine, using Microsoft C#, and staying within the rules of the shootout. G:\dev\haskell>primeshootoutmono3 Primes up to 10240000 679461 elapsed time: 0.921875 G:\dev\haskell>primeshootoutghc Primes up to 10240000 679461 0.8280000000000001 class NSieveBits { public int nsieve(int m) { int[] isNotPrime = new int[((m+1) >> 5) + 1]; int count = 0; int wordindex = 0; int bitmask = 4; for (int i=2; i <= m; i++) { //Console.WriteLine( i + " " + wordindex + " " + bitmask ); if ( ( isNotPrime[wordindex] & bitmask ) == 0 ) { //Console.WriteLine("prime: " + i ); for (int k = (i << 1); k <= m; k+=i) { int _wordindex = k >> 5; int _bitmask = 1 << ( k & 31 ); int _thisword = isNotPrime[_wordindex]; if( ( _thisword & _bitmask ) == 0 ) { isNotPrime[ _wordindex ] = _thisword | _bitmask; } } count++; } if( bitmask == ( 1 << 31 ) ) { wordindex++; bitmask = 1; } else { bitmask <<= 1; } } return count; } } It'd be more interesting to run these things in a multicore environment (16 cores would be ok, 64 would be better). Are there any utilities out there to do this? (vmware???)

On 8/10/07, Stefan O'Rear wrote:

Bool is 32 bits, but Don is using UArray. UArray is not parametric in the element type, which means it's less generally useful (no UArray of Complex Double, for instance), but conversely it is able to use more efficient representations depending on the type.

Ok, interesting :-)

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

On Friday 10 August 2007 03:51:49 Hugh Perkins wrote:

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.

In the interests of clarity, it is useful and important to distinguish between threading (i.e. concurrency) and parallelism. The former relates to the programmer's view of the world, and the latter relates to the computer's model of execution. As nomenclature, it is not universal, but is very common, and helps avoid conflating two quite different things. cheers, Tom -- Dr Thomas Conway drtomc@gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

On Friday 10 August 2007 12:37:31 Andrew Coppin wrote:

Stefan O'Rear wrote:

...

Bool is 32 bits, but Don is using UArray. UArray is not parametric in the element type, which means it's less generally useful (no UArray of Complex Double, for instance), but conversely it is able to use more efficient representations depending on the type.

Would be nice if it *could* somehow be parametric... but I have absolutely no idea how you'd do that. The transformation is self-evident enough to a human, but how do you explain it to a machine?

Check out the various papers, slides, and talks on NDP/parrallel arrays. There's much discussion on schemes to efficiently pack data types into unboxed arrays. Cheers, Spencer Janssen

(I somewhat suspect you'd have to bake this into the compiler itself it you wanted *arbitrary* types. Otherwise you'd have to write some special class that knows how to pack and unpack the data from the array, perhaps as a bundle of Word8s or something? Doesn't sound hugely fast...)

Hello Andrew, Friday, August 10, 2007, 9:37:31 PM, you wrote:

Would be nice if it *could* somehow be parametric...

ForeignArray may hold any Storable values. look at http://haskell.org/haskellwiki/Modern_array_libraries - we have no less than 10 array constructors :)) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

On 8/10/07, Michael Vanier wrote:

Just to get the history right: garbage collectors have been around a _long_ time, since the '60s in Lisp systems. They only became known to most programmers through Java (which is one unarguable good thing that Java did).

Ah interesting :-)

As for threading, in addition to Haskell's approach you might also look at Erlang, which has a quite different (and quite interesting) approach to the whole problem. I wonder if anyone has tried to implement a message-passing style of concurrency in Haskell.

Erlang message passing rocks :-) I'd love to see this working in Haskell. Note that Erlang's message passing is not perfect. Specifically, there is zero type or parameter checking. It will quite happily let the following compile: % initialization routines etc go here % ... % ping thread. this sends messages to pong ping() -> pong ! hello, pong ! hello, pong ! {hello}, % this does not throw a compile error pong ! hello, io:format("ping done~n" ). % pong thread, this listens for messages from pong pong() -> receive hello -> io:format("pong received hello~n"), pong() end. You can see that sending the tuple {hello} does not cause a compile time error (or even a runtime error for that matter), even though pong does not have a valid pattern for receiving it. Now, arguably the fact that we are pattern matching on the receiver at least means we dont do anything with the invalid data sent, but this is not rocket science: the standard technique to ensure decent compile time validation in rpc-type things is to use an interface. The interface defines the method names and parameters that you can send across. Both the receiver and the sender have access to the interface definition, and it is trivial to check it at compile time. (Caveat: havent looked enough into Erlang to know if there is a good reason for not using an interface?)

On 8/11/07, Benjamin Franksen wrote:

A certain amount of dynamism wrt the message content (high level protocol) is necessary for systems for which Erlang was designed, namely large distributed control systems with minimum down-times. For large distributed installations it is a matter of practicality to be able to upgrade one component w/o needing to recompile (and then re-start) all the other components that it communicates with -- for systems with expected down-times of 3 Minutes per year it is a matter of being able to meet the specifications. You'll have a hard time finding high-availability or large control systems which use an IDL approach for communication.

Hmmm, that's interesting. I'd never considered lack of typing to be a good thing for system robustness before! Question: to what extent does interface versioning get around this problem? I assume the issue we're trying to address is to be able to upgrade clients/servers/peers independently, without losing connectivity with unupgraded systems? So, using versioned interfaces: Initially we have: client1 marketinterface1 server marketinterface1 client2 marketinterface1 Then, we upgrade the server with a new interface, marketinterface2. Significantly, we keep the old interface. So now we have: client1 marketinterface1 server marketinterface1, marketinterface2 client2 marketinterface1 The whole system continues to work: client1 and client2 continue to chat with server on marketinterface1. Now we upgrade client1: client1 marketinterface2 server marketinterface1, marketinterface2 client2 marketinterface1 ... and client2: client1 marketinterface2 server marketinterface1, marketinterface2 client2 marketinterface2 Finally, we deprecate/remove marketinterface1 from the server: client1 marketinterface2 server marketinterface2 client2 marketinterface2

Hugh Perkins wrote:

On 8/11/07, Benjamin Franksen wrote:

...

A certain amount of dynamism wrt the message content (high level protocol) is necessary for systems for which Erlang was designed, namely large distributed control systems with minimum down-times. For large distributed installations it is a matter of practicality to be able to upgrade one component w/o needing to recompile (and then re-start) all the other components that it communicates with -- for systems with expected down-times of 3 Minutes per year it is a matter of being able to meet the specifications. You'll have a hard time finding high-availability or large control systems which use an IDL approach for communication.

Hmmm, that's interesting. I'd never considered lack of typing to be a good thing for system robustness before!

I didn't use the term robustness, which is typically used to express how well a program handles unexpected run-time conditions. What I refered to is maintainability in the face of continually changing requirements and the need to gradually upgrade components. (And rest assured I'm normally all for static typing!)

Question: to what extent does interface versioning get around this problem? I assume the issue we're trying to address is to be able to upgrade clients/servers/peers independently, without losing connectivity with unupgraded systems?

Yes (to the latter), and 'to a certain extent' to the former.

So, using versioned interfaces:

Initially we have: client1 marketinterface1 server marketinterface1 client2 marketinterface1

Then, we upgrade the server with a new interface, marketinterface2. Significantly, we keep the old interface. So now we have:

client1 marketinterface1 server marketinterface1, marketinterface2 client2 marketinterface1

The whole system continues to work: client1 and client2 continue to chat with server on marketinterface1.

Now we upgrade client1:

client1 marketinterface2 server marketinterface1, marketinterface2 client2 marketinterface1

... and client2:

client1 marketinterface2 server marketinterface1, marketinterface2 client2 marketinterface2

Finally, we deprecate/remove marketinterface1 from the server:

client1 marketinterface2 server marketinterface2 client2 marketinterface2

Yes, you can somewhat reduce the impact of an IDL based approach if you introduce the new interface in addition to the old one (and only deprecate the old interface after all components have been upgraded). However, this approach has its limits, especially if you consider large installation with 10s to 1000s of servers and clients (many of them being both at the same time), especially if upgrades are very frequent due to changing physical parameters, new requirements, additional instrumentation, etc. Let us be clear on one point: It is of course not possible for a client to make use of new features offered by a server if they do not know about these features. With an IDL approach, knowledge about new features need re-compilation and usually also new code to handle the new information. With a dynamic approach, this becomes largely a matter of changing the /configuration/ of a client, which is a much less disruptive process. Cheers Ben

On 8/10/07, Bulat Ziganshin wrote:

if you mean Erlang's sophisticated rules of which messages in queue to process first - this may be not yet implemented for Haskell. if you mean that program is just many threads which pass messages through channels to each other - it's easily accomplished in Haskell through Chan constructor. you can look at chameneos shootout entry, for example

Forgot to mention, a really cool thing about Erlang message-passing is that the other thread doesnt have to be on the same machine ;-)