Making a JavaScript sort visualizer with PixiJs and async Proxies

One thing I've always wanted to build is a sort visualizer. It seems like every programmer and their mom has a 30-minute long sort visualization video on Youtube, so I decided this winter break I'd implement one.

If you're unfamiliar with the problem of sorting, or just haven't seen it in a while, I wrote a short primer you can find here.

Also, if you want, you can just skip to the satisfying, finalized beep-booping visualizer. This post describes my journey, from an abortive C++/SFML attempt to refactoring the PixiJs visualizer after realizing I sucked at organizing JavaScript code.

Lame C++/SFML implementation

When I first started dabbling in this, I chose C++. I mostly did this because I've never made a graphical app with C++ before, only ever CLI programs. Also because my monkey brain thought “C++ fast”, which is clearly a good choice for a program that deliberately slows itself down.

Those who suffer or skip through all nine minutes of that will recognize a pretty standard mergesort, quicksort and then the very, very first part of a bubble sort. You'll also hear me making lunch in the background.

Even without OBS running, these visualizations are painfully slow - all of the rendering is done using SFML's basic painting API. This means that drawing looks like this:

// main.cpp
class SortVisualizer {
  // ...
public:
  void swap(int index1, int index2) {
    // ...
    draw();
  }
  void assign(int i, T val) {
    // ...
    draw();
  }
  void draw() {
    window->clear();
    window->draw(*visualizer);
    window->display();
  }
};

Every single time the array changes due to a swap or assign call, even if it's just a single value, the screen is cleared, and every element of the array is rerendered, completely synchronously.

It sucks. The sorts themselves run in microseconds - it's the window->display() call that's hogging all the cycles. I could fix it by using sprites instead - but if I'm going to rewrite everything anyways…

Cool kid JavaScript implementation

We can do better than this. WebGL has come leaps and bounds in the past few years, and JavaScript is fast enough for a visualization.

It looks like PixiJS is the standard for 2D rendering. Let's try and get an example working:

Chaos. Very good, that was easy enough. Let's do the visualization now. It looks like the ParticleContainer used above will be ideal for painting a bunch of rectangles, based on the documentation.

Rendering Rainbow Rectangles

Alright, we'll render to a div

<div id="pixidisplay2">
</div>

And start building our script based on that example:

const app2 = new PIXI.Application();
document.getElementById('pixidisplay2').appendChild(app2.view);

Aaaand now all the boilerplate to build the visualizer

let bar_count = 100;

let bars, arr;
[bars, arr] = build_visualizer(app2);

function build_visualizer(app) {
  // Use a ParticleContainer for maximum rendering efficiency
  const visualizer = new PIXI.ParticleContainer(bar_count, {
    scale: true,
    position: true,
    rotation: false,
    uvs: false,
    alpha: false,
    tint: true,
  });
  app.stage.addChild(visualizer);
  
  // Stores the bars we visualize sorts with
  const bars = [];

  // Stores the array we're actually sorting
  const arr = [];
  
  // Create a 1x1, white pixel square template that we can transform to make our visualization bars
  let graphics = new PIXI.Graphics();
  graphics.beginFill(0xFFFFFF);
  graphics.drawRect(0, 0, 1, 1);
  graphics.endFill();
  var template = app.renderer.generateTexture(graphics);

  // Build all of our bars
  for(let i = 0; i < bar_count; i++) {
    arr.push(i);

    const bar = PIXI.Sprite.from(template);
    setBar(bar, i, app);

    bar.x = (i / bar_count) * app.screen.width;
    bar.y = 0;

    bars.push(bar);

    visualizer.addChild(bar);
  }

  return [bars, arr];
}

Lastly, we need our helper functions:

// Convert HSL to RGB so we get pretty pretty rainbow colors from a linear space.
function hslToHex(h, s, l) {
  h /= 360;
  s /= 100;
  l /= 100;
  let r, g, b;
  if (s === 0) {
    r = g = b = l; // achromatic
  } else {
    const hue2rgb = (p, q, t) => {
      if (t < 0) t += 1;
      if (t > 1) t -= 1;
      if (t < 1 / 6) return p + (q - p) * 6 * t;
      if (t < 1 / 2) return q;
      if (t < 2 / 3) return p + (q - p) * (2 / 3 - t) * 6;
      return p;
    };
    const q = l < 0.5 ? l * (1 + s) : l + s - l * s;
    const p = 2 * l - q;
    r = hue2rgb(p, q, h + 1 / 3);
    g = hue2rgb(p, q, h);
    b = hue2rgb(p, q, h - 1 / 3);
  }
  const toHex = x => {
    const hex = Math.round(x * 255).toString(16);
    return hex.length === 1 ? '0' + hex : hex;
  };
  return `0x${toHex(r)}${toHex(g)}${toHex(b)}`;
}

