Zero-Cost Borrowing with Vale Regions, Part 2: Isolates (Preview, Draft)

Vale has an ambitious goal: to be fast, memory safe, and most importantly, easy. There are a lot of stellar languages that have two, and we suspect it's possible to really maximize all three.

To do this, we're harnessing a new concept called regions.

In Part 1, we saw how we can use pure functions to easily "immutably borrow" a region, to eliminate memory safety costs when accessing it.

That works really well for the sections of our program that can be phrased as pure functions. 2

We can use regions to eliminate memory safety overhead in other places too, using a concept called "isolates".

Isolates

An isolate is a hierarchy of data that nobody outside can point to, except for one owning reference outside that points at the root.

Some examples:

• If a Spaceship owns a private Engine field and nobody outside needs to access it, it's conceptually an isolate.
• In an entity-component-system architecture, each separate component (and the arrays holding them) are isolates.
• A webapp might choose to centralize each component's state into an isolate.
• A compiler could put a stage's Abstract Syntax Tree into an isolate.
• A message sent via a channel from one thread to another would be an isolate, giving a language fearless concurrency.

By default, nothing inside an isolate can point out either, though Part 3 shows how we can enable that using one-way isolation. Most private data can actually be expressed very cleanly with one-way isolation. 3

Part 4 also shows how one-way isolation can make certain patterns (iterating, determinants, etc.) and entire architectures (like entity-component-system) zero-cost. 4

For the rest of this post though, we'll focus on regular isolates, where nothing inside can point out.

Most programs are naturally hierarchies of isolated data, 5 no matter what language they're written in. We can use the ' syntax to help the compiler know where those isolates are, so it can make more optimal code. 6

One doesn't need to '-annotate everything, of course. Consistent with Vale's philosophy of avoiding forced complexity, isolates are opt-in.

One would '-annotate only the parts of their program that profiling suggests would benefit from optimization.

Immutable Borrowing

We can immutably borrow an isolate's data, allowing the compiler to skip generation checks when reading it. This can make our code faster.

This is the same mechanism used by pure functions, described in Part 1.

This allows us to get the optimization benefits of affine types (like those seen in Rust and Cyclone), but with a vital improvement: it doesn't have aliasing restrictions, and enables techniques and optimizations that require shared mutability. 7

An Example

First, here's an example before we use isolation. We'll add isolation to it afterward.

Generation checks are rarely a source of significant slowdowns. However, if we're in the hot path of a performance-critical program, profiling might suggest that we optimize this function.

Let's optimize!

Optimizing with Isolation

If we can immutably borrow cannon, then we can skip those generation checks!

One way to do this is to make cannon isolated, and then open it up .immutably. 9

Now, cannon is immutably borrowed, so reading it (like cannon.strength) is faster because it doesn't incur any generation checks.

In this example, reading anything from cannon is zero cost, because we used .imm to open the isolate immutably.

This is the true strength of isolates: they tell the compiler when areas of our data are immutable, so it can read them with zero cost.

A Real World Example

Let's say we want a level generator for a simple game.

Here's the coalesceImage function. 11

The important part here is the r' in &r'[][]bool. It means this parameter is in a separate region from the rest of the parameters, and we only see the region as read-only. 12

When main calls coalesceImage, the compiler sees two things:

• We're passing an isolated object.
• The function parameter sees it as from a read-only region.

The compiler concludes that nobody's going to change anything in the region, therefore it's temporarily immutable. It generates a coalesceImage function that is optimized accordingly, eliminating memory safety overhead when reading from that region.

If you're curious, here's the averageNeighbors function, which takes its parameters in a similar way:

func averageNeighbors<r'>(rand &LCGRand, tiles &r'[][]bool, x int, y int) bool {
  num_neighbors = 0;
  num_white_neighbors = 0;
  foreach neighbor_x in range(x - 1, x + 1) {
    foreach neighbor_y in range(y - 1, y + 1) {
      if neighbor_x in 0..tiles.len() and neighbor_x in 0..tiles[0].len() {
        set num_neighbors += 1;
        set num_white_neighbors += if white { 1 } else { 0 };
      }
    }
  }
  result_is_white =
      if num_white_neighbors * 2 == num_neighbors {
        // Even number of white and black neighbors, so choose randomly.
        rand.next() mod 2 == 0
      } else {
        // true if most neighbors are white
        num_white_neighbors > num_neighbors / 2
      };
  return result_is_white;
}

