Herb Sutter deferred heaps and pointers

[leonardo]

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”:

For a quicker overview of the talk you can find the slides here:

https://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:

https://github.com/hsutter/gcpp

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.)

[matthieum]

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.

[leonardo]

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?

[steveklabnik]

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.

[steven099]

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.

[ahmedcharles]

I believe it only keeps track of deferred_ptrs 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).

hsutter/gcpp/blob/master/deferred_heap.h

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.

[glaebhoerl]

There is… no such thing as a custom Copy impl. Did you mean Clone? (Or a Copy impl with custom bounds?)

[ahmedcharles]

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.

[rkruppe]

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.

[ahmedcharles]

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?

[rkruppe]

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?

[troplin]

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.

[troplin]

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.

[ahmedcharles]

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.

[Nemo157]

Rust’s Copy is about semantics, from the docs:

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.

[ahmedcharles]

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.

[Nemo157]

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 Copyable value. Goes against the “explicit is better than implicit” design goal though.

[ahmedcharles]

I suppose given that Rc, etc use .clone(), an implementation of deferred_ptr in Rust would probably just do the same.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.