Zero-Cost Borrowing with Vale Regions, Part 1: Immutable Region Borrowing

Vale has an ambitious goal: to be fast, safe, and easy. There are a lot of stellar languages that have two, and we suspect it's possible to really maximize all three using a new approach for memory safety called regions.

If you're unfamiliar, check out our high-level overview of regions. This article specifically covers the first core concept, called immutable region borrowing.

Immutable Region Borrowing

Regions let us immutably borrow data to unleash some powerful optimizations, to make Vale extremely fast.

Immutable region borrowing is when we inform the compiler that, during this scope, 0 we know we won't be changing a certain region of data.

A "region" of data might be:

• All existing data in the current thread, such as all data handed into a pure function.
• All data within a mutex.
• All data within an iso object. 1

The compiler can then help enforce that promise, and use it to eliminate generation checks, the only source of overhead for the generational references aproach (more on this below).

It also has secondary optimization effects:

• Inform the LLVM optimizer that this data will not change, which lets it optimize more aggressively.
• Code outside the scope (such as the caller of a pure function) can eliminate some of its generation checks too, since it knows its data wasn't changed by the called function.

In this article, we'll show you how it's all possible!

Immutable Borrowing Example: Pure Function

Regions can eliminate memory safety overhead for impure functions 2 and for groups of data marked iso, but let's start with the simplest example, a pure function.

For example, this snippet of code previously had 20 memory-safety-related operations:

pure func printShipNames(tenShips &List<Ship>) {
  foreach ship in tenShips {
    println(ship.name);
  }
}

But when regions are added to the language, that drops to zero.

What just happened?

Let's rewrite the above snippet to clarify where the 20 memory-safety-related operations used to happen:

pure func printShipNames(tenShips &List<Ship>) {
  foreach i in 0..tenShips.len() {
    ship = tenShips[i]; // Generation check here
    name = ship.name; // Generation check here
    println(name);
  }
}

These operations are called "generation checks", and they make our program memory-safe.

What are they, and how do regions eliminate them?

Generation Checks

Vale doesn't have reference counting or garbage collection. It uses a more efficient method called generational references.

To summarize generational references: Each allocation 3 has a "current generation number". Each non-owning reference is made of a pointer to the object, plus the "remembered generation number" of the object at the time the reference was created.

Whenever we dereference a non-owning reference, we do a "generation check." It's as if the reference is saying:

and the person who opens the door says:

or instead:

As you can imagine, we have to do generation checks whenever we suspect that the target object might have disappeared since the time we made the reference.

However, with immutable borrowing, the compiler can track which objects were alive before the call, and skip generation checks on them.

How Regions Work

Here's the above snippet again:

pure func printShipNames(tenShips &List<Ship>) {
  foreach i in 0..tenShips.len() {
    ship = tenShips[i]; // No generation check here
    name = ship.name; // No generation check here
    println(name);
  }
}

Vale knows that we don't have to do these generation checks. Before we dive in, here's a high-level overview of why:

1. At the call-site, the compiler automatically predetermines whether the List<Ship> is alive when we call the function. 5
2. The compiler sees that the function itself is pure, and knows no pre-existing data will change within the function.
3. The compiler tracks what region data comes from; it knows ship and therefore name both refer to something in the pre-existing memory "region".
4. It concludes that if the List<Ship> is still alive, its indirectly owned objects are still alive. It owns the contained Ships, so they are still alive. 6 Therefore, it doesn't need to do the generation checks.

The above is very high-level. Let's dive in and clarify!

How a caller passes a known-live object

In #1 above, we mention that the caller will determine whether the List is alive. Let's add a caller function, to see it in action.

To reiterate, printShipNames takes a raw reference for its tenShips parameter, not a generational reference.

The user never has to know about the difference between raw references and generational references. This lets us keep the language simple, and decouple optimization from logic concerns.

How a caller passes a non-owning reference

The above was the easy case. We knew myShips was alive because we had an owning reference. But what if we have a non-owning reference?

Note that Vale often can know whether a non-owning reference is alive, via static analysis or hybrid-generational memory. But sometimes, it might not.

In the following example, the callerFuncB function has a non-owning reference, which is a generational reference under the hood.

So why a raw reference, instead of a generational reference?

