使用 UnboxedSums 定义的求和类型是否比普通枚举更有效?

Are sum types defined with UnboxedSums more efficient than plain enum?

例如,这里是简单的Haskell枚举数据类型:

data Bool = False | True

自 GHC-8.2.1 以来有 -XUnboxedSums 扩展,允许以更节省内存的方式定义求和类型。这是文档中的引述:

In the degenerate case where all the alternatives have zero width, such as the Bool-like (# (# #) | (# #) #), the unboxed sum layout only has an Int32 tag field (i.e., the whole thing is represented by an integer).

我想知道,这种表示是否比使用简单的普通 Haskell 枚举数据类型更有效?

这里是完整的文档:

语义和表示

这两种类型不能互换使用。

类型

data Bool = False | True

是提升型。这意味着变量 x :: Bool 仍然可以未评估(例如 thunk)。因此它将被表示为一个指针。

对比

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

未提升,实际上只能有两个值,并且将只表示为机器整数。

Space效率

确实如此,但是 不是 意味着后者更 space 有效:因为 TrueFalse 是空构造函数(它们不带任何参数),它们在程序的静态代码中一劳永逸地存在,指针只是指向它们。所以在所有情况下成本都是一个机器字。

运行时间效率

未装箱的变体可能比 Bool:

稍微更有效
  • 对于Bool,代码首先必须检查是否已经计算过?,然后它可以根据它是哪个构造函数进行分支。

    分支非常有效:代码不必为此遵循指针:指针地址低几位中的“指针标记”将指示它是哪个构造函数。不过,屏蔽其他位会产生一些成本。

  • 在未装箱的变体中,嗯,它只是 01,不需要 thunk 检查。

有一天可能会成真的事情

jberryman 说:截至 2021 年 1 月,以下内容似乎尚未实施,但有一天事情可能会如此。

数据类型拆箱

如果你定义这样的数据类型

data Foo = Foo {-# UNPACK #-} !Bool

你应该得到和你写的完全一样的结果

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

因为这是未装箱总和扩展的主要目的。

在函数中拆箱

如果您在 Bool 参数中定义了一个严格的函数,例如

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

然后我可以想象(但没有检查)编译器将其优化为一个 worker,它需要一个 (# (# #) | (# #) #) 和一个 wrapper 负责 thunk 检查。然后,包装器可能会在使用 foo 的使用站点中内联,并且一切都可能以 (# (# #) | (# #) #).

的形式结束

结论

不客气。