React Virtualisation from scratch
Tags: webdev, react, typescript, frontend
Published: 2023-10-06 21:27:20


> I am open for hire on Fiverr! If you think my skills could be of use, please ping me a message [here](https://www.fiverr.com/s/XPLmoV)!

If you have been using React for awhile, you may have heard of the infamous virtualisation library [react-window](https://github.com/bvaughn/react-window) or it's predecessor [react-virtualized](https://github.com/bvaughn/react-virtualized)

Both of the library aims to help developer to render large list of tabular data efficiently. You may ask why virtualise it when you can just do the following
```tsx
type LargeListItem = {
   id: string
   content: string
}

function ComponentA() {
   // .. a very large list
   const largeList: LargeListItem[] = []; 
   return (
      <ul> 
        {largeList.map((item) => (
            <li key={item.id}>{item.content}</li>
        ))}
      </ul>
   )
}
```  
that looks pretty efficient to me, doesn't it?

For a list with small size of number, that's a total valid option. But imagine when there is 50,000 item in the list, React will have to render all of 50,000 components even majority of them will be out of the screen. Not only does it wasted the processing power and it also sacrificed the render ing time for zero benefit. 

So how can we render long list of item efficiently? 

**Worry not, Virtualisation comes to rescue!**


![Jumping into Nether portal](https://media1.giphy.com/media/MoVAwwWxY27Sm92KMh/giphy.gif?cid=ecf05e47frgzt0lywtrlf9sonhj0wenfv9ixhqdnt0q5y9za&ep=v1_gifs_related&rid=giphy.gif&ct=g)

If you have played Minecraft before, you would realise not everything are rendered on your map. Blocks are only rendered when your sight reaches it, virtualisation works the same by only render what you would see on your window instead of everything.

The same technique are used in lots of online tool, e.g: Miro, Figma, Google Maps ... e.t.c as there are many components to render on the board usually but majority are not needed when user's focus is only on part of the app. 

![Figma interface](https://europe1.discourse-cdn.com/figma/original/2X/1/19a62fad298d009ae487f9891ebc768aa408482b.gif)

Enough said, Let's build it **from scratch**! 

## Virtualised Whiteboard

The idea is very simple, anything the user viewport touches we rendered, don't render if not. 

![Diagram for showing the idea behind virtualisation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fc8yqnu8kz7rr90c1x09.png)

I bounded the content with a larger rectangle but in reality it can be infinite - just like Minecraft.

Talk is cheap, let's see some code. For this demo, I am using Next.js

### User viewport

Firstly, let's look at locating the user viewport which is the small rectangle in the diagram above. 

```tsx
"use client";
import type { PropsWithChildren } from "react";
import { cloneElement, isValidElement, useState, useCallback } from "react";

export function Viewport({ children }: PropsWithChildren) {
    return (
        <div className="h-screen w-screen overflow-scroll">
                {children}
        </div>
    )
}
```
In this component, we set the dimension to fill the screen and render the child which would be the whiteboard where the content should be render. We also allow viewport to scroll as it's guaranteed the whiteboard would be larger the viewport.

For simplicity, let's assume the whiteboard are 10000px * 10000px in size instead of infinite. In that case, implementation of the whiteboard would be very simple. 

```tsx
"use client";

export function Whiteboard() {
    return (<div className="w-[10000px] h-[10000px]"/>)
}
```
then we wire the components up,
```tsx
import { Viewport } from "./components/viewport";
import { Whiteboard } from "./components/whiteboard";

export default function Home() {
  return (
    <Viewport>
      <Whiteboard/>
    </Viewport>
  )
}
```
There you have it you very own virtualised whiteboard! 
![First draft version of virtualised whiteboard](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2925ya8eqokis9vsle5d.gif)

Hmm... a little underwhelming is it? And Where's the virtualisation !!???
![where's the beef](https://media.tenor.com/ordOZ2elCpAAAAAd/wheres-the-beef-burger-king.gif)

Let's make something to render on the whiteboard to add some colours to it! 

```tsx
type MemoProps = {
    bgColour: string
}

export function Memo({ bgColour }: MemoProps) {
    return (
        <div 
            className={`drop-shadow-md rounded`} 
            style={{
                height: 48,
                width: 48,
                backgroundColor: bgColour
            }}
        />
    )
}
```
Memo Component with random background colour. Let's render 10000 memos and put it on to the whiteboard.

```tsx
"use client";

import { Memo } from "./memo";

const BACKGROUND_COLOURS = ['#fca5a5', '#fb923c', '#fde047', '#bef264', '#6ee7b7', '#7dd3fc', '#d8b4fe']

function randomHexColour() {
  return BACKGROUND_COLOURS[Math.floor(Math.random() * BACKGROUND_COLOURS.length)];
}

const MEMOPoistions = Array(10000).fill(0).map((_, idx) => ({
    id: idx,
    x: Math.random() * 10000,
    y: Math.random() * 10000,
    bgColour: randomHexColour()
}))

export function Whiteboard() {
    return (
        <div className="w-[10000px] h-[10000px] relative">
            {MEMOPoistions.map(({id, bgColour, x, y }) => (
                <div
                    key={id}
                    className="absolute"
                    style={{
                        top: y,
                        left: x
                    }}
                >
                    <Memo bgColour={bgColour} />
                </div>
            ))}
        </div>
    )
}
```
![Whiteboard with a lots of memos](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/x8iw6ld2b8j2lp7sz3bf.png)
<figcaption>Looks colourful! But wait.... </figcaption>
![Render time](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uim9a5m8pv9firq9gzjg.png)

It takes close to 400ms for one render !? Imagine how many time will be wasted when you have to update content (state) of the memo? Let's virtualise it to save some resource!

## Virtualisation 

To work out what to render or not, we will have to figure out what are overlapping with viewport.

Let's start by calculating the bounding rectangle of the viewport and pass it to the child.

```tsx
type ViewportRenderArgs = {
    viewportHeight: number
    viewportWidth: number
    viewportTop: number
    viewportLeft: number
}

type ViewportProps = {
    render: (args: ViewportRenderArgs) => ReactNode
}

export function Viewport({ render }: ViewportProps) {
    // callback reference for calculating viewport height & view
    const [viewportDimensions, setViewportDimensions] = useState({ height: 0, width: 0 });
    const [viewportLocation, setViewportLocation] = useState({ top: 0, left: 0 })

    const calculateViewportDimensions = useCallback((el: HTMLDivElement) => {
        setViewportDimensions({
            height: el.clientHeight,
            width: el.clientWidth
        });
    }, [])

    const onScroll = useCallback((evt: React.UIEvent<HTMLDivElement>) => {
        const el = evt.target;
        if (el instanceof HTMLDivElement) {
            setViewportLocation({ top: el.scrollTop, left: el.scrollLeft });
        }
    }, []);

    return (
        <div
            ref={calculateViewportDimensions}
            onScroll={onScroll}
            className="h-screen w-screen overflow-scroll">
            {/* render children with renderProps and pass in viewport constraints */}
            {render({
                viewportHeight: viewportDimensions.height,
                viewportWidth: viewportDimensions.width,
                viewportLeft: viewportLocation.left,
                viewportTop: viewportLocation.top
            })}
        </div>
    )
}
```
We also changed to use `renderProps` instead of `children` as [React document suggests not to use cloneElement to override props](https://react.dev/reference/react/cloneElement#alternatives).

Now that the whiteboard component know the size of the viewport and also the position of it. We can find out what memo are overlapping with the viewport using a data structure called [R-tree](https://en.wikipedia.org/wiki/R-tree) which is optimised to look for overlapping rectangle! 

There's a great library call [rbush](https://github.com/mourner/rbush) written by [mourner](https://twitter.com/mourner) which suits our purpose perfectly! Please do give a star to the repository if you like!

we can then utilise this library to look for the memo we should render! 

The following is what the new code for the whiteboard looks like:

```tsx
type Memo = {
    id: string
    bgColour: string
    x: number
    y: number
}

type WhiteboardProps = {
    viewportHeight: number
    viewportWidth: number
    viewportTop: number
    viewportLeft: number
    MEMOs: Memo[]
}

type BoundingBox = {
    minX: number 
    minY: number
    maxX: number
    maxY: number
}

type MemoMetadata = {
    id: string
    bgColour: string
}

export function Whiteboard({
    viewportHeight,
    viewportWidth,
    viewportTop,
    viewportLeft,
    MEMOs,
}: WhiteboardProps) {

    const rtree = useMemo(() => {
        const anchors = []
        for (const memo of MEMOs) {
            anchors.push({
                minX: memo.x,
                minY: memo.y,
                maxX: memo.x + 48, // memo left position plus it's width
                maxY: memo.y + 48, // memo top position plus it's height
                id: memo.id,
                bgColour: memo.bgColour
            })
        }
        const rbush = new Rbush<BoundingBox & MemoMetadata>();
        return rbush.load(anchors);
    }, [MEMOs]);

    const visibleMEMOs = useMemo(() => {
        // search for memos that overlapped with viewport
        return rtree.search({
            minX: viewportLeft,
            minY: viewportTop,
            maxX: viewportWidth + viewportLeft,
            maxY: viewportHeight + viewportTop,
        })
    }, [rtree, viewportHeight, viewportLeft, viewportTop, viewportWidth])

    return (
        <div className="w-[10000px] h-[10000px] relative">
            {visibleMEMOs.map(({ id, bgColour, minX, minY }) => (
                <div
                    key={id}
                    className="absolute"
                    style={{
                        top: minY,
                        left: minX
                    }}
                >
                    <Memo bgColour={bgColour}/>
                </div>
            ))}
        </div>
    )
}
```
And finally extract the Memo positions and metadata to parent component so it don't re-generate the position every re-render.

```tsx
export default function Home() {

  const MEMOs = useMemo(() => Array(10000).fill(0).map(() => ({
    id: nanoid(),
    x: Math.random() * 10000,
    y: Math.random() * 10000,
    bgColour: randomHexColour()
  })), []);

  return (
    <Viewport
      render={(viewportArgs) => (
        <Whiteboard
          MEMOs={MEMOs}
          {...viewportArgs}
        />
      )}
    />
  )
}
```
![Virtualised whiteboard](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s52jvg2vantd5trxe1bc.gif)
<figcaption>Look Mum, it's virtualising!!!</figcaption>

![Improved performance](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wpc7tx85shnstbz1wyqh.png)

Due to the nature of rendering subset of components instead of all of them, the rendering hugely improved from **400ms** to _**140ms**_! And not to mention the benefit it brings when we introduce more interactivity and state update to the app, I see this as an absolute win!

As you might see, the app still looks a bit laggy even with the performance boost. There's number of trade off you could do in order to facilitate the rendering process: 

- using [flatbush](https://github.com/mourner/flatbush) library instead of rbush which optimise the statically placed element, from the benchmark in the repository it could boost up to 5x the performance of rbush.
- increase the bounding box of viewport so some buffer memo will be rendered even though not visible in viewport to smoothen the scroll.

## Conclusion
Thank you for sticking with me, I hope you enjoyed and find this article useful. This is the technique used in my website: https://moosic.pro - a Piano MIDI visualiser & recorder, please feel free to check it out if you're interested.

I am also [open for hire on Fiverr](https://www.fiverr.com/s/XPLmoV), so if you think my skills could be of use, please don't hesitate to send a message there!

There's lot more I can add but I am gonna stop here. 

Here's something for you to think about
- how can I alter this so the canvas can be infinite ?
- how to improve the scroll with drag scroll? 

Feel free to checkout the repository
{% embed https://github.com/sheunglaili/virtualised-whiteboard %} and play around with it.

If this article get more than 100 reactions, I might continue and add functionality like dynamically place memo anywhere on the whiteboard!