memory - 分配这个结构时，浪费了多少内存？

Question

我正在基于 Rust 中的 bplus 树构建索引树，并且到目前为止使用了父节点的定义:

struct Parent<T : std::fmt::Debug> {
    subtree_count : [usize; Arity],
    children      : [*mut ParentOrLeaf<T>; Arity],
    used          : usize, 
}

在我的 Arity=8 的 64 位计算机上，总内存需求为 136 字节。我正在使用 std::alloc::Layout::new和 std::alloc::alloc分配这个结构。但我担心，仅仅比 2 的幂(136 > 128)稍大一点，malloc 库最终会为此数据结构分配 256 个字节而不是 136 个字节。由于这是一个容器类型，浪费了一半的内存分配是 Not Acceptable 。std::alloc::Layout::new::<Parent<T>>().align()按预期报告布局为 8。
这个结构在分配时实际会占用多少内存？
如果浪费这么多内存，我可以换 subtree_count : [usize; Arity]至 subtree_count : [usize; Arity-1] ，这将使总内存为 128。然后重做我的库的所有优化逻辑以处理更改。但在此之前，我想确保这确实是必要的。

Answer 1

如果大小为 136，这意味着数组或向量中许多结构的连续分配将为每个结构使用恰好 136 个字节。
在单独分配一些结构体时，浪费的空间量仅取决于底层 malloc()策略，但不是分配类型的属性。
例如，在我的 stable-x86_64-unknown-linux-gnu 平台上对您的示例进行了快速而肮脏的改编，结果如下:

size 136
align 8
arr delta1 136
arr delta2 136
box delta1 144
box delta2 144

当然，不能保证三个分配的结构彼此靠近，但在这种特定情况下它们是，并且浪费的(不是真正浪费，而是分配器本身使用的)空间是 8 个字节。

struct ParentOrLeaf<T: std::fmt::Debug> {
    value: Option<T>,
}

const Arity: usize = 8;

struct Parent<T: std::fmt::Debug> {
    subtree_count: [usize; Arity],
    children: [*mut ParentOrLeaf<T>; Arity],
    used: usize,
}

fn main() {
    type P = Parent<i32>;
    let l = std::alloc::Layout::new::<P>();
    println!("size {}", l.size());
    println!("align {}", l.align());
    let ptr: *mut ParentOrLeaf<i32> = std::ptr::null_mut();
    let arr = [
        P {
            subtree_count: [0; Arity],
            children: [ptr; Arity],
            used: 0,
        },
        P {
            subtree_count: [0; Arity],
            children: [ptr; Arity],
            used: 0,
        },
        P {
            subtree_count: [0; Arity],
            children: [ptr; Arity],
            used: 0,
        },
    ];
    let a0 = &arr[0] as *const P as usize;
    let a1 = &arr[1] as *const P as usize;
    let a2 = &arr[2] as *const P as usize;
    println!("arr delta1 {}", a1 - a0);
    println!("arr delta2 {}", a2 - a1);
    let p0 = Box::new(P {
        subtree_count: [0; Arity],
        children: [ptr; Arity],
        used: 0,
    });
    let p1 = Box::new(P {
        subtree_count: [0; Arity],
        children: [ptr; Arity],
        used: 0,
    });
    let p2 = Box::new(P {
        subtree_count: [0; Arity],
        children: [ptr; Arity],
        used: 0,
    });
    let a0 = p0.as_ref() as *const P as usize;
    let a1 = p1.as_ref() as *const P as usize;
    let a2 = p2.as_ref() as *const P as usize;
    println!("box delta1 {}", a1 - a0);
    println!("box delta2 {}", a2 - a1);
}