14

在我的kdtree项目中，我只是将深度计数器从 -based 替换为基于in类型Int的显式计数器。这是差异。Key aaKDTree 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

在我深入核心之前......有人知道这里发生了什么吗？

编辑 1

正如 Thomas（和 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

刚刚快速浏览了核心输出。显然，更改会根据要专门化的类阻止功能，对吗？

前：

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 来“解决”这个问题。这实际上导致所有内容都被内联并删除显式字典传递。

我对这个解决方案不太满意，因为这意味着我必须在文档中放置一个很大的“请专业化你的调用以实现良好的性能”警告。

4

2 回答 2

1

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

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

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

结果，我刚刚删除了所有（硬）INLINE和SPECIALIZE pragma，并在适当的地方（即在基准套件中使用的每个函数上）用INLINEABLE pragma替换它们。结果，我得到了比在所有函数上使用内联编译指示更好的时间。

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

于 2014-05-22T12:43:39.313 回答
0

这可能没有帮助，因为它没有解决真正的问题，即代码变慢，但您可以使用type而不是data. 原因kFirstand kSuccdon't work 是因为没有办法a从他们的应用程序中推断出什么，所以没有办法选择一个实例，因为实例只依赖于a而不是Key a。您可以通过为这些功能提供见证来解决此问题：

class KDCompare a where
  type Key a :: *

  kSuccWith :: proxy a -> Key a -> Key a
  kFirstWith :: proxy a -> Key a

然后相应地修改您的功能：

kdtree :: (KDCompare a, G.Vector v a) => BucketSize -> v a -> KDTree v a
kdtree mb vs = ana (kdtreeF mb) (kFirstWith vs, vs) 

kdtreeF :: (KDCompare a, G.Vector v a) => BucketSize -> (Key a,v a) -> KDTreeF v a (Key a,v a)
kdtreeF (BucketSize mb) (k0, v0) = go (k0, v0)
  where go (k,fs) | G.length fs <= mb = LeafF (G.convert fs)
                  | otherwise         = NodeF k (G.head r) (kSucc' k,l) (kSucc' k,r)
                    where (l,r) = splitBuckets k fs
                          kSucc' = kSuccWith v0

Key将and分开可能更有意义KDCompare：

class Enum a => Key a where 
  kSucc :: a -> a
  kFirst :: a

class KDCompare a where
  dimDistance  :: Key key => key -> a -> a -> Double
  realDistance :: a -> a -> Double

然后您的数据类型必须通过键参数化：

data KDTree k v a = Node k a (KDTree k v a) (KDTree k v a)
                    | Leaf (v a)


data KDTreeF k v a f = NodeF k a f f | LeafF (v a)
  deriving (Functor)

但是您的函数可以更自然地编写：

kdtree :: (Key key, KDCompare a, G.Vector v a) => BucketSize -> v a -> KDTree key v a
kdtree mb vs = ana (kdtreeF mb) (kFirst, vs)
于 2014-05-22T02:00:26.563 回答