Являются ли типы сумм, определенные с UnboxedSum, более эффективными, чем обычный enum? - PullRequest
Новая
       27

Являются ли типы сумм, определенные с UnboxedSum, более эффективными, чем обычный enum?

0 голосов
/ 12 сентября 2018

Например, вот простой тип данных перечисления Haskell: 

data Bool = False | True

Начиная с GHC-8.2.1, есть расширение -XUnboxedSums, которое позволяет определять типы сумм более эффективным способом памяти. Вот цитата из документации:

В вырожденном случае, когда все альтернативы имеют нулевую ширину, например, Bool -подобный (# (# #) | (# #) #), в макете с неупакованной суммой есть только поле тега Int32 (т. Е. Все это представлено целым числом).

Интересно, является ли это представление более эффективным, чем использование простого простого типа данных перечисления Haskell?

А вот полная документация:

1 Ответ

0 голосов
/ 12 сентября 2018

Семантика и представление

Эти два типа нельзя использовать взаимозаменяемо.

Тип 

data Bool = False | True

является поднятым типом.Это означает, что переменная x :: Bool все еще может быть оценена (например, thunk).Поэтому он будет представлен в виде указателя.

В отличие от него 

(# (# #) | (# #) #)

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

Эффективность пространства

Это, однако, не означает, что последний более эффективен в пространстве: поскольку True и False являются нулевыми конструкторами (они не принимают аргументов),они существуют раз и навсегда в статическом коде вашей программы, и указатели просто указывают на них.Таким образом, во всех случаях стоимость составляет одно машинное слово.

Эффективность времени выполнения

Вариант без коробки может быть немного более эффективным, чем Bool:

  • Для Bool код должен сначала проверить это уже вычислено? , а затем он может переходить на том конструкторе, в котором он находится.

    Разветвление довольно эффективно: код делаетдля этого не нужно следовать указателю: «тег указателя» в младших битах адреса указателя будет указывать, какой это конструктор.Тем не менее, существует небольшая стоимость маскировки других битов.

  • В варианте без коробки, ну, это просто 0 или 1, и проверка thunk не требуется.

Распаковка в типах данных

Если вы определили тип данных как этот 

data Foo = Foo (-# UNBOX #-} !Bool

, вы должны получить точно такой же результат, как если бы вынапишите 

data Foo = Foo (# (# #) | (# #) #)

, так как это было основной целью расширения суммы без коробки.

Распаковка в функциях

Если вы определяете строгую функцию в Boolаргумент, например 

foo True = "Hello"
foo False = "World!"

, тогда я мог представить (но не проверял), что компилятор оптимизирует это в worker , который принимает (# (# #) | (# #) #) и оболочку который заботится о проверке.Оболочка может затем встроиться в сайты использования, где используется foo, и все может закончиться в терминах (# (# #) | (# #) #).

Заключение

Не беспокойтесь.

...