代数数据类型 (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*
和(位) Actor :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;
};
模式匹配只是
switch
的问题在 msg -> ctor
.哪一个更可取,尤其是考虑到递归类型?
在我的脑海中,我猜想第一个的局部性更好并且它避免了负载,同时它可能会使用更多的内存......所以第二个选项有更好的内存占用但性能更差......?
最佳答案
以下是一些解释 GHC 如何实现数据结构的资源:
关于llvm - 代数数据类型的首选内存布局是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37417782/