Weak references are weird.

This post is a collection of all the mysterious and arcane mechanisms that languages use to offer weak references.

Our quest was to figure out the best approach to use for Vale, that aligned with its goals of being fast, memory safe, and easy to use.

In the end, we made a completely new approach!

What are they supposed to be?

In most languages, 0 normal references are "strong". As long as there is at least one strong reference to an object, the object stays alive. When the last strong reference goes away, the object is deallocated. 1

We can also have weak references to the object, which don't keep the object alive. After the target object dies, they appear to be null. 2

These aren't just useful to break ref-counting cycles. They're also used to know when something still logically exists, to factor into our program's behavior. If you ever seen an alive or dead boolean in a class, you're likely seeing a good use-case for weak references.

For example, we can use it in an observer:

Or perhaps a magic missile can check if its enemy still exists:

It's a rather useful tool! And it's pretty simple under the hood.

...except in Objective-C.

Objective-C's Global Weak Pointer Tracking Manager 3

Objective-C has a mutex-guarded global hash map, tracking all the weak references and what objects they point to.

Specifically:

• When we make a new weak reference to an object, we add an entry to the map:
  • The key is the address of the object,
  • the value is the address of the weak reference itself (a double-pointer, so to speak).
• When we get rid of a weak reference to an object, we remove that entry from the map.
• When an object dies, it looks for all the entries for the object...
  • From each of those entries, it gets the address of the weak reference.
  • It uses that address to set the weak reference to nil.

Unexpectedly, there are benefits to this approach!

• Given a weak reference, checking if it's pointing at a live object is extremely fast. We just have to check if the reference is nil.
• This doesn't have the "zombie allocation" problem that Swift and Rust have; this approach may use less memory than they do.
• Until we make the first weak reference, this approach uses zero overhead.

But of course, it has drawbacks:

• It's extremely slow to create and destroy weak references. It has to obtain a global lock and do some hash map operations.
• Each weak reference costs 16B, sometimes more. 4

Swift's Zombie Objects 5

When Swift isn't using the Objective-C approach for compatibility reasons, Swift actually does something pretty elegant.

A Swift object has two counters in it:

• A counter which counts how many strong references point at the object.
• A counter which counts how many weak references point at the object.

Remember how we said "when the last strong reference goes away, the object is deallocated"? That's not true for Swift.

Let's say an object has strong references and weak references pointing at it.

When the last strong reference goes away, the object is deinitialized, but not deallocated. I like to think that deinitializing just zeroes out all the fields. 6

The object isn't deallocated quite yet; the object is in kind of a "zombie state" because it has no usable contents, but it's kept alive while there are still weak references pointing to it.

If we ask one of these weak references "are you pointing at a live object?", it will look into the object and check if the strong ref count is positive. If so, it responds true. If it's zero, it responds false. 7

Later, when we let go of the last weak reference, the weak reference counter goes to zero, and the object is deallocated; the zombie is finally destroyed.

Swift's approach has some benefits:

• It has some memory overhead (two counters per object, one could say the zombie objects also take up space)
• It's very fast, because the ref-count is next to the rest of the object's fields, which is very cache-friendly. 8

and some costs:

• We pay the space cost of weak references even if we never use them.
• Zombie objects: the entire object's allocation might stick around even after the last strong reference disappears.
• All objects must be separately allocated in the heap, we can never have a weak reference to an object that lives inside another object's memory.

Swift's approach is very simple, and I like that. 9

C++'s weak_ptr

If we look at the memory layout, C++ is similar to Swift; right next to the object we can have a strong ref count and a weak ref count. 10

In C++, we choose whether an object can have weak references to it or not. A Spaceship will by default not have any counters, but a shared_ptr<Spaceship> will have them.

We can make a weak reference, a weak_ptr<Spaceship>, from any shared_ptr<Spaceship>.

This has benefits:

• We can opt-in to the counters' 16B overhead only when we need it. 11

And a cost:

• Each weak_ptr is 16B. 12

And some oddities:

• If we make the allocation with make_shared, the object and its control struct share an allocation, resulting in zombie objects. 13
• If we have a regular pointer (Spaceship*) we cannot get a weak_ptr<Spaceship> unless Spaceship inherits from std::enable_shared_from_this.

Rust's Weak

Rust's Rc and Weak are basically C++'s shared_ptr and weak_ptr, with a couple differences:

• Rust's Rc always puts its counters next to the object, whereas C++ lets us put it in a separate block if we want to.
• Given a &Spaceship, we aren't able to get a Weak<Spaceship>.

We don't often see Rc and Weak in Rust. Instead, we use other mechanisms that behave like weak references.

Weak References, Hidden in Plain Sight

We've now seen a few different kinds of weak references. However, if we zoom out a bit, we see a lot of things that act very similarly to weak references.

A weak reference is basically something that you can trade for a regular reference to the object if it still exists.

When you think of it that way, a lot of things are weak references.

For example, a string containing a filename, like myfile.txt. We can trade it for the contents of a file, if the file still exists:

Or perhaps we have an integer ID, and we can use it to look up a Spaceship in a map:

Notice how we first check for existence, and then use the resulting data. Just like a weak reference!

My favorite kind of weak-reference-in-disguise is the generational index, often used in C++ and Rust programs.

Generational Indices

We often store our objects in arrays or vectors, such as a Vec<Spaceship>. 14 When we destroy a Spaceship, we often like to reuse its spot for another Spaceship.

Sometimes, we remember a Spaceship's index in the Vec. Later, we might want to know if that Spaceship is still there, or if it's been reused. Here's how!

