4 ms·

I work on the protobuf team at Google, and I'm a big fan of Rust, though I haven't written much actual Rust except a bunch of Project Euler solutions. For prot

I work on the protobuf team at Google, and I'm a big fan of Rust, though I haven't written much actual Rust except a bunch of Project Euler solutions. For protobuf in C++, we've been moving more and more in the direction of using arenas for memory allocation. When you parse a protobuf, it creates a tree of objects that are usually all deleted at the same time. Freeing an arena is much, much cheaper than traversing the tree of objects and calling free() on each one. My dream has been that Rust protobuf could support arenas as well as C++, but use Rust's type system to make it all provably correct at compile time (in C++ the lifetime management is inherently manual and unsafe). For absolute top performance, arenas will always beat trees of unique pointers (which I think corresponds to Rust's Box<> type). I don't know Rust's type/lifetime system well enough to know if this is possible. I was looking recently at arenas in Rust and I noticed that Rust's version of placement new seems to be stalled: "Unfortunately the path forward for placement new in Rust does not look good right now, so I've reverted this crate to work more like a memory heap where stuff can be put, but not constructed in place." https://docs.rs/light_arena/1.0.1/light_arena/ https://docs.rs/light_arena/1.0.1/light_arena/ Does anyone know more about this?

staticassertion 6y ago
AFAIK the current method for hacking in placement new is to use something like this: https://github.com/glandium/boxext https://github.com/glandium/boxext Some more context. There used to be a `box` keyword too. https://github.com/rust-lang/rust/issues/50047 https://github.com/rust-lang/rust/issues/50047
pcwalton 6y ago
Placement new is just an optimization to avoid the initial memcpy from the stack in cases in which LLVM can't work it out itself. I don't believe that placement new ever enables semantics that aren't possible with plain old move semantics.
- haberman 6y ago
  Ah, in that case it sounds like heterogenous arenas are more or less a solved problem in Rust, even if they aren't necessarily 100% optimal. Probably the more difficult piece then is just how to model arena ownership of a tree of objects that all have links between them. We want to guarantee that links to sub-messages remain valid, which we would expect to be true if they are all in the same arena. But I believe Rust allows moving/swapping objects in and out of the arena?
  - eddyb 6y ago
    > heterogenous arenas are more or less a solved problem in Rust To expand a bit on what pcwalton said: Rust never had a concept of a type you can't move (we likely can't ever introduce it) and placement was never about "in-place construction" (Rust doesn't even have a concept of "construction", but rather focuses on initialization). There is `Pin<&mut T>` which prevents e.g. replacing the value behind it with another `T` one, but there the restriction is in the pointer itself (you can think of it as `&pin mut T`), not in the pointee, and it's not that relevant here, it mainly exists to allow library code to correctly interface with the internally self-referential generators (that `async fn`s are built on). In the scenario you describe you would use shared references (with appropriate lifetime parameterization on relevant data types), not mutable ones (which imply exclusivity), nor raw pointers (which is the only way to get the C++-like problems). That will limit you to immutable data by default, so if you want to mutate some leaf fields, you wrap them in `Cell` (which prevents invalidation because `&Cell<T>` doesn't allow creating references inside the `T` value) or some kind of atomic/lock if you want concurrent access. This already solves all the problems you were thinking of, and it doesn't even fundamentally require an arena (what you need an arena for is the dynamic graph structure, assuming you want to use references/pointers and not integer indices). In essence, the more you rely on safe Rust features, the harder this is to get wrong or end up with a misusable API. Oh and the Rust compiler itself has used arenas since before 1.0 (IIRC), and with every year we move more data into them, though most are 100% immutable (which helps with compiler correctness, especially incremental recompilation), or even interned (deep deduplication by caching allocation attempts). We can even get away without dynamically tracking destructors by making most arena-allocated data destructor-less (we mostly just had to replace `Vec<T>` with arena-allocated `&[T]` to make that work).
zozbot234 6y ago
Rust objects can always be moved to arbitrary places in memory, so I'm not sure how "in place" construction of a Rust object can even make sense unless it explicitly involves the Pin<P> feature to prevent moves. This is quite different from C/C++ where there's no default expectation that a constructed object can be bitwise-copied somewhere else in memory. Even Box<T> is really a special case since the object is meant to be accessed via an owning pointer or a (shared or mutable) reference; when accessing the underlying T by value, that always involves a move of the object so again there's no such thing as being "in place".
- staticassertion 6y ago
  Placement new is just avoiding a copy. Without placement new allocating an object involves: a) Constructing the object on the stack b) Copying it to the heap With placement new you construct the object directly on the heap, thus avoiding a copy. It's purely an optimization to avoid a single copy. It's a bit surprising that Rust doesn't have it, given the focus on control over such things, and that it had an experimental 'box' keyword for this at 1.0. edit: To be clear, the extra copy is not guaranteed - compilers can elide it. In order to help the compiler do this you can look at crates like boxext, which provide extension methods on Box that help the compiler to remove the copy. But placement new guarantees this.
  - deleted 6y ago
    [deleted]
  - nemothekid 6y ago
    IIRC, Rust did have this optimization (or LLVM was doing it), but then there was a version bump or change in IR that disabled it and it wasn't trivial to fix.
    - staticassertion 6y ago
      There should be an optimization pass for this, certainly, but the placement new syntax guarantees it.
  - 6y ago
