Repository navigation
Solving the Multicore Dilemma
This page condenses and updates two older articles, "The Flow Manifesto" (2010) and "Solving the Multicore Dilemma" (2012). The language was called Flow when those articles were written. It was renamed Zed in 2012, when the zedlang.org domain was registered. The text below brings the two articles up to date with the design of Zed at the end of 2026. The rest of the language is summarized on Motivations and Design Philosophy Behind Zed.
"Finding: There is no known alternative for sustaining growth in computing performance; however, no compelling programming paradigms for general parallel systems have yet emerged." (p. 81)
"Recommendation: Invest in research and development of programming methods that will enable efficient use of parallel systems not only by parallel systems experts but also by typical programmers" (p. 99)
-- The Future of Computing Performance: Game Over or Next Level? Fuller & Millett (Eds.); Committee on Sustaining Growth in Computing Performance, National Research Council, The National Academies Press, 2010
Per-core performance now grows much more slowly than it once did, while the number of cores keeps rising. When the first of these articles was written, in 2010, AMD had just launched the Opteron 6100, with 8 or 12 cores per chip. In October 2024, AMD launched the EPYC 9965, with 192 cores per chip, and Intel's Xeon 6 has up to 128 performance cores. In 2010, GPUs were a niche for general-purpose code. Now they hold most of the arithmetic capacity of many machines.
The languages most people use have not kept up. For parallel work, today's mainstream languages offer much the same tools as in 2010, with better libraries and a few new language features: threads, locks, futures, async/await, parallel streams and actors. Every one of these leaves it to you to decide which work may run in parallel and how that work is synchronized. So most code still runs on one core, and multithreaded code is prone to races and deadlocks.
In Zed, the line below sums every row of a table, and the rows run on as many cores as there are, with no thread, lock or parallel library written:
sums = rows.map(row -> row >< (+)); // no row's sum depends on another's, so they run in parallelPaul Graham described the problem in 2012:
"It would be great if a startup could give us something of the old Moore's Law back, by writing software that could make a large number of CPUs look to the developer like one very fast CPU. There are several ways to approach this problem. The most ambitious is to try to do it automatically: to write a compiler that will parallelize our code for us. There's a name for this compiler, the sufficiently smart compiler, and it is a byword for impossibility. But is it really impossible?"
-- Paul Graham, "Frighteningly Ambitious Startup Ideas," March 2012
This page argues two things. The sufficiently smart compiler can be built if a language makes one specific restriction, described below. And without that restriction, such a compiler can handle only some programs, never all. Libraries and models such as java.util.concurrent, Spark, Erlang-style message passing and OpenMP help, but each requires the program to be shaped around it. The goal is a program that says what to compute, while the compiler decides how to split the work, at every scale from single operations to clusters of machines:
"Write once, parallelize anywhere."
- Automatic parallelization. Scheduling work across processors becomes the system's job, as garbage collection made reclaiming memory the system's job. The only sequencing in a program is data dependency.
- The classic bugs cannot be written. Data races, deadlocks inside the program, null dereference, use before initialization, and unhandled failures (such as division by zero or out-of-bounds indexing) cannot be expressed in the language.
- Parallelization by algebra. Where the checker proves the properties of an operator (associativity, commutativity, identity elements), the compiler regroups and reorders computations. That lets it parallelize code that looks serial, such as a fold.
- One source for many machines. Where it can, the compiler derives the cost of each computation as a function of its input sizes, so it can choose how to split the work for the machine at hand. One program compiles to multicore CPUs, WebAssembly, GPUs and clusters of machines, and a program whose every part has a static schedule also compiles to hardware synthesis.
-
Precise memory management. There is no manual
malloc/freeand no tracing garbage collector. Memory is allocated when a value is about to be computed and released when its last reader is done, as read off the edges of the dependency graph. - Deterministic results. By default, the same inputs give bit-identical outputs at any core count, floating point included.
- Incremental execution. When an input changes, only what depends on it is recomputed, and the result is the same as recomputing from scratch.
Goals 1, 2, 4 and 5 were the goals of Flow in 2010, and the 2010 article also described the idea behind goal 3. Goals 6 and 7 came later. As the sections below show, they follow from the same design decision. You can use Zed without knowing any of this theory. Goal 2, for example, means that where an index may fall outside an array, the code must say what to do:
x = a[i] else 0; // a[i] may be #outOfBounds, and the program must handle it; here it becomes 0In a pure functional language, two calls to a function cannot interfere with each other, since neither has side effects. In Haskell, map sum [[1,2,3], [4,5,6], [7,8,9]] sums three sublists that do not depend on each other, so the three sums could run at once. The same computation in Zed is
sums = [[1, 2, 3], [4, 5, 6], [7, 8, 9]].map(xs -> xs >< (+)); // [6, 15, 24]But most programmers work in imperative languages such as C++, Java, Python, JavaScript or Rust. So telling them to use a pure functional language does not solve the dilemma in practice.
Imperative languages have side effects. In the Java code below, addToTotal(5) returns a different value each time. Two things go wrong when several threads call it. += is not atomic, so concurrent calls can lose updates. And return total reads total a second time, so a thread can return another thread's update instead of its own:
public class Counter {
private int total;
public int addToTotal(int num) {
total += num;
return total;
}
}In general, which write a given read will see cannot be decided statically; predicting it in every case is as hard as the halting problem. With several threads, a read can see an older or a newer write depending on scheduling. That is a race condition.
Here is a second way to describe the difference. Functional code gathers (pulls) values into a function's parameters and returns one result, which is computed once and never changed. Imperative code also scatters (pushes) values to mutable locations any number of times, possibly from several threads. This Java method counts the words of each length:
int[] histogram(String[] words, int maxLen) {
int[] hist = new int[maxLen + 1];
for (String w : words)
hist[w.length()]++;
return hist;
}Each word scatters a +1 to the bucket for its length:
flowchart LR
w1[""a""] -- "+1" --> h1["hist[1]"]
w2[""zed""] -- "+1" --> h3["hist[3]"]
w3[""flow""] -- "+1" --> h4["hist[4]"]
w4[""the""] -- "+1" --> h3
w5[""cat""] -- "+1" --> h3
That is a natural way to write the code. But ++ is not atomic, so splitting the loop across threads needs atomic increments, locks, or thread-local copies merged afterward. You could turn the loop into a gather (for each length, count the words of that length), but done naively that reads the input once per bucket:
hist = for n in 0..=maxLen { words.where(w -> w.len == n).count };Run as written, that reads words once per bucket. On every length that some word has, Zed's compiler proves it equal to the one-pass group-and-count shown below, and the plans for the two agree on those lengths. The two differ only in that this form also lists the lengths with no words, as 0.
For imperative code in general, deciding which parts can safely run in parallel is undecidable. Compilers handle restricted cases, with techniques such as auto-vectorization and polyhedral loop optimization.
A program's data dependency graph shows which values (not variables) are needed to compute which other values. A value cannot depend on itself, directly or indirectly. So the graph is a directed acyclic graph (DAG), and its paths define a partial order on the values. (The 2010 and 2012 articles called this structure a "lattice." That was wrong. A partial order is a lattice only if every pair of elements has a least upper bound and a greatest lower bound, and most dependency graphs lack them.)
a = 5;
b = f(a);
c = f(a * 2);
d = g(a) + f(a);
e = b + c;
h = d / e;flowchart TD
a --> b
a --> c
a --> d
b --> e
c --> e
d --> h
e --> h
Nothing orders b, c and d relative to one another, nor d relative to e. Any order of these lines that puts every definition before its uses computes the same result. Such an order is called a topological sort, or a linear extension of the partial order. Lines with no directed path between them can run at the same time once their inputs exist.
When you write a program as a sequence of lines, you perform a topological sort in your head. The compiler must then work to rediscover which orderings mattered. The 2010 article concluded that statements should be writable in any order. Zed does not do that. Within a block, a name must be defined above every line that uses it, so a reader never meets a name before it is introduced. But that order is for the reader only. It does not constrain evaluation, and lines with no dependency path between them may run at the same time whatever their position. Top-level declarations may appear in any order:
area(positional r: Rect) = r.w * r.h; // Rect is declared below it, which is allowed at the top level
struct Rect { w: int, h: int }An editor can still show the same program as a graph; the text is one topological sort of that graph.
The graph of values is always a DAG, because a value is computed after the values it reads. The graph of variable references in imperative source is not. A loop that updates x reads x both before and after the update. In an imperative language the compiler cannot in general know, before the program runs, which write a read will see, so it cannot know the true dependency graph. In a pure functional language, the structure of the program shows its data dependencies directly. That, more than the absence of side effects as such, is why functional programs are much easier to parallelize automatically than imperative ones.
Zed keeps the look of a loop that updates a variable, but each read names a step, so the graph is known before the program runs. In the loop below, p is the value the step starts from, which initial gives at step 0, and p' is the value the step computes:
fact = loop {
initial i = 1;
initial p = 1;
while i <= n;
p' = p * i;
i' = i + 1;
};Programmers do not need unrestricted mutable state. They need to count things, accumulate results, update state in a loop and write output. So the question is this: what is the smallest restriction of an imperative language that makes every program's dependency graph known at compile time?
The answer is to remove the ability to read the current value of a variable. Think of what happens when a variable changes. A new node holding the new value appears in the graph. Readers that have not yet run must now point to it, while readers that have already run still point to the old value. With several threads, one reference can thus mean different dependencies depending on timing, which is a race condition. And because dependencies can change at any time, the compiler cannot in general determine statically when memory may be released.
Unrestricted goto fell out of use because it made the control flow of a serial program hard to follow. Reading the current value of a variable does the same to the dependency graph of a parallel program. There is a physical reason too. A write takes time to reach other cores, so cores running at the same time share no single present instant, much as observers separated in space share none in relativity. A language that lets code read a value as it is at the present instant invites results that depend on timing.
The restriction Zed makes so that an imperative language can be parallelized precisely is to make it impossible to read the current value of a variable.
Zed offers three things in its place:
-
Read the only value a name will ever have.
total = readings >< (+);definestotalonce, as the reduction ofreadingswith+. There is no other value oftotalto see. -
Read a value at a named step. At step
tof a loop,x'is the value computed at stept,xis the value from stept-1(at step 0, the valueinitialgives), andx[t-k]is the value fromksteps back. Each names exactly one value:sim = loop t { while t < maxSteps; initial pos = p0; initial vel = v0; pos' = pos + vel * dt; vel' = vel + a(pos) * dt; until pos'.x > bound; };Each step is one generation.
pos'in one step isposin the next. Soposandvellook like variables updated in place, but every read refers to one fixed step. After the loop,sim.posis the final position, andsim::framesis the whole history, keyed by step number. Reading the whole history needs a proved bound on the number of steps, whichwhile t < maxStepsgives; the test onpos'.xalone ends the loop but bounds no count. -
Push values to a collection that combines them with a declared operation. In the word-length histogram, every word pushes 1 to the bucket for its length, and each bucket adds what it receives. The order in which the 1s arrive does not matter, since
+is associative and commutative:hist: int ->? int with reducer((+)); for w in words { hist[w.len] <- 1; };<-is the push operator.int ->? intsayshistmaps someintkeys tointvalues, andreducer((+))says how several values pushed to the same key are combined. No reader seeshistuntil every push to it is done.
You can also write the histogram with no collection to push to: words.group(w -> w.len).count groups the words by length and counts each group. It means the same as the push version, and the compiler turns both into the same internal form.
The source code of a program directly and statically gives its data dependency graph.
In Zed, a reference to a value is the only thing that orders computation:
lo = xs >< min else 0;
hi = xs >< max else 0;
span = hi - lo; // lo and hi have no path between them, so they run in parallel; span waits for bothMany properties follow from that:
- Values, not places. A node of the graph is a value. It cannot be read until it is complete, and it never changes after that. A value is never read while it is being written, whether one writer produces it or a reducer combines many pushes into it. There are no mutable places, so data races cannot occur. Change is the arrival of new values at new steps; old values are not overwritten.
- The graph gives the available parallelism. Two nodes with no directed path between them can be computed in parallel.
- No deadlocks inside a program. A deadlock needs a cycle of waits, and the value graph has no cycles. Queues between parts of a program are not an exception. Only a queue at a port, where the program meets the outside world, can have an overflow policy or make its writer wait. The compiler derives the size of every queue between two parts of the program from the dependency graph, so its writer never waits on it, and a program whose graph or queue sizes the compiler cannot determine does not compile. A bound written on such a queue is only checked against that derived size. A queue written and read inside one loop or recursion is state the loop carries: it cannot block, and the checker must prove that it does not grow without bound. A program can still wait on the outside world. (The 2012 article missed the queue case.)
- No uninitialized reads. An operation is not scheduled until the values it reads are complete.
- Precise memory management. The graph determines when each value is allocated and released: statically where the last reader is known at compile time, and by exact reference counting otherwise.
- Visible dead code. Values that reach no output are pruned and never computed, though a port write, a port read that is not safe to repeat, a process start or a call of foreign code that keeps state still runs where it is reached. A name bound in a block that nothing reads is a compile error, so dead code does not hide.
- Streaming. The pruned graph is a pipeline through which data flows from inputs to outputs. So the same code can process a batch or, where no step needs the whole input, an endless stream of events.
This is related to dataflow programming. But Zed keeps its restriction narrow while still giving these guarantees, so Zed code looks like ordinary code: names, assignments, loops, if and function calls.
The same DAG turns up all over computing. Spreadsheets enforce it. Static single assignment (SSA) form, inside nearly every optimizing compiler, rebuilds it for scalar values, except that loops close cycles through phi nodes. Out-of-order CPUs devote much of each core's logic to rebuilding it at run time, over a small window of instructions, through register renaming. Build systems and reactive UI frameworks each implement part of it. And the most widely used parallel data systems are built on it:
- Spark turns each job into a directed acyclic graph, and its transformations are lazy: they run only when a result is needed.
- Flink dataflows are directed graphs that start at sources and end at sinks.
- A Beam pipeline is a directed acyclic graph of transforms.
- TensorFlow builds a graph of operations so that, among other things, it can find independent parts of a computation and split them between threads or devices.
In each of these, the programmer builds the graph through a library interface, and code outside the graph is ordinary sequential code. Mainstream languages make you write the DAG as a sequence of statements over mutable places. The compiler and CPU then try to recover the lost parallelism, while you add threads and locks by hand, and with them the races and deadlocks the DAG never had. In Zed, the program text directly gives the graph.
Functional programs gather values into function calls; imperative programs also scatter values to places. In Zed, push and pull are two directions of the same edge in the value graph, and the compiler converts between them. The push histogram and group followed by count become the same internal form. So you write whichever is clearer:
hist = words.group(w -> w.len).count; // pull: the same internal form as the push histogram aboveThe compiler then chooses whether to evaluate each edge by push or by pull:
- Pull computes only what is demanded, but may recompute shared work unless its result is kept.
- Push computes each value once, but may compute values nobody reads, and must know its readers.
Dynamic programming shows both. A table filled forward row by row (push) and a memoized recursion from the requested entry (pull) are the same recurrence run in two directions.
if behaves differently in the two directions. In pull, if uses only the branch it selects. The other branch may be started early on a spare core, but its result is discarded, and a branch is never started early if it is not proved to end, writes to a port, reads a port whose reads are not safe to repeat, starts a process, or calls foreign code that keeps state. In push, a value is pushed to one target, to another, or nowhere, so a target may receive no value, one, or several. Such a target is a collection of zero or more values. It is complete, and only then readable, once all its sources have finished.
One rule makes this safe. A push is legal if the compiler proves that different writers write different keys, or if the target declares a reducer that combines several values for one key. Pushed values are keyed by where they came from, and those keys have no natural order, so the checker must prove the reducer associative and commutative, and it then combines values in any order and grouping, as they arrive. An operator that is associative but not commutative, such as string concatenation, is used with >< over an ordered collection instead, and combines values in that collection's order. By default, no result depends on the order in which values arrive. Reduction is the only place in Zed where pushed values merge, so the compiler handles all merging the same way.
Pushing values to keys and reducing each key is how MapReduce works. Over a DAG, pushes and reductions turn a program's collection work into a pipeline of fine-grained map and reduce stages, with no separate framework.
A finite DAG always finishes if each node does. But a language whose programs all finish is not Turing-complete. The structured program theorem says sequence, selection and repetition suffice to express any computable function. The DAG gives sequence, and if and match give selection.
Repetition comes from generations. Each step of a loop computes its values from earlier steps' values, until a condition holds (or forever, for a loop over a stream). An operation in step n+1 cannot start until the values it reads from earlier steps exist. Within a step, everything independent can run in parallel, and independent parts of different steps can overlap. Unrolled, with one copy of the body per step, the graph is still acyclic, though infinite for a loop that never ends.
A loop is a value. sim.pos is its final position, sim::frames is its history keyed by step number from 0 (readable because maxSteps bounds the steps), and sim::len is its number of steps. How much history is kept changes storage, not meaning. The compiler infers how many past steps the code can still read and stores only those. If the code reads only pos and pos', the running loop keeps one frame of pos, as a programmer would by hand.
A loop may never end, and no compiler can decide that in general. When the checker cannot prove that a definition ends, the build warns that it is not proved to end, rather than guessing. Where it finds an input on which the definition runs forever, the warning prints that input:
// proved to end: n falls by 1 at each call and stays at least 0, so nothing is printed
countDown(positional n: int[0..]) = if n == 0 { 0 } else { countDown(n - 1) + 1 };
// warning: with `n = 1`, `halve(n - 2)` calls `halve(-1)`, `halve(-3)`, … forever
halve(positional n: int) = if n == 0 { 0 } else { halve(n - 2) + 1 };A finite @timeout on main proves that the run stops by its deadline, and the warning notes this. But a run stopped by the deadline ends as a fault with no value, so --total still rejects the definition.
The 2010 article said Flow had no stack. That still holds for the meaning of a program: calls and recursion expand subgraphs, and nothing in a program's meaning depends on a call stack. The generated code may still use the machine stack for calls where that is cheapest. Memory release, however, follows last use rather than stack order: a value is released when its last reader is done.
Manual memory management is hard to get right, and a garbage collector fixes only part of the problem. In Zed, memory release is determined from the dependency graph:
- Where a value's last use is known at compile time, it is released at that point in the generated code, and it has no reference count. Fusing adjacent operations removes many intermediate values altogether, since a fused intermediate is never allocated.
- Where the last use is not known at compile time, the value has a reference count. That happens, for example, when several readers running in parallel share a value and any of them may finish last. The count is exact, because the value graph is acyclic.
sq = for i in 0..<n { i * i };
total = sq >< (+); // sq has one reader, so it is fused into the sum and never storedBacon, Cheng and Rajan ("A Unified Theory of Garbage Collection," OOPSLA 2004) showed that tracing and reference counting compute the same thing, tracing as a least fixed point and reference counting as a greatest one. They also showed that the two differ only on cycles: reference counting cannot reclaim cyclic garbage. A Zed value graph has no cycles, so reference counting is exact, and a tracing collector would find nothing the counts miss.
A node's readiness to run and its readiness to be released are two counts, one over its incoming edges and one over its outgoing edges. A node may run when all its inputs exist, and may be released when all its readers are done.
Cyclic data, such as a graph with cycles or a doubly linked list, is held in one of two ways: as a graph of identifiers (an edge holds the IDs of its ends), or in an arena whose nodes are all freed together. Zed has no tracing collector and no cycle collector.
- It does not prevent leaks. A tracing collector frees only unreachable objects, so a reference the program still holds but will never use again keeps its object alive. Clearing such references by hand is manual memory management under another name. In Zed, a value is released right after its last use, even while the scope that defined it is still active, so a name that is never read again keeps nothing alive.
-
It does not choose the representation for you. In garbage-collected languages you still pick the container (such as a list, an array or a hash table), and the collector only reclaims it. In Zed, you write the value,
sq = for i in 0..<n { i * i };, and the compiler chooses how to represent it, or fuses it away. - It costs memory. Hertz and Berger ("Quantifying the Performance of Garbage Collection vs. Explicit Memory Management," OOPSLA 2005) found that "with five times as much memory, an Appel-style generational collector with a non-copying mature space matches the performance of reachability-based explicit memory management. With only three times as much memory, the collector runs on average 17% slower than explicit memory management. However, with only twice as much memory, garbage collection degrades performance by nearly 70%."
- It costs pause time or cores. In 2010, pauses of many seconds on large heaps were common. Modern JVM collectors such as ZGC and Shenandoah keep pauses under a millisecond by running concurrently with the program. That costs CPU time (collector threads on other cores, and barriers in the program's own code) and extra memory headroom.
In the function below, rows is released at its last read, before render runs, though the body has not ended:
pageFor(positional text: Utf8String) {
rows = parse(text) else [];
n = rows::len; // the last read of rows: it is released here
return render(n); // rows takes no memory while this runs
}Every value computed inside the program is immutable and can be recomputed from its inputs, so dropping one discards work but loses no state. (One exception: an unordered reduction, once read, is recomputed only with the grouping it first used, so it cannot give a second value.) Memory management then becomes a choice, made by the scheduler from the cost model: keep a value, or recompute it from its nearest kept ancestors. One analysis of the graph finds the cheap places to write checkpoints, to cache results, and to split memory into arenas. Below, the second pass needs hi from the first, so the two passes cannot be fused into one:
sq = for i in 0..<n { i * i };
hi = sq >< max else 0;
hits = sq.where(x -> x == hi).count; // the scheduler keeps sq for this pass, or recomputes it, by cost-
Partitioning by cost. Where it can, the compiler derives the cost of functions and subgraphs and chooses the grain size from it. For each region it picks a strategy from a fixed catalog: static list scheduling where costs are tightly bounded, work stealing where they depend on the data, vectorization, flattening of nested parallelism for GPUs, and pipelines whose queue sizes are derived from the graph.
-
Switching methods by input size, never by racing them. Where two methods give identical output with different scaling, the compiler can switch between them at the input size where their derived cost formulas cross, never at a size found by timing them, and both sides of the switch are tested. The one exception is an
@equivalentswitch the program writes between two functions proved equal: its switch size may be tuned from timings on each target, and the tuned size is written beside the source, so the build stays reproducible. Zed never runs two different methods at once and takes the first to finish, since then which method ran would depend on timing. -
Associativity. An associative reduction can be split into a tree,
((a + b) + (c + d)) + ((e + f) + (g + h)), whose subtrees run in parallel. Threads can also fold separate parts of a collection and combine the partial results. A loop can become a parallel scan the same way when the composition of its step functions has a compact form, as for a step that is affine over a semiring such as(max, +). -
Commutativity. A commutative and associative reduction can also combine values in any order, as they arrive. The checker establishes that this is safe by proving the operator's laws, so you do not have to. Where the checker cannot prove them, a reduction that needs them is rejected. A floating-point reduction instead runs on one fixed tree, and
>< op treeasks for that tree on any type whereopis total. (Data Parallel Haskell'sfoldPoffered a parallel fold in 2010, but the programmer had to guarantee associativity and call a special function.) -
Floating point. Floating-point addition is not associative, so a parallel sum split differently on different core counts can give different results. By default, every floating-point reduction in Zed uses a canonical tree whose shape depends only on the number of values, never on the number of cores, so the result is bit-identical at any core count. The
compensatedpolicy (Neumaier's compensated summation on the same tree) gives more accuracy for about 1.5 times the cost.unorderedgives up determinism for speed, and the result's type records that choice. -
Fusion. Adjacent operations are fused into one loop:
words.map(w -> w.len) >< maxnever builds the list of lengths. -
Memoization on request.
@memoizedbefore a function caches its results by argument. The build fails if two calls with the same arguments could give different results (for example, because the function reads a port). Each memoization table lives in an arena that is freed when the evaluation marked@memoizationArenaabove it ends, or whenmainends if no such mark is written:@memoized fib(positional n: int[0..]) -> int = if n < 2 { n } else { fib(n - 1) + fib(n - 2) }; -
Evaluation on demand. An infinite source works when only a finite part is read:
firstPrime = (for i in n.. { i }).where(isPrime).first;stops at the first prime. Higher candidates may be tested in parallel ahead of time, and that work is canceled once a lower prime is found. -
Partial evaluation. An expression whose inputs are all known at compile time is evaluated then, by the same evaluator that runs the program.
After the 2012 article, a reader, Dan Pologea, raised a point in the comments. In the DAG example above, a feeds b and c, and both feed e. Suppose the graph runs as a pipeline over a stream of inputs, perhaps across machines. Then e must combine the b and the c that came from the same a. If one value is delayed, reordered or lost, and values are matched by arrival order, e silently combines the wrong pair. As he put it, "we need to preserve the waves (i.e. all the outputs produced at the same 'time')".
The 2012 reply, that blocking is needed only where paths converge, answered only half the question. Zed never matches values by arrival order. Every value has a keypath: the input, step and element that produced it. Where paths converge, values are paired by keypath:
b = xs.map(f);
c = xs.map(g);
e = b.zip(c); // pairs b[k] with c[k] by the key k, never by the order in which they arriveInputs that enter the program together form a wave. Inside the program, each wave's results are committed together, so no reader sees a mix of old and new values. What a reader outside the program sees of a failed wave depends on the output port: a transactional port hides it, while a terminal or a socket may already show part of it. This gives three properties:
-
Deterministic parallelism. The same inputs give bit-identical outputs at any core count, except for a short, fixed list of sources of nondeterminism, such as the arrival order of input at ports and
unorderedreductions. - Incremental and reactive execution. No value is ever overwritten, and every read of a changing quantity names its step. So when an input changes, only its dependents are recomputed, with the same result as a full recomputation. A user interface, a spreadsheet and a build system are then ordinary programs that update as their inputs change.
- Provenance and time travel. The immediate inputs of every value are known, so you can trace any value back to the program's inputs, and a debugger can step backward as well as forward. A reduction's result names the level it collapsed rather than each element. The full chain back to the inputs is kept where it is asked for, such as for failures and in debugging.
The Future of Computing Performance (p. 82) lists five challenges: finding independent operations, communicating between them, preserving locality, synchronizing them, and balancing the load. Zed answers the first and fourth directly. Independent operations are those with no directed path between them, and synchronization happens only where paths converge. (In the 2012 reply to Dan Pologea: blocking happens "vertically" in the DAG, at points of convergence, and no locking is needed "in the horizontal direction.")
parts = chunks.map(c -> c >< (+)); // independent: no synchronization
total = parts >< (+); // the only synchronization is here, where the paths convergeThe other three, communication, locality and load balancing, remain scheduling problems. But the compiler has more to work with: where it can, it derives the cost of nodes and edges as functions of input sizes, and the algebra of the operators says which regroupings are allowed.
If the dependency graph of every program is a DAG known at compile time, and every failure is a typed value, many long-standing problems are solved at once. Even the smallest program shows several of them. In this one, each line is converted independently of the others, the output is the same on any number of cores, and each line's memory is released once it is written:
main(m: MainArgs) {
m.stdout <- m.stdin.map(l -> l.upper else "");
}The problems this solves:
- The multicore dilemma: computation is scheduled in parallel by the partial order of the graph, with grain size chosen by the cost model.
- Data races: the graph orders values, not variables, so no read depends on timing.
- Deadlocks inside a program: the graph has no cycles, queues between parts of a program have derived sizes, and state carried by a loop cannot block, so a program can wait only on the outside world.
- Nondeterministic results: outputs are bit-identical at any core count, floating point included, apart from the short, fixed list of sources of nondeterminism above.
- Uninitialized memory: no operation is scheduled before the values it reads are complete.
- Manual memory management, dangling pointers, double frees and leaks of unreachable memory: each value is released exactly once, after its last reader finishes, and never while a reader remains. Cyclic data in an arena is freed with the arena.
- Holding memory too long: a value is released as soon as its last reader finishes, even while its enclosing scope is still active.
- Tracing garbage collection pauses and heap headroom: there is no tracing garbage collector.
- Null dereference, out-of-bounds indexing, division by zero and unhandled exceptions: every possible failure is a typed value that must be handled or passed along (see Motivations and Design Philosophy Behind Zed).
- Incremental computation and caching: recomputing only what changed, with the same result as recomputing everything, is part of the core language.
Zed requires a program's dependency graph to be readable from its source, and it gets there by removing the ability to read the current value of a variable. In place of total += x, a program writes the one value total will ever have:
total = readings >< (+);The graph defines a partial order. From it, the compiler derives both a parallel schedule and a plan for allocating and releasing memory. By tracking the algebra of operators and the cost of functions, Zed can parallelize code that looks serial and choose its partitioning by input size. By making time explicit, with generations and waves in place of a single shared present, Zed also makes the same programs deterministic, incremental and traceable. Parallelism, memory management, determinism, incremental execution, provenance, and the absence of data races and of deadlocks inside a program all rest on one object: the program's value-dependency graph.