memory - Rust - 为什么 malloc/alloc 和更多 'idiomatic' 方法之间的内存使用差异如此之大

Question

我一直在使用和修改这个库 https://github.com/sile/patricia_tree
有点困扰的一件事是在 node.rs 中使用了多少不安全，特别是，它被定义为只是指向某个堆位置的指针。在执行自述文件页面(维基百科输入)上列出的第一个基准测试时，PatriciaSet 使用 ~700mb(PatriciaSet 只是在它的根目录下保存一个节点)

pub struct Node<V> {
    // layout:
    // all these fields accessed with ptr.offset
    //   - flags: u8
    //   - label_len: u8
    //   - label: [u8; label_len]
    //   - value: Option<V>
    //   - child: Option<Node<V>>
    //   - sibling: Option<Node<V>>
    ptr: *mut u8,
    _value: PhantomData<V>,
}

并使用 malloc分配:

        let ptr = unsafe { libc::malloc(block_size) } as *mut u8;

有人告诉我这个内存没有正确对齐，所以我尝试添加新的 alloc api 并使用 Layout/alloc，这也仍然没有正确对齐，只是似乎“工作”。 full pr

       let layout = Layout::array::<u8>(block_size).expect("Failed to get layout");
       let ptr = unsafe { alloc::alloc(layout) as *mut u8 };

这个单一的变化，它也持有 layout在 ptr 指向的内存块中，在非常大的树的性能测试下，导致内存消耗增加了 40%。布局类型只有 2 个字宽，所以这是出乎意料的。对于相同的测试，这使用接近〜1000mb(与之前的700相比)
在另一次尝试中，我尝试删除大部分不安全的内容并使用更使用rust 的东西 full pr here

pub struct Node<V> {
    value: Option<V>,
    child: Option<*mut Node<V>>,
    sibling: Option<*mut Node<V>>,
    label: SmallVec<[u8; 10]>,
    _value: PhantomData<V>,
}

以您可能期望使用rust 的方式创建节点

        let child = child.map(|c| Box::into_raw(Box::new(c)));
        let sibling = sibling.map(|c| Box::into_raw(Box::new(c)));
        Node {
            value,
            child,
            sibling,
            label: SmallVec::from_slice(label),
            _value: PhantomData,
        }

性能方面，它大约相当于原始未修改的库，但它的内存消耗似乎并不比仅在 HashSet 中插入每个项目好多少，第一个基准测试使用约 1700mb。
使用节点的最终数据结构是压缩树或“帕特里夏树”。除了 Node 的结构之外，没有其他代码被更改。以及一些惯用地脱离这些变化的方法的实现。
我希望有人能告诉我究竟是什么导致了这些实现之间的内存消耗如此巨大的差异。在我看来，它们应该差不多。它们都分配了大约相同数量的宽度大致相同的字段。不安全的第一个能够在线存储动态标签长度，因此这可能是一个原因。但是 smallvec 应该能够用较小的标签尺寸做类似的事情(仅使用 Vec 更糟糕)。
寻找任何关于为什么最终结果如此不同的建议或帮助。如果好奇，运行这些的代码是 here尽管它分布在原始作者和我自己的仓库中
用于如何调查这些之间差异的工具也将公开!

Answer 1

您看到内存使用量增加的原因有两个。我将假设一个标准的 64 位 Unix 系统。
首先，一个指针是 8 个字节。一个 Option<*mut Node<V>>是 16 个字节，因为指针不受引用发生的可空优化的影响。引用永远不能为空，因此编译器可以转换 Option<&'a V>如果值为 None，则转换为空指针如果是 Some，则为常规指针，但指针可以为空，因此这里不会发生。 Rust 使枚举字段的大小与数据类型的大小相同，因此在这里每个指针使用 16 个字节。
处理这个问题的最简单和最安全的方法就是使用 Option<NonNull<Node<V>>> .这样做会使您的结构总共减少 16 个字节。
二、您的SmallVec大小为 32 字节。在某些情况下，它们避免需要堆分配，但尽管名称如此，它们并不一定很小。您可以使用常规 Vec或盒装切片，这可能会以额外分配为代价降低内存使用率。
通过这些更改并使用 Vec ，您的结构将是 48 字节大小。对于盒装切片，它将是 40。原来使用的是 72。您看到的节省多少取决于您的标签有多大，因为您需要为它们分配空间。
此结构所需的对齐是 8 个字节，因为任何类型(指针)的最大对齐是 8 个字节。即使在 x86-64 这样的架构上，所有类型都不需要对齐，它仍然更快，有时甚至更快，所以编译器总是这样做。
原始代码根本没有正确对齐，要么完全失败(在 SPARC 上)，要么性能很差(在 PowerPC 上)，要么如果启用(在 MIPS 上)需要在内核中设置对齐陷阱，或者如果没有则失败.内核中的对齐陷阱用于非对齐访问的性能非常糟糕，因为您必须执行完整的上下文切换才能加载和移动两个单词，因此大多数人将其关闭。
这没有正确对齐的原因是因为 Node包含一个指针，它出现在结构中的偏移量不能保证是 8 的倍数。如果它被重写为 child和 sibling属性首先出现，然后如果内存适当对齐(malloc 保证但您的 Rust 分配没有)，它将正确对齐。您可以创建一个合适的 Layout与 Layout::from_size_align(block_size, std::mem::align_of::<*mut Node>()) .
因此，虽然原始代码在 x86-64 上运行并节省了大量内存，但它的性能很差并且不可移植。
我在这个例子中使用的代码如下，加上一些关于 Rust 如何处理可空类型的知识以及关于 C 和内存分配的知识:

extern crate smallvec;
use smallvec::SmallVec;
use std::marker::PhantomData;
use std::ptr::NonNull;

pub struct Node<V> {
    value: Option<V>,
    child: Option<NonNull<Node<V>>>,
    sibling: Option<NonNull<Node<V>>>,
    label: Vec<u8>,
    _value: PhantomData<V>,
}

fn main() {
    println!("size: {}", std::mem::size_of::<Node<()>>());
}