Последствия использования GADT для производительности - PullRequest
Новая
       7

Последствия использования GADT для производительности

9 голосов
/ 25 марта 2011

Когда отвечая на вопрос с предложением использовать GADT , в комментариях возникали некоторые вопросы, касающиеся производительности. Вопрос касался класса типов PlotValue: 

class PlotValue a where
    value :: a -> Double

и мой ответ предложил использовать GADT Input: 

data Input where
    Input :: (PlotValue a, PlotValue b) => Maybe a -> Maybe b -> Input

но детали, я полагаю, несущественны.

Меня интересует два аспекта производительности:

Время : Существуют ли какие-либо затраты времени выполнения, связанные с сопоставлением с шаблоном, например 

case x of
    Input (Just a) (Just b) -> value a * value b
    _ -> 0.0

сверх обычных затрат, соответствующих двум Maybe значениям?

Space : Сколько накладных расходов хранит значение типа Input? Я предполагаю, что он несет в себе два PlotValue словарей для каждого значения типа Input («указатель» каждый?), Что означает, что [Input] будет гораздо более неэффективным с точки зрения использования памяти, чем использование (Just Double, Just Double) или, еще лучше, (# #Double, #Double #) - если вы храните результаты value в обычном или распакованном кортеже.

Так что, хотя мне нравится выразительность, которую дают мне GADT, я никогда особо не задумывался об аспектах исполнения. Кто-нибудь может рассказать мне больше об этом (и о любых других скрытых расходах, о которых я мог бы не знать)?

1 Ответ

13 голосов
/ 25 марта 2011

Я думаю, что вы забили накладные расходы. Для каждой экзистенциально определенной переменной вам нужны соответствующие (указатели на) словари. Это занимает место, и что еще хуже, вызовы методов будут медленными. (*) В вашем примере будет косвенным вызовом функции, тогда как с Double это было бы примитивным оператором.

...