代数数据类型的首选内存布局是什么？

Question

代数数据类型 (ADT) 是由具有可能递归的单元、乘积和和类型组成的类型。

考虑 Haskell 中的一个简单 ADT：

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

或者在 Rust 中使用不同的示例：

enum Message {
    Quit,
    ChangeColor(i32, i32, i32),
    Move { x: i32, y: i32 },
    Write(String),
}

Haskell（垃圾收集）和 Rust（非垃圾收集）如何在内存中实际表示这些，以及它们应该如何表示？

我主要对更简单的非垃圾收集情况感兴趣，但如果非垃圾收集，解决方案必须对堆和堆栈都可行，例如 Rust。

LLVM 或 C/C++ 中的表示是我感兴趣的。

使用第二个例子，我可以想到两个选项：

选项 1，使用联合：

enum MCtor { CQ, CCC, CM, CW  };

struct Message {
    enum MCtor ctor;
    union {
        void*; /* Quit */
        struct { int r; int g; int b; } /* ChangeColor */
        struct { int x; int y; } /* Move */
        struct { char* str; } /* Write */
    };
};

选项 2，使用单独的分配void*和（位）转换：

enum MCtor { CQ, CCC, CM, CW  };

typedef struct { int r; int g; int b; } ChangeColor;
typedef struct { int x; int y; } Move;
typedef struct { char* str; } Write;

struct Message {
    enum MCtor ctor;
    void* data;
};

模式匹配只是switchon 的问题msg -> ctor。

哪一个更可取，尤其是考虑到递归类型？

在我的脑海中，我猜想第一个的局部性更好并且它避免了负载，同时它可能会使用更多的内存......所以第二个选项有更好的内存占用但性能更差......？

Answer 1

以下是一些解释 GHC 如何实现数据结构的资源：

• Johan Tibell 在 ZuriHac 2015 上的演讲（视频） （幻灯片）（演讲从幻灯片 42 开始）
• GHC 评论：堆对象的布局