5 ms·
Okay. let's talk about Box. Box<T> is always a single usize if T is Sized, and two usizes if T is not. T is not sized when it's a trait. If T is Sized, then Bo
by steveklabnik 8y ago
Okay. let's talk about Box.
Box<T> is always a single usize if T is Sized, and two usizes if T is not. T is not sized when it's a trait. If T is Sized, then Box<T> puts the T on the heap, and the Box itself is a pointer to it.
Box<Fn()> is a "trait object" the double pointer. It looks like this:
pub struct TraitObject {
pub data: *mut (),
pub vtable: *mut (),
}
The first pointer is a pointer to the data, and the second pointer is a pointer to a vtable. So in the Box<Fn()> case, data is the captures, and the vtable is the code.
So when you write code like this:
// in a function body somewhere
let x = 5;
let f = Box::new(|| x);
Rust generates code that looks roughly like this:
// at item level
struct Env<'a> {
x: &'a i32,
}
// an impl of Fn for Env, i'm not writing that out
// in a function body somewhere
let x = 5;
let env = Env { x: &x };
let memory = GlobalAlloc::alloc(..);
// copy env into memory, i'm not writing that out
let f = TraitObject {
data: memory,
vtable: pointer_to_vtable_im_not_writing_out,
}
make sense? The Env is on the heap.
Before I move on, It's worth noting that, in the case of a closure which has no captures:
let f = Box::new(|| 5);
you get:
// at item level
struct Env;
// an impl of Fn for Env, i'm not writing that out
// in a function body somewhere
let x = 5;
let env = Env;
let memory = GlobalAlloc::alloc(..);
// copy env into memory, i'm not writing that out
let f = TraitObject {
data: memory,
vtable: pointer_to_vtable_im_not_writing_out,
}
since Env is a unit struct, it has zero size, and so gets optimized out at compile time, which also ends up removing all of the data stuff, which means it's back to a regular function pointer (fn instead of Fn).
Anyway.
So, if we were to do an SSO-like optimization here, we only have a single usize, the data pointer, to work with. We still need the function pointer, so we can't re-purpose it.
In theory, that would mean that an environment that has a total size of less than usize could be stored inline. It's not clear to me how often this is true, and if it would be worth it. But none of these internal representations are stable, so it's possible for Box<Fn()> at least.
Compare this to std::string. Different compilers implement it differently, but let's look at gcc:
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/std/string#L64 https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-...
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/basic_string.h#L156-L165 https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-...
You've got a pointer to the data, the size, and a union of the buffer vs the capacity. In the end, on a 64 bit system, this is 32 total bytes of space! Box<Fn()> by contrast, is 16 bytes total, and we can only use 8 bytes of that. Additionally, strings often do have individual byte data, but closures, given that they capture by default, have a size of at least 8. maybe a move closure that has a bunch of small numbers in it might make a good fit for some sort of SSO-style optimization here, but environments tend to be bigger and space is smaller than strings.
Does that all make sense?
- int_19h 8y agoNot quite - that still doesn't explain why there can't be an SSO-optimized FnBox with extra padding that's there specifically to fit the kind of Fn that only needs to store the frame pointer, inline on the stack. In fact, now I'm even more confused as to why it can't be done generically for Box<Fn>: > The first pointer is a pointer to the data, and the second pointer is a pointer to a vtable. So in the Box<Fn()> case, data is the captures, and the vtable is the code. If a given lambda can capture via a single frame pointer (because it borrows everything), why can't that frame pointer just be stored directly in the `data` field? Why does it have to indirected, with data pointing to another pointer on the heap? And if borrow-capturing lambdas don't actually capture via frame pointer, why not? Or are you saying that lambdas that borrow everything aren't actually all that common? But if they aren't, then why does capture by borrowing reference the default for lambdas?
- steveklabnik 8y ago> that still doesn't explain why there can't There can, you'd have to write it yourself. > If a given lambda can capture via a single frame pointer (because it borrows everything), why can't that frame pointer just be stored directly in the `data` field? If there's a single thing it's borrowing, then yes, it could. If there's any more than one, it won't fit. > Or are you saying that lambdas that borrow everything aren't actually all that common? I'm saying that closures that borrow exactly one thing aren't actually all that common.
- int_19h 8y agoI think you're misunderstanding what I mean by "frame pointer". What I'm saying is that if a lambda is capturing local variables from a single stack frame by borrow (which ensures that it can't outlive them), then it doesn't need individual pointers to every variable. It just needs a pointer to the stack frame where they live, and it can access the individual variables by offset, same as the function to which that frame belongs does. It's compiler magic, of course - i.e. it means that such lambdas don't have a straightforward translation to a regular Rust object. But it's magic that behaves as if you had individual references, so it's a completely transparent optimization except for size of the resulting object. On Intel architectures, you can think of it as stashing away EBP/RBP. And lambdas that only capture locals from one frame, and all of them by reference, seems like a very common kind of lambda to me, making that optimization worthwhile.