First Class Goto

Oort is an experimental programming language I have been working on, on and off (mostly off), since 2007. It is a statically typed, object-oriented, imperative language, where classes, functions and methods can be nested arbitrarily, and where functions and methods are full closures, ie., they can be stored in variables and returned from functions. The control structures are the usual ones: if, for, while, do, goto, etc.

It also has an unusual feature: goto labels are first class.

What does it mean for labels to be first class? It means two things: (1) they are lexically scoped so that they are visible from inside nested functions. This makes it possible to jump from any point in the program to any other location that is visible from that point, even if that location is in another function. And (2) labels can be used as values: They can be passed to and returned from functions and methods, and they can be stored in data structures.

As a simple example, consider a data structure with a “foreach” method that takes a callback function and calls it for every item in the data structure. In Oort this might look like this:

table: array[person_t];

table.foreach (fn (p: person_t) -> void {
        print p.name;
        print p.age;
    });

A note about syntax. In Oort, anonymous functions are defined like this:

fn (<arguments>) -> <return type> {
    ...;
}

and variables and arguments are declared like this:

<name>: <type>

so the code above defines an anonymous function that prints the name and the age of person and passes that function to the foreach method of the table.

What if we want to stop the iteration? You could have the callback return true to stop, or you could have it throw an exception. However, both methods are a little clumsy: The first because the return value might be useful for other purposes, the second because stopping the iteration isn’t really an exceptional situation.

With lexically scoped labels there is a direct solution – just use goto to jump out of the callback:

  table.foreach (fn (p: person_t) -> void {
          print p.name;
          print p.age;

          if (p.age > 50)
              goto done;
      });

@done:

Note what’s going on here: Once we find a person older than 50, we jump out of the anonymous callback and back into the enclosing function. The git tree has a running example.

Call/cc in terms of goto
In Scheme and some other languages there is a feature called call/cc, which is famous for being both powerful and mind-bending. What it does is, it takes the concept of “where we are in the program” and packages it up as a function. This function, called the continuation, is then passed to another, user-defined, function. If the user-defined function calls the continuation, the program will resume from the point where call/cc was invoked. The mind-bending part is that a continuation can be stored in data structures and called multiple times, which means the call/cc invocation can in effect return more than once.

Lexically scoped labels are at least as expressive as call/cc, because if you have them, you can write call/cc as a function:

call_cc (callback: fn (k: fn()->void)) -> void
{
    callback (fn() -> void { 
        goto current_continuation;
    });

@current_continuation:
}

Let’s see what’s going on here. A function called call_cc() is defined:

call_cc (...) -> void
{
}

This function takes another function as argument:

callback: fn (...) -> void

And that function takes the continuation as an argument:

k: fn()->void

The body of call/cc calls the callback:

callback (...);

passing an anonymous function (the continuation):

    fn() -> void {
        goto current_continuation;
    }

@current_continuation:

that just jumps to the point where call_cc returns. So when callback decides to invoke the continuation, execution will resume at the point where call_cc was invoked. Since there is nothing stopping callback from storing the continuation in a data structure or from invoking it multiple times, we have the full call/cc semantics.

Cooperative thread system
One of the examples on the Wikipedia page about call/cc is a cooperative thread system. With the call_cc function above, we could directly translate the Wikipedia code into Oort, but using the second aspect of the first-class-ness of labels – that they can be stored directly in data structures – makes it possible to write a more straightforward version:

run_list: list[label] = new list[label]();

thread_fork (child: fn() -> void)
{
    run_list.append (me);
    child();
    goto run_list.pop_head();
@me:
}

thread_yield()
{
    run_list.append (me);
    goto run_list.pop_head ();
@me:
}

thread_exit()
{
    if (!run_list.is_empty())
        goto run_list.pop_head();
    else
        process_exit();
}

The run_list variable is a list of labels containing the current positions of all the active threads. The keyword label in Oort is simply a type specifier similar to string.

To create a new thread, thread_fork first saves the position of the current thread on the list, and then it calls the child function. Similarly, thread_yield yields to another thread by saving the position of the current thread and jumping to the first label on the list. Exiting a thread consists of jumping to the first thread if there is one, and exiting the process if there isn’t.

The code above doesn’t actually run because the current Oort implementation doesn’t support genericity, but here is a somewhat uglier version that actually runs, while still demonstrating the principle.

Celebrities die 2.7183 at a time

