# Herb Sutter deferred heaps and pointers **URL:** \ **Category:** language design\ **Created:** [October 10, 2016, 9:26am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183 "2016-10-10T09:26:33Z")\ **Posts on this page:** 19\ **Page:** 1
**Author:** ![leonardo](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/leonardo/32/1344_2.png) [@leonardo](https://internals.rust-lang.org/u/leonardo)\ **Post date:** [October 10, 2016, 9:26am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/1 "2016-10-10T09:26:33Z")
Herb Sutter deferred heaps and pointers I've seen a recently released talk by Herb Sutter, quite interesting (and not too much hard to understand even if you aren't at the skills level of a C++ library designer), "Lifetime Safety By Default - Making Code Leak-Free by Construction - Herb Sutter - CppCon 2016": [![](https://img.youtube.com/vi/JfmTagWcqoE/maxresdefault.jpg "CppCon 2016: Herb Sutter “Leak-Freedom in C++... By Default.”") ](https://www.youtube.com/watch?v=JfmTagWcqoE) For a quicker overview of the talk you can find the slides here: > > > //github.com/CppCon/CppCon2016/tree/master/Presentations/Lifetime%20Safety%20By%20Default%20-%20Making%20Code%20Leak-Free%20by%20Construction The talk is about smart C++ pointers that help safety and correctness of C++ code. The unique\_ptr\<\> is like Box\<\> of Rust, then there's shared\_ptr\<\>, etc. In the second part of the talk Herb shows that to handle graphs and ownership cycles you can invent a new smart pointer, and he explains deferred\_ptr, deferred\_allocator and deferred\_vector. deferred\_allocator creates a memory zone (a deferred\_heap) where you can use cyclic pointers, like when you need to build a graph data structure. The pointers are handled with reference counter inside a deferred\_heap. There is a basic implementation of those things: > **[GitHub - hsutter/gcpp: Experimental deferred and unordered destruction...](https://github.com/hsutter/gcpp)** > > Experimental deferred and unordered destruction library for C++ - GitHub - hsutter/gcpp: Experimental deferred and unordered destruction library for C++ I remember that recently there's interest in introducing back a Gc\<\> type in Rust, perhaps those ideas Herb Sutter can be quite useful. There are even notes about making the Rust compiler optimizer aware of some of that semantics: > The current implementation is not production-quality. In particular, it's a pure library solution that requires no compiler support, it's single-threaded, it dynamically registers every deferred\_ptr, and it doesn't try to optimize its marking algorithm. The GC literature and experience is full of ways to make this faster; for example, a compiler optimizer that is aware of deferred\_ptr could optimize away all registration of stack-based deferred\_ptrs by generating stack maps. The important thing is to provide a distinct deferred\_ptr type so we know all the pointers to trace, and that permits a lot of implementation leeway and optimization. (GC experts, feel free to plug in your favorite real GC implementation under the deferred\_heap interface and let us know how it goes. I've factored out the destructor tracking to keep it separate from the heap implementation, to make it easier to plug in just the GC memory and tracing management implementation.) ---
**Author:** ![matthieum](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/matthieum/32/4023_2.png) [@matthieum](https://internals.rust-lang.org/u/matthieum)\ **Post date:** [October 13, 2016, 6:04pm UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/2 "2016-10-13T18:04:42Z")
There is one specific part of `deferred_heap`/`deferred_ptr` that is specific to C++, and would be impossible to port to Rust I fear. When the `deferred_heap` destructs an object, it firsts nulls out all `deferred_ptr` pointing to it, thus ensuring that no cycle occurs during destruction. This feature, however, requires that at any time `deferred_heap` keep a list of all `deferred_ptr` objects pointing into it, which means that when a `deferred_ptr` _moves_ it updates `deferred_heap`. In Rust, no user-defined function is invoked when a value is moved. ---
**Author:** ![leonardo](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/leonardo/32/1344_2.png) [@leonardo](https://internals.rust-lang.org/u/leonardo)\ **Post date:** [October 13, 2016, 6:16pm UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/3 "2016-10-13T18:16:59Z")
> [@matthieum](#): > > In Rust, no user-defined function is invoked when a value is moved. If having a Gc\<\> is sufficiently important, can you modify Rust adding a hook for moves? ---
**Author:** ![steveklabnik](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/steveklabnik/32/4524_2.png) [@steveklabnik](https://internals.rust-lang.org/u/steveklabnik)\ **Post date:** [October 13, 2016, 6:42pm UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/4 "2016-10-13T18:42:14Z")
> [@leonardo](#): > > can you modify Rust adding a hook for moves? This is something that we very explicitly do not support. Knowing that moves are always just a memcpy is extremely important. ---
**Author:** ![steven099](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/steven099/32/3871_2.png) [@steven099](https://internals.rust-lang.org/u/steven099)\ **Post date:** [October 19, 2016, 7:05am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/5 "2016-10-19T07:05:45Z")
An alternative to move constructors could be immovable types. A nullable immovable cell type could be used to contain address values which would be unusable unless they are in an immovable cell. The methods for updating the value in the cell and a drop impl could handle any necessary bookkeeping. A basic sketch of immovable types would be to have it so that assignment is only legal if the RHS is a literal value. Immovability would be contagious like opting out of an unsafe auto trait is. Placement new could perhaps be used to allow immovable values to be boxed. As far as generics are concerned, type parameters would have to default to movable. The fact that the deferred heap scheme has to nullify arbitrary pointers willy nilly also plays havoc with owning references and such. I suppose it wouldn’t be entirely unreasonable to make it illegal to have an immovable type in a mutable slot, which would help address this issue. Edit: Alternatively you could use type state rather than null to distinguish the dropping case, which could be tracked through a type parameter. You’d probably need HKT so that you can transmute an arbitrary type between the normal case and the dropping case and ensure that any contained deferred pointers are linked to the same type parameter as the outer type. ---
**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\ **Post date:** [October 21, 2016, 7:04am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/6 "2016-10-21T07:04:42Z")
I believe it only keeps track of `deferred_ptr`s that are inside the arena allocation, since those are the only ones that need to be zero’d before a collection is done. Roots can’t be zero’d, since they are the ones that actually own data. And while I haven’t looked at the code, one of the benefits of `deferred_ptr` is that it is trivially copyable and assignable (aka, just a memcpy). > After looking at the implementation, it seems plausible that it could be implemented as a Copy type with a custom copy impl, which is effectively the same as implementing a copy constructor with some custom logic. ---
**Author:** ![glaebhoerl](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/glaebhoerl/32/1978_2.png) [@glaebhoerl](https://internals.rust-lang.org/u/glaebhoerl)\ **Post date:** [October 21, 2016, 8:40am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/7 "2016-10-21T08:40:34Z")
There is… no such thing as a custom `Copy` impl. Did you mean `Clone`? (Or a `Copy` impl with custom _bounds_?) ---
**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\ **Post date:** [October 22, 2016, 2:31am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/8 "2016-10-22T02:31:15Z")
I spoke loosely, but the point is the same. You can have clone() implemented by a Copy type which does the same thing that deferred\_ptr’s copy constructor does. And it doesn’t have a move constructor. ---
**Author:** ![hanna-kruppe](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hanna-kruppe/32/6540_2.png) [@hanna-kruppe](https://internals.rust-lang.org/u/hanna-kruppe)\ **Post date:** [October 22, 2016, 8:36am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/9 "2016-10-22T08:36:15Z")
That still doesn’t make sense to me. While you can do whatever you like in a Clone impl, if the type also implements Copy, an accepted RFC says that Clone shall be equivalent to memcpy (i.e., Copy). And even without that, if it’s Copy, clone() won’t always be called – so I don’t see how you could rely in clone() to do any bookkeeping or other important work. ---
**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\ **Post date:** [October 23, 2016, 7:29am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/10 "2016-10-23T07:29:13Z")
I didn’t know that Copy required that the clone be equivalent to memcpy. It seems like a very restrictive requirement in light of types like deferred\_ptr. C++ requires that implementations maintain side effects whenever a move or copy happens, even though it allows implementations to elide moves and copies, which it turns out is a worthwhile requirement. Was this considered when making accepting the RFC? ---
**Author:** ![hanna-kruppe](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hanna-kruppe/32/6540_2.png) [@hanna-kruppe](https://internals.rust-lang.org/u/hanna-kruppe)\ **Post date:** [October 23, 2016, 9:26am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/11 "2016-10-23T09:26:46Z")
The RFC is numbered 1521, if you want to check. But first I would like to hear what this hypothetical deferred\_ptr::clone impl would do. As I said, you can already arbitrarily duplicate values without involving the Clone impl because it’s Copy. **What harm could possibly come from omitting a few more clone calls?** ---
**Author:** ![troplin](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/troplin/32/1182_2.png) [@troplin](https://internals.rust-lang.org/u/troplin)\ **Post date:** [October 23, 2016, 9:36am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/12 "2016-10-23T09:36:09Z")
`Clone` is the Rust equivalent of a nontrivial copy constructor in C++. What’s the point of a data structure being trivially copiable and at the same time having a nontrivial copy constructor? That’s not even possible in C++ AFAIUI. ---
**Author:** ![troplin](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/troplin/32/1182_2.png) [@troplin](https://internals.rust-lang.org/u/troplin)\ **Post date:** [October 23, 2016, 10:29am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/13 "2016-10-23T10:29:51Z")
After reading the description of `deferred_ptr`, I've come to the conclusion that it is actually _not_ trivially copiable. I think you mean the following: > Using `shared_ptr` can be problematic in real time systems code, because any simple `shared_ptr` pointer assignment or destruction could cause an arbitrary number of objects to be destroyed, and therefore have unbounded cost. This is a rare case of where prompt destruction, usually a wonderful property, is actually bad for performance. [...] By design, `deferred_ptr` assignment cost is bounded and unrelated to destructors, and `deferred_heap` gives full control over when and where `collect()` runs deferred destructors. This makes it a candidate for being appropriate for real-time code in situations where using `shared_ptr` may be problematic. Assignment is not trivial, just bounded. In Rust this would probably translate to `drop` being bounded. ---
**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\ **Post date:** [February 20, 2017, 1:02pm UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/14 "2017-02-20T13:02:08Z")
Sorry, must have missed this. C++ has the notion of trivially copyable/moveable, but this means that the type uses a compiler generated or user defaulted constructor or assignment operator, transitively. However, non-trivial move constructors and assignment operators can be written to be non-throwable, which usually implies that they don’t allocate and that they are bounded in complexity by the size of the object (i.e. they are only a struct copy). Copy constructors can be non-throwable while leaving both objects in a valid state, as well and these would have the same complexity as a move constructor. Rust’s `Copy` is (or perhaps should be) equivalent to the C++ notion of a copy constructor with a non-throwing implementation. Meaning, `Copy` is about performance, not semantics. But it also seems that Rust currently requires that `Copy` includes additional semantic requirements above `Clone`, which means that while `Clone` is the equivalent of a copy constructor which is non-trivial and can throw, `Copy` is restricted to being a trivial copy constructor. ---
**Author:** ![Nemo157](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nemo157/32/11585_2.png) [@Nemo157](https://internals.rust-lang.org/u/Nemo157)\ **Post date:** [February 20, 2017, 1:54pm UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/15 "2017-02-20T13:54:44Z")
Rust's `Copy` _is_ about semantics, from [the docs](https://doc.rust-lang.org/std/marker/trait.Copy.html): > Types whose values can be duplicated simply by copying bits. `Copy` is just a marker trait stating that any type implementing the trait _must_ satisfy the above rule. If you need to do _anything_ at all when duplicating values you cannot implement `Copy`, you must implement `Clone` and have users explicitly call `.clone()` anywhere they need to make a duplicated value e.g. `Rc` does not implement `Copy` as it needs to update its reference count during the clone. ---
**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\ **Post date:** [February 20, 2017, 2:14pm UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/16 "2017-02-20T14:14:46Z")
For the record, I know that `Copy` isn’t what I want it to be and what the docs say, I was stating my opinion. To clarify, I’d like Rust to allow me to represent the equivalent of a non-throwing, non-trivial copy constructor in C++, that can be elided, but can have side effects if it is not elided. If only because, it’s useful to have. ---
**Author:** ![Nemo157](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nemo157/32/11585_2.png) [@Nemo157](https://internals.rust-lang.org/u/Nemo157)\ **Post date:** [February 20, 2017, 4:06pm UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/17 "2017-02-20T16:06:31Z")
I could actually see that being useful, some sort of `AutoClone` marker trait that injects calls to `.clone` (that are somehow able to be optimised out if it can just move instead) when it would normally copy a `Copy`able value. Goes against the “explicit is better than implicit” design goal though. ---
**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\ **Post date:** [February 20, 2017, 11:01pm UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/18 "2017-02-20T23:01:15Z")
I suppose given that Rc, etc use `.clone()`, an implementation of `deferred_ptr` in Rust would probably just do the same. ---
**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\ **Post date:** [March 25, 2019, 8:27am UTC](https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183/19 "2019-03-25T08:27:06Z")
Closed on March 25, 2019, 8:27am UTC This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.