Reimplementing setTimeout to use condition variables

[rgerd]

I implemented @syntheticmagus's idea of using a condition variable and priority queue, and it works: #844

The PR currently has experience.js modified into a unit test, I'd revert this change before taking out of draft. Please feel free to review the rest of it if you have suggestions, or comment here if you think another approach would be better.

Anecdotally, on my surface laptop I'm seeing 13% CPU usage with the TimeoutDispatcher running a continuous 1 second ping, and 25% CPU usage with the original recursive wait call. The only drawback I've seen is that setTimeout isn't 100% accurate with the worker thread approach, usually adding about a 10ms delay. I tried increasing the priority of the worker thread with the native Win32 API to no avail. Seems like this is generally still in-line with the MDN spec, which implies that setTimeout calls will be placed on the queue and gotten to when the browser is finished with other important work. Babylon.JS mostly uses setTimeout with a delay of 0 to defer / asynchronize work, so I just threw in a check to optimize for that.

[ryantrem]

I guess this still results in one blocked thread, which maybe is ok. It seems like another alternative would be to use platform specific timers (e.g. timer_create on Android (I think) and NSTimer on iOS (I think)) and have a general purpose delay helper in the Arcana library. Then we could just use this for Babylon Native's setTimeout implementation probably without any thread blocking (and a general purpose delay would probably be useful elsewhere).

[bghgary]

Maybe it is useful to see what browsers do.

[tymlipari]

@rgerd how is this implemented in react-native? I'd be concerned about us over-engineering a solution here. While it's bad that we're blocking the JS thread so substantially, the overhead with hopping from timer threads back to the JS thread may be equally bad. Sure, it may not stall the JS thread, but it may negatively affect other things. Certainly we shouldn't need a dedicated thread for this.

What's an average number of pending callbacks in a BabylonNative app? If we're looking at something like <50 callbacks pending at once, it may make more sense to just provide a special hook to the JS dispatcher loop to drain the pending callbacks list linearly as the O(n) execution per-loop is still probably less involved than thread-hopping from the timer callback.

[bghgary]

provide a special hook to the JS dispatcher loop to drain the pending callbacks list linearly

Isn't this what is already implemented before @rgerd's PR? I'm not 100% sure what you mean by this.

[tymlipari]

Most likely, I haven't personally dug into the code too much. I was mostly writing my questions for posterity since @rgerd and I discussed a bit more offline, and the thread-hopping overhead was my main concern.

I think from talking it through we're going to first see if the existing implementation can be reworked to improve the throughput before pursuing an implementation that requires thread coordination.

[bghgary]

Thread coordination has overhead, but unless there are a lot of contention, it should be relatively cheap. If we use OS constructs like @ryantrem suggest, then it might be even cheaper. I'm not sure how much we can rely on OS implementation since they are likely different between platforms and may cause subtle differences.

[tymlipari]

Agreed. But on a device like HL2 having a dedicated thread for something like this is unnecessarily wasteful (memory commit, scheduling overhead, etc.). If doing a single-threaded naive implementation looks like it won't fix the issue, then I agree we should try and rely on OS primitives as they're likely designed to minimize overhead (e.g. Windows we'd probably just use CreateThreadpoolTimer)

[ryantrem]

I tried to find the react native implementations for reference last week but couldn’t seem to find them with 10 or so minutes of looking. :/

[tymlipari]

React Native implementation details:

Appears to be a combination of a JavaScript polyfill plus native modules. The functions like setTimeout appear to be defined in JSTimers.js.

NativeTiming has different implementations for iOS & Android:

• Android:

  • Module Impl - TimingModule.java
  • Logic Impl - JavaTimerManager.java
    Simple PriorityQueue with hook into React’s frame choreographer to check timers every frame and fire the ones that’ve expired.

• iOS: RCTTiming.mm

  • Similar to Android, keeps a simple dictionary of all pending timers, then each React frame it runs the set of values and fires any that’ve expired

• Windows: TimingModule.cpp

  • Likewise naive implementation with pending timers kept on a list. Interestingly the timers are tracked on the XAML thread and then serialized and dispatched to the JS thread to invoke the callbacks. Not being familiar with the iOS and Android react threading models, I can’t tell if this is different or not.

[rgerd]

Sounds like the React Native implementation is preferable since it's basically the same as what we had before but it avoids churning through std::functions and adding a bunch of extra dispatch calls, it doesn't use any other threads, and it's a simple implementation.

Spec implies that setTimeout callbacks will run at the next opportunity instead of right on time, so it feels like we could just check the list of timers after each blocking_tick call inside WorkQueue (or even onRender) and add the work to the queue for each expired timer.
https://html.spec.whatwg.org/multipage/timers-and-user-prompts.html#dom-settimeout-dev
https://developer.mozilla.org/en-US/docs/Web/API/WindowOrWorkerGlobalScope/setTimeout#reasons_for_delays