The claim that celebrities die in threes is usually dismissed as the result of the human propensity to see patterns where there are none. But celebrities don’t die at regularly spaced intervals either. It would be very weird if a celebrity predictably died on the 14th of every month. And once you deviate from a regularly spaced pattern, some amount of clustering is inevitable. Can we make this more precise?

Rather than trying to define exactly what constitutes a celebrity, I’ll simply assume that they die at a fixed rate and that they do so independently of each other (The Day the Music Died notwithstanding). It follows that celebrity deaths is a Poisson process with intensity $\lambda$ where $\lambda$ is the number of deaths that occur in some fixed time period.

As an example, suppose we define celebrityhood in such a way that twelve celebrities die each year on average. Then $\lambda = 12/\text{year}$, and because the time between events in a Poisson process is exponentially distributed with parameter $\lambda$, the average time between two deaths is $1/\lambda$ = 1/12th year, or one month.

What does it mean for celebrities to die $n$ at a time? We will simply say that two celebrities die together if the period between their deaths is shorter than expected. If the celebrity death rate is 12/year, then two celebrities died together if their deaths were less than one month apart. Similarly, three celebrities died together if the period between death 1 and death 2 and the period between death 2 and death 3 were both shorter than a month. In general, $k$ celebrities died together if the $k - 1$ periods between their deaths were all shorter than expected.

Here is a diagram of 10 years worth of randomly generated deaths with 12 deaths per year and clusters as defined above highlighted:

Average cluster size
Suppose a celebrity has just died after a longer than average wait. This death will start a new cluster, and we want to figure out what the size of it is.

In a Poisson process the waiting time between two events is exponentially distributed with parameter $\lambda$, so it can be modelled with a stochastic variable $W \sim Exp(\lambda)$. The cluster size itself is modelled with another stochastic variable, $C$, whose distribution is derived as follows.

The cluster size will be 1 when the waiting time for the next death is larger than or equal to the average (which is $1/\lambda$ for the exponential distribution):

$\text{P}(C = 1) = \text{P}(W > 1/\lambda)$

The probability that the cluster will have size 2 is the same as the probability that the next waiting time is shorter than average and the next one after that is longer:

$\text{P}(C = 2) = \text{P}(W \le 1/\lambda)\cdot \text{P}(W > 1/\lambda)$

For size three, it’s the probability that the next two waiting times are shorter and the third one longer:

$\text{P}(C = 3) = \text{P}(W \le 1/\lambda)^2\cdot \text{P}(W > 1/\lambda)$

In general, the probability that the next cluster will be size $k$ is:

$\text{P}(C = k) = \text{P}(W \le 1/\lambda)^{k - 1}\cdot \text{P}(W > 1/\lambda)$

So what’s the average size of a Celebrity Death Cluster? The expected value of $C$ is given by:

$\displaystyle \text{E}[C] = \sum_{k=1}^\infty k \cdot \text{P}(C = k) = \sum_{k=1}^\infty k\cdot \text{P}(W \le 1/\lambda)^{k - 1}\cdot \text{P}(W > 1/\lambda)$

Plugging in the distribution function for the exponential distribution, we get:

$ \begin{align*} \text{E}[C] &= \sum_{k=1}^\infty k \cdot (1 - e^{- \lambda \cdot (1/\lambda) })^{k - 1} \cdot (1 - (1 - e^{- \lambda \cdot (1 / \lambda)}))\\ &= \sum_{k=1}^\infty k \cdot (1 - e^{- 1})^{k - 1} \cdot e^{-1} \end{align*} $

It’s not hard to show that this infinite series has sum $e$ (Hint: Use the fact that $k x^{k - 1}$ is the derivative of $x^k$), so on average, celebrities die 2.7183 at a time.

The Radix Heap

The Radix Heap is a priority queue that has better caching behavior than the well-known binary heap, but also two restrictions: (a) that all the keys in the heap are integers and (b) that you can never insert a new item that is smaller than all the other items currently in the heap.

These restrictions are not that severe. The Radix Heap still works in many algorithms that use heaps as a subroutine: Dijkstra’s shortest-path algorithm, Prim’s minimum spanning tree algorithm, various sweepline algorithms in computational geometry.

Here is how it works. If we assume that the keys are 32 bit integers, the radix heap will have 33 buckets, each one containing a list of items. We also maintain one global value last_deleted, which is initially MIN_INT and otherwise contains the last value extracted from the queue.

The invariant is this:

The items in bucket $k$ differ from last_deleted in bit $k - 1$, but not in bit $k$ or higher. The items in bucket 0 are equal to last_deleted.

