3 ms·

> Collections are not parametrized by an allocator, like in C++ or (future) Rust. What does he mean by this?

Georgelemental 4y ago
My understanding is, instead of the allocator being a generic parameter of the type, it's a value you pass to the constructor.
- tialaramex 4y ago
  The crucial trick is that it's not just the constructor, it's everywhere which might allocate. Rust's proposed allocator API (what the article calls future Rust) takes an allocator for constructors, but the effect is the type parameter is just inferred during construction, the same way if you say OK, make me a Vec of this array of Strings, Rust infers the Vec's type Vec<String>. Zig's standard library provides both conventional compound structures like those I described for Rust, and "Unmanaged" variants in which you must provide an allocator every time you do anything which might allocate, so e.g. addOne on ArrayListUnmanaged requires the allocator, which it will only actually use if adding a single element to the ArrayList exceeded its current capacity. It will assume this is the correct allocator to de-allocate the old backing storage and allocate new storage, so you can't use this design to move from one allocator to another. Interestingly Zig's ensureTotalCapacity not only avoids the problem of C++ reserve where it destroys the amortized growth behaviour, but it actually insists on exponential growth even if that considerably outstrips the growth requested. Say we've got 15 Foozles in an ArrayList with capacity 16 (or Rust's Vec or C++ std::vector). We know we want to put 20 more foozles in, for a total of 35, although maybe more. Rust's Vec says OK, reserve(20), we were thinking of next growing from 16 to 32, but 35 won't fit in 32, so 35 it is. Capacity becomes 35. Popular C++ std::vector implementations likewise will pick 35 here. But Zig's ArrayList says 16 + 8 + 8 = 32 not big enough, try 32 + 16 + 8 = 56. Capacity becomes 56!
steveklabnik 4y ago
Psuedo-Rust code here, showing off both styles. Parameterized by an allocator: struct Foo<T, A: Allocator> { // ... } impl<T, A> Foo<T, A> { fn new() -> Foo<T, A> { // do something to make a new foo, calling functions via A } } contrast with "an allocator is passed in explicitly to every method which actually needs to allocate." struct Foo<T> { // ... } impl<T> Foo<T> { fn new<A: Allocator>(a: A) -> Foo<T> { // do something to make a new foo, calling functions via A } } (EDIT: "new" was a bad choice for me to pick here, see the child comment that uses 'put' instead; I was not trying to suggest that the allocator only parameterizes a constructor, but any call that would need to allocate.)
- MrBuddyCasino 4y ago
  Thanks for the example. I wasn't aware this is something that was planned for Rust, seems like a pretty large breaking change. Interesting!
  - steveklabnik 4y ago
    Nothing is breaking! The change isn't a move to a zig-like style, but instead, that in today's Rust, you have struct Foo<T> { // ... } and not struct Foo<T, A: Allocator> { // ... } This isn't breaking because there is a default type provided for A. The handwave is over "Today's Rust", as this machinery has already landed, in a sense, it's just not really possible to use with the standard library because the allocator API isn't fully stable. Here's an actual example: https://doc.rust-lang.org/stable/std/vec/struct.Vec.html https://doc.rust-lang.org/stable/std/vec/struct.Vec.html See that "A = Global"?
    - MrBuddyCasino 4y ago
      I see. I'm interested in the motivation and design goals behind it, is there something that spells those out? The only thing I could find quickly is this [0]. [0] https://internals.rust-lang.org/t/why-bring-your-own-allocator-apis-are-not-more-popular-in-rust/14494/16 https://internals.rust-lang.org/t/why-bring-your-own-allocat...
      - steveklabnik 4y ago
        https://rust-lang.github.io/rfcs/1974-global-allocators.html https://rust-lang.github.io/rfcs/1974-global-allocators.html was the original RFC. My vague understanding is that there's a working group https://github.com/rust-lang/wg-allocators https://github.com/rust-lang/wg-allocators The further I get from working on Rust day to day, the less I know about these things, so that's all I've got for you.
    - throwawaymaths 4y ago
      what if you want there to be individual allocators (of the same type) that you want to point differently based on <X condition>. For example in a M:N greenthreaded system perhaps you want each greenthread to have its own arena allocator. But you can't use something like threadlocal, because at any time a greenthread might move to any given OS thread? Is that possible in rust?

My understanding is, instead of the allocator being a generic parameter of the type, it's a value you pass to the constructor.

tialaramex 4y ago
The crucial trick is that it's not just the constructor, it's everywhere which might allocate. Rust's proposed allocator API (what the article calls future Rust) takes an allocator for constructors, but the effect is the type parameter is just inferred during construction, the same way if you say OK, make me a Vec of this array of Strings, Rust infers the Vec's type Vec<String>. Zig's standard library provides both conventional compound structures like those I described for Rust, and "Unmanaged" variants in which you must provide an allocator every time you do anything which might allocate, so e.g. addOne on ArrayListUnmanaged requires the allocator, which it will only actually use if adding a single element to the ArrayList exceeded its current capacity. It will assume this is the correct allocator to de-allocate the old backing storage and allocate new storage, so you can't use this design to move from one allocator to another. Interestingly Zig's ensureTotalCapacity not only avoids the problem of C++ reserve where it destroys the amortized growth behaviour, but it actually insists on exponential growth even if that considerably outstrips the growth requested. Say we've got 15 Foozles in an ArrayList with capacity 16 (or Rust's Vec or C++ std::vector). We know we want to put 20 more foozles in, for a total of 35, although maybe more. Rust's Vec says OK, reserve(20), we were thinking of next growing from 16 to 32, but 35 won't fit in 32, so 35 it is. Capacity becomes 35. Popular C++ std::vector implementations likewise will pick 35 here. But Zig's ArrayList says 16 + 8 + 8 = 32 not big enough, try 32 + 16 + 8 = 56. Capacity becomes 56!

steveklabnik 4y ago

Psuedo-Rust code here, showing off both styles. Parameterized by an allocator: struct Foo<T, A: Allocator> { // ... } impl<T, A> Foo<T, A> { fn new() -> Foo<T, A> { // do something to make a new foo, calling functions via A } } contrast with "an allocator is passed in explicitly to every method which actually needs to allocate." struct Foo<T> { // ... } impl<T> Foo<T> { fn new<A: Allocator>(a: A) -> Foo<T> { // do something to make a new foo, calling functions via A } } (EDIT: "new" was a bad choice for me to pick here, see the child comment that uses 'put' instead; I was not trying to suggest that the allocator only parameterizes a constructor, but any call that would need to allocate.)

MrBuddyCasino 4y ago
Thanks for the example. I wasn't aware this is something that was planned for Rust, seems like a pretty large breaking change. Interesting!
- steveklabnik 4y ago
  Nothing is breaking! The change isn't a move to a zig-like style, but instead, that in today's Rust, you have struct Foo<T> { // ... } and not struct Foo<T, A: Allocator> { // ... } This isn't breaking because there is a default type provided for A. The handwave is over "Today's Rust", as this machinery has already landed, in a sense, it's just not really possible to use with the standard library because the allocator API isn't fully stable. Here's an actual example: https://doc.rust-lang.org/stable/std/vec/struct.Vec.html https://doc.rust-lang.org/stable/std/vec/struct.Vec.html See that "A = Global"?
  - MrBuddyCasino 4y ago
    I see. I'm interested in the motivation and design goals behind it, is there something that spells those out? The only thing I could find quickly is this [0]. [0] https://internals.rust-lang.org/t/why-bring-your-own-allocator-apis-are-not-more-popular-in-rust/14494/16 https://internals.rust-lang.org/t/why-bring-your-own-allocat...
    - steveklabnik 4y ago
      https://rust-lang.github.io/rfcs/1974-global-allocators.html https://rust-lang.github.io/rfcs/1974-global-allocators.html was the original RFC. My vague understanding is that there's a working group https://github.com/rust-lang/wg-allocators https://github.com/rust-lang/wg-allocators The further I get from working on Rust day to day, the less I know about these things, so that's all I've got for you.
  - throwawaymaths 4y ago
    what if you want there to be individual allocators (of the same type) that you want to point differently based on <X condition>. For example in a M:N greenthreaded system perhaps you want each greenthread to have its own arena allocator. But you can't use something like threadlocal, because at any time a greenthread might move to any given OS thread? Is that possible in rust?