Promises executor dominates over timeouts

[djspiewak]

First, some table-setting:

var canceled = false;

const loop = () => {
  if (!canceled) {
    console.log("looping");
    new Promise((resolve, reject) => loop());
  }
};

setTimeout(() => { console.log("canceling"); canceled = true; }, 5);
loop();

This does what you would expect: it loops for a while and then cancels.

So does the following:

import scala.concurrent.ExecutionContext
import scala.concurrent.duration._
import scala.scalajs.concurrent.QueueExecutionContext
import scala.scalajs.js.timers

object Test {
  def main(args: Array[String]): Unit = {
    var cancel = false
    val exec: ExecutionContext = QueueExecutionContext.timeouts()
    def loop(): Unit = {
      if (!cancel) {
        println("looping")
        exec.execute(() => loop())
      }
    }

    timers.setTimeout(5.millis) { println("canceling"); cancel = true }
    loop()
  }
}

Again, loops for a little while and then cancels.

This, however, loops forever:

import scala.concurrent.ExecutionContext
import scala.concurrent.duration._
import scala.scalajs.concurrent.QueueExecutionContext
import scala.scalajs.js.timers

object Test {
  def main(args: Array[String]): Unit = {
    var cancel = false
    val exec: ExecutionContext = QueueExecutionContext.promises()        // <---- this is the only difference!
    def loop(): Unit = {
      if (!cancel) {
        println("looping")
        exec.execute(() => loop())
      }
    }

    timers.setTimeout(5.millis) { println("canceling"); cancel = true }
    loop()
  }
}

It appears that if any outstanding work is available on the promises queue, it will dominate over the timeouts queue. My guess without looking at the code is that this is a consequence of a well-intentioned optimization within ScalaJS itself which fails to yield, since it definitely doesn't reproduce within Node.

[sjrd]

Thanks for the detailed report!

FTR, the code is here:

scala-js/library/src/main/scala/scala/scalajs/concurrent/QueueExecutionContext.scala

Lines 46 to 62 in 430f915

	private final class PromisesExecutionContext extends ExecutionContextExecutor {
	private val resolvedUnitPromise = js.Promise.resolve[Unit](())
	def execute(runnable: Runnable): Unit = {
	resolvedUnitPromise.`then` { (_: Unit) =>
	try {
	runnable.run()
	} catch {
	case t: Throwable => reportFailure(t)
	}
	(): Unit | js.Thenable[Unit]
	}
	}
	def reportFailure(t: Throwable): Unit =
	t.printStackTrace()
	}

There's nothing that obviously tries to short-circuit the event loop. We explicitly call then for every job, which is always supposed to yield to event loop. But perhaps it doesn't for already-completed Promises?

[djspiewak]

I dug deeper myself! It appears that both then and the Promise constructor are evaluated eagerly! (in other words, exactly what you theorized regarding already-completed promises) My JS example is actually super weird because if you remove the console.log, it just immediately blows the stack. In other words, Promise in JS is really a lot more like Promise in Scala and a lot less like Future. A bit of googling around finds a fair number of posts where people suggest using setTimeout(..., 0) as a workaround for this problem. In other words, exactly what timeouts() already does.

But at any rate, this implies that promises in and of itself is actually not a valid executor. I haven't yet found a way to get JavaScript to reliably bounce through the event queue without using setTimeout.

[oleg-py]

fyi - V8 has separates queues for tasks, microtask queue (used e.g. for promise.then) and macrotask queue (used e.g. for setTimeout):
https://javascript.info/event-loop

The spec for promises and jobs deliberately doesn't restrict how priority should work for different types of tasks:
https://www.ecma-international.org/ecma-262/11.0/index.html#sec-jobs

[djspiewak]

fyi - V8 has separates queues for tasks, microtask queue (used e.g. for promise.then) and macrotask queue (used e.g. for setTimeout):

The fact that I can get things to stack overflow by using then on a resolved Promise implies that it's not bouncing to any queue, prioritized or otherwise. I did some more research yesterday, and I think the only general solution to this involves a polyfill: https://github.com/YuzuJS/setImmediate My preferred solution would be for ScalaJS to simply have this (or a port of it) as its global executor, since promises don't really do what is needed to satisfy the contract and timeouts is far too slow.

[sjrd]

The fact that I can get things to stack overflow by using then on a resolved Promise implies that it's not bouncing to any queue, prioritized or otherwise.

If that is true, that's a huge bug in V8, and we should report it if it hasn't already been reported. Because that is clearly violating the specs of Promises.

[djspiewak]

