Making a font picker

A long while ago when building the Pinecast site builder, I came had a need for a dropdown that allows the user to choose a font from Google Fonts. Most font pickers in other applications show each typeface off by rendering its own name. While apps like Google Docs and others only display a handful of fonts to choose from, the Site Builder required the display of over a thousand fonts. This introduced a rather unique and complicated set of challenges.

Fonts on Google Fonts are served as WOFF2 (or WOFF, or another format if your browser is older). Using these directly is a poor option for a dropdown because opening the dropdown would trigger thousands of downloads of hundreds of megabytes of font files from Google. Triggering the download when the font is to actually be displayed would make scrolling laggy and cause flashes of unrendered fonts.

Instead, I decided to pre-render each font. By doing this, an easily-renderable preview could be stored in my JavaScript and drawn to the screen immediately.

I started the project by building a compiler. This compiler downloads the full list of fonts from the Google Fonts API. It filters out poor candidates for fonts to include (like barcodes) and creates data structures to store metadata. Each font’s TTF file is saved to /tmp and passed to opentype.js to be rendered as an SVG. Each SVG’s path (that is, the vector path, not the file path) is saved as a string to render with React later.

This required a good deal of tinkering. Each TTF file is loaded as a Buffer into memory, and the resulting SVG path can be dozens of kilobytes. If done concurrently, Node easily hits out-of-memory errors. I didn’t solve this problem properly (e.g., with a semaphore), but instead used a write stream to dump each line of the rendered font paths to the disk early, allowing the garbage collector to clean up each font file and path as it’s rendered.

The font picker using the pre-rendered font paths

This produced the results that I wanted, but a new challenge emerged. The resulting TypeScript file was enormous. After gzip, the file was megabytes large. Even if I discarded all fonts that take more than 14KB as an SVG path, the resulting bundle was three megabytes larger than it was before.

An argument could be made for slow load times in such a complex application and loading indicators (like spinners or dancing dots) could be used to mitigate the delay in loading the JavaScript bundle. This isn’t satisfying, though, and as Google adds new fonts, the problem will only get worse.

Code splitting to the rescue

A quick way to stop the bleeding is to load the font data separately from the main JavaScript bundle. There are a few obvious approaches. The most naive is to download the font data as a JSON file with fetch. This makes it simple to load the font when it’s needed, but there’s a lot of boilerplate involved and it doesn’t play well with the build system.

The other answer is to lean on Webpack to do the heavy lifting for us. This technique is known as code splitting.

Code splitting is a way of instructing Webpack to generate a second (or third, or fourth…) JavaScript bundle containing a chunk of your application. You can then load that chunk after the initial bundle has loaded.

I won’t go into details about how to do code splitting with Webpack, as there are many articles out there that go into great detail. The long and short of it is that you load the bulky JavaScript file after the rest of the page, letting your application load sooner and only blocking rendering of your UI on the download when the UI is rendered before the JavaScript chunk has loaded.

Once my font previews were stored in their own file the performance issues are only a problem if you open the font picker. Many users won’t open a font picker, so the problem is mostly mitigated. That said, we still don’t want it to take ten or fifteen seconds for your fonts to load when the font picker is first opened.

Thinking about compression

Size is still a problem. The bundle containing the font path data is over three megabytes on its own. There’s got to be a better way.

I suspected that there was a way to encode SVG paths such that the consume less space. SVG paths are letters (“commands”) followed by zero or more decimal numbers (“parameters”). I speculated that a binary encoding would be far more efficient than a text-based one. It’s hard to say whether it would yield any benefit with back-of-the-napkin math:

• If we encode the binary data with ascii85 (since binary data can’t be encoded directly in a JavaScript file), it would add ~25% overhead.
• Many SVG path commands have two floating point numbers. With 64 bit floats, that’s 16 bytes for every command with two parameters, though we can use 32-bit floating point numbers to save 8 bytes. Pairs like 0 0 will be far shorter than eight bytes when stored as a string, but pairs like -12.12 15.67 save a few bytes with a binary encoding.
• The more floating point parameters per path command, the more likely it is that bits will be saved (since there are more opportunities for wasted bits in a string encoding). The distribution of commands will play a large part in determining the size.

