DEV Community: Martin Devillers

Polishing the charts

Martin Devillers — Wed, 20 May 2020 02:32:35 +0000

This week I've been working on the polish of the Big O Visualizer. No, I'm not translating the website to the Polish language (sorry Poland!), but:

pol·ish (verb) make the surface of (something) smooth and shiny by rubbing it.

A.k.a. just raising the bar on things. Whether I'm working on a multi-million user international product or my own little pet project, I like to use my own products every day. I wake up with them and I go to bed with them. And even though I've looked at the same screen every day for the last thirty days... sometimes I can just wake up, open that same screen I've been staring at for ages and think:

... No.

... This doesn't look right.

... Has this always been like this?

... This won't do.

... I have to change this immediately.

I had a moment like this a couple of days ago when I opened the Big O Visualizer on my smartphone, looked at the charts and thought:

... Ugh...

My biggest peeve was that the whole thing just looked constrained and awkward on a smaller viewport. I wondered if it was feasible to cram this much information in such a small space. I mean, whenever I see a big news website embed charts in their articles they don't work that well on my smartphone (iPhone XS for those wondering). Can this be improved? Or are responsive charts like responsive tables: doomed to fail.

And thus I scurried to my desk in my bathrobe and started taking the thing apart.

Highcharts Responsive versus React Responsive

Initially, I tried to use Highchart's own Responsive functionality, which was recently introduced in their 5.0 release. Unfortunately, this didn't play well with react-jsx-highcharts, the React plugin I'm using to integrate Highcharts into this project.

However, the React ecosystem is home to the excellent react-responsive plugin by Eric Schoffstall. This plugin introduces the useMediaQuery Hook, which allows me to do delicious things like:

const ComplexityChart = ({ title, children }: ComplexityChartProps) => {
  const { theme } = useThemeUI()
  const isDesktop = useMediaQuery({ minDeviceWidth: theme.breakpoints?.[0] as string })
  const yAxisLabels = isDesktop ? { rotation: 0, padding: 5, x: -8 } : { rotation: -90, padding: 0, x: -3 }
  const titleStyle = isDesktop ? { fontSize: theme.fontSizes?.[2] } : { fontSize: theme.fontSizes?.[1] }
  const chartMarginRight = isDesktop ? 70 : 0
  const chartSpacing = isDesktop ? [10, 10, 15, 10] : [10, 5, 15, 5]
  const [colorMode] = useColorMode()
  const isDark = colorMode === `dark`

  return (
    <HighchartsChart plotOptions={plotOptions} callback={setTheme} key={colorMode} sx={{ backgroundColor: "chart" }}>
      <Chart marginRight={chartMarginRight} spacing={chartSpacing} zoomType="xy" backgroundColor="transparent" />
      <Title style={titleStyle}>{title}</Title>
      <Loading>Running analysis...</Loading>
      <Legend />
      <Tooltip />
      <XAxis type="logarithmic" min={10} max={10000}>
        <XAxis.Title>Elements (n)</XAxis.Title>
      </XAxis>
      <YAxis type="logarithmic" min={10} max={100000000} labels={yAxisLabels}>
        {isDesktop && <YAxis.Title>Operations (O)</YAxis.Title>}
        {children}
      </YAxis>
    </HighchartsChart>
  )
}

The lines of interest are:

Line 3. Create a fresh useMediaQuery Hook using the desktop breakpoint from the current theme.
Line 4. Render the Y-axis labels normally on desktop and 90 degrees rotated on mobile. This reduces the width of the Y-axis on mobile, so there's more space left for the chart.
Line 5. Match the font-size of the title with the rest of the site. This is just to keep things consistent with the theme, which uses a larger font size on desktop than on mobile.
Line 6. Reserve some whitespace to the right of the chart on desktop to render the labels. On desktop, we will keep the complexity labels out of the chart area, but on mobile we're going to pull those in.
Line 7. Give the chart some more space on desktop.
Line 22. Render the title of the YAxis only on desktop. This powerful feature of the useMediaQuery Hook allows you to conditionally render any React component given a media query. Cool stuff.