If that is true, that's a huge bug in V8, and we should report it if it hasn't already been reported. Because that is clearly violating the specs of Promises.

It's like, all over StackOverflow (recursive constructor), so it's certainly not an unknown thing. I think it's also very telling that the polyfills for setImmediate don't bother touching Promise at all.

Hunting around a bit, I think that @oleg-py hit it right on the head: this is a difference between the micro- and macrotask queues. The microtask queue, by spec, doesn't trampoline until all tasks are exhausted. Which is to say that if you have an eager microtask which enqueues an additional microtask callback, the stack depth will increase proportionally. This is in contrast to macrotasks, which tick each time (source: the first paragraph of this section). This isn't a violation of the spec, it's just what Promises do: they're just a continuation monad, nothing more.

ExecutionContext needs to reliably trampoline, and you can make a pretty strong argument that it needs to reliably yield. Thus, I believe that setImmediate is a more appropriate solution. Here's a lovely article discussing the surrounding issues and hinting at some of the stupid politics which bizarrely surround this non-standard.

[sjrd]

It's like, all over StackOverflow (recursive constructor), so it's certainly not an unknown thing. I think it's also very telling that the polyfills for setImmediate don't bother touching Promise at all.

The link you mention explains that the constructor runs synchronously, but that a callback to then always runs asynchronously. This is also my understanding of the spec. We use then for all tasks in an execution context precisely to force a new job. If nested then calls cause a stack overflow exception, that's an engine bug. That should take care of the trampolining aspect, which I agree must work for execution contexts.

---

Now, I agree with the microtask v macrotask explanation. That explains why endless chains of then will prevent any setTimeout from executing. If indeed we want to also guarantee yielding to the macrotask loop, we still have two strategies:

• Use setImmediate
• Use Promises most of the time, and once in a while (every ms?) use setImmediate.

I'm reluctant to abandon the Promise approach, because Promise is exactly the correspondant to Scala's Futures. People writing plain JavaScript are using Promises all the time. Why is it not an issue for them? If it's not an issue for them, how come it's an issue for us?

[djspiewak]

Use Promises most of the time, and once in a while (every ms?) use setImmediate.

What's the advantage to this though? Why not just always use setImmediate? The only reason to not use setImmediate is you need polyfills to achieve it in a cross-platform manner, but if you're still going to use it at least once, then you haven't avoided that problem. From my understanding, setImmediate's performance (when natively available) is on par with a tick of the microtask loop.

I do believe we need to use the macrotask loop, otherwise neither timers nor IO will work correctly. This is basically a matter of fairness in scheduling.

I'm reluctant to abandon the Promise approach, because Promise is exactly the correspondant to Scala's Futures. People writing plain JavaScript are using Promises all the time. Why is it not an issue for them? If it's not an issue for them, how come it's an issue for us?

It's not an issue for them for two reasons. First, you don't see JavaScript applications that are as pervasively Promise-ified as you see with Cats Effect IO, or arguably even Future. Second, most JavaScript applications on the server side are trivially IO-bound (because if they were compute bound, they wouldn't be using node in the first place), and on the client side are primarily event and rendering driven. This scenario doesn't arise very frequently with the two most common applications for the language, though it certainly does arise, which is why so many people use the setImmediate polyfill! (4.6 million public dependents, btw)

Also remember that most people using Promises are doing it precisely to wrap up asynchronous callbacks. If you create a Promise which wraps setTimeout, your thread of execution is going to bounce through the macrotask loop regardless of Promise's semantics, and I would be willing to bet that this describes about 99% of how people use Promise in JS.

I would also disagree with the characterization that Promise is the JavaScript analogue of Future. It really isn't. Promise is the JavaScript analogue of Future where you evaluate everything with the parasitic executor rather than global. If you do that naively on the JVM, you'll end up with awful fairness and extremely high latency on request/response cycles.

The scenario where pure Promise usage falls down is precisely the scenario we're seeing here: a long-running compute chain which needs to frequently yield control back to the event loop so as to handle IO and/or timers. This kind of scenario works just fine with setImmediate, and also works fine (but very slowly) with setTimeout, but it does not work with Promise. Scala's ExecutionContext implicitly promises to handle this type of situation (because, absent pathological implementations, it does handle this type of situation when running on the JVM), which is why I think it is correct to simply use setImmediate every time.

[ritschwumm]

i think setImmediate is what's needed here, too - but https://developer.mozilla.org/en-US/docs/Web/API/Window/setImmediate says "This method is not expected to become standard, and is only implemented by recent builds of Internet Explorer and Node.js 0.10+. It meets resistance both from Gecko (Firefox) and Webkit (Google/Apple)." and relying on a polyfill that abuses postMessage and might have to rely on that one working the same way as it does now for a long time feels quite wrong to me.

there's no way to regain fairness by most often using queueMicrotask (or it's equivalent using a resolved promise) and only sometimes using setTimeout, right?

