为什么引入相关类型会影响我的表现？

Question

在我的kdtree项目,我刚刚更换被深度计数器Int为基础的,以一个明确的Key a基础上,类型a在KDTree v a.这是差异.

现在,虽然我认为这应该是类型级别的更改,但我的基准测试显示性能急剧下降:

之前:

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

后:

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

在我深入Core之前......任何人都知道这里发生了什么？

编辑1

所建议的托马斯(和userxyz)我取代data Key a :: *与type Key a :: *和相应改变的执行情况.这对结果没有任何重大影响:

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

编辑2

刚看了一下Core输出.显然,这种改变会阻止依赖于类的功能专门化,对吧？

之前:

lvl20 :: KDTree Vector (V3 Double) -> [V3 Double]
lvl20 =
  \ (w4 :: KDTree Vector (V3 Double)) ->
    $wpointsAround $fKDCompareV3_$s$fKDCompareV3 lvl2 lvl4 nrRadius q w4

后:

lvl18 :: KDTree Vector (V3 Double) -> [V3 Double]
lvl18 =
  \ (w4 :: KDTree Vector (V3 Double)) ->
    $wpointsAround $dKDCompare lvl1 lvl3 nrRadius q w4

编辑的小更新2:使用INLINE编译指示疯狂不会改变这里的事情.

编辑3

快速实现userxyz建议的内容:http://lpaste.net/104457 之前曾经存在过,无法使其工作:

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 => k -> V3 a -> V3 a -> Double
      at src/Data/KDTree.hs:47:3-13
      ‘k’ is a rigid type variable bound by
          the type signature for
            dimDistance :: Key k => k -> V3 a -> V3 a -> Double
          at src/Data/KDTree.hs:47:3
    Relevant bindings include
      k :: k (bound at src/Data/KDTree.hs:47:15)
      dimDistance :: k -> V3 a -> V3 a -> Double
        (bound at src/Data/KDTree.hs:47:3)
    In the pattern: V3X
    In a case alternative: V3X -> ax - bx
    In the second argument of ‘($)’, namely
      ‘case k of {
         V3X -> ax - bx
         V3Y -> ay - by
         V3Z -> az - bz }’

编辑4

嗯......我想我只是通过在函数中抛出SPECIALIZE pragma来"解决"这个问题.这实际上导致所有内联都被内联并删除显式字典传递.

我对这个解决方案不太满意,因为这意味着我必须在文档中加上一个很大的"请专门调用你的电话以获得良好的性能"警告.

Answer 1

纯粹是偶然，我偶然发现了这个问题：GHC 中自动专业化的传递性

OP 引用了“来自GHC 7.6 的文档：”（强调我的）：

[你]通常甚至一开始就不需要SPECIALIZE pragma。编译模块 M 时，GHC 的优化器（使用 -O）自动考虑 M 中声明的每个顶级重载函数，并将其专门用于 M 中调用它的不同类型。优化器还考虑每个导入的INLINABLE重载函数，并将其专门用于 M 中称为的不同类型。

因此，我刚刚删除了所有（硬）INLINE和SPECIALIZE编译指示，并在适当的情况下（即在基准测试套件中使用的每个函数上）将它们替换为INLINEABLE编译指示。因此，与所有函数上的内联编译指示相比，我获得了更好的时间。

精髓：让编译器完成它的工作，但有时给他一个提示。