Optimizing for the common case, in language design

TL;DR — Hardware designers make the common case fast. A language can make the common case need no extra words. The most common parallel loop starts one task per index. Go, C# and JavaScript first made that loop a trap, and later changed the language. Rust makes it correct with one keyword, move. In Vx, a task takes each variable the way it uses it (borrow, copy or move) with no move keyword, and a copy can never go stale. The loop needs nothing extra, and a program that a silent copy would get wrong fails to compile.

“Make the common case fast” is one of the oldest rules of computer architecture. A designer measures what programs do most often, and spends the effort there. The rare case can be slow, as long as it stays correct. The same rule works for a programming language. There, the cost is what the programmer must write and read. So the common case should need no extra words, and the rare case should be visible in the code.

The common case: one task per index

Most parallel code starts a task for each item of a list, or for each index of a range. Each task needs its own index, and it reads data that all the tasks share. In Vx, the loop looks like this:

fn work(i : i32) -> void {
  println!("task {}", i);
}

fn main() -> i32 {
  tasks {
    for i in 0..4 {
      spawn { work(i) };   // the task copies i
    }
  }
  return 0;
}

It prints task 0 to task 3. A tasks block waits for every task that it starts, so no task can outlive the variables that it uses. Each task gets its own copy of i, so i may end with its iteration of the loop. A task ends at its join: a call to join() on the task's handle, or the end of its tasks block. Today each task runs to its end at its spawn, which the design allows. Threads come later (#1863).

Three languages made this loop a trap

The loop looks simple, but three popular languages first got it wrong. In each one, the task or the closure kept a reference to the loop variable, and the loop changed that variable. This is the example from the Go team's post “Fixing For Loops in Go 1.22”:

func main() {
    done := make(chan bool)

    values := []string{"a", "b", "c"}
    for _, v := range values {
        go func() {
            fmt.Println(v)
            done <- true
        }()
    }

    // wait for all goroutines to complete before exiting
    for _ = range values {
        <-done
    }
}

Before Go 1.22, the three goroutines shared one variable v. The post says that they “usually print ‘c’, ‘c’, ‘c’”, and calls the mistake “one of the most common Go mistakes”. Go 1.22 changed for loops so that “each iteration of the loop creates new variables, to avoid accidental sharing bugs”.

C# had the same problem with foreach. Eric Lippert, then on the C# compiler team, called it “the single most common incorrect bug report we get”. People reported a compiler bug, but their code was wrong. C# 5 made the foreach variable new for each iteration (his post). JavaScript made the same choice with let. A closure made in a for (var i ...) loop sees one shared i, and three such closures return 3 3 3. With for (let i ...), they return 0 1 2.

In all three languages, the fix made the common case right with no new keyword. Each iteration of the loop got its own variable.

Rust: correct, with one keyword

Rust's scoped threads borrow the variables that they use. A borrow of i cannot outlive its iteration, and a scoped thread may run until the end of the scope. So Rust refuses the loop:

use std::thread;
fn work(i: usize) -> usize { i * 2 }
fn main() {
    thread::scope(|s| {
        for i in 0..4 {
            s.spawn(|| work(i));
        }
    });
}
error[E0373]: closure may outlive the current function, but it borrows `i`, which is owned by the current function

The error suggests move, and s.spawn(move || work(i)) compiles. This is correct, and the code says what it does. But move applies to every variable that the closure uses. To share one Vec among the threads of a loop, Rust code first writes let v = &v;. Then each thread copies a reference, and the Vec stays where it is. Without that line, the first iteration moves v, and the second gets E0382, “use of moved value”. So the loop index forces move, and move then forces a workaround for the shared data, which should stay where it is.

Rust programmers know this pattern well. Niko Matsakis's draft RFC “Explicit annotation on captures” shows it, with let y = &y; before a move closure. It says: “Most people don't realize this is an option and instead simply get frustrated.”

With move, Rust also copies a Copy value, and nothing warns about a later write to it. This program compiles, and the thread never stops:

use std::thread;
fn main() {
    let mut stop = false;
    thread::scope(|s| {
        s.spawn(move || while !stop {});
        stop = true;   // the thread has its own copy of stop
    });
}

A reader can see the copy, because the code says move. Without move, Rust refuses the write: error[E0506]: cannot assign to `stop` because it is borrowed.

Vx: the use decides