[djspiewak]

there's no way to regain fairness by most often using queueMicrotask (or it's equivalent using a resolved promise) and only sometimes using setTimeout, right?

That would help. If you want to straight-up avoid polyfills, it's not a horrible thing to do. It's still going to affect timer granularity to a significant degree, but perhaps that doesn't matter so much. Like, setImmediate is available in NodeJS, which is the only place where timer granularity is unclamped, so… in a sense only periodically yielding back to the macrotask queue isn't necessarily horrible.

The trick is how do you figure that out? Like we have no way of knowing, within the ExecutionContext framework, when we've run a long series of microtasks without yielding to the macrotask queue. If we could figure that out, then in theory we could just ensure we yield once every ~4 ms (the minimum clamp on setTimeout). As it stands though, the best thing we can do is probably just yield stochastically, or try to keep some general rolling metrics on the EC as we use it. That seems… complicated.

Is that really better than the polyfill? Like, if you look at the implementation, it's actually relying on some relatively robust mechanisms all things considered. By "robust" I mean "literally what the Chrome team suggests you use instead of setImmediate".

[djspiewak]

For anyone who finds this issue who is looking for a cargo-cultable quick fix… Cats Effect now has a partial implementation of a setImmediate polyfill, wrapped up in an ExecutionContext. It works in all modern browsers and NodeJS, though it doesn't presently support web workers. In all unsupported cases it falls back to setTimeout. https://github.com/typelevel/cats-effect/blob/series/3.x/core/js/src/main/scala/cats/effect/unsafe/PolyfillExecutionContext.scala

To be clear, my preferred solution here is still to upstream this functionality, since I do believe that setImmediate (and analogues) is a better match for ExecutionContext's semantics than Promise.then is, but if ScalaJS leadership determines otherwise (their knowledge is far beyond mine on these matters), CE can maintain the alternative.

[gzm0]

FWIW Scala.js' HTML executor also needs to work around this:

https://github.com/scala-js/scala-js/blob/v1.1.1/test-bridge/src/main/scala/org/scalajs/testing/bridge/HTMLRunner.scala#L129-L132

[gzm0]

At this point, I observe the following:

• This seems to be a genuine issue (both cats-effect and the Scala.js HTML executor which are at quite the opposite end of the Scala spectrum have this issue).
• setImmediate is not going to happen (most discussions seem to be from around 2013/2014).
• https://github.com/YuzuJS/setImmediate (or the port in Cats Effect) seems to rely on too much non-standard stuff to be viable for Scala.js core.

So I think trying to build an execution context that yields every once in a while to the macrotask queue is the best we can do.

I can take a stab at this.

[djspiewak]

So I think trying to build an execution context that yields every once in a while to the macrotask queue is the best we can do.

There's a new wrinkle in this btw. The only way you can reliably yield to the macrotask queue in a cross-platform fashion would be to use setTimeout, but timeouts are now disabled in Chrome on non-foreground tabs, and I don't think the microtask queue is similarly hampered. This is going to be a particular challenge because of the limited information inside of ExecutionContext, which can really only see opaque thunk submissions. So the only implementation route is likely just setting up a counter and yielding once every 1024 (or something) submissions.

