11 ms·

Rust vector guarantees

68 points by chewbacha 9y ago

saagarjha 9y ago
Just curious: what are differences between the guarantees provided by Rust's vectors and std::vector from C++?
- Manishearth 9y ago
  It's hard to know what really you're asking for, and how much you know about Rust. Rust itself has a bunch of guarantees. Rust's vector is guaranteed to work well within that framework. So, - No dangling pointers / UAF from stuff it gives you - No iterator invalidation from iterators you get from it - You can't push to it and invalidate references to its insides (this is really the iterator invalidation one over again) - You can't use it in a way that will not be data race safe These are all Rust guarantees; Vec just adheres to them. You can say that these guarantees are Vec guarantees too (which is why I'm saying "I'm not sure what you're asking for). c++ std::vector does not have these guarantees because c++ does not have these guarantees. You can get some of these guarantees by restricting yourself to coding a certain way but they kinda fall apart when stuff gets complex in my experience. Aside from that it's basically the same guarantees as std::vector, i.e. "will store stuff in contiguous space", "will allocate buffer with extra capacity as it grows" (this isn't actually a guarantee, but it's not going to change for either). One thing Rust's vector guarantees that C++ doesn't is that Rust's vector will not store elements inline; anything (with nonzero size) you push into it will be heap allocated. Rust's vector also never implicitly performs deep copies, but this isn't really a guarantee. Rust also has a concept of zero sized types, which C++ does not, and Rust's vector deals with them in a certain way, however since C++ doesn't have these types you can't really compare. It's possible C++ guarantees a drop order for where Rust's vector does not. I'm not sure.
  - mehrdadn 9y ago
    > You can get some of these guarantees by restricting yourself to coding a certain way but they kinda fall apart when stuff gets complex in my experience. I would assume that in Rust it would fall apart just the same, except perhaps at compile-time rather than at run-time?
    - Manishearth 9y ago
      > I would assume that in Rust it would fall apart just the same, except perhaps at compile-time rather than at run-time? No, because Rust gives you the tools to compartmentalize this stuff pretty well. Yes, if you write an unsound program it will fail to compile, but the language also guides you in the direction of not writing one, so huge complicated codebases written in 100% safe rust are possible and do compile. With C++ as complexity grows it's harder to keep stuff safe, in my experience. YMMV.
  - saagarjha 9y ago
    > how much you know about Rust Very little, so please bear with me ;) For example, from the linked page: > Most fundamentally, Vec is and always will be a (pointer, capacity, length) triplet. No more, no less. Does C++ also provide this guarantee? > Vec will never perform a "small optimization" where elements are actually stored on the stack for two reasons: Does C++ do this? and from your response: > No iterator invalidation from iterators you get from it How are you guaranteeing this? C++ doesn't, so what is going on behind the scenes to make this work in Rust? As you can see, I don't know enough about C++ as I would like either…
    - Manishearth 9y ago
      > Does C++ also provide this guarantee? I don't think it does. It might. > Does C++ do this? IIRC C++ is allowed to perform the optimization. I don't recall if any current implementations do. They might. Edit: I'm wrong, it's not, however std::string is allowed to. > How are you guaranteeing this? C++ doesn't, so what is going on behind the scenes to make this work in Rust? Because Rust has an entire system of ownership and borrowing which exists at compile time to ensure these things don't happen.
      - pbsd 9y ago
        C++ is not allowed to do the small buffer optimization for std::vector<T>. You'll find a number of small_vector<T> classes from third parties, though. The reason is that std::swap(v1, v2) must never invalidate existing iterators and/or references to elements into either vector, which the optimization would clearly break. std::string is the type you may be thinking of, where the standard does make a special exception to enable the SSO.
        Manishearth 9y ago
        aha! good to know. Yeah, I knew string can do SSO, so I assumed std::vector was allowed to as well.
      - saagarjha 9y ago
        Well, I must be misunderstanding how iterators work in Rust, then. AFAIK in C++ an iterator is a thin wrapper around a pointer in memory, and resizing the container can cause the underlying "base" array to move around to somewhere else if it's reallocated–thus, the invalidation of the old iterator. What is a Rust iterator doing in this case?
  - smitherfield 9y ago
    >One thing Rust's vector guarantees that C++ doesn't is that Rust's vector will not store elements inline; anything (with nonzero size) you push into it will be heap allocated. I believe this is incorrect and small-vector optimization is in fact disallowed by the C++ standard. In any case, standard or not, no implementation is ever going to do SVO because it would require a branch on every access, making them incompatible with SIMD instructions. >Rust also has a concept of zero sized types, which C++ does not No, C++ allows this optimization too, it just requires that the "sizeof" operator always returns an integer >= 1.
  - Matthias247 9y ago
    > One thing Rust's vector guarantees that C++ doesn't is that Rust's vector will not store elements inline; anything (with nonzero size) you push into it will be heap allocated. Does C++ really not guarantee this? If yes then I probably have written quite a bit of "broken" code, which assumes that element addresses stay constant during moves of the container. std::vector<A> vec1; // And initialize it A* a = &vec1[0]; auto vec2 = std::move(vec1); A* b = &vec2[0]; assert(a == b);
