3 ms·
Yes, I understand SSO. It’s just that these structures are already smaller than String/Vec would be by a third, so it’s harder to find something that fits. > i
by steveklabnik 8y ago
Yes, I understand SSO. It’s just that these structures are already smaller than String/Vec would be by a third, so it’s harder to find something that fits.
> if so, doesn't the implementation simply store a frame pointer inside the lambda,
Yes. That’s what I was talking about. That’s why you’d only be able to store one usize inline. You’d be replacing that single pointer with data. String and Vec have double the available space!
(Incidentally, String can’t do SSO in Rust due to it exposing the underlying storage; there are SSO strings available in a package if it’s significant in your use-case.)
- int_19h 8y agoBut if a lambda capture is already just a single pointer in this case, what exactly is on the heap when it's boxed? Like you said, it's one word for pointer to code, and one word for data. Why can't Box accommodate both directly within itself without heap-allocating? Is it the desire to have sizeof Box be a single word? But then why not offer SSO-enabled Box, or maybe even specifically FnBox, in a separate package, same as with strings?
- steveklabnik 8y agoOkay. 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.