The ComplexitySeries component is changed so that the complexity labels are pulled inside the chart area on mobile. Again, we use useMediaQuery to achieve this behavior:

const ComplexitySeries = () => {
  const { theme } = useThemeUI()
  const isDesktop = useMediaQuery({ minDeviceWidth: theme.breakpoints?.[0] as string })
  const plotOptions = {
    lineWidth: 0,
    marker: {
      enabled: false,
    },
    states: {
      hover: {
        lineWidth: 0,
      },
    },
    enableMouseTracking: false,
    showInLegend: false,
    dataLabels: {
      enabled: false,
      crop: false,
      allowOverlap: true,
      overflow: isDesktop ? "allow" : "justify",
      align: isDesktop ? "left" : "center",
      verticalAlign: "middle",
      format: `{series.userOptions.notation}`,
      x: isDesktop ? 0 : 5,
    },
  }
  const xPoints = Array.from({ length: 42 }, (v, i) => Math.min(10000, 2 ** i / 3))
  const complexitySeries = Complexities.common.map((r) => (
    <AreaSeries
      key={r.name}
      name={r.name}
      color={getColorForComplexity(theme, r)}
      notation={r.notation}
      data={xPoints.map((x) => ({ x, y: r.calculate(x) }))}
      {...plotOptions}
    />
  ))
  complexitySeries.forEach((x) =>
    Object.assign(x.props.data[x.props.data.length - 1], { dataLabels: { enabled: true } })
  )
  return complexitySeries
}

That's it! Just four lines of code (3, 20, 21 and 24) were changed to introduce this behavior.

The result

So what does this get us? See the below before and after:

Unresponsive Chart

Responsive Chart

Not bad. 👍

As always, head over to https://omi.cr to see the latest greatest of the Big O Visualizer 😃

Time for some reflection

Martin Devillers — Thu, 14 May 2020 23:09:22 +0000

It's been about a month since I started the Big O Visualizer. I think by now I've clocked well over a hundred hours writing code, experimenting with different technologies and tweaking the results. So I thought it was time to write a reflection on what went (not so) well.

First of all, whether I'm leading a multi-million dollar multi-team cross-country IT initiative or my tiny one-man pet project, the same things tend to happen. For instance, the things I thought would be hard didn't take that much time at all. Things like instrumenting the algorithms, creating the datasets and plotting the results in a chart. Looking back at my logs I had a rudimentary version of the final product up and running in less than two days. So what took so much time? Well, basically, it's that part after you finish a concept and say to yourself "Alright, now let's do it again but this time good. With frameworks and standards and such."

That's when trivial things pop-up that turn out not to be so trivial. Or well maybe they are but I'm just ~~stubborn~~ a perfectionist and I don't want to give up. A good example is the "Dark Mode" feature that came with the theme I picked. I choose LekoArt's excellent Minimal Blog, because it had everything I wanted in a theme: typography-only, syntax highlighting, dark mode and cool purple highlights (purple is my favorite color). However, as I was adding charts into the mix I wanted my charts to support dark mode too. Specifically, I wanted my charts to respond to the user switching color modes, just like the rest of the website does.

Oh boy.

That was a solid eight hours ~~wasted~~ getting different technologies to play nice. I could say this was due to my lack of experience with these technologies, and that this normally never happens but then again: every single project I've done comes with a new set of technologies. I mean, I hear tech recruiters sometimes say that they prefer "specialists" over "generalists", but then I think: specialists in what? Do specialists exist in a world where frameworks go from alpha, to market leader, to legacy in like, what, five years? And even if you stay loyal to one technology, that technology evolves as well. Angular 1 versus 2 is a good example. Microsoft also has a nice history of major bumping a version of something, while under the hood replacing pretty much everything except the name and logo. Now React is doing the same thing with React Hooks, introducing a "opt-in" feature that "only" adds a new way to handle state in React, which is totally not a big thing (it is) and this totally won't replace the old way you handled state (it will), because the React team is going to support the old way (for now) and you absolutely surely do not have to rewrite all your Class components into Functional components (you can see where this is going).