mehrdadn 9y ago
This seems wrong to me: > Vec will never perform a "small optimization" where elements are actually stored on the stack [because] it would penalize the general case, incurring an additional branch on every access. I don't follow this. I can see appending to a vector requiring an extra branch, but why would every access (like, say , vec[i] = 0) need an extra branch?
- barrkel 9y ago
  if (vec.size < THRESHOLD) { vec.local[index] = value; } else { vec->heap[index] = value; }
  - mehrdadn 9y ago
    Didn't they say Vec is a (pointer, capacity, length) triplet though? Wouldn't it just be vec.pointer[index] = value regardless of whether the pointer points to the stack or the heap?
    - barrkel 9y ago
      pointer would be pointing at internal structure memory, it would need to change on every copy then.
      - mehrdadn 9y ago
        > pointer would be pointing at internal structure memory, it would need to change on every copy then. Sure, sounds fine to me. What's wrong with this? The pointer would need to change on every copy anyway, since it'd need to point to a new buffer even if it were pointing to the heap.
        barrkel 9y ago
        It sounds fine from a C++ world of copy constructors. I think copy constructors aren't worth the exception safety downsides.
OtterCoder 9y ago
The one part of the spec that gives me pause is the fact that dropped memory isn't cleared. That sort of behavior has been the cause of so many network exploits. Is it worth worrying about here?
- JoshTriplett 9y ago
  If you want memory cleared on drop, you could do that by setting the global allocator to one that clears memory on free, rather than changing individual data structures.
  - mehrdadn 9y ago
    I suspect he doesn't want to pay the performance penalty on all containers, just for a particular container.
    - sitkack 9y ago
      As noted elsewhere in this thread, one can implement a Drop trait the clears memory on deallocation. https://github.com/cesarb/clear_on_drop https://github.com/cesarb/clear_on_drop
