Optimizing memory use in a Markdown parser

Ctrl + K<br>to search...

Home<br>&bull;

Software<br>&bull;

Contact Me

Optimizing memory use in a Markdown parser

edit

I&rsquo;m porting gpui-component (a Rust UI component library built on GPUI) to C++ as gpui-cpp. By which I mean: my friend Claude does the porting, I&rsquo;m just directing.

It uses markdown-rs (a CommonMark + GFM parser) markdown parser so I ported it too.

Then I optimized it.

This post describes what I did with the intention of teaching other how to optimize C++ code.

The starting point

There are 2 kinds of markdown parsers:

those that stream nodes as they parse

those that build an AST in memory

markdown-rs builds an AST. The game is about minimizing the size of AST node.

Rust version has different Node types of different sizes, the largest being 152 bytes.

Claude generated a single Node struct of 232 bytes.

I got it down to 16 bytes.

Here&rsquo;s the initial Node struct, before optimizations:

Node, 232 bytes

children 24<br>position 24<br>8 string fields — 128 bytes<br>align 24<br>nums 16<br>grey = padding and small fields · blue = growable vector · yellow = pointer+length strings<br>Node, 16 bytes (same scale)

lastKid · sibling · firstStr · kind+flags

Where the 232 went: 8 string fields at 16 bytes each (a char* plus a length), two growable vectors at 24 bytes each (children and table alignments), a 24-byte unist Position (line, column and offset at each end), six bools one to a byte, and the padding all of that dragged in.

Every node in the tree pays for every field, whichever kind it is. A Text node uses one string field and nothing else.

Arena allocator

It&rsquo;s important that all allocations are done in an arena.

Nodes in a parse tree all have the same lifetime which makes it a perfect use for an arena: a bump allocator that can only grow. The only way to free memory is to reset the arena.

This is different than calling malloc() to allocate each node individually and then having to call free().

It makes it easy to measure memory usage: check the arena size after parsing.

It also allows optimization tricks like compressing pointers.

How I measured

bun cmd/bench.ts markdown parses 64 KB of markdown in four shapes and reports the arena bytes the parse allocated:

prose — paragraphs, emphasis, links

nested lists — deep blockquotes and lists

gfm tables — tables all the way down

entities — text that is mostly &amp;-style character references

The number is the whole arena: nodes, the tokenizer&rsquo;s event list, and the strings. Not just sizeof(Node) × node count.

We also measure parsing time to make sure we don&rsquo;t trade size for speed.

Baseline, 64 KB of source:

prose 1646.1 KB (25.7× the source)

nested lists 1067.9 KB

gfm tables 2926.0 KB

entities 660.2 KB

1. Pointer compression for strings (bed71ee)

On 64-bit platforms, pointers are 8 bytes. Pointer compression reduces this to 4 bytes by calculating a 32-bit offset against a base pointer.

Google used compressed pointers in v8 with great result. Reduced memory usage and increased speed.

Our string type is the simplest possible string:

struct Str {<br>char* data;<br>size_t len;<br>};

That&rsquo;s at least 12 bytes per string, if len is 4 bytes. Due to alignment, the size is 16 bytes.

Strings are allocated in Arena so we can use the beginning of an arena as a base pointer and optimize the pointer from 8 bytes to 4 bytes.

We typedef ArenaStr as uint64_t. The lower 4 bytes is uint32_t compressed pointer and upper uint32_t is size.

We reduced the overhead of strings from 16 bytes to 8 bytes. Times 8 strings that&rsquo;s 64 bytes saved per node.

Added helper functions for allocating ArenaStr in arena and converting ArenaStr to Str.

Savings: 8 strings * 8 bytes, 64 bytes per node: 232 → 168 bytes.

shape<br>start<br>before<br>after<br>vs before<br>vs start

prose<br>1646.1 KB<br>1646.1 KB<br>1285.9 KB<br>-21.9%<br>-21.9%

nested lists<br>1067.9 KB<br>1067.9 KB<br>867.5 KB<br>-18.8%<br>-18.8%

gfm tables<br>2926.0 KB<br>2926.0 KB<br>2269.7 KB<br>-22.4%<br>-22.4%

entities<br>660.2 KB<br>660.2 KB<br>626.2 KB<br>-5.1%<br>-5.1%

2. Growing arena strings in place (a9d4f3a)

Some strings had to grow. Arena allocator doesn&rsquo;t provide freeing or reallocation. You can only allocate new strings, which wastes memory by leaving dead copies of the string we were appending to.

We can grow the last allocated string and that&rsquo;s what this change does. Luckily, most appends were done to the last string.

ArenaStrAppend checks whether the string ends exactly where the arena&rsquo;s next allocation would begin. If it does, the new bytes are pushed straight onto it and nothing is copied.

Decoding HTML entities (e.g. &amp;) broke that optimization by doing an allocation before appending to the string.

We switched to decoding entities into a 4-byte stack buffer which enabled optimized append.

shape<br>start<br>before<br>after<br>vs before<br>vs start

prose<br>1646.1 KB<br>1285.9 KB<br>1285.9 KB<br>+0.0%<br>-21.9%

nested lists<br>1067.9 KB<br>867.5 KB<br>729.2 KB<br>-15.9%<br>-31.7%

gfm tables<br>2926.0...