Killing a `Cow` made my JSON formatter 42% faster

A formatter styles code consistently, usually improving human readability. If you are unfamiliar with formatters, tokenizers, or abstract syntax trees, see my article on how formatters work

The JavaScript ecosystem has a gap—most formatters are either featureful or fast. Prettier is the standard in the JavaScript ecosystem, but it’s not the fastest. Oxfmt has made major strides—supporting parity with Prettier’s JavaScript formatting with much improved performance. One report found a migration to Oxfmt formatted their repo 6.5x faster—from 13.9 seconds to 2.1

However these gains do not apply to JSON. Oxfmt is 10–20% slower than Prettier for JSON. Oxfmt has a native JavaScript formatter, but it reasonably delegates to Prettier for file types without native implementations¹. Oxfmt plans for a native JSON implementation this year!

Prettier and Oxfmt both take more than a second to format a 2MB JSON file, while my formatter, JJPWRGEM takes around 30 milliseconds

To be fair, JJPWRGEM doesn’t have Prettier feature parity—but what if it did? It’s a great base, and I am confident there are performance gains to be found while implementing features

I started with a well scoped and impactful change—normalizing numbers like Prettier—and I ended up speeding up my formatter by 42% in the process. If you’re interested in how that was calculated, jump to the final benchmarks

Number normalization

Let’s start with 3 normalizations related to scientific notation for simplicity. They all build nicely on each other

1. Lowercases exponent symbol (from 1E5 to 1e5)
2. Strips + (from 1e+5 to 1e5)
3. Removes 0 exponents (from 1e0 to 1)

Baseline

At the moment, JJPWRGEM leaves numbers untouched and represents them as a single Cow<str>. I’ll explain more about Cow as relevant

I am benchmarking against several files with varying data shapes. Here are a few samples

{ "type": "FeatureCollection",
  "features": [{
    "type": "Feature",
    "properties": { "name": "Canada" },
    "geometry": {"type":"Polygon","coordinates":[
      [[-65.613616999999977,43.420273000000009],
       [-65.619720000000029,43.418052999999986],
       [-65.625,43.421379000000059], ...]
    ]}
  }]
}

{
	"events": {
		"138586341": {
			"description": null,
			"id": 138586341,
			"name": "30th Anniversary Tour",
			"subTopicIds": [337184269, 337184283],
			"topicIds": [324846099, 107888604]
		}
	},
	"areaNames": {
		"205705993": "Arrière-scène central",
		"205705994": "1er balcon central"
	}
}

{
  "statuses": [{
    "metadata": { "result_type": "recent", "iso_language_code": "ja" },
    "created_at": "Sun Aug 31 00:29:15 +0000 2014",
    "id": 505874924095815700,
    "text": "@aym0566x \n\n名前:前田あゆみ\n第...",
    ...
  }]
}

Deser refers to deserializing into an abstract syntax tree. The performance is represented by throughput to avoid size based discrepancies. A 1MB file will be formatter faster than a 3MB file, but MB/s is comparable for both!

Iteration 0: Build a new normalized string

The simplest approach is to build new strings for improperly formatted numbers

Unfortunately, each number needs traversed twice, once to find the range and again to validate it. Even if there are no numbers in our input, it requires slow heap allocations

We need a more complex approach that takes references to chunks of the input string

Iteration 1: 2 Cows

Only 2 parts of each number matter. The mantissa to left of the e and the exponent to the right. You may recognize this as scientific notation—1e5 represents $1e5$

Say we have 1E+5, we can store 1 and 5 and reconstruct 1e5. If we have an exponent, the e or E is lowercased. Any +s can be skipped since 1e5 and 1e+5 are equivalent

pub enum Token<'a> {
    Number {
        mantissa: Cow<'a, str>,
        exponent: Cow<'a, str>
    },
}

This approach works, but lowers performance across the board. Cow<str> comes with overhead raw str avoids, negatively affecting datasets without many numbers

What is a Cow anyways?

Cow stands for Clone On Write. It references data until mutation is needed, then duplicates it. This pays off when most values are unchanged—only data needing modification is cloned

