Module-based parallel JS strawman

parallelism.md

Parallel JS Strawman

Yes, this is a very significant departure from web workers, the current browser concurrency model. But I feel the lower level, more tightly integrated nature of it will make it far faster and lighter in practice, while still avoiding some significant footguns and working with the traditional single-threaded nature of JavaScript. Additionally, raw objects are much easier to deal with than pure message passing with workers.

Creating new threads

So here's my idea:

// parent.js
import.fork("./parent.js").then(thread => {
  const {module} = thread
  
  module.onSend(atomic (msg, args) => {
    switch (msg) {
    case "foo": doFoo(); break
    case "bar": doBar(args.bar); break
    default: doOther(args.opts)
    }
  })

  return module.run().then(() =>
    thread.close())
})

// child.js
let callback

export atomic function onSend(send) {
  callback = send
}

export atomic function run() {
  return Promise.resolve().then(() => send("foo"))
}

Add an import.fork(module) method-like expression, similar to how super() works. It's very highly inspired by @domenic's import() proposal, in that it uses a method-like syntactic form. This expression returns a promise to a thread instance, an object with the following properties/methods:

• thread.module - The exports for the main module of this thread.
• thread.global - The global instance for this thread. It is not identical to the parent thread's global object.
• thread.close() - Close the thread. This returns a promise resolved when the thread (and its spawned children) are all completely closed.
• thread.onClose(handler) - Register a handler for synchronous cleanup, triggered when the thread is closed (but after any remaining atomic calls).
• thread.active - Whether this thread is currently active (i.e. not closed).
• thread.closing - Whether this thread is currently closing, but not fully closed.
• thread.id - A unique symbol ID for this thread.

The instantiated module is literally the exported module itself, with minimal overhead. It's loaded inside its own separate realm. In the child, there is a global currentThread object with two methods:

