The last couple of years I have been researching solutions to loathsome symptoms of engines like `libChromiumContent`

as a native platform. The biggest one being the bottleneck of operations on the DOM. Although originally things like *scrolling* caused an **entire** repaint, it doesn't have to anymore.

There are two reasons why I'm strongly behind them as a platform. The first one, is that Web Assembly is now available (and C/C++, Rust is already available with it). The second reason is the vigorous list of APIs readily available for powerhouse applications. WebGL, Geolocation, Threads, Thread-Safe Typed Buffers, ServiceWorkers, Thread-Safe B+ Tree, Thread-Safe Image Processing, Channel Messaging; the list goes on.

No, really. If it weren't for the prospects of WASM, I'd probably be doing Java and/or Swift.

I want to talk about repaint segmentation of algorithms.

Suppose you have a large set of elements in your application. Say, thousands of backlog lines in a chat program. You represent every line as a `<p>`

. And every new line is an appended `<p>`

. It sounds like it wouldn't work, doesn't it? Any modern engine would freeze, as the expensiveness would be too much — much less changing the color or sorting those lines!

Google actually gives us a couple solutions to dealing with visual changes. In conjunction with reducing paint complexity, you can solve scenarios like the one above. I took it a step further. Let's take a look at a sample Google gives us for breaking large tasks into smaller, per frame availability.

Immediately when I saw this, I thought about divide-and-conquer algorithms and how this could be generalized for a class of problems *(with easing!)*.

## Quadratic problems.

Applying this segmentation to algorithms of \(\mathcal{O}(n)\) time is trivial. Let's take a look at quadratic, which initially may seem confusing. I took a look at bubble sort, being one of the sorts I know very well.

Here's a Codepen of it working. *(source code)*

Although

`swap`

here is only swapping the height, the result is the same. It causes a repaint. Moreover, some element's height may be the same, causing the visual variation illusion.

The code is beautifully straightforward. For \(\mathcal{O}(n^{2})\) (and, by extension, \(\mathcal{O}(n^{3})\)) segment the algorithm at the operation when enough time is available, here being `swap`

, calling `requestAnimationFrame`

at each 'depth'. It scales, and we can add easing or delay.

This approach works for **ANY** `n`

as it always runs the nth-depth operation when enough time on a frame is available. Mindblowing.

## Logarithmic problems.

→🦉

Next, I took a look at `quicksort`

, also straightforward to implement. The generalization works for all logarithmic and combinatoric problems.

To demonstrate how powerful this method is, here is the

`quicksort`

withbuffered segmentation. It does not complete, however, as pivot step atomicity is necessary.

Cool. Alright, let's break this down. First off, we notice `quicksort`

is async. The operation we segment is the partition, being the base operation for all recursive calls. Because we segment `partition`

on available frames, we want it to take its time. So I await a `Promise`

to the next `pivot`

in the sort — thus scaling the algorithm for all `n`

. The segmentation here isn't as fast as our quadratic solution. The atomicity of our `pivot`

operation cant be buffered into a time frame. **But the algorithm does complete for all n smoothly**.

If there were many base-case operations, or 0th and 1st, we'd segment them together — scaling into recursion.

## Last remarks

Some game-changing stuff here. I am completely confident I could build **very large** applications with close-to-native (if not fully native) speed. The research mentioned above has removed many problems regarding DOM applications at scale. If you have questions or thoughts send me a message on Twitter.

— Jahan