// Changes the appearance of a bar (height and color) based on value
function setBar(bar, val, app) {
  bar.tint = hslToHex(360 * val / bar_count, 100.0, 50.0);
  bar.scale.y = (val + 1) * (app.screen.height / bar_count);
  bar.scale.x = app.screen.width / bar_count;
}

Rainbow Pyramid Sort Visualizer

There we go. That's just an image of the result, but it doesn't actually do anything, so I figured there was no point in blasting your GPU with more WebGL contexts.

Alright, now let's actually make it do something.

Visualizing Sorts: First Pass

First we'll need to make swap and assign functions that add delays on array modification. This is needed because bare array accesses arr[i] are effectively instantaneous for visualization purposes, and without a short time delay, the visualizer will appear to just instantly self-sort.

async function swap(pos1, pos2) {
  let tempVal = arr[pos1];
  let tempBar = bars[pos1];
  arr[pos1] = arr[pos2];
  setBar(bars[pos1], arr[pos1], app2);
  arr[pos2] = tempVal;
  setBar(bars[pos2], arr[pos2], app2);
  // Wait 1ms on swap
  await timeout(1);
}

async function assign(i, val) {
  arr[i] = val;
  setBar(bars[i], val, app2);
  // Wait 1ms on write
  await timeout(1);
}

function timeout(ms) {
  return new Promise(resolve => setTimeout(resolve, ms));
}

Notice we only delay on writes; we can implement read delays later.

Alright, now it's just sorting algorithm… After sorting algorithm… After sorting algorithm. I'm not going to show all of them, if you're really curious you can view page source or look up a sort.

// Randomly shuffles an array
async function svShuffle() {
  for(let i = 0; i < arr.length; i++) {
    await swap(i, Math.floor(Math.random() * (arr.length - i)) + i);
  }
}

// Classic O(n^2) sort
async function svSelectionSort() {
  for(let i = 0; i < arr.length; i++) {
    let max = Number.MAX_VALUE;
    let max_i = -1;
    for(let j = i; j < arr.length; j++) {
      if(await lv(j, max)) {
        max = await svRead(j);
        max_i = j;
      }
    }
    await svSwap(i, max_i);
  }
}

// Classic O(n log n) sort
async function svMergeSort(start, end) {
  if(end - start <= 1) {
    return Promise.resolve();
  }
  let mid = start + Math.floor((end - start) / 2);
  await Promise.all([
    svMergeSort(start, mid),
    svMergeSort(mid, end),
  ]);
  let work = await svMerge(start, mid, end);
  for(let i = 0; i < work.length; i++) {
    await assign(start + i, work[i]);
  }
}

async function svMerge(start, mid, end) {
  let i = start;
  let j = mid;
  let work = [];
  while(i < mid && j < end) {
    if(arr[i] <= arr[j]) {
      work.push(arr[i]);
      i++;
    }
    else {
      work.push(arr[j]);
      j++;
    }
  }
  while(i < mid) {
    work.push(arr[i]);
    i++;
  }
  while(j < end) {
    work.push(arr[j]);
    j++;
  }
  return work;
}