Cells

Above, we showed how an isolate in a variable can be passed to a function that reads from it.

Isolates are incredibly versatile when held in local variables, as we saw above.

However, when a struct member is an isolate, it can only be accessed when: 13

• The containing struct is destroyed first. 14 15
• The containing struct is also an isolate.
• The containing struct is in an immutable region.
• We use a cell.

A cell relaxes these restrictions by moving some checks to run-time. 16

The above example did an immutable borrow using .imm. We can also:

• Mutably borrow the Engine with .open.
• Readonly borrow the Engine with .read, which lets us read it while others modify it.

There are two caveats to using cells:

• We can borrow it with .read and .open as much as we want, but the program will halt if it's ever borrowed with .imm and .open at the same time.
• The program will halt if someone destroys that Ship while someone is borrowing it.

So what's actually happening with that line, engine = ship.engine.imm;?

Cell Guards

When we borrow from a cell, we get a cell guard.

For example, if ship.engine is a ''Engine, then immutably borrowing it like engine = ship.engine.imm will make engine a CellGuard<imm, Engine>.

Under the hood, a CellGuard contains a pointer to the original cell.

When the CellGuard goes out of scope, will inform the original cell that we're done borrowing it.

This is how the language enforces that we don't immutably borrow and readwrite borrow the cell at the same time, which protects us from memory problems.

So if engine is a CellGuard<imm, Engine>, how is it possible to say engine.fuel, like in println(engine.fuel)?

A Cell Guard's Mask

A cell guard has an interesting quirk: it wears a mask.

Mentioning its name, like the engine in println(engine.fuel), does not give us the CellGuard<imm, Engine>.

Instead, it gives us the contents, &e'Engine. e is hidden, an implicit region that's conceptually tied to the cell guard.

The compiler then makes sure that no references into this region outlive the cell guard itself, similar to when we open a regular isolate.

Architectural Benefits

Besides having better performance via immutable borrowing, isolates and cells can also have architectural benefits as well.

First, it indirectly helps us stick to unidirectional data flow, the pattern where after we're done modifying the data, it's read-only for the rest of the operation. This pattern might be familiar:

• React (and other functional reactive programming approaches) are built upon this principle.
• The borrow checker steers us in this direction; we commonly construct some data and then only read it afterward.
• Functional programming enforces this pattern, by not letting us change data after it's constructed.
• This pattern is common in object-oriented code too, as a way to uphold invariants.

Second, it ensures that a struct's private data won't be unexpectedly changed by anyone outside.

In other languages, we can accidentally make a reference to some private data that escapes to someone outside our class. Then, someone uses that reference to modify the data that we thought was private, in unexpected ways that cause bugs. With regionsthe compiler prevents this from ever happening.

The best thing about isolation however is that it is opt-in. Consistent with Vale's philosophy of avoiding forced complexity, we never have to use isolation, or isolates, or regions at all. As more of us experiment with regions, we can learn the best places to apply them.

Conclusion

As we saw, isolates can be surprisingly powerful for optimization, and using them well can make a program much faster.

There are some details we didn't cover in the article:

• We can attach an allocator to an isolate, such as BumpAllocator^'Fleet. 17
• We can use an isolate to create something and then permanently freeze it. 18
• We can hand a mutably-opened isolate into a pure function, and have it remain mutable.
• We can't mutably .open a cell that's inside a read-only region (this has some benefits later for seamless concurrency), unless inside a mutex.
• We can completely contain a third-party library's code inside an isolate if we wanted to; isolates are very composable.

Part 3 also shows how an isolate's contents can point outside the isolate using one-way isolation, which fits well with most structs' private data.

Part 4 shows how we can have one object contain another region's data inline.

Part 5 then shows how to combine that with one-way isolation to make certain patterns (iterating collections, calculating determinants, etc.) and entire architectures (like entity-component-system) zero-cost. 19

That's all for now! We hope you enjoyed this article. Stay tuned for the next article, which shows how one-way isolation works.

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

20