Recall that Vale will detect any use-after-free by doing a generation check, and halt the program. The same thing happens when dereferencing null raw references. 11 So, dereferencing a null raw reference is equivalent to dereferencing a generational reference.

However, it's faster to dereference a raw reference than a generational reference, so we prefer to use raw references when we can. We know we can use raw references inside pure functions because we know the target object won't be destroyed during the call, so we can trust the raw reference to accurately represent whether the object is alive.

Summarizing how a non-pure function calls a pure function:

• If the compiler is positive the object is still alive, just pass the raw reference.
• If the compiler isn't sure, it does a generation pre-check, and pass the raw reference.

Tracking Immutable Data

Recall that printShipNames was pure.

The compiler enforces that data from before the pure function is immutable, at least while we're still in the call.

It can help to imagine a "region ID" that travels along with the pointer, but at compile time.

Above, it knew that tenShips points to an immutable region, so therefore tenShips[i] is also in an immutable region, and therefore ship and name point to data in an immutable region too.

That covers it! That's how the compiler knows ship and name are immutable, and i is mutable.

This tracking is called region tracking, because it tracks the region each piece of data comes from, and checks that we don't modify immutable regions.

Looks Familiar?

On first glance, immutable region borrowing looks similar to traditional borrow checking seen in Rust, Cyclone, and a couple other languages. However, there are a few fundamental differences:

• There's nothing like the borrow checker's aliasability-xor-mutability restrictions; objects can be aliased freely.
• Our code can use fast approaches that the borrow checker can't reason about, such as intrusive data structures and graphs, plus useful patterns like observers, back-references, dependency references, callbacks, delegates and many forms of RAII 14 and higher RAII.
• Region-markered code can be called by non-region-markered code, making our code more composable and reusable.
• Regions are optional and opt-in; one only explicitly uses them where it makes sense. Though, one still gets most of their benefits even if not using them explicitly.

Regions are more similar to mechanisms like:

• Pony's iso permission which represents an isolated region of objects.
• Forty2's ability to track objects from multiple regions simultaneously.
• Milano, Turcotti, and Myers's concurrency models.

Vale's contribution to the broader regions endeavor is in showing how:

• Objects in isolated regions can point to objects outside.
• A language can blend regions with single ownership (generational references) for better performance than other memory management techniques.
• A language can monomorphize "read-only" regions into mutable and immutable regions.

And with luck, we can bring all of this goodness into mainstream programming!

Conclusion

We've only covered one basic example, showing how pure functions use regions to eliminate memory safety overhead.

There are a lot of other ways regions help:

• Part 2 covers how we don't need a pure function to establish an immutable region! We can have an isolated sub-region (we have the only reference to it) and open it immutably.
• Part 3 shows how we can enable "one-way isolation", for sub-regions to have references outside their own region, and how we can eliminate generation checks for private data.
• Part 4 talks about how an object or array can contain other regions' objects inline, which helps automatically eliminate generation checks for data-oriented designs like entity component systems.
• Part 5 shows how regions can make iteration much faster, and how to use regions to make entire architectures (such as entity-component-system) zero-cost.

Regions don't just help performance, they also enable some novel features:

• Seamless, Fearless, Structured Concurrency, a way to parallelize any loop with a single keyword, with zero risk of data races.
• Fearless FFI which allows a function to operate on a safe region and an unsafe region simultaneously, without risk of corrupting the safe region's data.

There are some surprising details which aren't covered in this article:

• Pure functions can call impure functions; pure is not a viral function color. 15
• We can have a function that take some parameters from an immutable region, and some parameters from a mutable region.
• We can have a function that take parameters from a "read-only" region, which can be either mutable or immutable. This function is then monomorphized into both variants.
• When we return data from a pure function, it may need to be "re-generationed", turned from a raw pointer back into a generational reference. 16
• It does sometimes perform a generation pre-check when reading a non-owning reference from inside an immutable region. This is equivalent to the occasional extra bounds-check encountered in Rust, to turn an index into a reference.

That's all for now! We hope you enjoyed this article. Stay tuned for the next article, which shows how isolated sub-regions work.

If you're impressed with our track record and believe in the direction we're heading, please consider sponsoring us on GitHub!

With your support, we can bring regions to programmers worldwide.

See you next time!

- Evan Ovadia