Sorry, I went a bit ranty there.

So I spent a day on getting my chart to look good in the dark.

What else took a while?

Ah yes, I remember.

LINTERS

Linters are like pull requests. On the one hand, I am open to feedback, want other people to look at my code and absolutely belief it will make the world a better place. On the other hand, I just want to push my change and NO STEVE I DONT WANT TO PUT FINAL IN FRONT OF EVERY SINGLE VARIABLE BECAUSE WHATEVER. So linters are like that. You install it, you pick the Airbnb rule set because they're one of the few organizations that dared to create some form of standard and then you immediately regret all of these decisions when your console fills with lines after lines after lines of warnings and errors. In my case I'm actually getting hit twice because I'm also using TypeScript which comes with its own slew of you-should-probably-fix-this messages.

Fun times.

So I solved all of those and I felt okeyish as I pushed a commit that pretty much touched every single line of code I'd written at that point. Looking back I should setup the linter immediately the next time I start a new project. For the ruleset I still recommend the one from Airbnb but with the guideline that it's ok to disable a rule if you feel it's too strict or you simply disagree (especially when you Google said rule and you see a 100 comment long ~~poop-flinging contest~~ debate on GitHub). For the TypeScript part I recommend following the rules unless you have to bend perfectly fine and readable code into something that looks awkward but satisfies the checker. In that case, I'd just ignore the warning.

For the rest I spend a few days getting Web Workers to (not) work, which I already discussed in a previous post.

Finally, I've revised the content of the project a lot. When I started the project I had a simple mission to visualize time complexities with appealing charts. Once I had that I realized that the charts were kind of useless without the context in which they were used. So I had to create a proper narrative in which I could use my charts as a supportive element. Basically that means the age-old process of writing-scratching-writing articles. This process takes time, especially when you're writing about a subject you last saw in a university classroom lecture. I'm definitely no scientist in this field and there are dozens of people more qualified to write about this subject than I am. Yet, I'm the one visualizing this stuff at the moment so I'll (pretend to) be the expert until someone steps up and does a better job.

Wrapping up

I am very pleased with the results I've gotten so far. The tech-stack React + Gatsby + TypeScript + Netlify is easy to pick up, feels mature and is ridiculously powerful. The development experience of writing code and seeing the results pretty much instantly in your browser is simply amazing. I love compilers but I also love a tight feedback-loop and once you've tasted instant feedback it's hard to go back. The ability to mix Markdown with (custom) React components is otherworldly. Am I still writing code or am I just writing advanced interactive articles? Heck, I don't even feel like I'm building a website anymore. No more hours of tinkering with HTML and CSS, floating div's, playing with margins and padding, making sure it looks good in one browser, only to do it all over again for the next (IE I'm looking at you).

Nope, none of that.

I just specify a Box or Flex and let the framework figure out all the different dimensions on all the different viewports. For me that's the true strength of any technology: when it allows you to focus on your problem by hiding all the artificial problems you do/should not care about. No CEO has ever said that they wanted their product build in Angular, Vue or React. They just want it build good, cheap and fast. And that's what a good framework allows you to do :-)

Thank you for reading this!

Debugging production with hidden modals

Martin Devillers — Thu, 14 May 2020 04:29:09 +0000

I've added a debug modal so I can experiment with some new features on the production version of the Big O Visualizer. This is especially useful on my iPhone where my debugging tools are limited. So where is this screen? Well, I hid it, because it's super secret and I don't want visitors to mess with these experimental options.

...

Ok, I'll tell you where it is. There's an invisible button to the right of the website's title at the top of the screen. If you click/tap it rapidly (about eight times in less than three seconds) the modal will appear.

You should totally do that!

If you think this is just some crazy feature I've implemented in my own pet-project, think again because I've been building these hidden debug tools into most of my former client's applications (and yes with their consent). Why? Because I'm a huge fan of Testing In Production (yay) and not-such-a-big-fan of But It Worked On Develop/Test/Acceptance/Demo/RC/Spike/Bla (boo).