nipunn1313 6y ago
Hey @haberman! One of the authors here. We actually do have an arena-esque implementation built on top of pb-jelly internally, as it was needed for Magic Pocket. It's built on top of the Blob traits exposed by pb-jelly. It's not yet open-source, but it would be a good candidate to do next! It also definitely has unsafe code to your point. We open sourced the safe implementations that uses more standard types (Bytes/Buffer/Vec) first. There's a decent amount of cleanup needed before we can opensource that as well, as much of it was built years ago, when rust ecosystem was less mature (eg Bytes/Buffer weren't around yet). I like where you're thinking!
- haberman 6y ago
  That's great, I'll look forward to seeing the arena-oriented code someday. :)
zamalek 6y ago
Check out bumpalo[1]. Dodrio is a real-world[2] usage of bumpalo, so you can inspect that code to see how he deals with lifetimes correctly. Edit: GATs are how "placement new" (Rust doesn't have new at all, hence the airquotes) would work in Rust, assuming the author here meant to say "custom allocators." With GATs, you could create a pointer (Box, Arc, ArenaBox etc.) trait and use that on your message types.[3] "Placement new" is a whole different issue that ultimately boils down to a compiler optimization that is currently missing/not working and shouldn't functionally affect what you are trying to do at all. [1]: https://github.com/fitzgen/bumpalo https://github.com/fitzgen/bumpalo [2]: https://github.com/fitzgen/dodrio https://github.com/fitzgen/dodrio [3]: https://rust-lang.github.io/rfcs/1598-generic_associated_types.html https://rust-lang.github.io/rfcs/1598-generic_associated_typ...
eximius 6y ago
https://docs.rs/typed-arena/2.0.1/typed_arena/ https://docs.rs/typed-arena/2.0.1/typed_arena/
zelly 6y ago
R*st was designed to fragment the heap as much as possible. There's no way to fix it without major changes to the compiler or using "unsafe".

staticassertion 6y ago

AFAIK the current method for hacking in placement new is to use something like this: https://github.com/glandium/boxext https://github.com/glandium/boxext Some more context. There used to be a `box` keyword too. https://github.com/rust-lang/rust/issues/50047 https://github.com/rust-lang/rust/issues/50047

pcwalton 6y ago

Placement new is just an optimization to avoid the initial memcpy from the stack in cases in which LLVM can't work it out itself. I don't believe that placement new ever enables semantics that aren't possible with plain old move semantics.

haberman 6y ago
Ah, in that case it sounds like heterogenous arenas are more or less a solved problem in Rust, even if they aren't necessarily 100% optimal. Probably the more difficult piece then is just how to model arena ownership of a tree of objects that all have links between them. We want to guarantee that links to sub-messages remain valid, which we would expect to be true if they are all in the same arena. But I believe Rust allows moving/swapping objects in and out of the arena?
- eddyb 6y ago
  > heterogenous arenas are more or less a solved problem in Rust To expand a bit on what pcwalton said: Rust never had a concept of a type you can't move (we likely can't ever introduce it) and placement was never about "in-place construction" (Rust doesn't even have a concept of "construction", but rather focuses on initialization). There is `Pin<&mut T>` which prevents e.g. replacing the value behind it with another `T` one, but there the restriction is in the pointer itself (you can think of it as `&pin mut T`), not in the pointee, and it's not that relevant here, it mainly exists to allow library code to correctly interface with the internally self-referential generators (that `async fn`s are built on). In the scenario you describe you would use shared references (with appropriate lifetime parameterization on relevant data types), not mutable ones (which imply exclusivity), nor raw pointers (which is the only way to get the C++-like problems). That will limit you to immutable data by default, so if you want to mutate some leaf fields, you wrap them in `Cell` (which prevents invalidation because `&Cell<T>` doesn't allow creating references inside the `T` value) or some kind of atomic/lock if you want concurrent access. This already solves all the problems you were thinking of, and it doesn't even fundamentally require an arena (what you need an arena for is the dynamic graph structure, assuming you want to use references/pointers and not integer indices). In essence, the more you rely on safe Rust features, the harder this is to get wrong or end up with a misusable API. Oh and the Rust compiler itself has used arenas since before 1.0 (IIRC), and with every year we move more data into them, though most are 100% immutable (which helps with compiler correctness, especially incremental recompilation), or even interned (deep deduplication by caching allocation attempts). We can even get away without dynamically tracking destructors by making most arena-allocated data destructor-less (we mostly just had to replace `Vec<T>` with arena-allocated `&[T]` to make that work).

zozbot234 6y ago

Rust objects can always be moved to arbitrary places in memory, so I'm not sure how "in place" construction of a Rust object can even make sense unless it explicitly involves the Pin<P> feature to prevent moves. This is quite different from C/C++ where there's no default expectation that a constructed object can be bitwise-copied somewhere else in memory. Even Box<T> is really a special case since the object is meant to be accessed via an owning pointer or a (shared or mutable) reference; when accessing the underlying T by value, that always involves a move of the object so again there's no such thing as being "in place".

staticassertion 6y ago
Placement new is just avoiding a copy. Without placement new allocating an object involves: a) Constructing the object on the stack b) Copying it to the heap With placement new you construct the object directly on the heap, thus avoiding a copy. It's purely an optimization to avoid a single copy. It's a bit surprising that Rust doesn't have it, given the focus on control over such things, and that it had an experimental 'box' keyword for this at 1.0. edit: To be clear, the extra copy is not guaranteed - compilers can elide it. In order to help the compiler do this you can look at crates like boxext, which provide extension methods on Box that help the compiler to remove the copy. But placement new guarantees this.
- deleted 6y ago
  [deleted]
