如何创建一个 Rust 类型，该类型可以在单个字的大小内保存整数或指针？

Question

如何创建一个 Rust 类型，该类型可以在单个字的大小内保存整数或指针？

pointersoptimizationrustocamlunion-types

3

我是一个有用的助手，可以翻译文本。

（以下为翻译内容）：

我在谈论使用拳击作为一种运行时区分整数和指针的方式。这是一些编程语言用来帮助垃圾回收（例如OCaml）的技术，而不是 Rust 的 Box<T> 类型。

我有一个类似于以下代码的 Rust 枚举：

#[derive(Clone, Copy, Debug, PartialEq)]
enum Type<'ts> {
    TVar(usize),
    Constructed(&'ts ConstructedType<'ts>),
}

据我所知，此枚举的内存布局将占用两个字。一个用于标记，一个用于有效负载。如果可能的话，我想将内存适配到单个字中。

像OCaml这样的语言使用一种称为“整数装箱”的技术，利用了指针对齐的事实。这意味着最低位将为0。如果您将整数中的位向左移动一位并将整数的最低位设置为1，则可以使用该位作为标记，代价是损失一位整数精度。

Rust指针是否保证对齐？我如何在Rust中为我的类型实现这个技术？

- Calebmer

如果您将整数中的位向左移动一位，并将整数的最低位设置为1，那么您可以将该位用作标签，但代价是损失了一个整数精度位。是的，但这不是usize的目的，而且使用地址来做这个操作完全由实现定义。据我所知，Rust不建议这样做，因为这样做是完全不安全的。 - undefined

此外，这种方法也存在运行时成本：“即使是最警觉的读者也会对使用这种标记表示的整数算术的性能影响产生疑问。由于设置了最低位，对整数的任何操作都必须将最低位向右移动来恢复“本机”值。在这种情况下，原生代码 OCaml 编译器会生成高效的 x86 汇编代码，利用现代处理器指令尽可能隐藏额外的移位。加法只需要一个 LEA x86 指令，减法可能需要两个指令，而乘法则需要更多一些。” - undefined

2

但是我认为如果你使用原始指针和原始枚举（也称为C枚举），这是可能的，但正如我所说的，这样做将不太可移植，并且我认为除非你在嵌入式系统上工作，否则像这样稍微节省一点内存空间是不值得的。 - undefined

我理解安全性/运行时影响。我想知道如何实现这个优化，以便查看它是否适用于我的程序。但你可能是对的，我正在尝试进行优化。感谢提供一些理由。 - undefined

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Hall · Accepted Answer

我可能没有完全理解你的意思，但是我认为你需要一个union。

#[derive(Clone, Copy, Debug, PartialEq)]
enum Type<'ts> {
    TVar(usize),
    Constructed(&'ts ConstructedType<'ts>),
}

union CompactType<'ts> {
    num: usize,
    ptr: &'ts ConstructedType<'ts>
}

impl<'ts> From<CompactType<'ts>> for Type<'ts> {
    fn from(compact: CompactType<'ts>) -> Type<'ts> {
        unsafe {
            if compact.num & 1 == 1 {
                Type::TVar(compact.num >> 1)
            } else {
                Type::Constructed(compact.ptr)
            }
        }
    }
}

请注意，访问 union 的成员是不安全的，您必须确保所有不变量都得到执行。例如，您必须明确检查 CompactType 是否正确创建并且值在范围内，并防止对象在未经过这些检查的情况下被构造。

我建议为 CompactType 添加构造函数，以返回 Result 或 Option，以防您尝试使用过大的数字或指向未正确对齐的类型的指针。当TryFrom特性稳定后，您可以使用它，但在此期间：

enum CompactConvertError {
    NumTooBig(String),
    PtrNotAligned(String),
}

impl<'ts> Type<'ts> {
    fn to_compact(&self) -> Result<CompactType<'ts>, CompactConvertError> {
        match self {
            Type::TVar(num) => {
                if num >> (mem::size_of::<usize>() * 8 - 1) == 1 {
                    Err(CompactConvertError::NumTooBig(
                        String::from("The last bit of the usize cannot be used here"))
                    )
                } else {
                    Ok(CompactType { num: num << 1 | 1usize })
                }   
            },
            Type::Constructed(c) => {
                if mem::align_of_val(*c) % 2 == 1 {
                    Err(CompactConvertError::PtrNotAligned(
                        String::from("The pointer must be to a type with even alignment"))
                    )
                } else {
                    Ok(CompactType { ptr: c })
                }
            }
        }
    } 
}

这应该足够灵活，可以用一个通用类型参数替换ConstructedType。唯一的限制是不要将其从引用更改为拥有的值，否则您将不得不担心正确地丢弃它——在稳定的Rust中无法对union类型进行。

至于对齐方式，如果ConstructedType只有1个字节大小，则需要添加对齐方式，以确保它只在偶数字节上，否则Rust可能会选择更紧密地打包它们：

#[align(2)]
struct ConstructedType<'ts> { 
    // ...
}

如果大小超过2字节，绝对不要添加#[align(2)]。也许其他人可以提供更加稳健的解决方案。