The problem is that we tend to avoid building these tools into our products because they're of no value to our end-users. The fallacy is that the teams who build these products do not see themselves (or are not seen as) one of the most valuable end-users! So we limit these debug tools to non-production environments (or not build them at all), where they're of little value. Such a missed opportunity! So build debug windows and ship them proudly, like YouTube's video player:

Disclaimer: the options of these debug tools should be limited for (obvious) security reasons. Don't try to ship a hidden "Bypass Login Screen" or "Dump Database" option, because some hacker will definitely find it.

Custom React Hooks

All the settings are implemented as React Hooks which is a powerful and expressive new way to reuse functionality between components that was introduced with React 16.8.

Thanks to React Hooks, any component can use a setting with a simple one-liner: const [preanalyzedMode] = usePreanalyzedMode(), and then use the setting inside its useEffect method. Any changes to the setting will automagically propagate to the components, so they can update their state accordingly.

Each setting is a TypeScript enum that is persisted to the browser's localStorage. I adopted the useLocalStorage recipe from Gabe Ragland's excellent usehooks.com website and rolled into my own more TypeScripty useLocalStorageBackedEnum. This hook factory takes the name of the storage key, the enum used for the setting and a default value for the setting and returns a fully functional React Hook. The result looks like this:

import { Dispatch, useState } from "react"

function useLocalStorageBackedEnum<TEnum extends string, TEnumValue extends number | string>(
  key: string,
  enumType: { [key in TEnum]: TEnumValue },
  defaultValue: TEnumValue
): [TEnumValue, Dispatch<TEnumValue>] {
  const [storedValue, setStoredValue] = useState(() => {
    try {
      const item = window.localStorage.getItem(key)
      if (item === null) return defaultValue
      return (Number.isNaN(Number(item)) ? item : +item) as TEnumValue
    } catch (error) {
      console.log(error)
      return defaultValue
    }
  })

  const setValue = (value: TEnumValue) => {
    try {
      setStoredValue(value)
      window.localStorage.setItem(key, value.toString())
    } catch (error) {
      console.log(error)
    }
  }

  return [storedValue, setValue]
}

This custom Hook makes introducing settings as easy as:

export enum PreanalyzedMode {
  Enabled = "enabled",
  Disabled = "disabled",
  Persist = "persist",
}

export enum WebWorkerMode {
  Enabled = 0,
  Disabled = 99999999999999,
  XLOnly = 1000000,
}

export enum StopwatchMode {
  None = "none",
  Analyzer = "analyzer",
  Algorithm = "algorithm",
}

export const usePreanalyzedMode = () =>
  useLocalStorageBackedEnum("preanalyzed-mode", PreanalyzedMode, PreanalyzedMode.Enabled)
export const useWebWorkerMode = () =>
  useLocalStorageBackedEnum("web-worker-mode", WebWorkerMode, WebWorkerMode.Disabled)
export const useStopwatchMode = () =>
  useLocalStorageBackedEnum("stopwatch-mode", StopwatchMode, StopwatchMode.None)

I ❤ React

Implementing previous/next navigation

Martin Devillers — Thu, 14 May 2020 04:22:38 +0000

When you visit a page on the Big O Visualizer you'll see two arrows at the top right of the screen. These arrows are hyperlinks that allow you to navigate to the next or previous page. I've added these because they're handy for visitors who just want to browse the site's content without having to figure out the navigation structure.

Curious about the implementation? Then read on!

CSS-only

No images or inline vector data is used to render the arrows. In fact, it only took a few lines of (pseudo) CSS to create these:

arrow: {
  width: 4,
  height: 4,
  marginTop: "0.25rem",
  borderRightWidth: "0.25rem",
  borderRightStyle: "solid",
  borderTopWidth: "0.25rem",
  borderTopStyle: "solid",
  borderColor: "secondary",
  "&:hover": {
    borderColor: "heading",
  },
},