Let’s test!

A naive pass

The first and simplest test was to just create a binary encoding of SVG paths. I used the parse-svg module to parse the SVG paths into JavaScript arrays of arrays that transforms M1.8 0.2L0.2 -0.5 to look like [['M', 1.8, 0.2], ['L', 0.2, -0.5], ...], and then packed that into an ArrayBuffer composed of three parts:

• A 32-bit uint header listing the number of path commands
• A Uint8Array containing commands (the SVG term for the letters in the SVG path) that map to each character used in the paths
• A Float32Array containing each of the parameters for each path command

For each command type, there is a fixed number of parameters. M will always have two parameters, for instance. Based on the Uint8Array, we can intuit how many numbers to read from the Float32Array.

There’s a lot of waste here. First, 8 bits for the commands is a big waste: there are only about 20 commands defined by the SVG spec, which means that three bits are wasted per command. Next, 32 bits per parameter is FAR more than are needed. The path command M0 0 takes only four bytes to encode as a string, but we’re consuming nine bytes to encode it in our binary format.

I wrote a tiny script to automate the testing of my attempts, and the naive attempt produced this output:

Bytes saved: -721494
Ratio: 1.2097567163545102
Gzip ratio: 1.4426273810518684

Compared to the gzipped version of the original file, my naive attempt produced output that’s 40% bigger!

Packing the commands

My next pass was to start packing the data more tightly. The most obvious first step is packing the commands into five bits to represent each of the 20 possibilities.

I wrote an implementation of what I call UintNArray that takes a length and a number of bits per uint. It behaves just like a Uint8Array, except it truncates values to N bits instead of 8.

Using this to pack the commands instead of a Uint8Array, I was able to save a few bytes:

Bytes saved: -580885
Ratio: 1.1688470197477028
Gzip ratio: 1.4499228881612436

The total bytes saved was improved quite a bit! We saved about 150kb versus the previous attempt. Unfortunately, the gzipped file size increased pretty substantially.

This happens because the path commands often repeat. A given SVG path might contain the commands MLLLQLLQLLQLL, repeating subsets of that string over the the whole path. When each path command consumes exactly one byte, the repetition is present in the output. When the binary-encoded versions are not byte-aligned, there is far less repetition in the output. To gzip, this looks like random noise. By packing the data in more tightly, we’ve made it less compressible!

I picked at this a bit and found that opentype.js only ever uses four different commands: M, L, Q, and Z. That means we can fit each command in only two bits, and no command will ever cross bytes (since 8 is a multiple of 2), so gzip should be much more comfortable with the whole process.

Reducing the number of bits from 5 to 2 helped a bit, but not a huge amount:

Bytes saved: -440311
Ratio: 1.1279486700544477
Gzip ratio: 1.443929762564997

The new output is only 12% bigger than the original output, but we’re still 44% bigger in the gzipped output, though better than before.

Packing the parameters

I’ve left a huge chunk of low-hanging fruit on the tree here: the parameters. Four bytes per parameter is far more than needed. I first considered just halving that and crafting 16-bit floating point numbers, but that’s still very wasteful. Floating point numbers are interesting in that they go from -Infinity to +Infinity, with 50% of exactly-representable numbers between -1 and +1. This is wasteful because we can safely truncate the decimal values for our numbers to a small number of significant digits (most folks truncate their SVGs to 1–3 decimal places of precision). We definitely don’t need as many decimal places of precision as floating point numbers provide: if we truncate to two decimal places and 50% of all floating point numbers are between -1 and 1, that means that we’re wasting almost half of our 32 bits to store about 20 possible values: -0.9, -0.8, … 0.8, 0.9.

