5 ms·

This may be way too much for this topic, but where do closures get stored?

by madeuptempacct 8y ago

sam0x17 8y ago
If they are "boxed" they are on the heap, otherwise they are on the stack.
- int_19h 8y ago
  Don't they do small object optimization? In C++, implementations of std::function usually do that to avoid allocating for most common cases.
  - steveklabnik 8y ago
    Closures don't implicitly box, so any boxing would be done by the user directly, and so that would be up to them.
    - int_19h 8y ago
      I meant the Box type itself. In C++, std::string and std::function are usually intentionally padded, so that when the data is small enough, it can fit inside the object itself, rather than storing the pointer to heap-allocated storage.
      - steveklabnik 8y ago
        A Box'd Fn is two pointers: one to the code, and one to the data. The only way that this would work is if the data was a single usize, which is not likely to be many useful closures. In theory it could happen, I guess...
        int_19h 8y ago
        The idea is that you intentionally pad your type with fields that don't do anything other than provide a scratchpad for extra storage, much like over-allocating an array to avoid resizing on append. If the stored data is smaller, those go unused, so if you pick the wrong amount, the overhead is too great. But if you hit the sweet spot, it has very significant perf benefits, not only because it avoids hitting the allocator on copies, but also because of data locality. BTW, why wouldn't a lambda with a single usize field be common? I thought Rust captures everything by borrow by default; if so, doesn't the implementation simply store a frame pointer inside the lambda, and use it to access the captured variables? It seems like an obvious optimization...
        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 ago
        But 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 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?
glittery 8y ago
Closures have known size at compile-time, so they can be stored anywhere at all, although their types can't be named yet, so I don't think they can be stored in static memory.

This may be way too much for this topic, but where do closures get stored?

sam0x17 8y ago

If they are "boxed" they are on the heap, otherwise they are on the stack.

int_19h 8y ago
Don't they do small object optimization? In C++, implementations of std::function usually do that to avoid allocating for most common cases.
- steveklabnik 8y ago
  Closures don't implicitly box, so any boxing would be done by the user directly, and so that would be up to them.
  - int_19h 8y ago
    I meant the Box type itself. In C++, std::string and std::function are usually intentionally padded, so that when the data is small enough, it can fit inside the object itself, rather than storing the pointer to heap-allocated storage.
    - steveklabnik 8y ago
      A Box'd Fn is two pointers: one to the code, and one to the data. The only way that this would work is if the data was a single usize, which is not likely to be many useful closures. In theory it could happen, I guess...
      - int_19h 8y ago
        The idea is that you intentionally pad your type with fields that don't do anything other than provide a scratchpad for extra storage, much like over-allocating an array to avoid resizing on append. If the stored data is smaller, those go unused, so if you pick the wrong amount, the overhead is too great. But if you hit the sweet spot, it has very significant perf benefits, not only because it avoids hitting the allocator on copies, but also because of data locality. BTW, why wouldn't a lambda with a single usize field be common? I thought Rust captures everything by borrow by default; if so, doesn't the implementation simply store a frame pointer inside the lambda, and use it to access the captured variables? It seems like an obvious optimization...
        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 ago
        But 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 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?

glittery 8y ago

Closures have known size at compile-time, so they can be stored anywhere at all, although their types can't be named yet, so I don't think they can be stored in static memory.