Next to every object in the vector, we have an integer: Vec<(Spaceship, i64)>. That i64 is the Spaceship's current generation number. Every time we reuse a slot, we increment that number.

Whenever we want to remember a Spaceship's index, we'll also remember its generation number at the time. This is the remembered generation number.

For convenience, let's put the index and this "remembered generation number" in a little struct called a GenerationalIndex:

Now, if we want to know whether the Spaceship still exists, we just compare the current generation number to the remembered generation number, like:

It's as if the generational index is saying:

and the element at index 7 says:

or instead:

That's a generational index. It's like a weak reference!

However, there is one downside to generational indices: to "dereference" it, we need access to the containing Vec (like the enemies Vec above), usually passed in through a parameter.

This can sometimes be inconvenient: when we add a new parameter, we have to change our callers to supply it, and then our callers' callers, and our callers' callers' callers, which can result in "refactoring shockwaves". Doing this too often can cause churning APIs.

Sometimes, to work around this drawback, we give up and put all of our containers into a "god object" and pass that around as an argument to every function in our codebase.

Perhaps there's a better way to address this drawback. Read on!

Vale's Generational References

Vale adds something like the generational index, which we call a generational reference.

Every object has a "current generation number" next to it in memory. Whenever we destroy an object, we increment that number. 15

To make a weak reference to that object, we get two things:

• A pointer to the object. 16
• The object's current generation number.

...and stick them together.

To know whether the object still exists, Vale just compares the object's current generation number to our reference's remembered generation number.

Similar to the generational index, It's as if the reference is saying:

and the person who opens the door says:

or instead:

We implemented generational references, and found them to be at least 2.3x faster than reference counting!

Compared to the other weak reference approaches, this has benefits:

• Making or destroying new weak references is free, no reference counters need to be incremented.
• It enables Fearless FFI; C code cannot corrupt Vale objects. 17
• It doesn't suffer the zombie object problem.
• Supporting generational references costs an allocation only 8B!

And costs:

• Supporting generational references costs an allocation a whole 8B.
• It can take some virtual memory maneuvers to release memory to the OS. 18
• It can only be used for heap allocations, which have stable addresses.

We foresee the average Vale program blending three different approaches:

• For heap allocations, we'd use generational references.
• When we have convenient access to the container, we'd use generational indexes.
• For everything else, we'd use "augmented generational indexes" which also bundle in a reference to the container.

By offering these all in the standard library, we can make it easy to have fast weak references. That's good, because Vale's goal is to make speed and safety easier than ever before.

Conclusion

Thanks for reading! In the coming weeks, I'll be writing about how we can augment generational references with an "automatic borrow checker," so subscribe to our RSS feed or the r/Vale subreddit, or come hang out in the Vale discord.

If you found this interesting, please consider sponsoring us:

Sponsor us on GitHub!

With your help, we can write articles like this more often!

- Evan Ovadia

About the Vale Language Project

The Vale Language Project is not just about making Vale, it's about exploring, discovering, and publishing new programming language mechanisms that enable speed, safety, and ease of use.

The world needs more exploration here! Currently, most programming language research is is in:

• High-overhead languages involving reference counting and tracing garbage collection.
• Complex languages (Ada/Spark, Coq, Rust, Haskell, etc.) which impose a higher complexity burden on the average programmer.

These are useful, but there is a vast field of possibilities in between, waiting to be explored!

Our aim is to explore that space, discover what it has to offer, and make speed and safety easier than ever before.

In this quest, we've discovered a lot of new techniques:

• Region Borrow Checking, which adds mutable aliasing support to a Rust-like borrow checker.
• Generational Memory, for a language to ensure an object still exists at the time of dereferencing.
• Hybrid-Generational Memory, which ensures that nobody destroys an object too early, for better optimizations.

These techniques have also opened up some new emergent possibilities:

• Seamless concurrency, the ability to launch multiple threads that can access any pre-existing data without data races, without the need for refactoring the code or the data.
• Object pools and bump-allocators that are memory-safe and decoupled, so no refactoring needed.
• Fearless FFI, which allows us to call into C without risk of accidentally corrupting Vale objects.
• Deterministic replayability, to record all inputs and replay execution. Goodbye races and heisenbugs!
• Higher RAII, a form of linear typing that enables destructors with parameters and returns.

We also gain a lot of inspiration from other languages, and are finding new ways to combine their techniques:

• We can mix an unsafe block with Fearless FFI to make a much safer systems programming language!
• We can mix Erlang's isolation benefits with functional reactive programming to make much more resilient programs!
• We can mix region borrow checking with Pony's iso to support shared mutability.

...plus a lot more interesting ideas to explore!

The Vale programming language is only one combination of the features we've found. Our goal is to publish all the techniques we've found, even the ones that couldn't fit in Vale, so that other languages can make strides in this area.

Our medium-term goals:

• Publish the Language Simplicity Manifesto, a collection of principles to keep programming languages' learning curves down.
• Publish the Memory Safety Grimoire, a collection of "memory safety building blocks" that languages can potentially use to make new memory models, just like Vale combined generational references and scope tethering.
• Prototype the Region Borrow Checker in Vale, to show the world that shared mutability can work with borrow checking!
• Prototype Hybrid-Generational Memory in Vale, to see how fast and easy we can make single ownership.

We aim to publish articles biweekly on all of these topics, and inspire the next generation of fast, safe, and easy programming languages.

If you want to support our work, please consider sponsoring us on GitHub!

With enough sponsorship, we can:

• Work on this full-time.
• Turn the Vale Language Project into a 501(c)(3) non-profit organization.
• Make Vale into a production-ready language, and push it into the mainstream!

Sponsor us on GitHub!