Floating point numbers are a bad representation here. A simple change would be to use integers and just divide by 10. With 8-bit signed integers, this would allow -12.7 to 12.7. Sadly, this isn’t nearly enough, with the actual parameter values ranging into the hundreds.

One interesting property of these numbers is that there are a few values which appear in all of the SVGs many thousands of times, and a thousand or so numbers that are used fewer than ten times. Three hundred values are used exactly once.

I tallied up the number of occurrences of each numeric value across all fonts. I imported this data in CSV format into a spreadsheet and plotted it out. This was done per path command type, which I’ll discuss in a minute.

These are frequencies for the “M” path command type. The chart is truncated to show the top 10% of numeric values.

You can see here the zero is the most popular number for the M path command type, followed by 0.2, 0.3, and 0.1. Zero, in this case, is seen 660 times. Q and L each have much more dramatic numbers, having thousands of instances of 0 and 0.2.

One solution here is to use Huffman coding. Huffman coding is a process by which the most common symbols in a sequence are given the shortest representation, while the least common symbols in the sequence are given much longer representations. This allows the very common values to be encoded with far fewer bits.

This process treats each numeric value in our SVGs as a symbol. It doesn’t matter how precise the value is or even what the value is; what matters is the cardinality of our set of parameter values. A zero, for instance, could be encoded as three bits. 234.5, which appears only once, might consume fifteen bits or more.

Implementing this was challenging. There is no generic Huffman coding library available online that will not just generate the bit representation, but also the packed set of bits (compatible with, say, an ArrayBuffer). I adapted some code from the huffman_js library on Github to create an implementation that accepts arbitrary symbols (rather than characters) to build the tree used to formulate a Huffman code.

My initial attempt built a single Huffman tree for all numeric values in all commands in all paths. Applied on top of the previous attempt, we get these results:

Bytes saved: 2180514
Ratio: 0.3654320060935835
Gzip ratio: 1.0707779233309709

Wow! That’s quite good (2MB saved!), considering the paths are — at this point — losslessly encoded. We also haven’t really spent much time optimizing things.

What’s concerning is the gzip ratio. It’s still >1, which means the result will still take longer to load despite our valiant efforts. It’s 7% larger, which isn’t reassuring, but that’s pretty decent considering ascii85 is adding overhead.

Lossiness

So far my efforts have focused on lossless operations. This means encoding such that no information is lost: the output of the whole process is identical to the input. The opposite of lossless encoding is lossy encoding. This is when you discard information and decrease the output quality to save space, like in a JPEG image.

The first thing at the top of my mind is reducing the precision of “large” numeric values. The difference between 0.2 and 0.3 can be substantial, especially if repeated hundreds of times. The difference between 141.1 and 141.5, though, is almost undetectable.

I came up with some entirely arbitrary thresholds for how far to round. Here’s what I used:

function lossify(value) {
  if (Math.abs(value) > 70) {
    return Math.round(value / 4) * 4;
  }
  if (Math.abs(value) > 40) {
    return Math.round(value / 3) * 3;
  }
  if (Math.abs(value) > 20) {
    return Math.round(value / 2) * 2;
  }
  if (Math.abs(value) > 10) {
    return Math.round(value);
  }
  return value;
}

Basically, the further from zero a number gets, the lossier it gets. Imagine a number line: we want the values that we plot on the number line to “snap” to pre-defined values. But the further away from zero on the number line you get in either direction, the further away these snap-points are spaced. Near zero, the numbers don’t snap very far. Further away from zero, the numbers snap further away in either direction.

The idea here is that rounding numbers off reduces the cardinality of the set of encoded numeric values, which should reduce the number of symbols being encoded, which should reduce the length of the values produced by the Huffman coding.

You might be curious how this affects the rendered output. The answer is that it’s visually imperceptible, at least to me.

Let’s look at how that affected our output:

