title: Why does introducing associated types kill my performance?
body: <p>In my <a href="https://github.com/fhaust/kdtree" rel="nofollow noreferrer" title="kdtree"><code>kdtree</code></a> project I just replaced a depth counter from being <code>Int</code>-based to an explicit <code>Key a</code> based on the type <code>a</code> in <code>KDTree v a</code>. This is the <a href="https://github.com/fhaust/kdtree/commit/5cec941da5c4a88caf044702fd38ed6b0837b265" rel="nofollow noreferrer">diff</a>.</p>
  
  <p>Now while I believe this should be a type-level change only my benchmarks show a sharp drop in performance:</p>
  
  <p>Before:</p>
  
  <pre><code>benchmarking nr/kdtree_nr 
  mean: 60.19084 us, lb 59.87414 us, ub 60.57270 us, ci 0.950
  std dev: 1.777527 us, lb 1.494657 us, ub 2.120168 us, ci 0.950
  </code></pre>
  
  <p>After:</p>
  
  <pre><code>benchmarking nr/kdtree_nr 
  mean: 556.9518 us, lb 554.0586 us, ub 560.6128 us, ci 0.950 
  std dev: 16.70620 us, lb 13.58185 us, ub 20.63450 us, ci 0.950
  </code></pre>
  
  <p>Before I dive into <em>Core</em> ... anyone has any idea what's going on here?</p>
  
  <h2>Edit 1</h2>
  
  <p>As proposed by Thomas (and userxyz) I replaced <code>data Key a :: *</code> with <code>type Key a :: *</code> and changed the implementation accordingly. This hasn't had any significent impact on the result:</p>
  
  <pre><code>benchmarking nr/kdtree_nr
  mean: 538.2789 us, lb 537.5128 us, ub 539.4408 us, ci 0.950
  std dev: 4.745118 us, lb 3.454081 us, ub 6.969091 us, ci 0.950
  </code></pre>
  
  <h2>Edit 2</h2>
  
  <p>Just had a quick look at the Core output. Apparently the change prevents functions depending on the class to be specialized, right?</p>
  
  <p>Before:</p>
  
  <pre><code>lvl20 :: KDTree Vector (V3 Double) -&gt; [V3 Double]
  lvl20 =
    \ (w4 :: KDTree Vector (V3 Double)) -&gt;
      $wpointsAround $fKDCompareV3_$s$fKDCompareV3 lvl2 lvl4 nrRadius q w4
  </code></pre>
  
  <p>After:</p>
  
  <pre><code>lvl18 :: KDTree Vector (V3 Double) -&gt; [V3 Double]
  lvl18 =
    \ (w4 :: KDTree Vector (V3 Double)) -&gt;
      $wpointsAround $dKDCompare lvl1 lvl3 nrRadius q w4
  </code></pre>
  
  <p>Small Update to <em>Edit 2</em>: Going crazy with <em>INLINE pragmas</em> doesn't change a thing here.</p>
  
  <h2>Edit 3</h2>
  
  <p>Quickly implemented what <em>userxyz</em> suggested: <a href="http://lpaste.net/104457" rel="nofollow noreferrer">http://lpaste.net/104457</a>
  Been there before, can't make it to work:</p>
  
  <pre><code>src/Data/KDTree.hs:48:49:
      Could not deduce (k ~ KeyV3)
      from the context (Real a, Floating a)
        bound by the instance declaration at src/Data/KDTree.hs:45:10-49
      or from (Key k)
        bound by the type signature for
                   dimDistance :: Key k =&gt; k -&gt; V3 a -&gt; V3 a -&gt; Double
        at src/Data/KDTree.hs:47:3-13
        ‘k’ is a rigid type variable bound by
            the type signature for
              dimDistance :: Key k =&gt; k -&gt; V3 a -&gt; V3 a -&gt; Double
            at src/Data/KDTree.hs:47:3
      Relevant bindings include
        k :: k (bound at src/Data/KDTree.hs:47:15)
        dimDistance :: k -&gt; V3 a -&gt; V3 a -&gt; Double
          (bound at src/Data/KDTree.hs:47:3)
      In the pattern: V3X
      In a case alternative: V3X -&gt; ax - bx
      In the second argument of ‘($)’, namely
        ‘case k of {
           V3X -&gt; ax - bx
           V3Y -&gt; ay - by
           V3Z -&gt; az - bz }’
  </code></pre>
  
  <h2>Edit 4</h2>
  
  <p>Hmm ... I think I just "solved" the problem by just throwing <em>SPECIALIZE</em> pragmas at the functions. This in effect causes everything to be inlined and removes the explicit dictionary passing.</p>
  
  <p>I am not too happy with that solution as this means I have to put a big "please specialize your calls to achieve decent performance" warning in the docs.</p>