Concurrent Programming In Single Thread for Web: Fibers and Priority Scheduling
Let’s get this out of our way. Concurrency and Parallelism are not the same things. Where Concurrency is about managing task execution and giving a high response rate from the system, parallelism is all about executing multiple units of the program at the same time. You can still have concurrency in a parallel system and that’s often the case when you run out of independent threads to start, but generally, a multi-threaded ecosystem need not have the same tricks of concurrency up its sleeve. Although it’s changing quite soon, with languages like Java opting into Fibers and Coroutines as one of the supported language constructs.
Now you must be wondering, where do these concepts fit in the context of the Web? Well as it turns out most of the ideas we just named are specifically useful for execution environments that have access to only one thread at a time. Turns out the love child language of the Web i.e Javascript is a single-threaded language by design. ( 🔪 yes web workers are there but we won’t go there ). Given the current web, ecosystem chances are.
“Any application that can be written in JavaScript, will eventually be written in JavaScript.” — Jeff Atwood.
A few good examples would be web-based editors (video/image/code) and WebGL/Canvas-based games or like Typito’s video editor, (employer plug 😆).
Fibers
If you work with React then you may have heard about the recent changes and improvements from React Conf under the banner of React Fiber , which was a grounds up rewrite for the reconciliation system in React. They have shown some absolutely mind-boggling performance improvement by the virtue of async or as they call it concurrent rendering. So what exactly is Fiber?
A Fiber is a unit of work enclosed in function or object and often the scheduler or manager managing these units of work is preemptible i.e Fiber is an abstracted implementation of user space thread for co-operative multi tasking. To put it simply a Fiber function acts like a thread but is also responsible for yielding back to the system or scheduler to let it know that it is fine to pick up another Fiber node for execution , if required. These decision of what node to pick up can be based on different criterias, like in React , it’s often User event which effect any node (text box / mouse click) etc takes a higher precedence. Although React’s implementation does not prioritise node skipping on these ground always but a Fiber based system can take these calls. Effectively utilising the Single Core / Single thread system to increase system responsiveness.
Having a Fiber based execution system opens up possibilties where jobs can be batched or sepparated based on time budgets to build an adaptable round robin scheduling, since individual Fiber can opt in to yield when certain task is done. But Fiber’s are not exactly a unique idea and can be often be referred as the system level construct / implementation for prior existing ideas like Coroutines.
Coroutines
If you have been using languages like Javascript or Python , you already must be pretty familiar with the idea. Javascript’s async/await is a construct well known and is used for yielding back to the execution context , until an external resource is available or an I/O request is done. Python’s yield keyword , falls under the same category. Although for some reason JS seems to have less afinity towards yield semantics , but that’s a question for another day.
Even if you have not used any of these languages , to put in context Coroutines are function constructs that can return control to the execution context before the return statement. If it sounds familiar to Fiber, then you are right because it is. Coroutines happens to be more language agnostic implementation of the paradigm. Generally in a programing language where Coroutines are supported , the functions can use certain keyword to break the flow of control and hand it over to some callee function or some scheduler , which can then take a call on which other function from the Qeueu needs to be executed. This makes sure that all functions / routines always see some form of progress in their execution and in the end of the day be able to give better responsiveness. A good example of being responsive can be Node.js way of handling request and giving programmer the ability to suspend the execution midway if a database call is necessary. While Node.js can work on attending to other request with the same request handling code that supports suspension midway. All thanks to the Event Loop which enables this kind of Co-operative multi tasking. Well we have been talking about how schedulers can pick up Fiber or Coroutines for execution but we have not talked about how exactly are these decisions made.
Priority Scheduling
A big reason for Node.js success as a server side alternative to other Server Application Environment comes from it’s execution of it’s Event Driven system and how it prioritieses various event.
👆 The above video is a really good explanation of what the heck is an Event Loop in Node.js. But we are not going to talk just about Node.js. Similar Event loops also exist on browser. We are going to talk about what makes these event loops really special.
So let’s start with few scenario
- You have an application that allows user to drag UI elements from point A to point B , think Photoshop (dragging images or layers across the Canvas) 😎 . But every pixel movement requires quite intensive calculation. But the calculation may or may not impact the UI. But it’s necessary for the final result. The repeated expensive calculation is decreasing the frame rate and user is having a really poor experience 😖 . What can be done in such case ?
- You have an application with a search bar for searching some static resources . You played smart 🛠 and stashed in the static resource in frontend and now run all search functionality from frontend itself. But apparantly the static resource is quite long and every keystroke leads to a search , which then leads to a really long loop. While your code for search runs user is getting frustrated 😕 because the browser is not able to respond since there is only one thread to execute your code , which browser also happens to use for it’s own task like responding to keystrokes. What can be done in such case ?
- 3 years down the line your app has reached a million user. Your traffic is off the charts. You decide to just evaluate what kind of page load performance you are getting for your app. Turns out your server takes a ridiculous amount of time to respond to your core app. Well you did started of with Node , async await should have taken care of everything right ??
The answer to all these is effective usage of scheduling and managing priority. If a user event leads to a costly non priority calculation then it can easily be set up in a lower priority qeue to be executed later when necessary. Idle-Until-Urgent is really the answer here. You need not go ahead with the costly execution until it’s really necessary. Understanding Priority of task can really help making the system responsive when the resources are limited and you are at the mercy of only one thread.
The search bar problem is similar and can be solved from the ideas of Fiber discussed prior. The list processing need not be a long synchronous process. The list can be processed in chunks while yielding back to the browser thread , to let browser do it’s stuff like attending to user clicks and keystrokes. Each chunk execution can even be scheduled with browser api’s like requestIdleCallback which only executed when there is nothing else to be done by the execution context. Not only does this allow for browser to stay responsive it gives you the ability to preempt any running task and discard it since you know that a new keystroke means a new search request and older unfinished task can be discarded off. Fun fact this exact system is used by React as well , where prior unfinished reconciliation can be discarded of under concurrent rendering.
👆 The above is an excellent introduction to React code base as well as it’s inner working , which discuss the Work In Progress Tree idea.
This is an excellent GIST on the React scheduling architecture. You can refer here to understand and explore more on the ideas discussed above , regarding priority scheduling. Fare warning , this highly React specific.
Well the server issue is more nuanced but not something that can not be solved. Generally most server request handler ends up engaged in some I/O hence it’s expected that given we have lower number of CPU bound task we can expect a high throughput for number of request handled. But what happens when you really have CPU bound task. Well in this case we need to look into it’s priority, is it a user requested data which needs evaluation. In that case OS Threads might be your only way. In case if its not , in case a page response can be done earlier you can always refactor the CPU bound task to be attended later on in the request handler. To add it to the pattern you can use different priority qeueu offered by node.js as well to time on when certain CPU bound task needs to be executed. The Event Loop model gives you flexibility where you can instruct node to grab all user request and then have certain CPU bound task be executed in the next iteration just before grabbing all the HTTP request again.
In all of these cases one thing that was consistent , was deciding on the priority of task. Effectively deciding on priority of task will allow you to free up system resource and CPU locks , to co-operate better with other routines which may have higher priority like browser paint or attending to http request. In case of Browser Applications , this becomes extremely important because user experiences is affected when your code locks on to the CPU and executed for a really long time.
And you cannot scale a user’s machine. It will always be slower than your dev machine.
This needs to be considered though that all these concepts are only applicable as long as any long running function can be broken down in small quantums of work. But there are caveats to this as well , since yielding too often can slow down otherwise fast operations. Hence why these design decisions always need to be taken with much consideration.
These ideas have been around for a long time and their introduction and usage in the web will only lead to a better user experience however much remains to be desired from the current state of browser scheduling.
🙇 Hope it helps you to get a context and ideas on what can help you to write more responsive applications when in a single threaded execution context.
PS: I have been working on React and other Javascript related performance issues in our app , from past few months and this post is just for setting up the context on what the subsequent post will be talking about.