A to_lowercase function is a great use case—if the input is already lowercase, you can return a reference to the same string! In Rust terms, the data is “borrowed”

fn to_lowercase(string: &str) -> Cow<'_, str> {
    if string.is_lowercase() {
        // reference input string
        Cow::Borrowed(string)
    } else {
        // make a new string
        Cow::Owned(string.to_lowercase())
    }
}

Now imagine an uppercase input. A new string is created to avoid changing the referenced string. The Cow “owns” the new data and can update the allocated capacity without reallocating, but it must clean up that data when it goes out of scope

Since a Cow is potentially responsible to clean up its data, it pays a small performance penalty when it goes out of scope. This ultimately renders 20% of the program’s instructions useless! Cow’s flexibility was never used

Even worse, each Token could be a Number, so cleanup checks run on tokens like OpenCurlyBrace that carry no data

Let’s get rid of the Cows!

Iteration 2: use &str instead of Cow<str>

pub enum Token<'a> {
    Number {
        mantissa: &'a str,
        exponent: &'a str
    },
}

The compiler gets to remove all those cleanup instructions and branches, which is a huge win for every datasets

However, the “dense floats” dataset is below baseline since it has no exponents—paying the cost to check for exponents that never materialize. Let’s try splitting the tokens in 2 to avoid paying that cost

Iteration 3: Separate Mantissa and Exponent variants

Instead of 1 variant holding the full number, we’ll split it in 2 so the CPU can read 2 tokens at once, saving an instruction

pub enum Token<'a> {
    Mantissa(&'a str),
    Exponent(&'a str),
}

CPUs read memory in chunks—like reading a word at a time instead of a full sentence

A CPU fetches 64 bytes of RAM at a time into its cache for processing, meaning 2 &strs or Cow<str>s per token limits reads to one Token at a time

Variants holding 1 &str or Cow<str> are both 24 bytes, so the 2 fit in 1 read

“Dense floats” deserialization is now better than baseline, but “many objects and integers” has regressed from the previous iteration due to higher number parsing overhead

Iteration 4: Split the state machine

Parsing both the mantissa and exponent has ballooned the number state machine to 88 bytes. Just like with larger tokens, The CPU needs two reads per state change

A state machine is like a sequential checklist. To find where a number starts and ends, we can follow this (abbreviated) checklist

1. start with a digit or minus sign
2. then another digit or a . for a float
3. …
4. finish

At first, it made sense to have a full number state machine, but now we care about 2 separate chunks of that number

Not only will splitting allow the CPU to fetch the full state in one read, the compiler better optimize with less possibilities to reason about

enum MantissaState { ... }
enum ExponentState  {
    MinusOrPlusOrDigit,
    AfterSign,
    Digits,
    Zero,
    End
}

Now the “many objects and integers” dataset is even faster than baseline!

Unfortunately, “dense floats” has regressed to slightly below baseline, but that’s an acceptable tradeoff since typical JSON has more mixed data

Final Benchmarks

Switching from Cow to str and splitting Number token and state machines both help to improve performance

The headline of “42%” improvement refers to the strings and deep nesting dataset deserialization + prettification. The slower stage will pull down the faster one, so we add their times together and covert back to MB/s

For the baseline case

For the new implementation

Resulting in a gain of around 42%

Deserialization into AST

Benchmarks converting a string into an AST

“dense floats” pays for the extra unused token per number, but “many objects and integers” and “strings and deep nesting” have massive improvements due to converting Cow to str

Prettify from AST

Benchmarks serializing AST into a human readable string

“dense floats” suffered the most for a branch on each Number to check if an exponent is available to print. Other datasets are flat

Uglify from Token Stream

Converts a string into tokens and serializes into a compact string

Big improvements across the board. Avoids building a syntax tree, so serialization avoids branching with formatting like with AST to string paths

The benchmarks prove formatters can be fast and featureful—I did more work and improved performance in most categories. I’ll see y’all again when I implement the next Prettier feature!

Please consider subscribing to my RSS feed or your programs will give your CPU depression