• currentThread.close() - Close the currently running thread after the current tick ends. Or, in other words, make this tick the last.
• currentThread.onClose(handler) - Register a handler for synchronous cleanup, triggered when the thread is closed (but after any remaining atomic calls).
• currentThread.active - Whether the current thread is active (i.e. the thread's event loop is still alive).
• currentThread.closing - Whether the current thread is currently closing, but ticks are still being processed. It's useful to avoid requesting things when the tick is ending.

Safety

There are several safety mechanisms in place to avoid numerous race conditions, to continue to interoperate with traditional single-threaded JavaScript, and to maintain a level of overall sanity and stability within the language.

Atomic objects

There are now concepts of atomic objects and thread contexts. If an atomic object was created in your thread's context, you may modify it as you wish. If it was created in another thread's context, you can only read it, and attempting to modify it in any way (including its internal slots) causes a TypeError to be thrown. Consider it a special proxy of sorts.

• All module objects are atomic.
• Many builtin global objects and methods are atomic:
  • Promise and its prototype
  • Object and its prototype
  • Array and its prototype
  • The various typed array types/prototypes, including TypedArray and its prototype
  • SharedArrayBuffer and its prototype
  • ArrayBuffer is intentionally not atomic
  • Most iterators are not atomic

To make an object atomic, you need to use a contextual keyword called atomic. Here's how it's used:

// atomic object literal
atomic {foo: 1, bar: 2}

// atomic regexp literal
atomic /foo/g

// atomic array literal
atomic ["foo", "bar"]

// atomic function - its instances are always atomic
atomic function foo() {}
atomic function () {}
atomic async function foo() {}
atomic async function () {}

// atomic arrow function
atomic foo => bar
atomic (foo, bar) => bar
atomic async foo => bar
atomic async (foo, bar) => bar

// atomic class - its instances are always atomic
atomic class Foo {}
atomic class {}

// atomic methods on atomic classes (same with objects)
atomic class Foo {
  foo() {}
}

// atomic getters/setters on atomic classes (same with objects)
atomic class Foo {
  get length() {}
  set length(value) {}
}

// atomic methods on non-atomic class (same with objects)
class Foo {
  atomic foo() {}
}

// atomic getters/setters on non-atomic class (same with objects)
class Foo {
  atomic get length() {}
  atomic set length(value) {}
}

There are two key restrictions/invariants with creating atomic objects:

1. Atomic objects may only reference other atomic objects, including from their prototype.
2. Methods defined on atomic classes and shorthand methods on atomic object literals are themselves implicitly atomic.

Any attempt to violate these invariants will result in a TypeError being thrown. This includes trying to add a non-atomic property to an atomic object or change an atomic object's prototype to point to a non-atomic object.

To clarify these invariants, here's a quick explanation in code:

// This is legal - non-atomic objects *may* contain atomic references
const object = atomic {foo: 1}
const wrapper = {value: object}

// This is legal - same as above
atomic class C { get foo() { return 1 } }
const wrapper = {value: new C()}

// This will throw an error on the second line
const object = {foo: 1}
const wrapper = atomic {value: object}

// This will throw an error on the second line
class C { atomic get foo() { return 1 } }
const wrapper = atomic {value: new C()}

To allow detection of an atomic object, there will be a few other useful methods added:

• Object.isAtomic(object) - Whether this object is atomic.
• Object.isFromThread(object) - Whether this object can be modified in this thread.

(Detection may be useful to avoid several errors)

Atomic object restrictions

If an object is not atomic, attempts to pass any reference to it outside its thread context will result in a TypeError being thrown.

• This includes getters, setters, return values, and function arguments.
• This is a major safety layer, to avoid a whole class of race conditions.
• This requires you to be explicit on what you want to be exposed.
• This includes the entire prototype chain (Object and its prototype are intentionally atomic).

When a thread dies, microtasks and macrotasks may no longer be scheduled on it, and attempts to schedule any more will be silently ignored. Methods defined on it will still work, but the thread's event loop itself is eligible for GC.

• To clarify, the thread's context survives thread death, and is managed with standard GC rules. The thread context is just another object in the heap, and the heap is shared across all threads.

Atomic function and class declarations are also immutable. This is to enable better optimized calls across thread boundaries, because it's difficult to determine at runtime whether optimizing away the binding is valid. Additionally, methods defined on classes and shorthand object methods are non-writable and non-configurable.

• This enables engines to omit the lock when retrieving these methods, so they only have to lock once when invoking.

export atomic function foo(bar) {
  doSomethingUnsafe()
  return foo()
}

Thread locking

When you call an atomic function from the same thread context it's defined in, no locking is required. It works just like a normal function call.

• This is to enable an optimization that would otherwise be impossible. Also, without this clause, the stuff below could force highly unintuitive behavior.

When you call an atomic function from a different thread context, it waits for the callee's thread to finish its current microtask first (if necessary), and then the method is called in the callee's thread context, but inside the caller's thread. This keeps the call synchronized with the caller's thread to avoid a whole class of race conditions.

• The callee's thread, if active, waits for the caller to finish and notify it when it returns.
• This minimizes the performance hit of cross-thread atomic calls, by requiring function-level locking.
• Getters and setters are themselves run as if they were functions.
• The lock on the caller's side can be done with a simple mutex.

Atomic functions can use and modify non-atomic variables within its context, but this is safe, since execution is locked to just a single thread, anyways.

All constant property accesses on atomic objects are done without locking, since they are, by their very nature, read-only. This enables a useful optimization so, say, you can do worker.doSomething() expecting only one lock, or you can do new Uint32Array(worker.sharedBuffer) without taking a large performance hit.

• Known non-configurable, non-writable own properties in atomic objects are included in this. (This is only known after the first access.)
• const module exports are included as well.
• var and let exports are not.
• All other properties are not.
• The weak reference proposal will need extended to work with atomic objects, so they can interact with objects accessed this way.

All potentially mutable property accesses on atomic objects are atomic, and synchronized in the same way function calls are. This avoids a similar class of race conditions, and can also be done with a simple mutex.

• This can be partially optimized away in thread-local code after doing some static analysis.

Timing

To clarify the timing, it's similar to an event loop interweaved within another event loop. There is already the microtask queue, but there will now be a thread task queue, run at higher priority, for coordinating cross-thread memory accesses. Any time a function is called or potentially mutable property accessed in a thread from another, a new thread task is created.

• When a function is called, a thread task is created to invoke that function. Once the function is executed and returns, the task completes and sends the return value to the calling thread.
• When a potentially mutable property is accessed, a thread task is created to retrieve and return the property.

If the thread is inactive, new thread tasks are immediately invoked. If the thread's busy, new thread tasks are added to the the queue in an implementation-defined order. If it's busy with a microtask, the current queue is run after that microtask ends.

When running the current queue, it's replaced with the next queue before each of the old queue's items are run. During this step, the queue is run until no more tasks are added, and then the thread may proceed with the next available microtask. An implementation may put a cap on how many iterations of thread task queues are run at a time to prevent resource starvation.

Note that the order tasks are iterated in is implementation-defined, so concurrent, lock-free queues may (and should) be used to prevent deadlock. This has no effect on tasks that depend on the result of other tasks.

Sharing

The structure of this will permit sharing across threads without much hassle. You don't have to own an object to share it with another thread. This opens up a massive amount of flexibility with how you manage the parallelism. For example, you could literally create your own IPC layer and share thread wrappers around. You could largely re-implement the Web Worker API at the language level, complete with structured cloning and SharedArrayBuffer transfer.

Scoping

Each thread context has its own realm. This adds a layer of insulation by preventing unexpected mutations to their global objects, enabling a partial sandbox.

• This means each thread has their own copy of the builtins.
• This makes threads a suitable sandbox mechanism for semi-trusted code (e.g. privileged extensions and plugins).

Also, module imports are cached per-thread context, so when a parent and a child import the same module, they get two different copies of it. This prevents a multitude of issues with potentially really odd race conditions.

• Yes, engines could theoretically reuse the original compilation data, in case the same module is imported twice. This is just an otherwise unobservable optimization.

Because threads live in an otherwise isolated environment, you could use it as a sandbox for semi-trusted code, such as priviledged extensions or plugins. The parent chooses what to share with the child, and the child chooses what to share with the parent.

Speed concerns

Any proposal that deals with parallelism must be acceptably fast - engines should still run old code as fast as before, and the new additions should still be relatively fast. Here's how my proposal addresses much of this:

• Atomicity is opt-in. Most of the slowdown could be mitigated with inline caches and code generation. Additionally, only objects and functions can be atomic, and the check is very branch prediction-friendly (which CPUs like) because the common case is it's usually the same.
• Atomic objects can be marked with a unique ID for their creator, further speeding up the check.
• Concurrent referencing/dereferencing of atomic objects could potentially complicate heap management and slow down GC. A lock-free GC heap could alleviate this issue somewhat, but this could require significant changes to some current JavaScript garbage collectors to permit concurrent referencing/dereferencing.
• Frequent calls across thread contexts will likely slow things down tremendously due to thread starvation (the child can't run its own tasks when frequently blocked). The correct fix is to either use SharedArrayBuffers or keep the communication asynchronous and minimize the time spent in other contexts.

Technically, the whole concurrency model is lock-free, because the "locks" are actually waits (waiting for the return value) instead. The thread tasks can be scheduled without locks, because the thread task execution order is implementation-defined. Additionally, lock-free parallel mark-and-sweep garbage collection algorithms exist. So the whole thing can be done without locks.

Security concerns

Of course, multithreading support opens the door to a whole host of potential security issues. This just covers some of the potential things to watch out for.

• If an atomic object is referenced and/or dereferenced by two threads at the same time, that could corrupt the heap unless that action is made atomic or lock-free.
• Cache timing attacks are of real concern here with constructed sub-nanosecond high resolution clocks, but Web Workers already have the same problem, and although it affects SharedArrayBuffers there, a resolution there will have similar effect here regarding mutable property accesses.
• Due to the design of this, race conditions inherent to parallelism (e.g. simultaneous read/write) are literally impossible (apart from SharedArrayBuffers), because no volatile variables exist, and synchronization is somewhat transparent.
• The implementation-defined iteration order for the thread task queue is to allow for lock-free queues to be used for scheduling. This prevents deadlock and creates room to mildly disrupt high-resolution clocks that use mutable property accesses.
• Browsers should put a cap on how many thread task queue iterations are performed at a time, to avoid thread starvation. Otherwise, an attacker could potentially issue repeated calls to a shared thread, blocking multiple threads in the process. Note that, as a vulnerability, this would be difficult to accomplish in practice, and would already signify a problem in single-threaded code barring direct access.