borrowing (read-write) and sharing (read-only) ArrayBuffer regions

borrowing-and-sharing.md

Goal

Typed arrays can be copied or transferred between workers, but it's not possible for multiple workers to work with a buffer in parallel without copies. This document describes two ways to improve this without introducing data races: transferring read-write access to disjoint regions of buffers, and transferring read-only access to shared buffers/regions.

Borrowing ArrayBuffer regions

This is a brief description of an idea for making it possible for workers to borrow disjoint regions of an ArrayBuffer. Example:

var subdivided = [originalBuffer.borrow(0, 1024),
                  originalBuffer.borrow(1024, 2048),
                  originalBuffer.borrow(2048, 3072),
                  originalBuffer.borrow(3072, 4096)];

// buffer object is "borrowed," similar to neutered
assert(originalBuffer.byteLength === 0);

// spawn workers for hacking on the borrowed regions
var workers = Array.build(4, function() { return new Worker(url) });

// transfer borrowed regions to workers (in practice probably include more info in the msg)
workers.forEach(function(worker, i) {
  worker.postMessage(subdivided[i], [subdivided[i]]);
});

// container to save the returned region buffers in
var returned = {
  count: 0,
  buffers: []
};

workers.forEach((worker, i) => {
  worker.onmessage = (event) => {
    returned.buffers[i] = event.data;
    if (++returned.count < 4)
      return;

    // must return all borrowed regions at once
    originalBuffer.unborrow(returned.buffers);

    // original buffer is accessible again
    assert(originalBuffer.length > 0);

    // do stuff with the results!
    doStuffWith(originalBuffer);
  };
});

Some of the high points:

• After calling .borrow on a buffer, it is in a "loaned" state, which is like neutering except that you can continue to call .borrow on it.
• You can only borrow disjoint regions of the buffer (internally it'll probably use an interval tree to enforce this).
• You cannot transfer a loaned buffer, but you can transfer its borrowed children.
• You can restore a loaned buffer by calling .unborrow with an array containing all the borrowed children (in any order).
• After restoring the loaned buffer, the borrowed buffer objects are neutered.
• The backing store has to be atomically ref-counted (no GC necessary since cycles are impossible), since borrowed regions can be transferred to multiple threads.
• Since you have to have a reference to the parent buffer object to restore it, there's no danger that borrowed objects can introduce weird "revival" issues if the parent buffer is GC'ed.

Shared read-only ArrayBuffers

This is a brief description of an idea for sharing read-only versions of buffers. Example:

// make two read-only copies
var clones = originalBuffer.share(2);

// buffer object is "shared", similar to neutered
assert(originalBuffer.length === 0);

// can make more read-only copies
clones = clones.append(originalBuffer.share(2));

// spawn workers that will use the read-only copies
var workers = Array.build(4, function() { return new Worker(url) });

// transfer cloned regions to workers
workers.forEach(function(worker, i) {
  worker.postMessage(clones[i], [clones[i]]);
});

// container to save the returned region buffers in
var returned = {
  count: 0,
  buffers: []
};

workers.forEach((worker, i) => {
  worker.onmessage = (event) => {
    returned.buffers[i] = event.data;
    if (++returned.count < 4)
      return;

    // must return all shared regions at once
    originalBuffer.unshare(returned.buffers);

    // original buffer is accessible again
    assert(originalBuffer.length > 0);

    // do stuff with the results!
    doStuffWith(originalBuffer);
  };
});

High points:

• Similar to .borrow, but the only argument is the number of read-only clones.
• Parent enters the "shared" state, which is similar to loaned state.
• Use .unshare with all shared clones to restore the parent buffer.
• You can continue making more shared clones of a shared buffer; you just have to restore all shared clones at once.
• Shared children are neutered after unsharing.
• A shared parent buffer cannot be transferred.

Composing the two, and recursive slicing

• A borrowed buffer acts like a completely normal ArrayBuffer and can be shared or recursively loaned.
• A shared buffer can be recursive shared but not borrowed (since it's read-only).
• A common-case composition is to create read-only regions via:

var region = buffer.borrow(start, end);
var clones = region.share(N);

Planar formats

Even though the borrowed regions are contiguous, you can implement planar formats like

YYYY...UUUU...VVVV...

by dividing into 3 * n contiguous regions instead of n stride regions:

[YY][YY]...[UU][UU]...[VV][VV]...