Почему введение связанных типов убивает мою производительность?

В моем проекте kdtree я просто заменил счетчик глубины на Int на явный Key a в зависимости от типа a в KDTree v a. Это diff.

Теперь, когда я считаю, что это должно быть изменение типа, только мои тесты показывают резкое падение производительности:

Прежде чем погрузиться в Core... кто-нибудь знает, что здесь происходит?

Изменить 1

Как было предложено Thomas (и userxyz), я заменил data Key a :: * на type Key a :: * и соответствующим образом изменил реализацию. Это не оказало существенного влияния на результат:

Изменить 2

Просто взглянул на вывод Core. По-видимому, изменение препятствует функциям, зависящим от класса, быть специализированным, правильно?

Небольшое обновление для редактирования 2: сходит с ума от прагм INLINE, здесь ничего не меняется.

Изменить 3

Быстро реализовано то, что предложил userxyz: http://lpaste.net/104457 Был там раньше, не может заставить его работать:

Изменить 4

Хм... Я думаю, что я просто "решил" проблему, просто бросив СПЕЦИАЛИЗИРУЮЩИЕ прагмы в функции. Это фактически заставляет все быть встроенным и удаляет явный переход в словарь.

Я не очень доволен этим решением, так как это означает, что я должен поместить в документах большое "пожалуйста, специализируйтесь на своих звонках, чтобы добиться достойной производительности".

Ответы

Ответ 1

По чистой случайности я просто наткнулся на этот вопрос: Транзитивность авто-специализации в GHC

Там OP цитирует "From документы для GHC 7.6:" (выделение мое):

[Y] часто даже не нужна прагма SPECIALIZE. При компиляции модуля M оптимизатор GHC (с -O) автоматически рассматривает каждую перегруженную функцию верхнего уровня, объявленную в M, и специализируется на разных типах, в которых она вызывается в M. Оптимизатор также рассматривает каждый импортированный INLINABLE, и специализируется на разных типах, в которых он вызывается в M.

В результате я только что удалил все (жесткие) INLINE и СПЕЦИАЛИЗИРОВАННЫЕ прагмы и заменил их на INLINEABLE прагмы, где это необходимо (т.е. на каждая функция, которая используется в наборе эталонных тестов). В результате я получаю еще лучшие времена, чем с встроенными прагмами для всех функций.

Quintessence: пусть компилятор работает, но иногда дает ему подсказку.

Ответ 2

Это может быть не полезно, потому что это не относится к реальному вопросу, который замедляет работу кода, но вы можете сделать эту работу с type вместо data. Причина kFirst и kSucc не работает, потому что нет способа вывести то, что 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 и 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)