The problem is that you're going to end up messing significantly with sequencing and interleaving between parallel operations this way, since in any race between two Futures, one will get hit by the setTimeout while the other might not be, depending on how they're constructed. Future is certainly less susceptible to this than IO (where it's effectively a guarantee that this will happen), but it still seems likely to cause user-visible confusion.

One route you could take, if you really don't want to do the full setImmediate polyfill, is to just rely on the two features which Cats Effect's variant does: setImmediate (in NodeJS and IE9) and postMessage. The latter is extremely standard and available in all JS environments which have a DOM, while the former is intrinsically wired into a ton of NodeJS functionality and really isn't going anywhere. Remember that the reason (cited by the standards committee) that setImmediate isn't being added to the standard is the fact that it's easy to polyfill, so the spec authors clearly expect us to be doing these types of things.

The only downside to the above is you basically have to detect the webworker environment and fall back to setTimeout (or use MessageChannel), because setImmediate won't exist and postMessage will do the wrong thing. But, IMO, this seems a lot more reliable and less confusing (to users) overall, despite the fact that it's ugly AF to implement.

(speaking of which, I'm still in the hunt for a good way to run ScalaJS within web workers in a CI environment, for exactly this reason)

[gzm0]

There's a new wrinkle in this btw. The only way you can reliably yield to the macrotask queue in a cross-platform fashion would be to use setTimeout, but timeouts are now disabled in Chrome on non-foreground tabs, and I don't think the microtask queue is similarly hampered.

Thank you for pointing this out.

Knowing this quite shifts my perspective on this: We might have to accept that there isn't a good default ExecutionContext that Scala.js (core) can provide that reliably works on the web.

Note that Scala.js has it as an explicit goal to not rely on DOM APIs, but only things standardized in ECMAScript (setTimeout being a notable exception here).

Maybe we should look at this from a different angle:

• Can we provide a good ExecutionContext for the web outside of Scala.js?
  Yes, by putting what is in Cats Effect in a separate scalajs-web-execution-context (or similar) library.
• Can we prevent Scala.js users to shoot themselves in the foot by using the ExecutionContext provided by Scala.js proper?
  Unclear.
  • QueueExcecutionContext is probably sufficiently obscure that no further action is needed.
  • ExecutionContext.global OTOH is a natural choice for a lot of code and would do the wrong thing. We could add a compiler emitted warning that it is not good for use in DOM environments, but I suspect it will be mostly annoying and not prevent a lot of problems :S

[gzm0]

@sjrd what are your thoughts on this? ATM I think the best we can do in Scala.js core is somehow warn when ExecutionContext.global is used (of course with all the caveats that warnings with need for silencing bring :S).

[sjrd]

I'm still very uneasy about this whole thing. I have reread the whole discussion here. It I have to reluctantly agree that Promises are not a right fit for an ExecutionContext, unfortunately. At the same time, using anything else is a strong departure from our existing policy in Scala.js core not to use anything that is not standard in ECMAScript (or about to become standard, behind flags in ESFeatures).

Yes, setTimeout is special here, but note that so far we only use it:

• for javalib stuff directly related to timers (i.e., java.util.Timer): if setTimeout is not supported, that API will not be supported, but that's kind of expected from a user point of view
• for ExecutionContext when Promises are not available (so, never with an ECMAScript 2015+ engine)

In addition, all the engines that support timers support setTimeout with the same API. They don't have 3 or 4 different ways of doing the same thing.

I would like to say that other than that, we stick 100% to ES 2015. However I also have to admit that 1 case of polyfilling a non-ECMAScript API leaked into our implementation, a long time ago: using performance.now() when available to implement j.l.System.nanoTime():

scala-js/javalanglib/src/main/scala/java/lang/System.scala

Lines 72 to 92 in 88a19cf

	private object NanoTime {
	val getHighPrecisionTime: js.Function0[scala.Double] = {
	import Utils.DynamicImplicits.truthValue
	if (js.typeOf(global.performance) != "undefined") {
	if (global.performance.now) {
	() => global.performance.now().asInstanceOf[scala.Double]
	} else if (global.performance.webkitNow) {
	() => global.performance.webkitNow().asInstanceOf[scala.Double]
	} else {
	() => new js.Date().getTime()
	}
	} else {
	() => new js.Date().getTime()
	}
	}
	}
	@inline
	def nanoTime(): scala.Long =
	(NanoTime.getHighPrecisionTime() * 1000000).toLong

At least that one has a compliant fallback (if less precise).

Using even a polyfill of setImmediate would be a qualitative departure from our policy. I believe this is not acceptable. If we do it, we'll have a precedent to accept all sorts of other polyfills like that to implement "stuff": default locale, time-related things, who knows what.

Remains the option of warning against Execution.global. But then what would we suggest instead? We could tell people to use QueueExecutionContext if they know what they're doing. But already that is annoying for cross-platform code (JVM/JS). We would probably have to publish at least another library with something portable-ish. But then what I also fear is that libraries will start indiscriminately depending on that, and we'll be back with the same problem that we have today: that the ecosystem basically relies on something that doesn't always work. (Or, if it uses the setImmediate polyfill, that the ecosystem basically relies on something that is non-standard, which is almost as bad as if it were implemented in Scala.js core.)

ATM I don't see any real solution. All the choices we have are damned.

[gzm0]

Remains the option of warning against Execution.global. But then what would we suggest instead?

I wouldn't actually suggest something else (for portable usage). Simply allow users to disable the warning (ideally with the existing @nowarn mechanism). So if one needs portable code providing an ExecutionContext (which is an assumption I'd be willing to challenge, but let's keep it for now), ExecutionContext.global still works, it just needs an acknowledgment that it will not necessarily work as expected on the web (in "pure" JS engine OTOH it would).

[sjrd]

Hum, yes, I guess that makes sense.

[djspiewak]

I wasn't aware of the policy against polyfills. That design decision makes a ton of sense and I support it.

My thoughts for what they're worth… Leave the Promises executor in place exactly as it is, but warn whenever it (or global) is used. In the warning, point users to a separate library which ports setImmediate to ScalaJS. I'm happy to offer the PolyfillExecutionContext from Cats Effect as the starting point.

It's definitely clear that promises as an executor cause some serious problems in certain common types of execution modalities, but the problems aren't severe or ubiquitous enough (IMO) to warrant full on removal. A disableable warning and a blessed separate library seems best.

[gzm0]

@djspiewak would you be willing to publish the execution context of Cats Effect separately? If yes, I'll be happy to implement the relevant compiler warnings and point folks to it.

@sjrd would that work for you?

[sjrd]

Yes, that sounds reasonable.

[gzm0]

Ping @djspiewak

[djspiewak]

Sorry! Missed this. And yes I'm quite willing to do that. This would also make it a little easier to facilitate contributions from people who may have relevant knowledge on it, but who would rather not dive into Cats Effect itself.

[gzm0]

Absolutely! Web execution scheduling and Cats Effect seems to be two quite different pairs of shoes. In that case, I'll start investigating options of how we can warn when the global execution context is used.

[gzm0]

It seems that from a user interface POV, we have the following options to disable a warning when importing ExecutionContext.global (or it's implicit variant).

• @nowarn in 2.13.x, something else for earlier versions (con: different per scala version)
• Compiler option (con: global*, potentially unintuitive)
• Magic import (con: JVM compat, unintuitive)
• Our own annotation (con: JVM compat, unintuitive on 2.13.x)

• I'm not 100% sure if a global enable/ disable is a bad thing: Essentially, a given piece of JS code either needs to run on a web runtime or not.

@sjrd opinions?

[sjrd]

I think we should offer the global compiler option and an @nowarn-based solution. Users on recent enough versions of Scala would be encouraged to use the latter, and others could use the former.

Solutions that are not JVM compatible are not useful, IMO.

[gzm0]

Who is this waiting on? @djspiewak, do you simply need a repo under the scala-js org or is there anything else needed? (seems like scala-js/scala-js-macrotask-executor does not exist).

[djspiewak]

@gzm0 We're waiting on the repository creation. :-) Once that happens, we can PR the basic skeleton pretty quickly. It'll need GHA approval from an admin unless y'all give us write/admin access, but after that things should smooth out.

[gzm0]

I created https://github.com/scala-js/scala-js-macrotask-executor and added you as a maintainer.

I'll leave it up to @sjrd how to organize permissions.

[djspiewak]

The above project now contains the polyfill executor implementation, as well as almost all the associated testing and CI infrastructure. The only thing it's missing at present is the infrastructure for testing under webworker environments, which we're working on.

Incidentally, doing this uncovered the fact that the polyfill is not working on jsdom. It doesn't fail anything, but it falls back to setTimeout (with the associated clamping). We'll see if that's fixable (seems doable, since postMessage should be present in that environment).

Plan of record here is the following: typelevel/cats-effect#2314

[armanbilge]

Quick update: since yesterday we now have WebWorker test infrastructure running, as well as patched the polyfill for JSDOM.

[djspiewak]

I'll leave this issue open to track the culmination of @gzm0's compiler warning idea. In the meantime, over in polyfill land, I'll open an issue to track the drive towards 1.0.0.

[gzm0]

QQ is there already a readme somewhere that explains why using the global execution context is potentially bad? I doubt I'll come up with something short enough for an error message. So I was thinking to just refer to a page.

[armanbilge]

Does the readme at https://github.com/scala-js/scala-js-macrotask-executor work?

[djspiewak]

I doubt I'll come up with something short enough for an error message.

"The global execution context is based on Promises, which exhibit unfair scheduling semantics with respect to other elements of the event loop, such as I/O events, timers, and UI rendering. It is recommended that users employ the macrotask executor, to be found here: https://github.com/scala-js/scala-js-macrotask-executor"

Ish?

[armanbilge]

I took a stab at making @djspiewak's snippet hopefully a bit easier to follow for the less-informed:

The global execution context is based on Promises (microtasks). Using it may prevent macrotasks from running reliably, including I/O events, timers, and UI rendering. It is recommended that users employ the macrotask-based execution context found at: https://github.com/scala-js/scala-js-macrotask-executor.