Comparing Gutenberg Parsers

One of the things we've discussed before is how important the formal grammar specification is to the Gutenberg project. Blocks exist because when represented in their textual form we have a terse definition of how they should be written out and read in and what each element in that text means.

But as we know the real world is more constraining than our designs in theory are. That is, we have to make tradeoffs in order to make good ideas  practical. In Gutenberg we have to consider these constraints and tradeoffs with the parser code that converts between the serialized representation of a post in post_content and the in-memory data structure that powers blocks.

The primary tradeoff in Gutenberg is performance vs. clarity. The official Gutenberg parser is written in a language designed to describe documents and document grammars. It's intentionally limited with the goal of making the semantics of the representation primary at the cost of producing an inefficient parser executable. We want a fast parser but we also don't want to lose the clarity that our explicit and formal grammar specification provides.

How do we do this? We take care to compare competing parser implementations to ensure that they conform to the specification. In this document I want to lay out the roadmap, plans, and important considerations we need to take when building out this Gutenberg subsystem.

Requirements

• Verify semantic equality of parsers. Alternate parsers should produce a data structure that exhibits value-equality when compared to the output of the default parser.
• Compare parse runtime performance. Alternate parsers will exhibit different performance characteristics than the default parser. We want to be able to compare these characteristics across a broad variety of input 
• The comparison needs to remain simple and accessible to those who want to write alternate parser implementations.

Constraints

• Different parsers may have initial boot-up code that initializes on the first parse. We want to understand this startup performance but we care most about understanding how the parser will perform on repeated parses of a given document as this will represent the more typical use and need in the editor.
• Different parsers will run in different software environments. The in-editor parser will run in a browser but other parsers may run as PHP extensions, as PHP code, as Java code, in mobile operating systems, and more. We need to be able to compare the parse as an input document transforming into an output data structure and not as an entire system with different scaffolding needs for different environments.
• Benchmarks are notoriously difficult to write so that they produce meaningful results. We want to prioritize parsing real documents in use to provide reasonable comparisons of how these parsers will perform in actual use.

Details

Individual tests

If we want to be as implementation-agnostic as we can then I think we have to require the parsers under test to provide their own timing measurements in addition to the measurements we make.

Consider a PHP parser; in normal backend operation we start with a PHP string that produces a PHP data structure. If we ware wanting to compare the performance characteristics in a generic way then we have to convert out of PHP and into something like a JSON string. We may have to start a PHP process to do this but in the normal context PHP would already be running when it parsers. It's unfair to compare the additional overhead required for the benchmark against a JavaScript parser which requires none.

My plan therefore is that each parser should actually provide a basic HTTP server which accepts a document in a POST request and returns the parsed JSON data structure and internal metrics. This requires more effort on the part of the parser implementor and gives away some trust but it should isolate all of the language and platform dependent bits.

Let's look at an example JS-based parser then…

const express = require( 'express' );
cosnt parser  = require( './my-parser.js' );

const server  = express();

server.post( '/', ( request, response ) = {
	const start = process.hrtime();
	const parse = parser( request.body );
	const [ s, ns ] = process.hrtime( start );

	response.send( JSON.stringify( {
		parse,
		us: ( s * 1e6 ) + ns / 1000,
	} ) );
} );

server.listen( 80 );

In this snippet we track the runtime in the language of our choice how long the specific parse step takes and we report that back to the benchmark. We're not worried about people cheating the benchmarks because we're all on the same team. Small variations in performance also won't have much influence because we're not looking to micro-optimize.

Here's how a PHP test might look.

require_once( './my-parser.php' );

$document = file_get_contents( 'php://input' );
$tic = microtime( true );
$parse = my_parse( $document );
$toc = microtime( true );

echo json_encode( [
	'parse' => $parse,
	'us'    => $toc - $tic,
] );

We can see here that we've eliminated the PHP startup time from the test at hand. We will still measure the total time in the benchmark as it can provide additional insight, but we really want to know "how does this parser compare against that parser?"

This interface can inspire non-traditional parser architectures. How would performance change if we had an asynchronous parse? Maybe we want to move the parsing into a WebWorker and communicate across the boundary?

// setup server and communicate with a headless browser

server.post( '/', async ( request, response ) => {
	const start = process.hrtime();
	
	browser.on( 'parsed', parse => {
		const [ s, ns ] = process.hrtime( start );

		response.send( {
			parse,
			us: ( s * 1e6 ) + ns / 1000,
		} );
	} );

	browser.send( { action: 'parse', document } )
} )

Now whether we write our parser in Javascript, PHP, a PHP extension, Rust, Haskell, or Whitespace, whether it's synchronous or synchronous, whether local or returned from a remote HTTP API, we can test them all and compare them all in a reasonably agnostic and independent way.

Aggregating tests

We obviously can't host the parser tests on services like now or heroku because if they ran on shared hosts with different hardware then the results wouldn't be comparable – the hardware and load would bias the results.

However, we can generalize these tests and use technologies like Docker to provide isolation and reproducibility to the setup so that a single machine with controlled load can run each of the parsers in sequence without the test runs interfering with one another.

This architecture makes it even easier for us to investigate questions like "how does this parser run on PHP 5.4 vs. PHP 7.2?" or "how does this compare when run in node vs. when run in a browser?"