Is there a faster way to yield to Javascript event loop than setTimeout(0)?

Question

I am trying to write a web worker that performs an interruptible computation. The only way to do that (other than Worker.terminate()) that I know is to periodically yield to the message loop so it can check if there are any new messages. For example this web worker calculates the sum of the integers from 0 to data, but if you send it a new message while the calculation is in progress it will cancel the calculation and start a new one.

let currentTask = {
  cancelled: false,
}

onmessage = event => {
  // Cancel the current task if there is one.
  currentTask.cancelled = true;

  // Make a new task (this takes advantage of objects being references in Javascript).
  currentTask = {
    cancelled: false,
  };
  performComputation(currentTask, event.data);
}

// Wait for setTimeout(0) to complete, so that the event loop can receive any pending messages.
function yieldToMacrotasks() {
  return new Promise((resolve) => setTimeout(resolve));
}

async function performComputation(task, data) {
  let total = 0;

  while (data !== 0) {
    // Do a little bit of computation.
    total += data;
    --data;

    // Yield to the event loop.
    await yieldToMacrotasks();

    // Check if this task has been superceded by another one.
    if (task.cancelled) {
      return;
    }
  }

  // Return the result.
  postMessage(total);
}

This works but it is appallingly slow. On average each iteration of the while loop takes 4 ms on my machine! That is a pretty huge overhead if you want cancellation to happen quickly.

Why is this so slow? And is there a faster way to do this?

Answer 1

Yes, the message queue will have higher importance than timeouts one, and will thus fire at higher frequency.

You can bind to that queue quite easily with the MessageChannel API:

let i = 0;
let j = 0;
const channel = new MessageChannel();
channel.port1.onmessage = messageLoop;

function messageLoop() {
  i++;
  // loop
  channel.port2.postMessage("");
}
function timeoutLoop() {
  j++;
  setTimeout( timeoutLoop );
}

messageLoop();
timeoutLoop();

// just to log
requestAnimationFrame( display );
function display() {
  log.textContent = "message: " + i + '\n' +
                    "timeout: " + j;
  requestAnimationFrame( display );
}

<pre id="log"></pre>

Now, you may also want to batch several rounds of the same operation per event loop.

Here are a few reasons why this method works:

• Per specs, setTimeout will get throttled to a minimum of 4ms after the 5th level of call, that is after the fifth iteration of OP's loop.
  Message events are not subject to this limitation.

• Some browsers will make the task initiated by setTimeout have a lower priority, in some cases.
  Namely, Firefox does that at page loading, so that scripts calling setTimeout at this moment don't block other events ; they do even create a task queue just for that.
  Even if still un-specced, it seems that at least in Chrome, message events have a "user-visible" priority, which means some UI events could come first, but that's about it. (Tested this using the up-coming scheduler.postTask() API in Chrome)

• Most modern browsers will throttle default timeouts when the page is not visible, and this may even apply for Workers.
  Message events are not subject to this limitation.

• As found by OP, Chrome does set a minimum of 1ms even for the first 5 calls.

  ---

But remember that if all these limitations have been put on setTimeout, it's because scheduling that many tasks at such a rate has a cost.

Use this only in a Worker thread!

Doing this in a Window context will throttle all the normal tasks the browser has to handle, but which they'll consider less important, like Network requests, Garbage Collection etc.
Also, posting a new task means that the event loop has to run at high frequency and will never idle, which means more energy consumption.

Answer 2

Why is this so slow?

Chrome (Blink) actually sets the minimum timeout to 4 ms:

// Chromium uses a minimum timer interval of 4ms. We'd like to go
// lower; however, there are poorly coded websites out there which do
// create CPU-spinning loops.  Using 4ms prevents the CPU from
// spinning too busily and provides a balance between CPU spinning and
// the smallest possible interval timer.
static constexpr base::TimeDelta kMinimumInterval =
    base::TimeDelta::FromMilliseconds(4);

Edit: If you read further in the code, that minimum is only used if the nesting level is more than 5, however it does still set the minimum to 1 ms in all cases:

  base::TimeDelta interval_milliseconds =
      std::max(base::TimeDelta::FromMilliseconds(1), interval);
  if (interval_milliseconds < kMinimumInterval &&
      nesting_level_ >= kMaxTimerNestingLevel)
    interval_milliseconds = kMinimumInterval;