A Vx task takes each variable the way its body uses it (#1938):

Here one tasks block does all three. It borrows v, copies half and moves w, with no annotation:

import std::vec;

fn numbers(n : i32) -> Vec<i32> {
  let mut v = Vec<i32>::new();
  for i in 0..n {
    v.push(i);
  }
  return v;
}

fn sum(v : &Vec<i32>, start : i32, end : i32) -> i32 {
  let mut total = 0;
  for i in start..end {
    total += v[i];
  }
  return total;
}

fn last(v : Vec<i32>) -> i32 {
  return v[v.len() - 1];
}

fn main() -> i32 {
  let v = numbers(10);
  let w = numbers(3);
  let half = 5;
  let total = tasks {
    let left = spawn { sum(&v, 0, half) };    // borrows v, copies half
    let right = spawn { sum(&v, half, 10) };  // borrows v, copies half
    let tail = spawn { last(w) };             // moves w
    left.join() + right.join() + tail.join()
  };
  println!("{}", total);
  return 0;
}

It prints 47. Two tasks share v without let v = &v;, because both tasks only read it. So each variable gets its own treatment, from how the task uses it. The task borrows a big Vec that it reads. It copies a loop index. It moves a value that ends with its iteration of the loop. To move a variable that the body only borrows, the body writes let t = x;. That is the only extra line in the design, and few programs need it.

In Vx, a task takes each variable the way it uses it (borrow, copy or move) with no move keyword, and a copy can never go stale.

The trap in a silent copy

A silent copy goes wrong when the code around the task writes the variable later. The task never sees the new value. The first version of the change that adds tasks (#1925) copied stop here, so this program compiled and the task never stopped:

fn main() -> i32 {
  let mut stop = false;
  let mut spins = 0;
  tasks {
    spawn {
      while !stop {
        spins += 1;
      }
    };
    stop = true;   // the task copied stop, so it would never see this
  }
  return 0;
}

Rust's move has the same result, but the keyword shows the copy. In Vx nothing showed it. A warning, W1034, reported a write to a variable that a running task copied. It also reported code that was correct, such as spawn { work(x) }; x += 1;. A warning that fires on correct code teaches people to ignore it.

A copy that can never go stale

The fix keeps the copy and forbids the write that would show it. Until the task's join, or the end of its tasks block, the code around the task may not write a variable that the task copied. The variable may still end before the task does, as a loop index does. That is the reason the task copies it instead of borrowing it.

So the task sees the same value whether it copied the variable or borrowed it: the variable's current value. The checker treats the copy as a borrow that only a write conflicts with, so the error speaks of a borrow. The stop flag is now an error, with a hint:

Error[E4009] at 10:5: `stop` is assigned while it is borrowed, and the borrow is used after the assignment. A task that is not joined yet copied it, so it must not change until the task ends. To give the task the value that it has now, copy it into a new variable before the `spawn`. To share a value that changes, use an atomic.

Each rare case needs one line, and that line shows the intent. To give the task the value as it is now, the program copies it first:

fn work(x : i32) -> void {
  println!("work {}", x);
}

fn main() -> i32 {
  let mut x = 1;
  tasks {
    let x0 = x;
    spawn { work(x0) };   // the task copies x0, which nothing writes
    x += 1;
  }
  println!("x {}", x);
  return 0;
}

It prints work 1, then x 2. To share a value that changes, such as the stop flag, the program uses an atomic or a channel. W1034 is gone, and so are its false alarms. The rule made the formal model of tasks simpler too. With no write until the join, a copy at the spawn gives the task the same value as a read in place.

This is stricter than Rust in one place. A Rust move closure may change x after the spawn, because the closure has its own copy. Vx refuses that write until the join. A programmer who comes from Rust may meet this error. The hint fixes it in one line, and a write there is often a mistake, as the stop flag was.

One Rust complaint is a different problem: the Arc::clone before each thread::spawn. A thread from thread::spawn may outlive the function that starts it, so it cannot borrow, and shared data needs a reference count. A Vx task cannot outlive its tasks block, so it borrows instead. That complaint would return only if Vx added tasks that outlive their block.

Here are the five options that #1938 compared, on the two programs above:

OptionThe loopThe stop flagNew syntax
Copy, with a warningCompilesCompiles, with a warning that also fires on correct codeNone
Borrow onlyNeeds let j = i;ErrorNone
Rust's moveNeeds moveCompiles, and move shows the copyspawn move
A list, like C++'s [i, &v]Needs move(i)Compiles, and the list shows the copymove(..)
A copy never goes staleCompilesError, with a hintNone

Closures are next

A Vx closure has the same problem today:

fn main() -> i32 {
  let mut x = 10;
  let add = |y : i32| x + y;
  x = 20;
  println!("{}", add(1));
  return 0;
}

It prints 11, because the closure copied x when the program made the closure. Rust refuses the same program: error[E0506]: cannot assign to `x` because it is borrowed. The plan in #1938 is to give closures the same rule until their last use. That change can break programs that compile today, and each one needs a one-line fix, so a warning comes first, for one release.

The pattern

The design follows three rules:

Go and C# changed the meaning of their loops years after release. Vx can make the choice before its tasks ship. The change that adds tasks and spawn, #1925, is in review. Every Vx program in this post ran on its branch.

Vx is Apache 2.0 with the LLVM exception — install it and try the examples.