What is scheduling?
At a high level, scheduling can be thought of as a way of splitting up work and allocating it to be completed by a compute resource. The work can be processed at some point in the future, in an order, and by a given resource that the scheduler specifies.
For example, if we had a set of tasks of equal importance, lets say calculating billing and distributing invoices for users of your Software as a Service platform, we could use a scheduler to distribute that work in a way that was evenly distributing processing time to each task. If the tasks were of differing importance, we could allow the scheduler to prioritise work, ensuring more processing time was allocated to performing higher prioritised tasks. For instance, you might prioritise the work loads of paying customers over free users.
At a more granular level there are many different approaches of varying complexity to scheduling work. Some examples of mainstream scheduling strategies include: first in first out, earliest deadline first and round robin. The wiki for this is actually really strong, so I’ll defer to that for an in depth explanation.
- Tasks - Event handlers, setTimeouts, setInterval, etc
- Rendering steps - requestAnimationFrame queued work, Style, Layout, Paint
Knowing this helps us write and/or understand a well planned scheduler in conjunction with our own code. We can break up long running tasks into smaller tasks and interleave them with other work, for example performing layouts and repaints in an efficient manner.
The specifics of the event loop are much better left to others; specifically I would recommend Jake Archibald’s talk at JSConf Asia 2018 which is a superb elucidation on the subject (he also has a blog post).
User experience and scheduling
A recurring problematic theme in web applications is the the idea of jank; low frame rates and interactivity for end users. Having talked a bit about the event loop, how might we leverage that understanding to better improve our sites user experience? One prime example is Wilson Page’s fastdom which was one of the first schedulers I came across in late 2013. The core premise is that it’s possible to batch up DOM reads and writes, and then schedule them using
requestAnimationFrame for noticeably smoother animations.
requestAnimationFrame allows developers to schedule DOM updates right before the browser performs the next render cycle (style, layout, paint, composite). This prevents work being done mid frame causing it to miss the frame as shown in the following diagram (thanks Google). Clever stuff!
This approach can noticeably improve user experience for DOM heavy sites. However,
fastdom as a library is predominately about preventing layout thrashing, and generic work scheduling is outside of its scope. Furthermore,
requestAnimationFrame is arguably not an appropriate tool in and of itself to handle generic work; each request will run in it’s intended frame and does not distribute them across multiple frames.
Adoption by frameworks
Arguably one of the earlier stage examples of scheduling is the AngularJS (1) digest cycle. AngularJS came out in 2010, and it had its own built in event cycle (a scheduler of sorts) for handling its notorious two way data-binding system. An overview diagram can be seen below. The digest cycle checks for changes between the view data model and the DOM, and then re-renders after the cycle to reflect those changes. Certain elements of the cycle, by the documentations own omission, could be considered problematic, for example setTimeout(0) can be janky as the browser repaints after every event.
Angular, AngularJS’s successor has a different approach to change detection and updates which can be read about here. It also does some interesting things with asynchronous execution contexts (zones), allowing for a smarter way of doing operations like updating the DOM, error handling and debugging.
Vue.js takes the approach of batching DOM updates asynchronously. There is no ‘digest cycle’ as per AngularJS as Vue.js encourages a data driven approach. Here the batched operations are then flushed out to the DOM on a given tick cycle. The queue internally uses
MessageChannel, with a fall back to
setTimeout(fn, 0) if those aren’t available.
Other frameworks have explored a holistic view of how to handle the stream of user interactions, network requests, data flow and rendering. A prime and recent example of this is React. React Fiber, fully implemented in React 16, uses scheduling to improve perceived performance and responsiveness in complex web applications). In the world of the web not all computational work may be of equal importance to a user. For example typing and receiving immediate feedback may be a more critical interaction than having a dashboard receiving external data and updating instantaneously. The React team has done a lot work to it’s reconciliation algorithm to prioritise work in a way that is conducive to a pleasant user experience. This is done fundamentally by scheduling different updates at different priorities. Traditionally, all updates were treated synchronously, with no prioritisation. React’s reconciliation phase was uninterruptible, which could lead to low framerates for complex work loads. Here is an example of the Chrome profiler showing it taking ~750ms to render a frame (the green bar):
The way in which React Fiber attempts to keep consistent framerates is via what they have dubbed time slicing. The process uses
requestIdleCallback to defer low priority work to the browser’s idle times. Fiber also estimates the number of milliseconds of time remaining in the current idle stage, and when this elapses stops work to give the browser time to render a frame. For deeper explanation, check out Giamir Buoncristiani’s post, the React Fiber Architecture README by Andrew Clark and also Dan Abramov’s talk at this years Iceland JS Conf. In Dan’s demonstration you can clearly see the difference between the synchronous and asynchronous work patterns:
Another project that has (very recently) been leveraging scheduling is StencilJS. For those of you who aren’t familiar, StencilJS is a modern web framework that takes popular features from many recent frameworks, and combines this with compilation down to native Web Components. Manu Mtz-Almeida of the StencilJS team has recently been pushing commits for scheduling into the core framework, demoing some of his recent work on Twitter:
Introducing a new scheduler: the multi-stage queue.— Manu Mtz-Almeida (@manucorporat) April 18, 2018
It prevents low-rate but CPU expensive tasks to block high-rate but cheap DOM updates.
This way @stenciljs can deliver 60FPS even when the CPU is extremely busy, and we do it at 1⁄10 of the size of other algorithms pic.twitter.com/8ml97MOA39
You can see that the end goal is similar here to what React is doing with Fiber; try and keep the browser rendering at 60fps for a smooth user experience, whilst still completing non-rendering work in reasonable time-frames. Hopefully we’ll be seeing more from the Stencil team in the future!
The building blocks of scheduling in the browser
- setTimeout - Execute a given function at some point in the future
- setInterval - Execute a given function on some recurring schedule (every x milliseconds)
- Promises - An object representing the eventual success or failure of asynchronous operation
With ever improving browser standards we also have some interesting additional browser APIs that might help us to write smarter schedulers:
- requestIdleCallback - Schedule work to be done during the browsers idle periods. Supports deadlines.
- performance.now - Granular timing API for modern browsers
- async/await - Allows developers to write easier and cleaner asynchronous code, making it feel more synchronous
As well these, there is the previously mentioned
requestAnimationFrame for visual changes. Interestingly React was originally relying on
requestIdleCallback for Fiber, but now they’ve written their own polyfill for this (at time of writing). Indeed there is no single way to write a scheduler, and you could use a myriad of these features to create one. Getting this right appears to be a relatively tricky endeavour; in the words of Bertalan Mikolos “timing is a delicate thing, and slight mistakes can cause some very strange bugs.”.
Personally, the strongest example so far I’ve seen of a generic purpose scheduler is Justin Fagnani’s
requestAnimationFrame to allow developers to schedule work. It’s worth examining the source code to see how these are used (FYI: it’s written in TypeScript).
With teams like StencilJS following suit with their user centric scheduler, there is strong evidence to suggest that smarter scheduling may become commonplace across many approaches to building web applications. I haven’t seen much work done with Web Workers and scheduling, but feel this could be a strong contender for future work as inline Web Worker libraries have become more popular and Web Workers are non blocking on the main thread. I think this is especially true for long running tasks, see for example a little demo I did making a library called Fibrelite for offloading processing to an inline Web Worker.