On 8/10/07, <b class="gmail_sendername">Donald Bruce Stewart</b> <<a href="mailto:dons@cse.unsw.edu.au">dons@cse.unsw.edu.au</a>> wrote:<div><span class="gmail_quote"></span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
No, STUArray s Int Bool is a bit array.<br>Look at the space use. Or try replacing Bool with Word32, and see what happens.<br></blockquote></div><br>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.
<br><br>G:\dev\haskell>primeshootoutmono3<br>Primes up to 10240000 679461<br>elapsed time: 0.921875<br><br>G:\dev\haskell>primeshootoutghc<br>Primes up to 10240000 679461<br>0.8280000000000001<br><br>class NSieveBits
<br>{<br> public int nsieve(int m) {<br> int[] isNotPrime = new int[((m+1) >> 5) + 1];<br> int count = 0;<br><br> int wordindex = 0;<br> int bitmask = 4;<br> for (int i=2; i <= m; i++)<br>
{<br> //Console.WriteLine( i + " " + wordindex + " " + bitmask );<br> if ( ( isNotPrime[wordindex] & bitmask ) == 0 )<br> {<br> //Console.WriteLine("prime: " + i );
<br> for (int k = (i << 1); k <= m; k+=i) <br> {<br> int _wordindex = k >> 5;<br> int _bitmask = 1 << ( k & 31 );<br> int _thisword = isNotPrime[_wordindex];
<br> if( ( _thisword & _bitmask ) == 0 )<br> {<br> isNotPrime[ _wordindex ] = _thisword | _bitmask;<br> }<br> }<br> count++;<br> }
<br> if( bitmask == ( 1 << 31 ) )<br> {<br> wordindex++;<br> bitmask = 1;<br> }<br> else<br> {<br> bitmask <<= 1;<br> }<br> }
<br> return count;<br> }<br>}<br><br>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???)
<br><br>