<div>Background: I participated in this year's <a href="http://www.icfpcontest.org">ICFP programming contest</a> and our team did quite well, coming in 37th. Our simulator (in somewhat naive C++ with a good algorithm) took about 45 seconds to run the original problem, and afterwards one of my coworkers took the same algorithm and optimized it to run in about 6-10 seconds.
</div>
<div> </div>
<div>The rest of the email will have minor spoilers, so skip it if you want to work on the problem yourself.</div>
<div> </div>
<div>I'm using that problem as a good testcase for learning to write high-performance Haskell. I'm using the same data structure and basic algorithm as the C++ version, but I'm having problems getting the performance where I think it should be.
</div>
<div> </div>
<div>The relevant parts of the code:</div>
<div> </div>
<div><font face="courier new,monospace">> import qualified Data.ByteString.Base as B</font></div>
<div><font face="courier new,monospace">> import qualified Data.ByteString.Char8 as BC</font></div>
<div><font face="courier new,monospace">></font></div>
<div><font face="courier new,monospace">> type DNABlock = B.ByteString</font></div>
<div><font face="courier new,monospace">> type DNA = [DNABlock]</font></div>
<div> </div>
<div>I represent the DNA string as a simplified <a href="http://en.wikipedia.org/wiki/Rope_(computer_science)">rope</a> that supports fast reading from the front & prepending.</div>
<div> </div>
<div>To access this in a reasonable fashion, I used a view to let me treat the data as a string. Here's a sample bit of code using that view:</div>
<div> </div>
<div><font face="courier new,monospace">> matchConsts :: Int -> DNA -> (Int, DNA)</font></div>
<div><font face="courier new,monospace">> matchConsts len dna | len `seq` dna `seq` False = undefined -- force strictness</font></div>
<div><font face="courier new,monospace">> matchConsts len dna = case dnaView dna of</font></div>
<div>
<div><font face="courier new,monospace">> ('F':_) -> matchConsts (len+1) (dropDna 1 dna)</font></div>
<div><font face="courier new,monospace">> ('C':_) -> matchConsts (len+1) (dropDna 1 dna)</font></div>
<div><font face="courier new,monospace">> ('P':_) -> matchConsts (len+1) (dropDna 1 dna)</font></div><font face="courier new,monospace">> ('I':'C':_) -> matchConsts (len+2) (dropDna 2 dna)
</font></div>
<div><font face="courier new,monospace">> _ -> (len, dna)</font></div>
<div>
<div><font face="courier new,monospace"></font> </div>
<div><font face="courier new,monospace">> dropDna :: Int -> DNA -> DNA</font></div></div>
<div><font face="courier new,monospace">> dropDna n dna | n `seq` dna `seq` False = undefined -- force strictness</font></div>
<div><font face="courier new,monospace">> dropDna _ [] = []</font></div>
<div><font face="Courier New">> dropDna 0 dna = d</font></div>
<div><font face="courier new,monospace">> dropDna n (d:ds)</font></div>
<div><font face="courier new,monospace">> | n >= BC.length d = dropDna (n - BC.length d) ds</font></div>
<div><font face="Courier New">> | otherwise = B.unsafeDrop n d : ds</font></div>
<div><font face="Courier New">> {-# INLINE dropDna #-}</font></div>
<div><font face="courier new,monospace"></font> </div>
<div>Profiling showed that almost all of my time & allocations were spent in my view function:</div>
<div> </div>
<div><font face="courier new,monospace">> dnaView :: DNA -> String</font></div>
<div><font face="courier new,monospace">> -- dnaView d = foldr (++) [] (map BC.unpack d)</font></div>
<div><font face="courier new,monospace">> -- This was ridiculously slow for some reason that I don't entirely understand</font></div>
<div><font face="courier new,monospace">> dnaView [] = []</font></div>
<div><font face="courier new,monospace">> dnaView (d:ds)</font></div>
<div><font face="courier new,monospace">> | BC.null d = dnaView ds</font></div>
<div><font face="courier new,monospace">> | otherwise = (w2c $ B.unsafeHead d) : dnaView (B.unsafeTail d : ds)</font></div>
<div><font face="Courier New">> {-# INLINE dnaView #-}</font></div>
<div><font face="Courier New"></font> </div>
<div>The question I have for you, the haskell-cafe-reading-audience, is how can I get GHC to do smart code-gen for this? I want "case dnaView dna of ..." to not allocate and instead fuse the list generation with the pattern-match.
</div>
<div> </div>
<div> -- ryan</div>