- nemothekid 6y ago
  IIRC, Rust did have this optimization (or LLVM was doing it), but then there was a version bump or change in IR that disabled it and it wasn't trivial to fix.
  - staticassertion 6y ago
    There should be an optimization pass for this, certainly, but the placement new syntax guarantees it.
- 6y ago

nipunn1313 6y ago

Hey @haberman! One of the authors here. We actually do have an arena-esque implementation built on top of pb-jelly internally, as it was needed for Magic Pocket. It's built on top of the Blob traits exposed by pb-jelly. It's not yet open-source, but it would be a good candidate to do next! It also definitely has unsafe code to your point. We open sourced the safe implementations that uses more standard types (Bytes/Buffer/Vec) first. There's a decent amount of cleanup needed before we can opensource that as well, as much of it was built years ago, when rust ecosystem was less mature (eg Bytes/Buffer weren't around yet). I like where you're thinking!

haberman 6y ago
That's great, I'll look forward to seeing the arena-oriented code someday. :)

zamalek 6y ago

Check out bumpalo[1]. Dodrio is a real-world[2] usage of bumpalo, so you can inspect that code to see how he deals with lifetimes correctly. Edit: GATs are how "placement new" (Rust doesn't have new at all, hence the airquotes) would work in Rust, assuming the author here meant to say "custom allocators." With GATs, you could create a pointer (Box, Arc, ArenaBox etc.) trait and use that on your message types.[3] "Placement new" is a whole different issue that ultimately boils down to a compiler optimization that is currently missing/not working and shouldn't functionally affect what you are trying to do at all. [1]: https://github.com/fitzgen/bumpalo https://github.com/fitzgen/bumpalo [2]: https://github.com/fitzgen/dodrio https://github.com/fitzgen/dodrio [3]: https://rust-lang.github.io/rfcs/1598-generic_associated_types.html https://rust-lang.github.io/rfcs/1598-generic_associated_typ...

eximius 6y ago

https://docs.rs/typed-arena/2.0.1/typed_arena/ https://docs.rs/typed-arena/2.0.1/typed_arena/

zelly 6y ago

R*st was designed to fragment the heap as much as possible. There's no way to fix it without major changes to the compiler or using "unsafe".