LanguagesArchitecture
Note: Regions as a whole are still a work-in-progress, but part 1 has been successfully prototyped!

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!

Side Notes
(interesting tangential thoughts)
0

A "scope" is the duration of a function or a block inside a function. It can also be the lifetime of the containing object, the time between its construction and destruction.

1

An iso object is an object where anything it indirectly owns will only ever have references to something else indirectly owned by that original object.

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:

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

2

Most functions are impure. A function is only pure if it doesn't modify any data that existed before the call.

What just happened?

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

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

"Hello! I'm looking for the 11th inhabitant of this house, are they still around?"

and the person who opens the door says:

"No, sorry, I'm the 12th inhabitant of this house, the 11th inhabitant is no more." 4

or instead:

"Yes! That is me. Which of my fields would you like to access?"

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.

3

An allocation can contain multiple objects, so not every object has a generation.

4

This will halt the program. This is pretty rare in practice, and might become even rarer as we more eagerly detect problems before they happen, as part of Hybrid-Generational Memory.

How Regions Work

Here's the above snippet again:

vale
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!

5

This can either be determined by seeing the still-alive owning reference, or by doing a single generation check before the function.

6

The List<Ship> is a list of owning references. Nobody can destroy a Ship while the List<Ship> still has its owning reference.

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.

In the following example, the callerFuncA function adds some Ships to a list, and then passes it to printShipNames.

The Vale compiler sees these two facts:

  • myShips is an owning reference, so the memory it's pointing to must still be alive.
  • We're making a non-owning reference from myShips which we know is alive, so we know this non-owning reference points to something alive.

It then creates a raw reference 7 (without a generation) pointing to myShips, and passes it to printShipNames.

vale
func callerFuncA() {
myShips = List<Ship>();
myShips.add(Ship(10));
myShips.add(Ship(20));
// …
printShipNames(&myShips);

}


// Same function as before
pure func printShipNames(
tenShips &List<Ship>
)
{
foreach i in 0..tenShips.len() {
ship = tenShips[i]; // No gen check!
name = ship.name; // No gen check!
println(name);

}

}

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.

7

You can almost think of a "raw reference" as just a regular pointer. Under the hood, it sometimes also contains an offset integer that can later be used to recover the generation. This raw reference is sometimes 128 bits wide, and sometimes 64 bits, depending on the object and the CPU (we can use top-byte-ignore on ARM CPUs, and might put a offset-to-generation integer in there, though thats only a tentative design).

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.

However, a non-owning references into an immutable region is not a generational reference, it is actually just a raw reference 8 under the hood, which may or may not be null. 9 10

To turn a generational reference (like theirShips) into a raw pointer, we do a generation pre-check. We compare the generational reference to the object it points at, and:

  • If the check passes, we create a raw reference to the object.
  • If there's a mismatch instead, we create a raw reference to null.

We then hand this raw reference to printShipNames, in this example.

vale
func callerFuncB() {
myShips &List<Ship> = ;
// …
// Generation pre-check here
printShipNames(&myShips);

}


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

}

}

Note that even if there are nulls under the hood, there's no such thing as null in Vale. They are just a compiler implementation detail.

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

Recall from above notes, this raw reference might not be a raw pointer; it might have an offset-to-generation integer with it.

9

We use nullable raw pointers, just as our fathers did, and their fathers before them! But don't worry, Vale has no nulls, it's only an implementation detail.

10

There are extra considerations here for embedded devices where NULL is a valid memory address. On those, we'd supply a known invalid address, such as 0xFFFFFFFF00000000, or the address of some reserved, unmapped virtual address space. There are also language implications about the sizes of large non-array objects, feel free to swing by the discord server to learn more!

11

The former is caught by the generated code itself, and the latter is caught by the CPU's own protections.

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.

For example, if we tried to put tenShips.add(Ship(42)); in the function, the compiler would reject it.

The compiler tracks which variables point into that immutable region. It knows that whenever we dereference an immutable object, its members will also be immutable.

vale
// Same function as before
pure func printShipNames(
tenShips &List<Ship>
)
{
foreach i in 0..tenShips.len() {
ship = tenShips[i];
name = ship.name;
println(name);

}

}

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.

The user doesn't have to annotate which regions data came from, but it can be helpful for clarity. The following example shows the printShipNames with the optional explicit region markers.

  • The <r'> names a region. Named regions are immutable by default.
  • tenShips &r'List<r'Ship> says this argument is coming from the immutable region r'. 12
  • The function has its own private mutable region named my'.

pure func printShipNames<r'>(
  tenShips &r'List<r'Ship>) 13
my'{
  foreach i in 0..tenShips.len() {
    ship &r'Ship = tenShips[i];
    name r'str = ship.name;
    println(name);
  }
}

Note that even though pre-existing memory is in an immutable region, the compiler still allows us to change anything created since then.

Here's the same example, with the foreach loop expanded, to illustrate that i is changing.

In other words, a pure function can change anything except the memory that came before the call.

Keep in mind, these region markers are often inferred by the compiler, and usually not seen in Vale code.

// Same function as before
pure func printShipNames<r'>(
  tenShips &r'List<r'Ship>)
my'{
  i my'int = 0;
  while i < tenShips.len() {
    ship &r'Ship = tenShips[i];
    name r'str = ship.name;
    println(name);
    set i = i + 1; // Valid!
  }
}

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.

12

We could also write &r'List<Ship> instead, the r' applies deeply.

13

We could also write &r'List<Ship> instead, the r' applies deeply.

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:

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!

14

RAII is about automatically affecting the world outside our object. To affect the outside world, the borrow checker often requires us to take a &mut parameter or return a value, but we can't change drop's signature. To see this in action, try to make a handle that automatically removes something from a central collection. Under the hood we usually use unsafe mechanisms, including FFI.

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.

See you next time!

- Evan Ovadia

15

This is because in Vale, pure doesn't actually mean we can't access globals, it more means "freeze this thread's memory".

16

This is a pretty light operation on likely cache-hot memory, so it's not too bad. It can also be avoided by returning data in an iso.