Taming Go’s memory usage, or how we avoided rewriting our client in Rust

If you use a &mut Node as your pointer, you are attempting to answer those questions with "not me". Someone else has to own the Nodes. They've got to be somewhere on the stack or on the heap. There's nothing stopping you from defining the next pointer as Option. The problem is actually constructing a list.

Not many answers tell you why you can't do this in practice. I agree that this is not explained well enough in general, because new Rustaceans don't intuitively reach for references so it probably doesn't come up much and they're hard to use for this. But it's not that hard to see why:

Imagine you try to allocate all the Nodes at once (e.g. an array), and then use &mut references into the pre-allocated array. In order to set one &mut Node's next pointer, you will have to hold another &mut Node to set it to. This means you need to acquire mutable references to array elements, in the order that you wish them to appear in the linked list. This is actually really tricky to do: slice::get_mut(index)'s returned reference borrows the entire slice, so it doesn't let you have a &mut reference to two nodes at the same time. You need smaller &mut [Node] slices, somehow.

slice::split_first_mut is one way (in order), but if you have an array and can only create a linked list in the order nodes appear in the array, what's the point? Just use the array! Any other compiler-checked access order scheme will also be so limiting that you should just use a data structure of that exact shape anyway. To use an arbitrary order, you're going to need unsafe, so you'd basically be writing C.

To be fair, there is basically one application of this, and it's to have a sparsely populated constant size array that needs to be iterated in order. I made a demo:

https://play.rust-lang.org/?version=stable&mode=debug&editio...

The other problem is that you can't resize the backing array: your &mut Node references would be invalidated.

For this reason, pre-allocated lists like these are usually done with indices instead of references. The overhead is one pointer + offset and then a bounds check when dereferencing.

---

The other solutions answer the ownership question like so:

- You can use Box, so that each Node (acting as a list head) owns the entire tail of the list, uniquely, such that no other list can also refer to it. The tail is freed when the head is, unless of course you detach it first (let tail = node.next.take();).

- You can Arc/Rc the nodes, so that each node has a pointer, but not a unique pointer, to the next node. These can be duplicated, so lists can exhibit structural sharing if you are comfortable with that. Because of the sharing, freeing the head does not necessarily free any/all of the tail.

If you actually want this intrusive linked list functionality, consider using a real-world implementation like this: https://lib.rs/intrusive_collections

Dynamic-extent appears to be more similar to the "register" hint in C than to anything in Rust, in that it's an implementation-defined-behaviour hint. Rust has no such thing as hinting at storage class. Your variables are either T (stack) or Box (heap) or any other box-like construct involving T. You maintain complete control at all times, nothing is implementation-defined, and it's explicit. You can implement (and people have implemented) dynamic switching between stack and heap storage in a Rust library.

https://lib.rs/smallvec (stack to heap), https://lib.rs/tinyvec (smallvec with no unsafe code), https://lib.rs/arrayvec (stack only)

As you can see, these three library authors get to control very precisely how their types allocate and deallocate, and you basically mix and match these and the stdlib's smart pointers (and Vec) + other libraries like arenas, slot maps, etc to allocate the way you want.

> you'd probably achieve that type of resource control by exposing only WITH- macros in your API*

Yes, this and similarly using with_* closures both work, but both are more limited than destructors that run when something goes out of scope. A type that implements Drop can be stored in any other type, and the wrapper will automatically drop it. You can put LockGuard in a struct and build an abstraction around it.