On 8/10/07, Donald Bruce Stewart
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???)