GHC: Ticket #2422: Unrelated instance foils optimizer
http://ghc.haskell.org/trac/ghc/ticket/2422
<p>
I have a type <tt>(:.) a b</tt> that I use for vectors, so a 4d vector is <tt>a:.a:.a:.a:.()</tt>. This is just a linked list, so I also have a packed representation for Doubles, <tt>Vec4D</tt> and a class that relates the two representations.
</p>
<p>
The Storable instances for <tt>(:.)</tt> are inductive: if <tt>a</tt> and <tt>(b:.c)</tt> are Storable then so is <tt>(a:.b:.c)</tt>. So long as the source is a peek and the destination is a poke, the method calls optimize neatly and no <tt>(:.)</tt> values are allocated.
</p>
<p>
Here's the weird part: If I use the Storable methods of <tt>(:.)</tt> and the pack/unpack methods to extend a <tt>Storable</tt> instance to <tt>Vec4D</tt>, then the optimization of <em>the <tt>(:.)</tt> Storable methods</em> fails. The <tt>Vec4D</tt> instances are not used at all, and yet they affect optimization of the <tt>(:.)</tt> instances.
</p>
<p>
This is probably related to <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/2416" title="bug: Optimization defeated by merging module into main (closed: fixed)">#2416</a>. If I move the <tt>Storable</tt> instance for <tt>(:.)</tt> into <tt>Main.hs</tt>, then all optimization fails regardless of any instance for <tt>Vec4D</tt>. If I move the <tt>Storable</tt> instance for <tt>Vec4D</tt> into a different module than the instance for <tt>(:.)</tt>, then optimization works fine.
</p>
<p>
The example is in two files. I tried to merge them into one but that's when I discovered <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/2416" title="bug: Optimization defeated by merging module into main (closed: fixed)">#2416</a>.
</p>
<p>
Compiled with -O2.
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/2422
Trac 1.0.9sedillardFri, 04 Jul 2008 21:19:12 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/2422
http://ghc.haskell.org/trac/ghc/ticket/2422
<ul>
<li><strong>attachment</strong>
set to <em>Main.hs</em>
</li>
</ul>
TicketsedillardFri, 04 Jul 2008 21:19:41 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/2422
http://ghc.haskell.org/trac/ghc/ticket/2422
<ul>
<li><strong>attachment</strong>
set to <em>Lib.hs</em>
</li>
</ul>
TicketiglooSun, 06 Jul 2008 17:39:19 GMTdifficulty, milestone set
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:1
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:1
<ul>
<li><strong>difficulty</strong>
set to <em>Unknown</em>
</li>
<li><strong>milestone</strong>
set to <em>6.10 branch</em>
</li>
</ul>
<p>
Good testcase, thanks for the report!
</p>
TicketsimonpjMon, 05 Jan 2009 13:54:49 GMT
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:2
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:2
<p>
Good example! This is indeed what is making <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/2416" title="bug: Optimization defeated by merging module into main (closed: fixed)">#2416</a> go bad, but it's much easier to see here.
</p>
<p>
I've unraveled what's happening; just recording it here so I don't forget again. These remarks are mainly for me, so they may seem a bit cryptic.
</p>
<p>
From the instance for <tt>(Storable (a:.a:.v))</tt> we get something like
</p>
<pre class="wiki">Rec {
$f3 = \d. MkStorable ...(pbo d)...
pbo = \d. let pbo1 = peekByteOff ($f3 d) in \p q r. blah
end Rec }
</pre><p>
where <tt>peekByteOff</tt> is the method selector from the <tt>Storable</tt> class.
(See <tt>Note [How instance declarations are translated]</tt> in <tt>TcInstDcls</tt> for the overall game plan.) Then the simplifier inlines <tt>$f3</tt>, thereby breaking the recursion, to give
</p>
<pre class="wiki">pbo = \d. let ...d... in \p q r. blah
$f3 = \d. MkStorable ...(pbo d)...
</pre><p>
Now, when you add the "unrelated" instance, the specialiser kicks in, and makes a specialised version of both functions:
</p>
<pre class="wiki">$spbo = \p q r. blah blah blah
$sf3 = MkStorable ...$spbo...
</pre><p>
We've specialised for a particular dictionary <tt>d</tt>, and that means we can inline the specialised methods into <tt>$spbo</tt>. Alas, that makes <tt>$spbo</tt> big, so now it does not inline into the users of <tt>$sf3</tt>. Before, it did. In effect the unspecialised version looked a lot smaller than the specialised version.
</p>
<p>
But what about the INLINE pragma, you say? Well, it's hard to make it work right. If it attaches to the whole <tt>pbo</tt> we'd get
</p>
<pre class="wiki">Rec {
$f3 = \d. MkStorable ...(pbo d)...
pbo = __inline_me__ (\d. let pbo1 = peekByteOff ($f3 d) in \p q r. blah)
end Rec }
</pre><p>
But (for good reasons) we don't inline inside <tt>__inline_me__</tt>, so we won't get to break the recursive loop with <tt>$f3</tt>, which is terrible. GHC 6.10 currently pins the pragma on the body thus:
</p>
<pre class="wiki">Rec {
$f3 = \d. MkStorable ...(pbo d)...
pbo = \d. let pbo1 = peekByteOff ($f3 d) in
__inline_me__ (\p q r. blah)
end Rec }
</pre><p>
but this does not work right either (because eta expansion loses that <tt>__inline_me__</tt>).
</p>
<p>
I think the new inlining mechanism will help a lot, but I need to get it installed first. Stay tuned.
</p>
<p>
Simon
</p>
TicketiglooMon, 13 Apr 2009 15:46:27 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:3
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:3
<ul>
<li><strong>milestone</strong>
changed from <em>6.10 branch</em> to <em>6.12 branch</em>
</li>
</ul>
TicketiglooFri, 30 Apr 2010 16:40:29 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:4
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:4
<ul>
<li><strong>milestone</strong>
changed from <em>6.12 branch</em> to <em>6.12.3</em>
</li>
</ul>
TicketiglooSat, 19 Jun 2010 16:58:16 GMTpriority, milestone changed
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:5
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:5
<ul>
<li><strong>priority</strong>
changed from <em>normal</em> to <em>low</em>
</li>
<li><strong>milestone</strong>
changed from <em>6.12.3</em> to <em>6.14.1</em>
</li>
</ul>
TicketiglooThu, 24 Jun 2010 16:33:45 GMTstatus changed; failure, resolution set
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:6
http://ghc.haskell.org/trac/ghc/ticket/2422#comment:6
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>failure</strong>
set to <em>None/Unknown</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
The core is now the same with and without the instance.
</p>
Ticket