On 8/10/07, <b class="gmail_sendername">Donald Bruce Stewart</b> &lt;<a href="mailto:dons@cse.unsw.edu.au">dons@cse.unsw.edu.au</a>&gt; 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.&nbsp; Well, the mono example in the shootout is lacking quite a few optimizations, eg its using the builtin BitArray (slowww....), and it&#39;s not checking for the value of the bits before writing them.&nbsp; 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&gt;primeshootoutmono3<br>Primes up to 10240000&nbsp;&nbsp; 679461<br>elapsed time: 0.921875<br><br>G:\dev\haskell&gt;primeshootoutghc<br>Primes up to 10240000&nbsp;&nbsp; 679461<br>0.8280000000000001<br><br>class NSieveBits
<br>{<br>&nbsp;&nbsp; public int nsieve(int m) {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int[] isNotPrime = new int[((m+1) &gt;&gt; 5) + 1];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int count = 0;<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int wordindex = 0;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int bitmask = 4;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (int i=2; i &lt;= m; i++)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //Console.WriteLine( i + &quot; &quot; + wordindex + &quot; &quot; + bitmask );<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if ( ( isNotPrime[wordindex] &amp; bitmask ) == 0 )<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //Console.WriteLine(&quot;prime: &quot; + i );
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (int k = (i &lt;&lt; 1); k &lt;= m; k+=i) <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int _wordindex = k &gt;&gt; 5;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int _bitmask = 1 &lt;&lt; ( k &amp; 31 );<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int _thisword = isNotPrime[_wordindex];
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if( ( _thisword &amp; _bitmask ) == 0 )<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; isNotPrime[ _wordindex ] = _thisword | _bitmask;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; count++;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if( bitmask == ( 1 &lt;&lt; 31 ) )<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; wordindex++;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bitmask = 1;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bitmask &lt;&lt;= 1;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return count;<br>&nbsp;&nbsp; }<br>}<br><br>It&#39;d be more interesting to run these things in a multicore environment (16 cores would be ok, 64 would be better).&nbsp; Are there any utilities out there to do this? (vmware???)
<br><br>