Bytes saved: 2452764
Ratio: 0.2933209157366562
Gzip ratio: 0.8354983617125883

Excellent! We’ve gotten to a point where our gzipped output is smaller than the original gzipped file, by about 16%.

Another lossy technique that I investigated is the use of path simplification. I created a test implementation using the fabulous Paper.js library’s path simplification algorithm, but I found that the results, when rendered, were not good. Fonts have too many tiny details to be put through an existing simplification algorithm. There is perhaps a way to specialize one of those algorithms for use with fonts, but that’s a job for someone far smarter than I am.

More Huffman coding

I’d originally hypothesized that using three separate Huffman trees (one for each type of path command) would yield better results. Common numeric values for each command type would (theoretically) be associated with smaller strings of bits. If 0.2 is more common than 0 for a type, 0.2 would get a smaller string.

I tested this. I created an implementation of my Huffman coding library which allows you to specify the tree to use to encode and decode the next symbol. The results were not good.

Bytes saved: 2453094
Ratio: 0.29434068322385015
Gzip ratio: 0.8449959788970782

Notice that the number of bytes saved is greater than the previous result, but the ratio is worse. This is because each individual path took less space (by a handful of bytes) but the total file size was larger because it needs to store the extra two Huffman codes.

I then got another idea: we’re storing the commands as two bits each in our UintNArray, but some commands appear far more frequently than others. Instead of simply packing those bits in, we could create a Huffman code for those as well!

Bytes saved: 2479326
Ratio: 0.2862957215153192
Gzip ratio: 0.8343815695650806

The results here are an improvement, but not a big one. Only one of the commands ends up being one bit (granted, it appears very often), and the least common ones end up becoming three bits. It’s a net win overall, but when you only have a few hundred (or a few dozen) commands per path, it’s not a lot of bits total. In our case, it was about 20,000 total (with 1,000 fonts, that’s about what I’d expect).

My next thought is to store sequences of commands in a unit rather than treating each command as its own symbol. Here are the commands from the font Acme:

MLLLLLLLLLLZMLLLLZMLLQLLQLLQLLQLLQLLQLLLLQLLQLLQLLQLLQLLQLLQLLQLLQLLQLLQLLLQZMLQLLQLLQLLLLLLQLLLQLLQLLQLLQLLQLLQLLQLLQLLQLLLLLLQLLQLLQLLLLLZMLLQLLQLLLLQLLQLLQLLQLLQLLQLLQLLQLLQLLQLLQLLLLQZMLLQLLQLLLQLLQZ

I’ve highlighted all of the M and Z commands to make it easier to grok. A few interesting things to point out:

• Each “piece” of a glyph starts with an M and is followed by L and Q, until a Z is reached.
• Q and M are almost always followed by one or more Ls.
• The sequences of [MQ]L+ repeat very often.

I decided to create symbols by matching each string of commands with the regular expression/([MQ]L*|Z)/g, rather than treating each command as a symbol. It only took a bit of futzing to get the Huffman coding implementation to play nicely, and the results are not bad:

Bytes saved: 2513864
Ratio: 0.2758463779197209
Gzip ratio: 0.8172053280427702

Continuing to make good progress, another few percent off the gzipped bundle.

I played around with the regular expression, trying difference combinations that could improve the rate of compression. Some attempts:

• Limiting the number of consecutive Ls. Large numbers of consecutive L commands after an M or Q could lead to infrequently used symbols, while two shorter symbols (e.g., MLLLL and LLLL versus MLLLLLLLL) could be used more frequently. This had a negative impact.
• Matching QZ as its own symbol.
• Matching consecutive Q commands. This had no effect.

I settled on /(QZ|[MQ]L*|Z)/ since it seemingly produces the best results:

Bytes saved: 2515364
Ratio: 0.27538726434060756
Gzip ratio: 0.8158475953153337

Other potential ways to compress

The above outcome is where I stopped. But that’s not to say I have any shortage of additional ideas! Some things I’d like to try in the future when I have more time:

• M, Q, and L accept pairs of parameters (Q accepts two pairs). It would be interesting to explore whether the pairs could be treated as their own symbols to save space.
• Perhaps in combination with the previous idea, SVG commands that use capital letters use absolute coordinates. There are lowercase variants that use relative coordinates. When using relative coordinates, the values are likely to be smaller. It’s likely that if there are more small values, the cardinality of parameter values can be decreased. It would be an adventure to convert from absolute to relative coordinates, but it could yield a substantial win.
• I have not looked, but I suspect svgomg has some kind of lossless path simplification algorithm built-in. It would be interesting to explore whether it does, and if so, how it works. A lossless simplification algorithm would not be hard to drop into the code as-is.
• In the same vein as path simplification, sequences of L commands can likely be simplified pretty easily. L draws a line from the current cursor position to the point defined by the parameters. Some intermediate lines might be outright removable if the angle that two lines create has an angle close enough to 180°.

Implementation

Having the compressed versions of these fonts is great. Decoding them is not expensive to do in the browser, either, despite the memory use. I was not able to measure any notable pause when performing the decoding process.

The implementation of the font picker has very little magic: it’s a simple custom dropdown using react-list to minimize the number of nodes on the page at a time.

The main JavaScript bundle knows the list of fonts, so it is able to render one item in the dropdown per font family (falling back on a default typeface showing the name while the SVG paths load). The SVG paths and a component to render them are loaded with React.lazy. The component simply accepts the name of the font family as a prop.

The result is a smooth-scrolling dropdown of font family names rendered in their own typeface as a vector, with a reasonably small file size footprint. That’s not too bad!

Finishing up

This was a lot of work, but I learned a lot along the way. In the end I only saved about 18% off the final gzipped bundle size, though. That’s a bit of a tough pill to swallow. Gzip, as it turns out, is incredibly good at compressing content with repetition. And that’s not a bad thing! I didn’t measure it, but I’d be unsurprised if Brotli did an even more impressive job of compressing the data. Even if the ratio for Brotli is very close to 1, the resulting bundle is still very small.

Naturally, we must ask ourselves if the tradeoff between compute time (in this case, decoding time) and storage (in this case, bandwidth used). In this case, the compute time is insignificant enough that even if we did 10x the work, the tradeoff would still be worthwhile.

What is the real-world impact here? Well, the bundle size varies between deploys. Right now, the chunk containing the font data is sitting around 950kb gzipped. That means that the original gzipped size would be about 1.12mb, which we can round up to say is just about a quarter of a megabyte difference. That’s not insubstantial! For a user on a slow connection, that quarter of a megabyte can be a few seconds.

When I was doing this work, I had Dropbox’s Lepton image compressor in mind. Lepton works by applying lossless compression to JPEGs in a way that gzip on its own cannot. Gzip, despite being quite good, has no knowledge of what’s actually inside a JPEG. Lepton instead uses techniques specific to how a JPEG is encoded, unlocking the ability to save bytes that a naive compression algorithm can’t save on its own.

Now, of course, the purpose here is very different: Dropbox wants to save storage space on their servers, while Pinecast wants to reduce the number of bytes sent over the wire to customers’ browsers. The cost/time/resource tradeoffs are very different, but the underlying technical principles are very similar. And in terms of outcomes, it’s encouraging to see that Dropbox achieved ~22% compression, while I achieved an additional ~18% compression.

Overall, I’m happy with the outcome here. 18% isn’t the absolute best outcome I can hope for, but the uncompressed output is still almost 73% smaller, which is pretty cool as a purely academic exercise. I’ll probably revisit this work at some point to see if I can’t squeeze more bytes out. If you have ideas or suggestions, please don’t hesitate to get in touch.

Thanks also to Jeff Sarnat for poking me on Twitter and reminding me that I never finished this blog post. Polishing this up and getting it out the door was something I totally forgot to do!