In January this year, I applied for an overseas dev job. I was asked to finish a project as homework. The project required a ton of computations on the front end, which posed a challenge as I must ensure no operations should block the main thread. I didn’t want to move the computation to a worker thread because the data was consumed in the main thread. Serializing and de-serializing a large set of data also has a performance cost. Furthermore, to improve indexing performance, I used
Map to store the results, which is not serializable.
The task involved is as following:
Process a long list of news items, and index each item according to its tags. It looks like this in code:
If you’ve been working with React long enough, you’ve probably heard of React Fiber and time-slicing. React Fiber is a new reconciliation algorithm inside of the React core. It was designed to enable React to handle computations(mostly diffing caused by
setState) in a non-blocking way. When high priority tasks occur due to user inputs, React can pause low priority tasks and handle them immediately.
If you used to pass callbacks in Ajax programming or
node.js event handlers, you already know the technique I’m going to show you. I just find a fancier name for it: CPS(Continuation-passing Style).
Here’s an identity function you would write normally:
and here is a CPS version:
In continuation-passing style, instead of “returning” the procedure to its caller, you invoke the “current continuation” callback (provided by the caller) on the return value.
The foundation of CPS is simple:
The atomic operation we need to do in processing the list is as following:
So we need to slice our previous one big task to many small tasks like the above one. Here’s how to do it:
This introduces too many recursions and makes our code way more complicated without improving performance. But we are very close!
Notice a very important feature of the
indexNews function. It takes a continuation callback and calls the continuation after finishing the current task. We’ve achieved “Inversion of Control” here. We can tell
indexNews what to do in the next iteration.
In our case, we want it to move subsequent tasks to a new callstack so that we don’t put too much pressure on the current callstack.
However, we don’t want to move every task to its own callstack, which is unnecessary.
So, here’s the rule:
Each callstack can take 500 tasks, after that limit, we put the next 500 tasks in the next callstack. Repeat until all tasks are done.
We just need a few modifications to our previous code to achive this:
setTimeout method will move its callback to the next execution callstack.
We introduced a technique we already knew and rediscovered the hidden power of it. Continuation-passing Style enables us to have control over what happens next when the current operation is completed. Relying on this feature, we first sliced a very big task to many small ones, and then chunked them into different callstacks.
Check out the project here.