- cwzwarich 9y ago
  If your language (and program in Rust's case, since Rust has unsafe code) is memory safe, then the contents of deallocated memory shouldn't be internally observable. Technically speaking, you could add an API to Rust that returns an Option of a buffer by virtual address, and this would be completely safe. If you're truly concerned about the implications of preserving the contents of existing memory, you need to do it at a lower level in the allocator anyways. In the case that a pushing elements on a Vec causes the Vec's buffer to be reallocated, the allocator is free to either extent the existing allocation of the buffer or make a new allocation. If the allocator chooses the latter, then clearing the memory upon drop doesn't clear the old copy.
  - mehrdadn 9y ago
tom_mellior 9y ago
I don't understand the following sentence: > ... it is strongly recommended that you only free memory allocated by a Vec by creating a new Vec and dropping it. Could someone parse this for me? To me, it reads like "to free memory allocated by a Vec v, create a new Vec w and drop it (i.e., w)". This is obviously not what it is intended. What's the role of the second Vec? Is this only in a context where v is empty but its memory not yet freed? If so, why wouldn't shrink_to_fit work in that case?
- Manishearth 9y ago
  This is in case you turn the Vec into a raw pointer (using as_ptr() and mem::forget) so that you can pass ownership over FFI or something. In this case it is not recommended that you free it by calling free(), it is recommended that you free it by using from_raw_parts to reconstruct a new vector and let it drop. You need the second vec because the first vec is gone at this point. If it wasn't gone you could just let the destructor run. In Rust Vec and Box also work as the malloc primitives; if you absolutely need to allocate contiguous memory of runtime-known size the best way to do it is to allocate a Vec and then extract the pointer from it. (There is a proper allocation API coming soon; and of course you can just call malloc/free, but this is the recommended way of doing it)
- steveklabnik 9y ago
  I've filed a bug to elaborate, thanks! https://github.com/rust-lang/rust/issues/46879 https://github.com/rust-lang/rust/issues/46879
  - tom_mellior 9y ago
    Cool, thanks to both of you for the quick report and fix!

68 points by chewbacha 9y ago

saagarjha 9y ago

Just curious: what are differences between the guarantees provided by Rust's vectors and std::vector from C++?

Manishearth 9y ago
It's hard to know what really you're asking for, and how much you know about Rust. Rust itself has a bunch of guarantees. Rust's vector is guaranteed to work well within that framework. So, - No dangling pointers / UAF from stuff it gives you - No iterator invalidation from iterators you get from it - You can't push to it and invalidate references to its insides (this is really the iterator invalidation one over again) - You can't use it in a way that will not be data race safe These are all Rust guarantees; Vec just adheres to them. You can say that these guarantees are Vec guarantees too (which is why I'm saying "I'm not sure what you're asking for). c++ std::vector does not have these guarantees because c++ does not have these guarantees. You can get some of these guarantees by restricting yourself to coding a certain way but they kinda fall apart when stuff gets complex in my experience. Aside from that it's basically the same guarantees as std::vector, i.e. "will store stuff in contiguous space", "will allocate buffer with extra capacity as it grows" (this isn't actually a guarantee, but it's not going to change for either). One thing Rust's vector guarantees that C++ doesn't is that Rust's vector will not store elements inline; anything (with nonzero size) you push into it will be heap allocated. Rust's vector also never implicitly performs deep copies, but this isn't really a guarantee. Rust also has a concept of zero sized types, which C++ does not, and Rust's vector deals with them in a certain way, however since C++ doesn't have these types you can't really compare. It's possible C++ guarantees a drop order for where Rust's vector does not. I'm not sure.
- mehrdadn 9y ago
  > You can get some of these guarantees by restricting yourself to coding a certain way but they kinda fall apart when stuff gets complex in my experience. I would assume that in Rust it would fall apart just the same, except perhaps at compile-time rather than at run-time?
  - Manishearth 9y ago
    > I would assume that in Rust it would fall apart just the same, except perhaps at compile-time rather than at run-time? No, because Rust gives you the tools to compartmentalize this stuff pretty well. Yes, if you write an unsound program it will fail to compile, but the language also guides you in the direction of not writing one, so huge complicated codebases written in 100% safe rust are possible and do compile. With C++ as complexity grows it's harder to keep stuff safe, in my experience. YMMV.
- saagarjha 9y ago
  > how much you know about Rust Very little, so please bear with me ;) For example, from the linked page: > Most fundamentally, Vec is and always will be a (pointer, capacity, length) triplet. No more, no less. Does C++ also provide this guarantee? > Vec will never perform a "small optimization" where elements are actually stored on the stack for two reasons: Does C++ do this? and from your response: > No iterator invalidation from iterators you get from it How are you guaranteeing this? C++ doesn't, so what is going on behind the scenes to make this work in Rust? As you can see, I don't know enough about C++ as I would like either…
  - Manishearth 9y ago
    > Does C++ also provide this guarantee? I don't think it does. It might. > Does C++ do this? IIRC C++ is allowed to perform the optimization. I don't recall if any current implementations do. They might. Edit: I'm wrong, it's not, however std::string is allowed to. > How are you guaranteeing this? C++ doesn't, so what is going on behind the scenes to make this work in Rust? Because Rust has an entire system of ownership and borrowing which exists at compile time to ensure these things don't happen.
    - pbsd 9y ago
      C++ is not allowed to do the small buffer optimization for std::vector<T>. You'll find a number of small_vector<T> classes from third parties, though. The reason is that std::swap(v1, v2) must never invalidate existing iterators and/or references to elements into either vector, which the optimization would clearly break. std::string is the type you may be thinking of, where the standard does make a special exception to enable the SSO.
      - Manishearth 9y ago
        aha! good to know. Yeah, I knew string can do SSO, so I assumed std::vector was allowed to as well.
    - saagarjha 9y ago
      Well, I must be misunderstanding how iterators work in Rust, then. AFAIK in C++ an iterator is a thin wrapper around a pointer in memory, and resizing the container can cause the underlying "base" array to move around to somewhere else if it's reallocated–thus, the invalidation of the old iterator. What is a Rust iterator doing in this case?
- smitherfield 9y ago
  >One thing Rust's vector guarantees that C++ doesn't is that Rust's vector will not store elements inline; anything (with nonzero size) you push into it will be heap allocated. I believe this is incorrect and small-vector optimization is in fact disallowed by the C++ standard. In any case, standard or not, no implementation is ever going to do SVO because it would require a branch on every access, making them incompatible with SIMD instructions. >Rust also has a concept of zero sized types, which C++ does not No, C++ allows this optimization too, it just requires that the "sizeof" operator always returns an integer >= 1.
