大型代数数据类型的内存占用

Question

假设我有一个数据类型，带有许多构造函数。

data ManyValues
  = Value0
  | Value1
  | Value2
  ...
  | Value255
  | Value256
  deriving (Show,Eq)

这种数据类型每个值的内存占用是多少？我原来的理解是每个构造函数占用8位内存，但如果在数据类型中有比8位内可能值更多的构造函数，那么构造函数是否会增加到16位等，直到构造函数可以寻址数据类型中存在的所有构造函数？还是我把所有这些都搞混了？

- carpemb

---

这个可能会有帮助：https://dev59.com/ynA75IYBdhLWcg3wg5Vh - Sibi

谢谢，我在发布之前看到了那个。它提出了关于零字段构造函数的对象共享的有趣观点，但它没有解决当存在更多构造函数（甚至是零字段构造函数）时会发生什么，而这些构造函数无法用8位来表示。这是假设8位标头被用于此目的的情况。 - carpemb

在那个回答中，“word”这个头至少是32位。当然，原则上问题仍然存在（例如，一种方法可能是仅使用前32位来缩小选择范围），但如果你的数据类型有2^32个构造器，你可能会面临其他工程难题。 - pigworker

在编译过程中，各种ManyValues之间的区别被抹去了；你只需要这些信息来进行代码的类型检查。在运行时，每个值只是一个简单的单词，基本上表示该值存在。 - chepner

看起来我的问题是因为对“字”这个概念感到困惑。我一直在考虑8位字并在想“它如何寻址所有那些内存位置？”但是，在32位和64位的机器上，“字”将是32位和64位，这也在上面链接的SO问题中提到了。所以，只有当我也遇到虚拟内存的相当基本的限制时，我的担忧才是合理的，就像pigworker所说的那样。在发布这个问题之前，我应该好好睡一晚上。 :) - carpemb

Answer 1

据我所知，零元构造函数需要1个机器字的存储空间（即指向静态分配数据的指针）。因此，无论您的数据结构有1个这样的构造函数还是1,000,000个，它仍然只占用1个机器字。

带有字段的构造函数需要更多的空间，但是 GHC 特殊处理零元构造函数，将单个静态单例在所有该值的实例之间共享。（例如，在整个程序中只有一个“True”）。

当惰性求值计算出已经存在的值时（任何值），GHC 会用“重定向”节点覆盖惰性求值节点，这需要一些空间。垃圾收集器定期删除重定向节点。

- MathematicalOrchid

---

这很有道理，所以我标记了这个问题已回答。事实证明，我最核心的困惑是关于“1个机器字”实际上意味着什么。但现在我已经对这个问题进行了自我教育。尽管这引发了一个更深入的问题，即内存碎片化。 - carpemb

如果零元构造函数只是指向共享对象的指针，那么这是否意味着我可能引用了一个非常远离实际调用点的对象（直到GC将其移动到更近的位置）？在这种情况下，将低级数据表示为未装箱的线性数据结构中的智能构造Word32或Word64值会更有效率，以换取更低的分配和更好的内存局部性，从而放弃空间效率？ - carpemb

“在内存中非常远”为什么会成为一个问题？这不是内存局部性的工作方式。程序中的所有零元构造器都在一个连续的内存块中，永远不会移动。这应该是相当缓存友好的。 - MathematicalOrchid

我也不知道它们被连续保留，这太好了解了。 - carpemb

值得注意的是，前几个构造函数（32位和64位分别为3个或7个）会受到特殊处理。对于这些构造函数，构造函数编号存储在节点指针中，以节省内存加载。 - augustss