Являются ли Ана/Катаморфизмы более медленными?

После написания этой статьи я решил поместить свои деньги туда, где есть мой рот, и начал конвертировать предыдущий мой проект, чтобы использовать recursion-schemes.

Структура данных, о которой идет речь, представляет собой lazy kdtree. Пожалуйста, ознакомьтесь с реализациями с явным и неявным рекурсией.

Это в основном простое преобразование по строкам:

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

to

data KDTreeF v a f = NodeF a f f | Leaf v a

Теперь, сравнив весь shebang, я обнаружил, что версия KDTreeF примерно в два раза медленнее, чем обычная версия (найти весь пробег здесь).

Является ли это просто дополнительной оберткой Fix, которая замедляет меня здесь? И есть ли что-нибудь, что я мог бы сделать против этого?

Предостережение:

  • На данный момент это специализируется на (V3 Double).
  • Это приложение для метаморфизма. Гиломорфизм не подходит для kdtrees.
  • Я использую cata (fmap foo algebra) несколько раз. Это хорошая практика?
  • Я использую пакет Edwards recursion-schemes.

Изменить 1:

Связано ли это? https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers Является newtype Fix f = Fix (f (Fix f)) не "свободным"?

Изменить 2:

Просто сделал еще один набор тестов. На этот раз я протестировал строительство и деконструкцию дерева. Тест здесь: https://dl.dropboxusercontent.com/u/2359191/2014-05-15-kdtree-bench-03.html

Пока вывод Core указывает на то, что промежуточные структуры данных полностью не удаляются, и неудивительно, что линейные поисковые запросы доминируют сейчас, KDTreeF теперь немного быстрее, чем KDTree s. Не важно, хотя.

Ответы

Ответ 1

Я только что реализовал вариант дерева Thing + ThingF + Base instance. И угадайте, что... это удивительно быстро.

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

нет следа найденной структуры TreeF

Пусть числа говорят сами за себя, kdtreeu - новый вариант. Результаты не всегда столь же ясны, как и для этих случаев, но в большинстве случаев они, по крайней мере, так же быстро, как явная рекурсия (kdtree в тесте).

Benchmark results

Ответ 2

Я не использовал схемы рекурсии, а скорее свои собственные "ручные" ката, ana, Fix/unFix, чтобы генерировать (списки) и оценивать программы на небольшом языке в надежде найти тот, который сопоставлен список пар (входных, выходных).

По моему опыту, cata оптимизировался лучше, чем прямая рекурсия, и дал ускорение скорости. Также IME, ana предотвратил ошибки, которые вызывал мой наивный генератор, но этот make сосредоточился вокруг генерации окончательного списка.

Итак, я бы ответил, что нет, они не всегда медленнее, но я не вижу никаких очевидных проблем; поэтому они могут быть медленнее в вашем случае. Также возможно, что сами рекурсионные схемы просто не оптимизированы для скорости.