Concurrency and Preemption

Concurrency and Preemption

One can create concurrent and preemptable programs in NaaN with only minimal design effort. The following sections describe how NaaN achieves this relative to other familiar languages and techniques.

Background

Concurrency is an essential capability of modern software because it is almost always necessary to communicate with external systems. Multiple pending requests and responses require separate concurrent execution contexts to keep track of them.

Another important capability is preemption. It is quite common for programs to execute batch operations, which are best expressed as algorithms with a defined start and finish. Preemption allows waiting concurrent operations to respond quickly as responses arrive, instead of deferring until the batch operations has finished.

JavaScript is an example of a language that is not preemptable. If a batch operation runs more than about 20 seconds then web browsers will declare the page unresponsive and offer termination to the user. Avoiding this requires chopping up the code into segments, and if the code segment runtime is too long then the user interface becomes unresponsive. One can also move batch operations into an isolated thread, but this requires considerable programming effort.

Multithreading provides both concurrency and preemption. Execution of batch operations is automatically sliced into segments ("time slices"), and multiple threads provide concurrent execution contexts. However designing reliable and high-performance multithreaded systems is extraordinarily difficult.

“There are two styles of multithreaded programming: dangerously buggy, and fundamentally wrong. Only the best developers achieve the former.”
— Greg Robbins on Twitter/X

Multithreaded systems suffer from having a vast number of possible interactions among threads. This complexity can be reduced using synchronization primitives, but the concurrency benefits can easily be lost while iterating the design to improve reliability.

"Got some inherited Python 'threaded' code. They had so many semaphores it was linear."
— From a co-worker's war stories

Async/await has become a popular concurrency technique partly due to the challenges of multithreading design. One declares a function async and uses await to obtain the results of asynchronous calls within it. Unfortunately this brings fresh challenges, such as the requirement that async functions can only be awaited by async functions.^[1] JavaScript batch operations remain challenging due to the lack of preemption, but at least there is no need for synchronization primitives.

NaaN has a simple approach to concurrency and preemption that overcomes most of the obstacles described above.

The NaaN Concurrency Model

The NaaN concurrency model executes code in a single preemptable foreground along with any number of background fibers that can interrupt it. Fibers execute until they wait or complete, and cannot be preempted. All NaaN code is inherently asynchronous without special declarations.

Programming NaaN concurrency is done with four primitives: nonce, future, exec, and sprint.

A nonce^[2] is a primitive datatype with wait() and signal(<value>) methods. A nonce is created in the unsignaled state and supports the semantics of a dictionary with key/data pairs to store related metadata. Execution suspends by waiting on a nonce and resumes when another fiber signals the nonce. The value of the wait call is the value argument provided to signal. Nonce also has a reset() method that sets it to the unsignaled state again. The first signal to a nonce sets its value. All subsequent signals are ignored until the nonce is reset. Any number of fibers can wait on a nonce. When it is signaled they are all released, but the order of execution is unspecified.

The future(<function> [, delayMS]) builtin starts a new concurrent fiber executing function after an optional delay. If no delay is specified then the future is unscheduled. Future returns a nonce with three methods: run([delayMS]) to schedule or reschedule execution, cancel to unschedule execution, and wait to suspend the caller until the future begins execution.

The exec(<expression>) builtin enqueues a preemptable batch operation to run next in the foreground, after any existing batch operation(s) are complete. Foreground code can defer preemption temporarily by calling sprint(). Sprint takes effect immediately and terminates when the procedure that invoked it exits.

That is the entire model, and all other concurrency features are built from these primitives.

Discussion

The goal for NaaN concurrency is to provide the simplest possible mechanism for executing concurrent workloads without requiring complex design effort. It accomplishes this by appropriate mapping of workloads:

• Fibers execute for a short span of time, so there is no benefit to preempting them. Omitting preemption enormously simplifies writing correct code.

• Batch operations execute for longer spans of time. They are interrupted regularly by fibers, but only require synchronization for shared variables. In practice sprint() is rarely used.

• NaaN utilizes multiple CPU cores by remote evaluation in separate JavaScript worker threads. This is effective when the batch operations require significant real time to execute, or multiple batch operations should execute concurrently. For example, the NaanIDE build system uses worker threads to improve performance.

Because NaaN depends on cooperative execution, it requires that the programmer map workloads correctly. Long-running operations must be implemented as preemptable batch operations. Fibers must be limited to short-running operations, typically tens of milliseconds or less. If a fiber runs longer than 10 seconds then NaaN throws an unresponsive exception to terminate it. The same happens with the foreground if it runs too long with sprint active.

Action/Waiter example

In this example, a waiter function wishes to suspend until an action function completes its task. The waiter allocates the action future and then waits on its completion.

Play-lingo> function waiter(local pending) {
    pending = new(nonce)
    action = future(function () {
            printline("action")
            sleep(1000)
            pending.signal("done")
        })
    printline("start")
    action.run()
    printline("running")
    printline(pending.wait())
}

Play-lingo> waiter()
start
running
action                   // <- 1-second delay after "action"
done
$: "done"

In the code above, waiter() does the following:

1. allocates a nonce
2. creates an action that will, when run, delay 1 second and signal "done"
3. prints start
4. tells the action to run, though that doesn't actually happen yet
5. prints running while both waiter and action can run
6. waits for the signal from action
7. prints the signaled result, done

Note that running prints before action because executing .run() on a future makes it eligible for execution but does not preempt the running code. If you change the line action.run() to action.run().wait() then waiter is forced to suspend until action's future begins. This results in printing action before running because the future must reach its call to sleep() before waiter can resume.

Preemption examples

The NaaN REPL evaluates expressions in the foreground, so loop {} runs an infinite but preemptable loop. While it is running the NaaN Terminal's blue CPU status bar grows to 100% utilization. You can stop this with Control-C in the terminal or by using the interrupt button, which is the leftmost in the cluster of three buttons in the terminal header.

Play-lingo> loop {}      // <- NaaN CPU to 100%
^C
(ndb-1) q                // (q)uit the debugger
==> terminated in debugger

Play-lingo> 

If preemption is prevented with sprint then loop {} does not allow anything else to run. The CPU runs at 100% but the indicator doesn't show it because the code to update the HTML element cannot run. Even interrupt does not work. After 10 seconds NaaN tires of this selfishness and throws an exception.

Play-lingo> function() { sprint(), loop {} } ();
==> error: unresponsive

Play-lingo> 

Executing an infinite loop in a fiber also throws an exception, but the terminal doesn't show background exceptions by default:

Play-lingo> future(function(){ loop{} }, 0);
$: Nonce{3}              // <- shown after 10 seconds

Play-lingo>

However the debugger can be set to catch background exceptions:

Play-lingo> /d
(ndb-1) catch enable
exceptions: catch all
(ndb-1) c

Play-lingo> future(function(){ loop{} }, 0);
$: Nonce{3}

Play-lingo> 
==> Entering debugger on exception: (internal unresponsive)
Play::lambda
(ndb-1) 

Live Demo

Please try this out for yourself. The terminal is preloaded with the example above where waiter() works as shown, and waiter(true) waits for the action to start before running. You can enter waiter.proc to display its source code.

Working inside a small, transient, embedded terminal doesn't really convey the full power of NaaN. For a better experience please install the NaaN interpreter and the NaanIDE IDE that are available under the MIT license. The GUI debugger in NaanIDE is a big improvement over the CLI debugger available here.

Next Steps

The real power of NaaN concurrency emerges when combined with other features like closures and dynamic binding. Please stay tuned for future articles describing how to use these together.