Apparently the WHATWG and W3C specs disagree about whether the minimum of 4 ms should always apply or only apply above a certain nesting level, but the WHATWG spec is the one that matters for HTML and it seems like Chrome has implemented that.

I'm not sure why my measurements indicate it still takes 4 ms though.

---

is there a faster way to do this?

Based on Kaiido's great idea to use another message channel you can do something like this:

let currentTask = {
  cancelled: false,
}

onmessage = event => {
  currentTask.cancelled = true;
  currentTask = {
    cancelled: false,
  };
  performComputation(currentTask, event.data);
}

async function performComputation(task, data) {
  let total = 0;

  let promiseResolver;

  const channel = new MessageChannel();
  channel.port2.onmessage = event => {
    promiseResolver();
  };

  while (data !== 0) {
    // Do a little bit of computation.
    total += data;
    --data;

    // Yield to the event loop.
    const promise = new Promise(resolve => {
      promiseResolver = resolve;
    });
    channel.port1.postMessage(null);
    await promise;

    // Check if this task has been superceded by another one.
    if (task.cancelled) {
      return;
    }
  }

  // Return the result.
  postMessage(total);
}

I'm not totally happy with this code, but it does seem to work and is waaay faster. Each loop takes around 0.04 ms on my machine.

Answer 3

Looking at the downvotes in my other answer, I tried to challenge the code in this answer with my new knowledge that setTimeout(..., 0) has a forced delay of about 4ms (on Chromium at least). I put a workload of 100ms in each loop and and scheduled setTimeout() before the workload, so that setTimeout()’s 4ms would already have passed. I did the same with the postMessage(), just to be fair. I also changed the logging.

And the result was surprising: while watching the counters the message method gained 0-1 iterations over the timeout method at the beginning, but it stayed constant even up to 3000 iterations. – That proves that a setTimeout() with a concurrent postMessage() can keep its share (in Chromium).

Scrolling the iframe out of scope changed the outcome: there were almost 10 times as many message-triggered workloads processed compared to timeout-based ones. That has probably to do with the browser‘s intention to hand less resources to JS out of view or in another tab etc.

On Firefox I see a workload processing with 7:1 message against timeout. Watching it or leaving it running on another tab does not seem to matter.

Now I moved the (slightly modified) code over to a Worker. And it turns out that the iterations processed via timeout-scheduling is exactly the same as the message-based-scheduling. On Firefox and Chromium I get the same results.

let i = 0;
let j = 0;
const channel = new MessageChannel();
channel.port1.onmessage = messageLoop;

timer = performance.now.bind(performance);

function workload() {
  const start = timer();
  while (timer() - start < 100);
}

function messageLoop() {
  i++;
  channel.port2.postMessage("");
  workload();
}
function timeoutLoop() {
  j++;
  setTimeout( timeoutLoop );
  workload();
}

setInterval(() => log.textContent =
  `message: ${i}\ntimeout: ${j}`, 300);

timeoutLoop();
messageLoop();

<pre id="log"></pre>

Answer 4

I can confirm the 4ms round trip time of setTimeout(..., 0), but not consistently. I used the following worker (start with let w = new Worker('url/to/this/code.js', stop with w.terminate()).

In the first two rounds the pause is sub 1ms, then I get one in the range of 8ms and then it stays around 4ms each further iteration.

To reduce the wait I moved the yieldPromise executor in front of the workload. This way setTimeout() can keep it’s minimum delay without pausing the work loop longer than necessary. I guess the workload has to be longer than 4ms to be effective. That should not be a problem, unless catching the cancel message is the workload... ;-)

Result: ~0.4ms delay only. I.e. reduction by at least factor 10.¹

'use strict';
const timer = performance.now.bind(performance);

async function work() {
    while (true) {
        const yieldPromise = new Promise(resolve => setTimeout(resolve, 0));
        const start = timer();
        while (timer() - start < 500) {
            // work here
        }
        const end = timer();
        // const yieldPromise = new Promise(resolve => setTimeout(resolve, 0));
        await yieldPromise;
        console.log('Took this time to come back working:', timer() - end);
    }
}
work();

_{¹ Isn’t the browser limiting the timer resolution to that range? No way to measure further improvements then...}