Cone

The execution of a program unfolds over some interval of time. The lifetime of every temporary resource (e.g., variable or object) is the time span between that resource’s “creation” and “destruction”. This lifetime is wholly contained within the typically-longer lifetime of the program. The goal of this post is to explore how versatile lifetime analysis has increasingly become in managing memory efficiently, safely and with better performance. By the end of this post, we will explore exciting new ways to apply lifetime analysis, beyond their current support in Rust.

Note: You can read Russian translation here. I have always wanted the Cone compiler to be fast. Faster build times make it easier and more pleasant for the programmer to iterate and experiment quickly. Compilers built for speed, such as Turbo Pascal, D and Go, win praise and loyalty. Languages that struggle more with this, like C++ or Rust, get regular complaints and requests to speed up build times.

The decades-long golden age of Moore’s Law is fading. Slow, bloated software will find it increasingly difficult to hide behind the skirt of ever-faster computer hardware. Given that businesses and users will not yield on their demand for speedy software, developers will need to get a lot better at architecting for performance. In his excellent article on Performance Culture, Joe Duffy begins: “Performance is one of the key pillars of software engineering, and is something that’s hard to do right, and sometimes even difficult to recognize.

To complete our three-part series on permissions, which began with Race-Safe Strategies, let’s talk about the transitional nature of reference permissions. When are permissions transitional? When we can safely create a copy of a reference which has a different permission than the reference it copied from. There are several ways in which this can happen, which this diagram summarizes (and the following sections explain): The following sections describe the nature of several one-way transitions that flow downward in the diagram.

In my last post, Race-safe Strategies, one footnote stated “safety issues which look suspiciously similar to race conditions can crop up when a language supports the creation of “interior references” to shared, mutable values of certain types”. Let’s explore that now. I will begin by recapitulating Manish Goregaokar’s excellent post “The Problem With Single-Threaded Shared Mutable”. His post clearly explains why the Rust language wishes to steer developers towards RefCell for shared references over use of Cell, its inflexible shared, mutable counterpart.

I recently made the observation that many people seem unaware of the full collection of constraint mechanisms available for protecting race safety. Someone sensibly asked for a link to an article that provides a modern, comprehensive review. It turns out that the pickings are very slim; the best I could find is this Wikipedia article on thread safety. It’s accurate, but incomplete. To close that gap, let me take a stab here at more comprehensive treatment.

Most programming languages support only copy semantics. A value passed to a function or stored in a variable is a copy of the original value. We know it is a copy, because any change we make to the copy has no impact on the original value. A few languages, like C++ and Rust, also support move semantics. Unlike a copy, a transfer moves the original value to its new home; that value is no longer accessible at its previous home.

Note: The latter part of this post is outdated in terms of the mechanisms that the Cone compiler uses to de-alias ref-counted references. See this post for an updated description. In the world of automatic memory management, reference counting is considered to be one of the easiest to implement. The rules seem simple: When a reference is created to an allocated memory area, set its counter to 1 When the reference is copied (aliased), increment the counter When an alias is destroyed (de-aliased), decrement the counter When the counter reaches zero, free the reference’s memory area The simplicity of these rules does not always translate to a simple implementation.

Note: This is an outdated post, replaced by this post The Cone compiler performs a data flow analysis pass after name resolution and type checking. Given that this sort of analysis is rarely covered by compiler literature, I thought it might be useful to jot down some thoughts about its purpose and intriguing mechanics. Goals Like Rust (and unlike C), Cone applies constraints to references that ensure they can only access memory safely, even in the face of concurrency.

As mentioned in the previous post, all typed nodes use the TypedNodeHdr common header. It only contains a pointer to the node’s type. This type field applies to every node in the “expression” group. This group holds all node types that return a value, including leaf nodes like literals and variables, function call nodes, and even the block and if nodes. The type check pass focuses largely on this type field, ensuring it specifies a valid, consistent type.