Nikita Kirsanov

The simplest example of scheduling on the main thread

February 19, 2019

The problem

The more complex our applications become the more work browser have to do. And due to single threaded nature of javascript it is becoming harder to make our apps responsive (to respond to user interactions immediately).

Let's develop some simple app to clearly understand what I am talking about. An app I would like to create will generate huge array of random numbers and sort it.

Let's start with core feature - sort function. Yep, we are not going use

Array.prototype.sort, cause it will be impossible to improve it later. The simplest algorithm I know is bubble sort:

let sortPass = array => {
  let needOneMorePass = false

  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] > array[i + 1]) {
      let temp = array[i]
      array[i] = array[i + 1]
      array[i + 1] = temp

      needOneMorePass = true
    }
  }

  return needOneMorePass
}

let bubbleSortSync = array => {
  // do not mutate original array
  let clone = array.slice()

  while (sortPass(clone)) {}

  return clone
}

I've splitted algorithm into 2 functions to show how it is easy breakable into units of work - passes.

Now let's add some simple ui: button to trigger core functional of our app (sorting). To track ui responsiveness during algorithm execution we will add css animation and text input. Also we will try to display several array elements before and after sorting:

Have you seen that? Button click "stops the world": green block is not rotating anymore, input cannot be edited. And the reason for that is that browser processes everything in a single thread: it wasn't able to update layout and respond to user while we were sorting.

Stop the world

To improve our app we should not block main thread for more than 16ms (for 60 frames per second). Thus, we should be able to suspend the execution of the sort function and resume it after the browser has completed its work.

Schedule on the main thread!

Luckily our algorithm can be suspended/resumed easily and browser has nice API to determine best time to execute low priority (not connected to user interactions and animations) code - _requestIdleCallback. _Here is how we can use it:

// we won't be able to return sorted array synchronously anymore
// so let's use promises
let bubbleSortAsync = (array) => new Promise(resolve => {
  // immutability espeсially importaint in async code
  let clone = array.slice()

  requestIdleCallback(function step(deadline) {
    let needOneMorePass = false

    do {
      needOneMorePass = sortPass(clone)

    } while (needOneMorePass && deadline.timeRemaining())

    if (needOneMorePass) {
      // resume sorting later
      requestIdleCallback(step)
    } else {
      resolve(clone)
    }
  })
})

Experience became so smooth that I decided to rerender array elements on every callback (to show the progress). And here is a demo:

Here is how it looks in profiler:

Smooth sort profile

Looks cool, right? Though sorting takes a bit more time to finish, user doesn't feel that it is slow. That is exactly what we were looking for.

We are not alone in scheduling war

Pretty same ideas are used in newer version of react reconciliation algorithm - Fiber. But in our case we didn't take into account a lot of things:

  • it was easy to split work of bubble sort into chunks (what about other algorithms?)
  • we did not care about cancelation what if user pressed sort button again? can we drop a job we've done and start new one?
  • in real apps there would be probably more kind of jobs so what about prioritising?
  • ...

And we do not have to! React team has already solved all this complex things and we haven't even noticed that - there was no API changes when fiber was introduced.

Also one day browsers might introduce more convenient API for scheduling.

Useful links

Read next