title: Haskell vs C speed: Sieve of Eratosthenes
body: <p>Haskell one is implemented using optimized Data.IntSet with complexity O(lg n). However, there is a 15x (previously 30x) speed difference for n = 2000000 despite Haskell code is already optimized for even number cases. I would like to know whether/why my implementation in Haskell is imperfect.</p>
  
  <h2>Original Haskell</h2>
  
  <pre><code>primesUpTo :: Int -&gt; [Int]
  primesUpTo n = 2 : put S.empty [3,5..n]
      where put :: S.IntSet -&gt; [Int] -&gt; [Int]
            put _ [] = []
            put comps (x:xs) =
              if S.member x comps
              then put comps xs
              else x : put (S.union comps multiples) xs
                  where multiples = S.fromList [x*2, x*3 .. n]
  </code></pre>
  
  <h2>Update</h2>
  
  <p><code>fromDistinctAscList</code> gives a 4x speed increase. 2-3-5-7-Wheel speeds up by another 50%.</p>
  
  <pre><code>primesUpTo :: Int -&gt; [Int]
  primesUpTo n = 2 : 3 : 5 : 7 : put S.empty (takeWhile (&lt;=n) (spin wheel 11))
      where put :: S.IntSet -&gt; [Int] -&gt; [Int]
            put _ [] = []
            put comps (x:xs) =
              if S.member x comps
              then put comps xs
              else x : put (S.union comps multiples) xs
                  where multiples = S.fromDistinctAscList [x*x, x*(x+2) .. n]
            spin (x:xs) n = n : spin xs (n + x)
            wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel
  </code></pre>
  
  <h2>Benchmarking</h2>
  
  <p>All time are measured by *nix <code>time</code> command, real space</p>
  
  <pre><code>Haskell original : 2e6: N/A;    2e7: &gt;30s
  Haskell optimized: 2e6: 0.396s; 2e7: 6.273s
  C++ Set (ordered): 2e6: 4.694s; 2e7: &gt;30s
  C++ Bool Array   : 2e6: 0.039s; 2e7: 0.421s
  </code></pre>
  
  <p>Haskell optimized is slower than C++ Bool by 10~15x, and faster than C++ Set by 10x.</p>
  
  <h2>Source code</h2>
  
  <p>C Compiler options: g++ 5.3.1, <code>g++ -std=c++11</code>
  Haskell options: ghc 7.8.4, <code>ghc</code></p>
  
  <p>C code (Bool array) <a href="http://pastebin.com/W0s7cSWi" rel="nofollow">http://pastebin.com/W0s7cSWi</a></p>
  
  <pre><code> prime[0] = prime[1] = false;
   for (int i=2; i&lt;=limit; i++) { //edited
       if (!prime[i]) continue;
       for (int j=2*i; j&lt;=n; j+=i)
          prime[j] = false;
   }
  </code></pre>
  
  <p>C code (Set) <a href="http://pastebin.com/sNpghrU4" rel="nofollow">http://pastebin.com/sNpghrU4</a></p>
  
  <pre><code> nonprime.insert(1);
   for (int i=2; i&lt;=limit; i++) { //edited
       if (nonprime.count(i) &gt; 0) continue;
       for (int j=2*i; j&lt;=n; j+=i)
          nonprime.insert(j);
   }
  </code></pre>
  
  <p>Haskell code <a href="http://pastebin.com/HuMqwvRW" rel="nofollow">http://pastebin.com/HuMqwvRW</a>
  Code as written above.</p>