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 nomovekeyword, 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):
- It moves a variable that its body moves.
- It moves a variable that is not
Copyand that ends before the task's join. An example is a value made in one iteration of a loop. A borrow of that variable can never be valid. - It copies a
Copyvalue that it only reads, at itsspawn. As in Rust,Copyvalues copy bit by bit. They include numbers,boolvalues, shared references, and structs that implementCopy. - It borrows every other variable, until its join.
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
movekeyword, 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:
| Option | The loop | The stop flag | New syntax |
|---|---|---|---|
| Copy, with a warning | Compiles | Compiles, with a warning that also fires on correct code | None |
| Borrow only | Needs let j = i; | Error | None |
Rust's move | Needs move | Compiles, and move shows the copy | spawn move |
A list, like C++'s [i, &v] | Needs move(i) | Compiles, and the list shows the copy | move(..) |
| A copy never goes stale | Compiles | Error, with a hint | None |
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:
- The common case needs no extra words.
- The case that a silent default gets wrong is a compile error, with a hint.
- Each rare case needs one line, and the line shows the intent.
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.