Как найти распределение в функции Haskell, скомпилированной с помощью GHC?

Я использую GHC 7.4 для компиляции следующей функции:

nodups' :: [Int] -> Bool
nodups' = ok empty
  where ok _ [] = True
        ok seen (n:ns) = not (n `member` seen) && ok (n `insert` seen) ns
        member n word = testBit word n
        insert n word = setBit word n
        empty = 0 :: Int

Функция ищет повторяющиеся элементы в списке небольших целых чисел. Набор seen представляет собой представление множества малых целых чисел в виде битового вектора. Профайлер (run with ghc -prof -auto-all) утверждает, что функция ok составляет 22% общего объема. Глядя на результат с помощью -ddump-simpl, я не могу понять, почему этот код выделяется. Я проверил, и насколько я могу судить, он не выделяет thunk для вызова insert.

Что я должен посмотреть, чтобы определить часть моего выделенного кода?

Ответы

Ответ 1

В целом

Я знаю простые (научные) реализации функциональных языков, и если я правильно помню, есть G-Machine, которые могут использоваться с Haskell.

Это означает (опять же, если я правильно помню), что ваше состояние программы представлено как "Дерево", где узлы (для простоты) используют функции, которые вы используете в своем коде. Листы были бы аргументами. Затем "G-Maschine" смотрит вдоль "спины" (левая цепь узлов) и просматривает набор доступных "функций" ( "Суперкомбинаторы"?) Для соответствия шаблону, который он может применить. Если соответствие матчей распознается с левой стороны определения, оно затем заменяется на правую сторону определения.

Это означает, что даже простая строка типа

ok seen (n:ns) = not (n `member` seen) && ok (n `insert` seen) ns

или даже

(n:ns) = ns

делает что-то в памяти компьютера, то есть соответствует шаблону

       ...
     ...
    (:)
   /   \
  n     ns

и заменив его на

       ...
     ...
    ns

Конечный результат может потреблять меньше памяти, чем вход, но это динамический шаг и, следовательно, должен произойти где-то. Если это повторяется снова и снова (в "жесткой петле" ), это заставит вас заняться CPU, а также ваша память - только потому, что работает G-Machine. (Как я уже сказал, я не уверен, что здесь применяется G-Machine-концепция, но я думаю, что это нечто похожее).

Конкретные догадки

    member n word = testBit word n
    insert n word = setBit word n

Кроме того, я склоняюсь к некоторым подозрениям. testBit и setBit выглядят как индексные операции над списками. Если они есть, это может занять некоторую работу. Если они правильные массивы, все будет хорошо. Если они являются своего рода картами или наборами... ну... может быть дорогостоящее хеширование? Или реализовано через сбалансированное дерево, которое использует много (дорогостоящих?) Операций сравнения?