- Matthias247 9y ago
  > One thing Rust's vector guarantees that C++ doesn't is that Rust's vector will not store elements inline; anything (with nonzero size) you push into it will be heap allocated. Does C++ really not guarantee this? If yes then I probably have written quite a bit of "broken" code, which assumes that element addresses stay constant during moves of the container. std::vector<A> vec1; // And initialize it A* a = &vec1[0]; auto vec2 = std::move(vec1); A* b = &vec2[0]; assert(a == b);

mehrdadn 9y ago

This seems wrong to me: > Vec will never perform a "small optimization" where elements are actually stored on the stack [because] it would penalize the general case, incurring an additional branch on every access. I don't follow this. I can see appending to a vector requiring an extra branch, but why would every access (like, say , vec[i] = 0) need an extra branch?

barrkel 9y ago
if (vec.size < THRESHOLD) { vec.local[index] = value; } else { vec->heap[index] = value; }
- mehrdadn 9y ago
  Didn't they say Vec is a (pointer, capacity, length) triplet though? Wouldn't it just be vec.pointer[index] = value regardless of whether the pointer points to the stack or the heap?
  - barrkel 9y ago
    pointer would be pointing at internal structure memory, it would need to change on every copy then.
    - mehrdadn 9y ago
      > pointer would be pointing at internal structure memory, it would need to change on every copy then. Sure, sounds fine to me. What's wrong with this? The pointer would need to change on every copy anyway, since it'd need to point to a new buffer even if it were pointing to the heap.
      - barrkel 9y ago
        It sounds fine from a C++ world of copy constructors. I think copy constructors aren't worth the exception safety downsides.

OtterCoder 9y ago

The one part of the spec that gives me pause is the fact that dropped memory isn't cleared. That sort of behavior has been the cause of so many network exploits. Is it worth worrying about here?

JoshTriplett 9y ago
If you want memory cleared on drop, you could do that by setting the global allocator to one that clears memory on free, rather than changing individual data structures.
- mehrdadn 9y ago
  I suspect he doesn't want to pay the performance penalty on all containers, just for a particular container.
  - sitkack 9y ago
    As noted elsewhere in this thread, one can implement a Drop trait the clears memory on deallocation. https://github.com/cesarb/clear_on_drop https://github.com/cesarb/clear_on_drop
cwzwarich 9y ago
If your language (and program in Rust's case, since Rust has unsafe code) is memory safe, then the contents of deallocated memory shouldn't be internally observable. Technically speaking, you could add an API to Rust that returns an Option of a buffer by virtual address, and this would be completely safe. If you're truly concerned about the implications of preserving the contents of existing memory, you need to do it at a lower level in the allocator anyways. In the case that a pushing elements on a Vec causes the Vec's buffer to be reallocated, the allocator is free to either extent the existing allocation of the buffer or make a new allocation. If the allocator chooses the latter, then clearing the memory upon drop doesn't clear the old copy.
- mehrdadn 9y ago

tom_mellior 9y ago

I don't understand the following sentence: > ... it is strongly recommended that you only free memory allocated by a Vec by creating a new Vec and dropping it. Could someone parse this for me? To me, it reads like "to free memory allocated by a Vec v, create a new Vec w and drop it (i.e., w)". This is obviously not what it is intended. What's the role of the second Vec? Is this only in a context where v is empty but its memory not yet freed? If so, why wouldn't shrink_to_fit work in that case?

Manishearth 9y ago
This is in case you turn the Vec into a raw pointer (using as_ptr() and mem::forget) so that you can pass ownership over FFI or something. In this case it is not recommended that you free it by calling free(), it is recommended that you free it by using from_raw_parts to reconstruct a new vector and let it drop. You need the second vec because the first vec is gone at this point. If it wasn't gone you could just let the destructor run. In Rust Vec and Box also work as the malloc primitives; if you absolutely need to allocate contiguous memory of runtime-known size the best way to do it is to allocate a Vec and then extract the pointer from it. (There is a proper allocation API coming soon; and of course you can just call malloc/free, but this is the recommended way of doing it)
steveklabnik 9y ago
I've filed a bug to elaborate, thanks! https://github.com/rust-lang/rust/issues/46879 https://github.com/rust-lang/rust/issues/46879
- tom_mellior 9y ago
  Cool, thanks to both of you for the quick report and fix!