Notice all of the asyncing and awaiting. I'm not a huge fan of all of this cluttering up the algorithm, but it's necessary to ensure the visualization occurs alongside the running of the algorithm (as Pixi.js is running in the same thread as far as I'm aware).

Here's the result. There's no sound, we're lacking a few features, and because our array operation delay can't be changed, O(n log n) sorts like MergeSort and QuickSort go too fast while O(n^2) sorts take forever. But, spaghetti code that works is better than no code at all.

This code could be better; global vars and functions are sprayed all over the place and there are side effects galore. You can actually crash your JS interpreter if you mash the buttons on that visualizer because there's so much unpredictable behaviour from all the unregulated async functions running at once.

Refactoring Time

Bad programmers write bad code. Good programmers also write bad code, but they go back and make it good. Let's do that.

Pass 1: ES6 Classes

I figured I could cleanly encapsulate all of my code using ES6 classes. So, I blindly ran through this program and converted everything to class members and fields. I realized about halfway through refactoring that I wasn't getting any benefit from using classes. Quite the opposite, I was just making my code more verbose by slapping this in front of every function call and variable access. Also because of how weird the this keyword is in JS, I got tangled up using .call() recursively before I realized I was going about this the wrong way:

async function svMergeSort(start, end) {
  if(end - start <= 1) {
    return Promise.resolve();
  }
  let mid = start + Math.floor((end - start) / 2);
  await svMergeSort.call(this, start, mid);
  await svMergeSort.call(this, mid, end);
  let work = await merge.call(this, start, mid, end);
  for(let i = 0; i < work.length; i++) {
    await this.assign(start + i, work[i]);
  }
}

My brain doesn't immediately recognize that as a MergeSort because it's so… Weird. The Software Engineer in me is yelling at the Programmer in me that made this shitty interface.

JavaScript is an extremely flexible language. It reminds me of Lua, or Perl, in that regard. There are a lot of ways to do things, none of them are particularly right, just some of them just suck less than others. ES6 classes feel a bit like an afterthought, compared to real OOP languages. Classes have two purposes in classical OOP: hiding complexity and grouping functions with the data they operate on. ES6 classes do the latter but not the former, and they do the latter very verbosely.

So, let's step back. What am I trying to achieve?

  1. I want to visualize sorts
  2. So, what I really want to be able to do is have a view that updates efficiently whenever a sort changes an underlying model. This is Model-View-whatever architecture. Whenever I write a sort, it shouldn't care that it's being visualized; it's just operating on an array.
  3. But I don't want to use an MV* library because this is a one-off project. And also because I feel like there's an elegant way to do this with vanilla JS.
  4. I'd like this to be succinctly packaged up, even though I'm not going to reuse it, out of good practice.

Pass 2: Object Constructors and Proxies

After a bit of reading, I came to the following conclusions:

  1. I can use Proxies to wrap an Array, which effectively lets me do operator overloads with it. This has terrible performance, but again, we don't care because we're deliberately slowing these algorithms down anyways.
  2. I can effectively achieve private members in JS by not using classes, and instead abusing taking advantage of closures and objects. Thank you Douglas Crockford for writing about this. It feels wrong notationally, but, y'know, when in Rome.
  3. Combining these two approaches into a SortVisualizer “class”, I can Proxy my private arr as a property, and add implicit calls to the visualizer (like manipulating bars and playing/pitching sounds) in the getter, as well as adding the per-operation delay with timeout.

Anyways, all of this is equivalent to a Factory function with operator overloads in C++. The leap to JavaScript has been strange and entertaining.

Let's look at the code. All of the visualizer is wrapped up in one big constructor now, equivalent to a class in OOP languages:

function SortVisualizer(parent) {
  // Private variables
  var bar_count = 1000;
  const minFreq = 440;
  const maxFreq = 2000;
  var write_delay = 0.2;
  var read_delay = 0.1;

  // Graphics initialization (PIXI)
  const app = new PIXI.Application({ resizeTo: document.getElementById(parent) });
  document.getElementById(parent).appendChild(app.view);

  const visualizer = new PIXI.ParticleContainer(bar_count, {
    scale: true,
    position: true,
    rotation: false,
    uvs: false,
    alpha: false,
    tint: true,
  });
  app.stage.addChild(visualizer);
  
  const bars = [];
  const arr = [];
  
  const graphics = new PIXI.Graphics();
  graphics.beginFill(0xFFFFFF);
  graphics.drawRect(0, 0, 1, 1);
  graphics.endFill();
  const template = app.renderer.generateTexture(graphics);

  for(let i = 0; i < bar_count; i++) {
    const bar = PIXI.Sprite.from(template);
    setBar(bar, i, app);

    bar.x = (i / bar_count) * app.screen.width;
    // bar.y = app.screen.height * 0.5 - bar.scale.y * 0.5;
    bar.y = 0;

    arr.push(i);
    bars.push(bar);
    visualizer.addChild(bar);
  }

A lot of this is similar to the build_visualizer function we created before, however, all of the variables being defined here are private! This is because, due to closures, they can only be accessed from other functions defined within the constructor. They are outside of scope beyond the constructor. Clever and cool.

Here, I added beep-booping noises using JavaScript's built-in audio controller, with an oscillator to generate pure sine waves.

  // Audio initialization
  var audioCtx = new (window.AudioContext || window.webkitAudioContext)();
  var oscillator = audioCtx.createOscillator();
  oscillator.type = 'sine';
  oscillator.frequency.setValueAtTime(440, audioCtx.currentTime); // value in hertz
  var gain = audioCtx.createGain();
  gain.gain.setValueAtTime(0.4, audioCtx.currentTime);
  oscillator.connect(gain);
  gain.connect(audioCtx.destination);
  oscillator.start();
  audioCtx.suspend();

Defining functions using the function name() {}; syntax are equivalent to var name = function() {}. Like the private variables we defined above, defining a function within a constructor makes them private.

  // Private functions (privileged call private access)
  function playBoop() {
    audioCtx.resume();
  };
  function pauseBoop() {
    audioCtx.suspend();
  };
  function pitchBoop(val) {
    oscillator.frequency.setValueAtTime((val / bar_count) * (maxFreq - minFreq) + minFreq, audioCtx.currentTime);
  };
  function setBar(bar, val) {
    bar.tint = hslToHex(360 * val / bar_count, 100.0, 50.0);
    bar.scale.y = (val + 1) * (app.screen.height / bar_count);
    bar.scale.x = app.screen.width / bar_count;
  }

Here we define out privileged functions; instead of being defined with var name = function() {};, they are defined as this.name = function() {};. This makes them accessible as an object property, while still giving them access to private vars (and functions). This is equivalent to a public function in C++.

  // Privileged Functions ( public call private access )
  this.setOperationDelay = function () {
    write_delay = document.getElementById("write-delay").value;
    read_delay = document.getElementById("read-delay").value;
  };
  this.runAlgo = async function(sort) {
    this.setOperationDelay();
    playBoop();
    await sort(this.arr);
    pauseBoop();
  };
  this.reset = async function() {
      write_delay = 0;
      read_delay = 0;
      await timeout(100); // Give the sort time to complete
      for(let i = 0; i < arr.length; i++) {
       await (this.arr[i] = i);
      }
  }

Lastly, let's look at our Proxy'd array. Proxies intercept accesses to an Object, in this case an array. We intercept function calls with the apply handler, we intercept array assignments arr[i] = val with the set handler, and array accesses arr[i] with the get handler. Notice that both get and set are asynchronous, allowing us to implement both read and write delays.

Note that this Proxy isn't particularly performant; each set is in reality a property access, which tends to be slow in JS. As a result, this technique shouldn't be used in high-performance code, but works fine for stuff like this.

  this.arr = new Proxy(arr, {
    // Trap for any function calls
    apply: function(target, thisArg, argumentsList) {
      return thisArg[target].apply(this, argumentList);
    },
    // Trap for arr[i] = thing
    set: function(target, property, value, receiver) {
      return new Promise((resolve, reject) => {
        pitchBoop(value);
        target[property] = value;
        setBar(bars[property], value);
        timeout(read_delay).then(() => {
          resolve(true);
        });
      })
    },
    // Trap for arr[i]
    get: function(target, property, receiver) {
      if(property == 'length')
        return target.length;
      else {
        return new Promise((resolve, reject) => {
          pitchBoop(target[property]);
          timeout(read_delay).then(() => {
            resolve(target[property]);
          });
        });
      }
    },
  });
}

And there is a benefit to doing things this way: we can write sorts in a separate module, using nearly-vanilla JavaScript array access syntax:

async function mergeSort(arr, start, end) {
  if(arguments.length == 1) {
    await mergeSort(arr, 0, arr.length);
  }
  else {
    if(end - start <= 1) {
      return Promise.resolve();
    }
    let mid = start + Math.floor((end - start) / 2);
    //await Promise.all([
    await mergeSort(arr, start, mid);
    await mergeSort(arr, mid, end);
    //]);
    let work = await merge(arr, start, mid, end);
    for(let i = 0; i < work.length; i++) {
      await (arr[start + i] = work[i]);
    }
  }
}

The only part of the interface that has been exposed is the asynchronous nature of the array accesses.

Alright, now I'm satisfied. There's a bit of JavaScript weirdness going on, but this code is well-organized, reusable and many bugs have been eliminated.

Read Delay (ms):
Write Delay (ms):

Sorts, visualized! Feel free to play around with the buttons and see what happens. I recommend shuffling before sorting.

Conclusion

This started off as a fun first post for a technical project and actually ended up being really educational with regards to organizing JavaScript. I feel like I have a much better idea of how to avoid terrible frontend spaghetti code, which I'm sure will be valuable for future projects, both commerical and personal.

One thing I entertained is making the API for the SortVisualizer completely synchronous, eliminating the awaits in the sort implementations. This would make them completely indistinguishable form their canonical implementations, which sounds, for lack of a better word, sexy.

This could be done by running all the visualization in the primary UI loop, and running sorts in a separate thread with web workers. I ended up sticking with the async/await because JavaScript has no buit-in sleep function. The closest thing is to just while loop until you eat enough cycles to reach your desired sleep time, and that felt super wrong.

I may try this in the future, but for now, enjoy asynchronous booping.

My next post will probably be about either stupid-efficient realtime raymarching, the wavefunction collapse method of procedural tiling, or about my experience with the international genetically engineered machine competition.