Here is a question most languages answer badly: how many threads is my program using?

Badly, because the answer is usually spread across the code. A thread pool constructed here, a parallel-for there, an executor passed down four call levels. Changing the answer means changing all of it, and nobody can tell you from the source what happens if you double the core count.

In Mica the answer is a build flag:

mica --tasking single           # the default: one carrier
mica --tasking multicore,4      # four

A carrier is an operating-system thread the scheduler runs tasks on. The same source compiles either way. What this article is about is which of your program’s answers that changes — and the answer is none of the ones that matter.

The example is examples/Carriers. Build and run it twice:

make -C examples/Carriers run
make -C examples/Carriers run MICA_EXTRA_FLAGS="--tasking multicore,4"

What does not change

Three tasks, a thousand increments each, of one shared cell:

task Bump(rounds : int64);
var
    i : int64;
begin
    i := 0;

    while i < rounds do
    begin
        synchronized shared := shared + 1;
        i := i + 1;
    end;
end;
A shared total, held exact by the mark
  shared: 3000

3000 on one carrier. 3000 on two. 3000 on four. The synchronized mark is why: it holds a lock across the whole read-modify-write, so no two increments can interleave inside the critical section. On one carrier that lock is never contended and costs almost nothing; on four it is what keeps updates from being lost.

You did not write the lock. You wrote the word synchronized in front of a statement, and the compiler worked out which lock and where to release it. What that word means, and why the compiler refuses the version without it, is the data-race freedom article — this one is about what happens after you have written it.

The better answer is not to share at all

Exactness is not the only thing worth having. Look at the same arithmetic, partitioned:

task Partition(tag : int64, rounds : int64);
var
    i, sum : int64;
begin
    sum := 0;
    i := 0;

    while i < rounds do
    begin
        sum := sum + tag;
        i := i + 1;
    end;

    synchronized totals[tag] := sum;
end;
The same total, partitioned instead of shared
  totals[1]: 1000
  totals[2]: 2000
  totals[3]: 3000
  sum: 6000

The running total is a local. A thousand additions touch nothing another task can see, and one marked statement publishes the result. One lock instead of a thousand.

This is the shape to reach for first, and the reason is not performance folklore — it is that the two versions are exact for different reasons. Bump is exact because its increments queued. Partition is exact because its tasks never met. The second property survives contention, scales with carriers, and cannot be undone by someone later adding a fourth task.

Try it. Delete the word synchronized from Partition’s last line. The compiler refuses it — even though each task writes a different slot, and even though you can see that from the source. Why it refuses anyway is the subject of the next article, and the refusal is the interesting part.

A loop that never suspends

Now the part that decides whether a cooperative scheduler is usable at all.

Tasks hand the carrier on at suspension points. So what happens to a task that has none — a compute loop, no Yield, no I/O, nothing a reader could point at as the place it gives way?

task Busy(rounds : int64);
var
    i, sum : int64;
begin
    sum := 0;
    i := 0;

    while i < rounds do
    begin
        sum := sum + i;
        i := i + 1;
    end;

    WriteLn("  busy: finished, sum %lld", sum);
end;

Schedule that for ten million iterations, first, and a chatty neighbour second:

concurrent
    schedule Busy(10000000);
    schedule Polite(3);
end;
A loop that never suspends does not starve its neighbour
  polite: turn 0
  polite: turn 1
  polite: turn 2
  busy: finished, sum 49999995000000

All three of Polite’s turns arrive before Busy finishes, although Busy was scheduled first and its source contains no suspension point at all.

The compiler planted one. Every loop inside a task body carries a safepoint at its back edge, strip-mined to every 1024th iteration through a per-loop counter. When that point is reached and a peer is ready, the running task offers the carrier and goes to the back of the queue.

That is a stronger guarantee than it looks. Responsiveness is bounded by iterations rather than by whether the author remembered to yield — a hot loop in a procedure three calls deep, written by someone who never heard of tasks, cannot starve the program. Cooperative scheduling usually means “cooperative if everybody cooperates”. Here it does not.

The cost is designed to disappear where it is not needed:

  • The fast path is a load, an add, a store, a compare and a branch. The runtime call happens on one iteration in 1024.
  • A loop inside a synchronized mark carries no safepoint at all. The mark is a no-preemption promise: its whole extent runs as one step, so nothing can route a task out of a half-finished critical section.
  • A compilation unit that declares no tasks and no generators gets no safepoints anywhere. Sequential code pays nothing.

Deadlines reach through the same point

A scope can be given a millisecond budget. When it elapses the children are cancelled and the owner moves on to its drain:

procedure Bounded(budget : int64, rounds : int64);

    task Spin(limit : int64);
    var
        i : int64;
    begin
        i := 0;

        while i < limit do
            i := i + 1;

        WriteLn("  spin: ran to its own end");
    end;

begin
    defer if ScopeTimedOut() then WriteLn("  outcome: the scope timed out")
                              else WriteLn("  outcome: the scope completed");

    concurrent
        ScopeDeadline(budget);
        schedule Spin(rounds);
    end;
end;

Called with a 25 ms budget and a hundred billion iterations, and then with a five second budget and one:

A deadline stops even a loop that never suspends
  outcome: the scope timed out

The same scope, finishing inside its budget
  spin: ran to its own end
  outcome: the scope completed

The first Spin never printed. It was stopped mid-computation, and the only place it could be stopped is the back-edge safepoint — which is why the fairness mechanism and the cancellation mechanism are the same mechanism. A language with no safepoint can offer you a deadline, but it cannot make it reach a while loop.

ScopeTimedOut is the paired query, and reading it in a defer is deliberate: the deferred statement runs after the drain, so it sees the scope’s final state and can tell a timed-out block from one that completed.

What does change: the order

Everything quoted above is identical on one carrier and on four. Run the example both ways and the totals, the sums and the outcomes match line for line.

One section can move: the order of polite against busy. And that is the honest summary of what multicore promises — correct results, never an interleaving. If your program needs an order, it has to say so, which is what a join, a deadline or a mark is for.

The carrier count of one deserves a sentence of its own, because if you parameterise the count from a config file it is reachable. --tasking multicore,1 — multicore machinery, one thread — behaves like the single default: a pool of one has no second carrier to provide the fairness the flavour otherwise leaves to parallelism, so the safepoint’s offer stands there too, and this example prints the same lines in the same order as the build with no flag at all. One carrier is also what a bare multicore resolves to on a one-processor machine, so that machine is not a special case either.

What this does not do

Multicore is not automatic parallelism. --tasking multicore,4 gives the scheduler four carriers. It does not split your loops, vectorise your arithmetic, or find parallelism you did not express as tasks.

More carriers is not always faster. Bump’s thousand marked increments contend for one lock; adding carriers adds contention, not throughput. Partition is the shape that scales, and the difference is in your source, not in the flag.

Output ordering is not a test oracle. Anything you assert about interleaving under multicore is asserting about luck. Assert on sums, counts, and the post-join state — which is exactly what this example prints.

A deadline is not a hard real-time bound. It fires at the next safepoint or suspension point, so its resolution is up to 1024 loop iterations plus whatever one iteration costs. It is a budget, not a timer interrupt.

What the compiler proved

You changed the number of threads your program runs on without touching a line of it, and every value it computed stayed the same. A compute loop with no suspension point in it still let its neighbour run, and still stopped when its deadline fired. And the one thing that did change — the order two unrelated tasks printed in — is the one thing the model never promised you.

Next

Data-race freedom, proved at compile time — the article about the word synchronized, and about all the programs the compiler will not let you write without it.