Basically the above styling creates a square element where the top and right edge have a thick border. In the TSX component template I add a rotate(45deg) or rotate(225deg) to rotate the whole thing so the arrow points in the right direction. The relevant snippet looks like this:

const PrevNextNav = (section: DoublyLinkedLoop<string>, slug: string) =>
  section.contains(slug) && (
    <Flex pt={[1, 2, 3]}>
      <TLink as={Link} sx={{ variant: `links.secondary` }} to={section.prev(slug)!} alt="Previous page">
        <div sx={{ variant: `icons.arrow`, transform: `rotate(225deg)` }} />
      </TLink>
      <div sx={{ variant: `icons.dot` }} />
      <TLink as={Link} sx={{ variant: `links.secondary` }} to={section.next(slug)!} alt="Next page">
        <div sx={{ variant: `icons.arrow`, transform: `rotate(45deg)` }} />
      </TLink>
    </Flex>
  )

Doubly Linked Loop

In order for this feature to work, there needs to be some kind of data structure that helps me to figure out the next (or previous) page, given the current page the user is on. I choose a Doubly Linked Loop, which is a new structure I made up. It's essentially a regular Doubly Linked List but where the tail is always connected to the head. This property ensures I can blindly call next or previous on the structure, without having to worry that I'm going over some kind of edge. It also means the structure no longer has a clear beginning (headless) or end (tailless), which is why I choose to call it a Loop rather than a List. Internally, there's still a root, which is always the first element that was added.

The final implementation looks like this:

interface Node<T> {
  value: T
  prev: Node<T>
  next: Node<T>
}

export default class DoublyLinkedLoop<T> {
  root!: Node<T>
  length: number

  constructor(array: T[]) {
    this.length = 0
    array.forEach(this.add.bind(this))
  }

  add(item: T) {
    const node = {
      value: item,
    } as Node<T>
    if (this.length === 0) {
      // eslint-disable-next-line no-multi-assign
      node.prev = node.next = this.root = node
    } else {
      const last = this.root.prev
      this.root.prev = node
      last.next = node
      node.prev = last
      node.next = this.root
    }
    this.length++
  }

  find(item: T): Node<T> | undefined {
    let node = this.root
    for (let i = 0; i < this.length; i++) {
      if (node.value === item) {
        return node
      }
      node = node.next
    }
    return undefined
  }

  contains(item: T): boolean {
    return this.find(item) !== undefined
  }

  next(item: T): T | undefined {
    const node = this.find(item)
    return node?.next?.value
  }

  prev(item: T): T | undefined {
    const node = this.find(item)
    return node?.prev?.value
  }
}

And the usage of this data structure looks like this:

const pages = new DoublyLinkedLoop([
  "/docs",
  "/demo",
  "/sorting/bubble-sort",
  "/sorting/selection-sort",
  "/sorting/insertion-sort",
  "/sorting/counting-sort",
  "/sorting/quick-sort",
  "/sorting/merge-sort",
  "/sorting/heap-sort",
  "/sorting/tim-sort",
  "/live",
  "/about",
])

This wouldn't be the Big O Visualizer without me explaining the time complexity of the Doubly Linked Loop. The add method, which is the only mutation method available, has a constant time complexity: O(1). All the query operations (contains, prev and next) use the find method internally, which has a worst-case linear time complexity: O(n), where n represents the amount of elements in the loop. Since I'm not building Wikipedia the amount of elements (read: pages) will always be insignificant and thus I'm happy with a linear time complexity.

Web Workerizing CPU-hungry JavaScript

Martin Devillers — Thu, 14 May 2020 04:14:47 +0000

The last few days I've been busy with the final major feature I wanted to build into the Big O Visualizer: Web Workers. Why is this relevant? Without Web Workers, all JavaScript inside the page runs on the browser's main thread. The main thread is where a browser processes user events and paints. By default, the browser uses a single thread to run all the JavaScript in your page, as well as to perform layout, reflows, and garbage collection. This means that long-running JavaScript functions can block the thread, leading to an unresponsive page and a bad user experience.

