Category: Optimization

For the next JS13k game jam I want to use some cute pixel fonts. I have always liked them and the retro aura they bring. From previous experience I know when game jam time comes in, the one thing you don’t have is time. Therefore, in an effort to be ready for it, I went ahead and did some of research ahead of time. I wanted to implement something that would work for the canvas renderer of my ECS architecture.

As with all things 13k, the issue is always size. Using a standard TTF or WOFF2 fonts is basically a no-go. The font just takes too much of the available KBs.

People are crafty though and have come up with a clever way of creating low overhead fonts. The original version I believe is PixelFont. The gist of it is letters are stored as an array of pixels:

The idea

Initially I thought “if data is store as 0 and 1, it can also be expressed as a binary number”. Therefore, the A written as (see explanation in the PixelFont repository):

var A = [
    [, 1],
    [1, , 1],
    [1, , 1],
    [1, 1, 1],
    [1, , 1]
];

Can also be expressed as: (keep in mind, the zeroes were removed in the above snippet to save bytes)

var A = [
    [ 0, 1, 0 ],
    [ 1, 0, 1 ],
    [ 1, 0, 1 ],
    [ 1, 1, 1 ],
    [ 1, 0, 1 ]
];

Which can be further distilled into (saving trailing zeroes, array brackets, and commas):

var A = [
    2, // 0 1 0
    5, // 1 0 1
    5, // 1 0 1
    7, // 1 1 1
    5  // 1 0 1
];

Shoot … we might as well go all in:

var A = 11133; // 010 101 101 111 101

Somebody more clever than me came up with the even better approach of storing these as unicode characters. The letter A becomes var a = "㹏"; … And that is the follow up to PixelFont: TinyFont self-touted as the “Tiniest possible pixel font for your JS games“. Nice!

Note: Storing unicode characters takes 1-4 bytes. So just because you see one character on the screen it doesn’t mean the file size will be 1 byte. Example: the character 㹏 uses 3 bytes. Numbers use one byte. Storing “892” would also be 3 bytes.

The problem

When looking at the code for TinyFont I realized that while the font was super light, the rendering of it wasn’t all that fast. It is good enough for loading screens or games that don’t change frames all that often. But if you need 60 fps with animated text, render speed could be an issue.

I ran a test writing the first paragraph of “Lorem Ipsum” to get a better sense of speed. One word or a couple of letters would render fast enough regardless of the algorithm.

Here’s the meat of the original renderer:

const renderChar = (charX, char) => {
	const pixelSize = size/height;
	const fontCode = chars[char.charCodeAt()] || '';
	const binaryChar = isNumber(fontCode) ? fontCode : fontCode.codePointAt();

	const binary = (binaryChar || 0).toString(2);

	const width = Math.ceil(binary.length / height);
	const marginX = charX + pixelSize;
	const formattedBinary = binary.padStart(width * height, 0);
	const binaryCols = bin2arr(formattedBinary, height);

	binaryCols.map((column, colPos) =>
		[...column].map((pixel, pixPos) => {
			ctx.fillStyle = !+pixel ? 'transparent' : color; // pixel == 0 ?
			ctx.fillRect(x + marginX + colPos * pixelSize, y + pixPos * pixelSize, pixelSize, pixelSize);
		})
	);

	return charX + (width+1)*pixelSize
};

[...string].reduce(renderChar, 0);

After 200 runs it would average 1.2315 milliseconds to finish the job. Not too bad at first sight. But you only have 16ms to do all the work for a frame, the text alone took around 7.5% of the time. To me that’s unacceptable.

There are some things here I immediately don’t like. Painting transparent blocks can’t be any good, map on spread on map, the binary.padStart() call seems suspect, etc.

I refactored that whole renderChar function into using binary numbers directly and bitwise operations to do the traversing:

