Repaint Segmentation of Algorithms

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.

Codepen. (source code)

To demonstrate how powerful this method is, here is the quicksort with buffered 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