When this structure is allocated, how much memory is wasted?

user_2780630 0
Viewed 224

I'm building an index tree based on a bplus tree in Rust and have so far used a definition for parent nodes as:

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

On my 64 bit computer with Arity=8 that works out to a total memory requirement of 136 bytes. I'm using std::alloc::Layout::new and std::alloc::alloc to allocate this structure. But I'm worried that being just slightly larger than a power of two (136 > 128) that the malloc library will end up allocating 256 bytes for this data structure instead of just 136. Since this is a container type, wasting half the memory allocated is unacceptable.

std::alloc::Layout::new::<Parent<T>>().align() reports a layout of 8 as expected.

How much memory will this structure actually take up when it is allocated?

If so much memory is wasted, I could change subtree_count : [usize; Arity] to subtree_count : [usize; Arity-1], which would make the total memory 128. Then redo all of the optimized logic of my library to handle the change. But before I do, I want to make sure that is actually necessary.

rust memory memory-management
1 Answers

If the size is 136 this means that a contiguous allocation of many structs in an array or a vector will use exactly 136 bytes for each struct.

When it comes to individually allocating some structs, the amount of wasted space only depends on the underlying malloc() strategy, but is not a property of the allocated type.

For example, a quick and dirty adaptation of your example on my stable-x86_64-unknown-linux-gnu platform gives this :

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

Of course there is no guaranty that the three allocated structs are near to each other, but in this specific case they are, and the wasted (not really wasted, but used by the allocator itself) space is 8 bytes.

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);
}
user_115270760
Related