For example, if we compare an item from bucket 10 to last_deleted, we will find that bits 31–10 are equal, bit 9 is different, and bits 8–0 may or may not be different.

Here is an example of a radix heap where the last extracted value was 7:

As an example, consider the item 13 in bucket 4. The bit pattern of 7 is 0111 and the bit pattern of 13 is 1101, so the highest bit that is different is bit number 3. Therefore the item 13 belongs in bucket $3 + 1 = 4$. Buckets 1, 2, and 3 are empty, but that’s because a number that differs from 7 in bits 0, 1, or 2 would be smaller than 7 and so isn’t allowed in the heap according to restriction (b).

Operations
When a new item is inserted, it has to be added to the correct bucket. How can we compute the bucket number? We have to find the highest bit where the new item differs from last_deleted. This is easily done by XORing them together and then finding the highest bit in the result. Adding one then gives the bucket number:

bucket_no = highest_bit (new_element XOR last_deleted) + 1

where highest_bit(x) is a function that returns the highest set bit of x, or $-1$ if x is 0.

Inserting the item clearly preserves the invariant because the new item will be in the correct bucket, and last_deleted didn’t change, so all the existing items are still in the right place.

Extracting the minimum involves first finding the minimal item by walking the lowest-numbered non-empty bucket and finding the minimal item in that bucket. Then that item is deleted and last_deleted is updated. Then the bucket is walked again and all the items are redistributed into new buckets according to the new last_deleted item.

The extracted item will be the minimal one in the data structure because we picked the minimal item in the redistributed bucket, and all the buckets with lower numbers are empty. And if there were a smaller item in one of the buckets with higher numbers, it would be differing from last_deleted in one of the more significant bits, say bit $k$. But since the items in the redistributed bucket are equal to last_deleted in bit $k$, the hypothetical smaller item would then have to also be smaller than last_deleted, which it can’t be because of restriction (b) mentioned in the introduction. Note that this argument also works for two-complement signed integers.

We have to be sure this doesn’t violate the invariant. First note that all the items that are being redistributed will satisfy the invariant because they are simply being inserted. The items in a bucket with a higher number $k$ were all different from the old last_deleted in the $(k-1)$th bit. This bit must then necessarily also be different from the $(k-1)$th bit in the new last_deleted, because if it weren’t, the new last_deleted would itself have belonged in bucket $k$. And finally, since the bucket being redistributed is the lowest-numbered non-empty one, there can’t be any items in a bucket with a lower number. So the invariant still holds.

In the example above, if we extract the two ‘7’s from bucket 0 and the ‘8’ from bucket 4, the new heap will look like this:

Notice that bucket 4, where the ‘8’ came from, is now empty.

Performance
Inserting into the radix heap takes constant time because all we have to do is add the new item to a list. Determining the highest set bit can be done in constant time with an instruction such as bsr.

The performance of extraction is dominated by the redistribution of items. When a bucket is redistributed, it ends up being empty. To see why, remember that all the items are different from last_deleted in the $(k - 1)$th bit. Because the new last_deleted comes from bucket $k$, the items are now all equal to last_deleted in the $(k - 1)th$ bit. Hence they will all be redistributed to a lower-numbered bucket.

Now consider the life-cycle of a single element. In the worst case it starts out being added to bucket 31 and every time it is redistributed, it moves to a lower-numbered bucket. When it reaches bucket 0, it will be next in line for extraction. It follows that the maximum number of redistributions that an element can experience is 31.

Since a redistribution takes constant time per element distributed, and since an element will only be redistributed $d$ times, where $d$ is the number of bits in the element, it follows that the amortized time complexity of extraction is $O(d)$. In practice we will often do better though, because most items will not move through all the buckets.

Caching performance
Some descriptions of the radix heap recommend implementing the buckets as doubly linked lists, but that would be a mistake because linked lists have terrible cache locality. It is better to implement them as dynamically growing arrays. If you do that, the top of the buckets will tend to be hot which means the per-item number of cache misses during redistribution of a bucket will tend to be $O(1/B)$, where $B$ is the number of integers in a cache line. This means the amortized cache-miss complexity of extraction will be closer to $O(d/B)$ than to $O(d)$.

In a regular binary heap, both insertion and extraction require $\Theta(\log n)$ swaps in the worst case, and each swap (except for those very close to the top of the heap) will cause a cache miss.

In other words, if $d = \Theta(\log n)$, extraction from a radix heap will tend to generate $\Theta(\log n / B)$ cache misses, where a binary heap will require $\Theta(\log n)$.