const pixelSize = size / height;
const renderChar = (charX, char) => {
	const fontCode = chars[char.charCodeAt()] || '';
	let bin = Number.isInteger( fontCode ) ? fontCode : fontCode.codePointAt();
	const binary = ( bin || 0 ).toString( 2 );
	const width = Math.ceil( binary.length / height );

	ctx.fillStyle = color;
	for ( let col = width; col > 0; col-- ) {
		for ( let row = height; row > 0 && bin > 0; row-- ) {
			bin & 1 && ctx.fillRect( x + charX + col * pixelSize, y + row * pixelSize, pixelSize, pixelSize );
			bin >>= 1
		}
	}

	return charX + ( width + 1 ) * pixelSize;
};

This averaged 0.3559ms to render. Without a doubt it is better than 1.2315ms. I’m thinking this is going very well and I might be done. Little did I know this was just the beginning. It dawned on me that I didn’t test the original PixelFont. Their code is extremely simple, no fancy magic, just straight up array traversing. The result: it rendered in 0.2172ms. WHAT?!??!?!?! I thought TinyFont would be an upgrade, but it certainly was not.

Back to the drawing board … this can be improved.

The slowest part is drawing ctx.fillRect(). So I need to do the least amount of drawing possible, and get to it as fast as possible.

Inspired by greedy meshing in voxel engines, once we find a cell that needs to be painted, we check the rest of the column for other painted cells and expand the rectangle. So as an example, instead of painting four 1×1 cells, we can paint one 1×4 rectangle. It is a bit much, but it does work!

This setup ran at 0.2029ms. Marginally better than PixelFont’s 0.2172. The good news is, it is consistently marginally faster.

Big idea time … err … obvious idea time. This part of the code is taking too long:

const fontCode = chars[char.charCodeAt()] || '';
let bin = Number.isInteger( fontCode ) ? fontCode : fontCode.codePointAt();
const binary = ( bin || 0 ).toString( 2 );
const width = Math.ceil( binary.length / height );

In short, these lines decode the unicode character into binary. There is no need to have this take place during the render loop! I moved it into the init function instead and it looked similar to this:

const keys = Object.keys( chars ).map( i => parseInt( i ) );

keys.forEach( ( key ) => {
    const char = chars[ key ];
    if ( char != undefined ) {
        const bin = Number.isInteger( char ) ? char : char.codePointAt();
        const binary = bin.toString( 2 );
        const width = Math.ceil( binary.length / height );
        chars[ key ] = {
            data: bin | 0,
            width: width,
        };
    }
} );

This made all the difference. Now the rendering took 0.1522ms!

Can we do better? Yes. Yes we can. The original script used array reduce to start writing to ctx. Let’s remove the overhead of calling the reducer and refactor that into a for loop. The result: 0.1360ms … tiny gains, but gains never the less.

More better: instead of storing the binary data and width in the chars object, let’s save it in typed arrays:

const widths = new Uint8Array( len );
const bins = new Uint32Array( len );

// Decode the binary values for each char ahead of time. This is slow-ish.
keys.forEach( ( key ) => {
    const char = chars[ key ];
    if ( char != undefined ) {
        const bin = Number.isInteger( char ) ? char : char.codePointAt();
        const binary = bin.toString( 2 );
        const width = Math.ceil( binary.length / height );
        bins[ key ] = bin;
        widths[ key ] = width;
    }
} );

Time to render: consistent 0.1099ms. Not bad at all. That is so much faster than the original.

Conclusion

While I am happy with these results, it is important to note that a native fillText() call runs these same tests at 0.013ms. Significantly faster, but also not unexpected. fillText uses the actual font and the drawing of it is closer to the metal. We are just drawing a bunch of rectangles that look like a font.

The .min file size of this latest version is 1.02kb. That is 262bytes larger than the original (780b). While the point of the tiniest font is to be the tiniest, I think the difference in performance is well worth the cost (1.2315ms vs 0.1099ms).

Full code at: https://github.com/federicojacobi/tinyfont.js/tree/pre-render