Hello all,<br><br>First of all, I'm sorry that this email is so absurdly long. But it's not easy to explain the problem at hand, so I took a step-by-step approach. The executive summary is: GHC can do a <i>great </i>job with inlining, but often it doesn't, and I don't understand why. So I have some questions, which are highlighted in the text below. In general, any insights regarding inlining or improving the performance of generics are welcome. My final goal is to be able to state that generic functions (in particular using GHC.Generics) will have no runtime overhead whatsoever when compared to a handwritten type-specific version.<br>
<br><br><font size="4">The setting</font><br><br>Generic programming is based on representing datatypes in a uniform way using a small set of representation types. Functions defined on those representation types can then be applied to all datatypes, because we can convert between datatypes and their representations.<br>
However, generic functions tend to be slower than their specialised counterparts, because they have to deal with the conversions. But clever inlining (together with other compiler optimisations) can completely remove this overhead. The problem I'm tackling is how to tell GHC exactly what it should in the particular case of optimisation of generic code.<br>
<br><br><font size="4">Simplified example</font><br><br>I'll focus on the problem of optimising a non-trivial function for generic enumeration of terms. My experience shows that GHC does quite good at optimising simple functions, especially consumers (like generic equality). But producers are trickier.<br>
<br>First, we'll need some auxiliary functions:<br><br><blockquote style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex;font-family:courier new,monospace" class="gmail_quote">-- | Interleave elements from two lists. Similar to (++), but swap left and<br>
-- right arguments on every recursive application.<br>--<br>-- From Mark Jones' talk at AFP2008<br>{-# NOINLINE (|||) #-}<br>(|||) :: [a] -> [a] -> [a]<br>[] ||| ys = ys<br>(x:xs) ||| ys = x : ys ||| xs<br>
<br>
<br>-- | Diagonalization of nested lists. Ensure that some elements from every<br>-- sublist will be included. Handles infinite sublists.<br>--<br>--