title: Haskell and mutable structures' performance
body: <p>I was studying the answers given in <a href="https://stackoverflow.com/questions/2915137/optimizing-haskell-code">Optimizing Haskell code</a> and noticed that using a small input would indeed result in a faster Haskell run compared to Python.</p>
  
  <p>But as the dataset grew in size, Python took the lead. Using a hashmap based version had improved the performance, but it was still lagging behind.</p>
  
  <p>Even worse, I tried transliterating Python's dictionaries into hashtables and observed a hard performance hit. I really want to understand what's going on as I'll need mutable structures for a future application.</p>
  
  <p>Here's the slightly modified Python code :</p>
  
  <pre><code>#! /usr/bin/env python2.7
  import random
  import re
  import cPickle
  
  class Markov:
      def __init__(self, filenames):
          self.filenames = filenames
          self.cache = self.train(self.readfiles())
          picklefd = open("dump", "w")
          cPickle.dump(self.cache, picklefd)
      print "Built a db of length "+str(len(self.cache))
          picklefd.close()
  
      def train(self, text):
          splitted = text.split(' ')
          print "Total of %d splitted words" % (len(splitted))
          cache = {}
          for i in xrange(len(splitted)-2):
              pair = (splitted[i], splitted[i+1])
              followup = splitted[i+2]
              if pair in cache:
                  if followup not in cache[pair]:
                      cache[pair][followup] = 1
                  else:
                      cache[pair][followup] += 1
              else:
                  cache[pair] = {followup: 1}
          return cache
  
      def readfiles(self):
          data = ""
          for filename in self.filenames:
              fd = open(filename)
              data += fd.read()
              fd.close()
          return data
  
  Markov(["76.txt"])
  </code></pre>
  
  <p>Haskell, with the original response (<strong>train4</strong>), a hashmap variant thereof (<strong>trainHM2</strong>) and the hashtable transliteration (<strong>trainHT</strong>) :</p>
  
  <pre><code>{-# LANGUAGE BangPatterns,DeriveGeneric #-}
  
  import GHC.Generics (Generic)
  
  import Data.List (foldl')
  import Data.Hashable
  
  import qualified Data.Map as M
  
  import qualified Data.HashMap.Strict as HM
  import qualified Data.ByteString.Char8 as B
  
  import qualified Data.HashTable.IO as HT
  
  --Using this instead of tuples yielded a 5~10% speedup
  data StringTuple = STP !B.ByteString !B.ByteString deriving(Ord,Eq,Generic)
  instance Hashable StringTuple
  
  type Database3 = M.Map StringTuple (M.Map B.ByteString Int)
  type DatabaseHM = HM.HashMap StringTuple (HM.HashMap B.ByteString Int)
  type DatabaseHT = HT.BasicHashTable StringTuple DatabaseInnerHT
  type DatabaseInnerHT = (HT.BasicHashTable B.ByteString Int)
  
  train4 :: [B.ByteString] -&gt; Database3
  train4 words = foldl' update M.empty (zip3 words (drop 1 words) (drop 2 words))
      where update m (x,y,z) = M.insertWith' (inc z) (STP x y) (M.singleton z 1) m
            inc k _ = M.insertWith' (+) k 1
  
  trainHM2 :: [B.ByteString] -&gt; DatabaseHM
  trainHM2 words = trainHM2G words HM.empty
      where 
      trainHM2G (x:y:[]) !hm = hm
      trainHM2G (x:y:z:rem) !hm = trainHM2G (y:z:rem) (HM.insertWith (inc z) (STP x y) (HM.singleton z 1) hm)
              where inc k _ = HM.insertWith (+) k 1
  
  
  trainHT :: [B.ByteString] -&gt; IO (DatabaseHT)
  trainHT words = do 
   hm &lt;- HT.new 
  
   trainHT' words hm 
   where 
    trainHT' (x:y:[]) !hm = return hm
    trainHT' (x:y:z:rem) !hm = do
     let pair = STP x y
     inCache &lt;- HT.lookup hm pair
     case inCache of
      Nothing -&gt; do
       htN &lt;- HT.new :: IO (DatabaseInnerHT)
       HT.insert htN z $! 1
       HT.insert hm pair $! htN
      Just ht -&gt; do
       cvM &lt;- HT.lookup ht z
       case cvM of
        Nothing -&gt; HT.insert ht z 1
        Just cv -&gt; HT.insert ht z $! (cv+1)
     trainHT' (y:z:rem) hm
  
  main = do contents &lt;- B.readFile "76.txt"
        let bcont = B.split ' ' $ contents
        print $ length bcont
        let db = train4 $ bcont
        print $ "Built a DB of " ++ show (M.size db) ++ " words" 
        --let db = trainHM2 $ bcont
        --print $ "Built a DB of " ++ show (HM.size db) ++ " words"         
        --db &lt;- trainHT $ (bcont)
        --print $ "Built a DB" 
  </code></pre>
  
  <p>A makeshift C++11 transliteration (requires -fpermissive to compile, feel free to correct it) :</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;fstream&gt;
  #include &lt;sstream&gt;
  #include &lt;vector&gt;
  #include &lt;unordered_map&gt;
  #include &lt;tuple&gt;
  
  /*
   Hash stuff here
   Taken from https://stackoverflow.com/a/7111460/314327
  */
  size_t hash_combiner(size_t left, size_t right) //replacable
  { return left^right;}
  
  template&lt;int index, class...types&gt;
  struct hash_impl {
      size_t operator()(size_t a, const std::tuple&lt;types...&gt;&amp; t) const {
          typedef typename std::tuple_element&lt;index, std::tuple&lt;types...&gt;&gt;::type nexttype;
          hash_impl&lt;index-1, types...&gt; next;
          size_t b = std::hash&lt;nexttype&gt;()(std::get&lt;index&gt;(t));
          return next(hash_combiner(a, b), t); 
      }
  };
  template&lt;class...types&gt;
  struct hash_impl&lt;0, types...&gt; {
      size_t operator()(size_t a, const std::tuple&lt;types...&gt;&amp; t) const {
          typedef typename std::tuple_element&lt;0, std::tuple&lt;types...&gt;&gt;::type nexttype;
          size_t b = std::hash&lt;nexttype&gt;()(std::get&lt;0&gt;(t));
          return hash_combiner(a, b); 
      }
  };
  
  namespace std {
      template&lt;class...types&gt;
      struct hash&lt;std::tuple&lt;types...&gt;&gt; {
          size_t operator()(const std::tuple&lt;types...&gt;&amp; t) {
              const size_t begin = std::tuple_size&lt;std::tuple&lt;types...&gt;&gt;::value-1;
              return hash_impl&lt;begin, types...&gt;()(1, t); //1 should be some largervalue
          }
      };
  }
  
  /*
   Hash stuff end
  */
  
  using namespace std;
  
  /*
   Split, from https://stackoverflow.com/a/236803/314327
  */
  vector&lt;string&gt; &amp;split(const string &amp;s, char delim, vector&lt;string&gt; &amp;elems) {
   stringstream ss(s);
   string item;
   while (getline(ss, item, delim)) {
   elems.push_back(item);
   }
   return elems;
  }
  
  vector&lt;string&gt; split(const string &amp;s, char delim) {
   vector&lt;string&gt; elems;
   split(s, delim, elems);
   return elems;
  }
  /*
   Split end
  */
  
  typedef tuple&lt;string,string&gt; STP;
  
  unordered_map&lt; STP,unordered_map&lt; string,int &gt; &gt; train(vector&lt;string&gt; &amp;words)
  {
   unordered_map&lt; STP,unordered_map&lt; string,int &gt; &gt; cache; 
  
   for(int i=0;i&lt;words.size()-2;i++)
   {
    STP tup = make_tuple(words[i],words[i+1]);
    auto it = cache.find(tup);
    if(it!=cache.end())
    {
     auto it2 = it-&gt;second.find(words[i+2]);
     if(it2!=it-&gt;second.end())
     {
      it2-&gt;second += 1;
     }
     else
      it-&gt;second[words[i+2]] = 1;
    }
    else
    {    
     unordered_map&lt; string,int &gt; cacheInner;
     cacheInner[words[i+2]] = 1;
     cache[tup] = cacheInner;
    }
   }
  
   return cache;
  }
  
  int main()
  {
   ifstream ifs("76.txt");
   stringstream buf;
   buf &lt;&lt; ifs.rdbuf();
   string contents(buf.str());
  
   auto words = split(contents,' '); 
   cout &lt;&lt; words.size(); 
  
   auto wordCache = train(words);
  
   cout &lt;&lt; "\nHashtable count " &lt;&lt; wordCache.size();
  
   cout &lt;&lt; "\n";
   return 0;
  }
  </code></pre>
  
  <p>And the results are :</p>
  
  <p>C++ (GCC 4.6.3)</p>
  
  <pre><code>$ g++ -O3 -fpermissive -std=c++0x cpptest.cpp -o cpptest
  $ /usr/bin/time -f "%E" ./cpptest
  1255153
  
  Hashtable count 64442
  0:01.02
  </code></pre>
  
  <p>Python (2.7)</p>
  
  <pre><code>$ /usr/bin/time -f "%E" ./pytest.py 
  Total of 1255153 splitted words
  Built a db of length 64442
  0:02.62
  </code></pre>
  
  <p>Haskell (GHC 7.4.1) - "train4"</p>
  
  <pre><code>$ ghc -fllvm -O2 -rtsopts -fforce-recomp -funbox-strict-fields hasktest.hs -o hasktest
  [1 of 1] Compiling Main             ( hasktest.hs, hasktest.o )
  Linking hasktest ...
  $ /usr/bin/time -f "%E" ./hasktest
  1255153
  "Built a DB of 64442 words"
  0:06.35
  </code></pre>
  
  <p>Haskell - "trainHM2"</p>
  
  <pre><code>$ /usr/bin/time -f "%E" ./hasktest
  1255153
  "Built a DB of 64442 words"
  0:04.23
  </code></pre>
  
  <p>Haskell - "trainHT" - Using Basic variant (which is close to what Python does for dictionaries, I guess ?) </p>
  
  <pre><code>$ /usr/bin/time -f "%E" ./hasktest
  1255153
  "Built a DB"
  0:10.42
  </code></pre>
  
  <p>Using Linear or Cuckoo for both tables</p>
  
  <pre><code>0:06.06
  0:05.69
  </code></pre>
  
  <p>Using Cuckoo for the outermost table and Linear on the inside</p>
  
  <pre><code>0:04.17
  </code></pre>
  
  <p>Profiling had shown that there's quite a lot of GC, so, with +RTS -A256M</p>
  
  <pre><code>0:02.11
  </code></pre>
  
  <p><sub>For the input data, I chose <a href="http://www.gutenberg.org/files/76/76.txt" rel="nofollow noreferrer">76.txt</a> as indicated in one of the answers and duplicated the whole text 12 times. It should amount to about 7 MBs.</sub></p>
  
  <p><sub>Tests were run on Ubuntu 12.04 in a VirtualBox container, using a single i5-520M core. Done more than a single run, all the results were pretty close.</sub></p>
  
  <p>The last result is pretty fine for this microbenchmark, but <strong>is there anything else to improve in the code</strong>, considering that :</p>
  
  <ul>
  <li>Cuckoo &amp; Linear might be better suited for this dataset, but the "generic" Python solution is good to go without much an optimisation in this regard,</li>
  <li>Valgrind reports that the C++ &amp; Python versions take approximately <code>60MBs</code> whilst Haskell RTS reports anywhere from <code>125MBs</code> (Cuckoo&amp;Linear) to <code>409MBs</code> (Basic, larger heap) of memory for the same task. Wouldn't tweaking the garbage collector this much in a production environment be detrimental ? Is it possible to refactor the code so it has less memory usage ?</li>
  </ul>
  
  <p><strong>Update :</strong></p>
  
  <p>I guess "reducing garbage" is what I'm looking for. I know Haskell doesn't work the same way C++ does, but I want to know if it's possible to reduce garbage produced in imperative code, as the C++ example consumed half the memory without any space leaks. It'd hopefully be an improvement in terms of memory usage and execution time (as there'll be less GC). </p>
  
  <p><strong>Update 2 :</strong></p>
  
  <p>Computing the length during the table construction has reduced the memory footprint for sure (down to around <code>40MBs</code>, actually !), which causes the GC to take longer, resulting in a slower execution time (due to discarding values that had been lazily read from the list, I presume ?).</p>
  
  <p>And yes, hashtables' operations take a significant amount of time. I'll try mimicking alterations to see if it improves any further.</p>