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

Когда отвечая на вопрос с предложением использовать 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?

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

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


performance haskell gadt
person yatima2975    schedule 24.03.2011    source источник

Ответы (1)


arrow_upward
13
arrow_downward

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

person augustss    schedule 24.03.2011
comment
Однако аналогичное утверждение верно для ООП и объектов неконечных классов (каждый такой объект, переданный в метод, нуждается в указателе на таблицу виртуальных методов или эквивалент), а C++ или Java имеют достаточную производительность для множества приложений. Конечно, в обоих этих языках вы бы использовали не-OO вещи, такие как массивы, для некоторых вещей для повышения производительности. Очевидный комментарий, но я хотел поставить его в перспективе. - person Robin Green; 26.03.2011
comment
Спасибо за ответ, подтверждающий мои подозрения! Мне кажется, что (*) в выражении case всегда используется для типа Double -> Double -> Double, поскольку результатом value является Double, но value будет оцениваться все время и может быть дорогим (например, разбор String), поэтому здесь простые Doubles сделает намного лучше. - person yatima2975; 28.03.2011