In the context of this project, that long-running JavaScript would be the algorithms that are analyzed in order to generate the data required to draw the graph. Before this change, the page would simply "lock up" and wait until JavaScript has Bubble Sorted its way through all the data. This meant the page would not respond to any clicks. Worse, navigating quickly through the site could actually crash the browser. Yuck.

So in order to circumvent this I use Web Workers to move the CPU-hungry JavaScript to the background and have the foreground wait (in a non-blocking manner) until the background threads are finished. As quoted from MDN web docs: "Web Workers are a simple means for web content to run scripts in background threads".

Personally, I wouldn't call Web Workers simple.

Simple would be if I could just slap a special keyword like background or worker on any function and it would magically run on a different thread. This is definitely not the case with Web Workers (yet). Moreover, they don't naturally play well with the (arguably exotic) stack this project uses, because:

Web Workers are created from a separate hosted JavaScript file, whereas this project uses a single generated fat artifact.
Web Workers do not inherit any of the objects from the main thread, whereas this project uses a rich module oriented model.
Communication between the main thread and the Web Workers is limited to serializable data only, meaning this projects core types Algorithm and DataSet cannot be passed along.
Web Workers come with their own overhead, which can be greater than the gain from multi-threaded execution.

In the rest of this post, I'll explain how I handled each of these issues.

Packages to the rescue

The first challenge was to get Web Workers to run in the first place. Since this project uses Babel, Webpack and a bunch of other plugins to transpile and bundle all assets into a single JavaScript artifact, there is no straightforward way to separate a piece of the code-base so it can be used by a Web Worker. Luckily, there are several npm packages that address this exact issue (and more). workerize and comlink were created with the same philosophy: make the integration of Web Workers in a JavaScript/TypeScript heavy environment straightforward. They both offer a Webpack loader workerize-loader and comlink-loader that handles the generation of the worker bundles.

Both offer an automatic way of Web Workerizing modules by renaming them from my-amazing-module.js to my-amazing-module.worker.js. Unfortunately, I couldn't get it with any of both loaders to work. workerize-loader did pick up the *.worker.ts files, but couldn't "see" the methods. After some Googling it was revealed that workerize only supports modules with functions and not classes. So I switched to comlink-loader, which supports both functions and classes. Unfortunately I couldn't autowire this package into my TypeScript set-up. In the end I ditched the automatic mode in favor of explicit mode. This also allows me to load modules side-by-side both in the regular way and in the Web Workerized way.

Workerize all the things

Another major challenge was the question: what to web workerize? Specifically: Do I workerize the analysis for the entire chart, or for each individual algorithm or even each single run per algorithm. The more granular the task, the more workers will be spawned and the more we benefit from horizontal scaling (in theory at least). Initially, I decided to workerize the analyzer, because it is the single-point-of-entry for the whole analysis. This gives each chart its own dedicated worker that will handle all the data processing for that chart. More specifically, this means that the following function will be wrapped by comlink:

export async function analyze(
  algorithms: Algorithm[],
  dataSets: DataSet[],
  sizes: number[] = logarithmics,
  scatter = false
): Promise<Analysis[]> {

One of the key features of packages like workerize or comlink is that they hide the whole Worker.postMessage and Worker.onmessage mechanism. They simply wrap the provided function and return a function with the same signature. Internally, a bespoke RPC-style implementation is used to send data in and out of the Web Worker. While this abstraction is great, it is also leaky:

Uncaught DOMException: Failed to execute 'postMessage' on 'Window': An object could not be cloned

This cryptic error message is the result of an important limitation of Web Workers: you can only pass serializable data to a Web Worker. For those unfamiliar with the term, serialization is the process whereby an object or data structure is translated into a format suitable for transferal over a network, or storage (e.g. in an array buffer or file format). Most programming languages and frameworks support one or multiple serialization techniques. In the JavaScript world, the most used (de)serializer is JSON.stringify and JSON.parse, which turns a JavaScript object into a JSON-string and vis versa.

In the above case both Algorithm and DataSet are classes that contain properties and methods, which means these objects cannot be (de)serialized without losing important parts of their model. Thus when these arguments are passed internally by comlink to the Worker.postMessage function, the browser protects us by throwing an exception.

Since there is no way around this limitation I am left with two options:

Refactor the function
Workerize something else

Since both Algorithm and DataSet are classes that are used throughout the project, I went with option 2.

Import... what exactly?

My next target for workerization would be the Algorithm.executeAndCount function.

public async executeAndCount(array: number[]): Promise<number> {

As you can see, this function's signature number[] => number consists of primitives that are suitable for serialization. In order to wrap this function, I let comlink-loader import the entire class like so:

import BubbleSortWorker from "comlink-loader!./bubble-sort"
import CountingSortWorker from "comlink-loader!./counting-sort"
import HeapSortWorker from "comlink-loader!./heap-sort"
import InsertionSortWorker from "comlink-loader!./insertion-sort"
import MergeSortWorker from "comlink-loader!./merge-sort"
import QuickSortWorker from "comlink-loader!./quick-sort"
import SelectionSortWorker from "comlink-loader!./selection-sort"
import TimSortWorker from "comlink-loader!./tim-sort"

It may not look so DRY to do this for every single algorithm, but this is necessary in order to bundle the correct algorithm with the worker. After this I expected the various imports to be functionally symmetric to the original implementation.

They were not.

This is because comlink-loader imports a factory method, that can be used to get an instance of the module, where each instance is tied to its own worker. This is actually a powerful feature, because it allows you to control how many workers you want per module. comlink-loader also has a singleton-mode, where each module is always tied to one worker. Unfortunately this mode gave transpile-time errors. In the end I rolled my own wrapper function that takes an instance of Algorithm and applies the worker behavior to the executeAndCount function, which looks like this:

export default function workerize(algorithm: Algorithm, workerFactory: () => Worker) {
  let worker: Worker
  const unworkerizedExecuteAndCount = algorithm.executeAndCount.bind(algorithm)

  const getWorkerAlgorithm = async () => {
    if (!worker) {
      worker = workerFactory()
    }
    // eslint-disable-next-line new-cap
    return new worker.default()
  }

  const workerizedExecuteAndCount = async (array: number[]) => {
    const shouldWorkerize = algorithm.timeComplexityWorst.calculate(array.length) > 1000000
    if (shouldWorkerize) {
      const workerAlgorithm = await getWorkerAlgorithm()
      const transferable = Float32Array.from(array)
      return workerAlgorithm.executeAndCount(transfer(transferable, [transferable.buffer]))
    }
    return unworkerizedExecuteAndCount(array)
  }

  algorithm.executeAndCount = workerizedExecuteAndCount

  return algorithm
}

The getWorkerAlgorithm function creates a new worker-bound module, if it doesn't already exist. It then uses this worker to create a new instance of the specific algorithm's class. This code looks a bit wonky, but that's just how comlink-loader generates wrapped classes.

The interesting thing about workerizedExecuteAndCount is that it can decide whether or not to run the current invocation on the Web Worker (background) or on the main thread (foreground). It uses the size of the array (n) and the known worst-case time complexity to calculate the expected run time of the execution. If this run time exceeds a certain threshold (in this case a million operations), the calculation is executed using a Web Worker.

Where's the gain?

After I tied this all together I expected my application to be faster.

Yes and no.

While the reported page load improved significantly (near instant), the charts actually took longer to render. I built a simple stopwatch using the User Timing API to confirm my suspicion. Load times of the charts had doubled across the project! It would seem these Web Workers are somehow slower than the regular JavaScript execution engine on the main thread. On further inspection, I found out that Web Worker's come with their own overhead, which can be significant depending on how you treat them:

Each Web Worker is essentially its own independent environment, similar to an independent browser tab. This means that creating a Web Worker takes time especially if it needs to pull resources from a server.
Transferring data in and out of the Web Worker is an expensive operation if you're sending a lot of data.
The Web Worker is simply slower than the main thread. Granted that I may be doing something dumb, there are other engineers who've observed similar behavior here, here and here.

Fortunately, the first point can be mitigated by inlining the Web Worker and the second point can be mitigated by using the Transferable interface to transfer data. You can see the Transferable API in action below on lines 5 and 6.

  const workerizedExecuteAndCount = async (array: number[]) => {
    const shouldWorkerize = algorithm.timeComplexityWorst.calculate(array.length) > 1000000
    if (shouldWorkerize) {
      const workerAlgorithm = await getWorkerAlgorithm()
      const transferable = Float32Array.from(array)
      return workerAlgorithm.executeAndCount(transfer(transferable, [transferable.buffer]))
    }
    return unworkerizedExecuteAndCount(array)
  }

First the input array is copied to a Float32Array, which supports the Transferable interface. Second, Comlink.transfer is used to transfer the data to the Web Worker. Internally, this uses the second argument in worker.postMessage(message, [transfer]). The date is quite literally lift-and-shifted from the main thread to the worker thread, which means that after this operation the data is no longer available in the main thread. Obviously, a sorting algorithm that wipes the input data is useless, but since we're only interested in measuring the run time in this project this is an acceptable side effect.

Wrapping up

Moving my CPU-hungry code to Web Workers wasn't a straightforward process, but I'm happy with the results. Can we improve further? Certainly! In the current implementation, each type of algorithm has its own thread, because this was the easiest to setup in the end. However, this doesn't align well with the required resource capacity. Since we're dealing with CPU-bound tasks, it'd make more sense to match the amount of workers with the amount of available (virtual) cores. This could be implemented in a new WorkerPool class that manages a fixed size of generic workers (navigator.hardwareConcurrency would make a good candidate for the size). The pool accepts work and uses one of the available workers to handle the work. If there are no workers available, it will wait for the next available worker.

Calvin Metcalf worded the essence of Web Workers well at the end of his article on the subject, so I'd like to close this chapter by quoting him:

The worker is not really about parallelism, that is more of a side benefit, it’s about concurrency and getting things out of the most valuable thread you have, the UI thread. A web worker isn’t about making something take 2 seconds instead of 4 seconds, it’s about doing that thing with the DOM freezing for 0 seconds.

Amen.

Launching the Big O Visualizer

Martin Devillers — Thu, 14 May 2020 02:15:54 +0000

Last month I launched the Big O(omicron) Visualizer on https://omi.cr. This tool provides a framework for analyzing the performance of algorithms by making its run time complexity visual in an appealing graph.

I came up with the idea for this project while doing a refresher on Computer Science fundamentals. A typical exercise followed the format: "Given problem statement X, implement an algorithm Y. What is the time complexity of Y? Can it be improved? If so, what is the best time complexity possible?". These questions are straightforward for simple or well-known algorithms, but when things get more exotic and there are a lot of moving parts involved, it can become quite hard to reason about an algorithm's time complexity. It was during this process that I had the thought of analyzing an algorithm's complexity by measuring its actual runtime behavior. And thus, the Big O(micron) Visualizer was born.

Being a pet-project, I picked a fresh stack of modern and exciting frameworks and technologies I wanted to familiarize myself with. The most notable technologies used in this project are React, Gatsby, TypeScript and Highcharts. This project was initialized using a popular Gatsby starter LekoArts/gatsby-starter-minimal-blog, which emphasizes typography and has minimal aesthetics. whawker/react-jsx-highcharts serves as the glue between Highcharts and React, making it easier to create charts that respond to things happening inside the website.

Feedback

If you have any questions or ideas, then please direct them at me by opening an issue on the project's GitHub repository. All feedback is welcome!

Thank you

Lennart/LekoArts for making such cool Gatsby themes
Will Hawker for making React JSX Highcharts
Kyle Jensen for making javascript-algorithms
Marco Ziccardi for making Node-TimSort and of course Tim Peters the original creator of TimSort