Optimizing memory usage in a markdown parser

A developer optimizing a C++ port of the markdown-rs parser reduced AST node size from 232 bytes to 16 bytes, cutting memory usage by up to 75.2% across benchmark shapes. The optimization involved arena allocation, string growth, struct field reordering, and packing booleans, with the largest improvement in the entities benchmark dropping from 660.2 KB to 163.8 KB.

I’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’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 parser: 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. In Rust there are various kinds of nodes, the largest being 152 bytes. Claude generated a single Node struct of 232 bytes. I got it down to 16 bytes. Here’s the initial Node struct, before optimizations: 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’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 &-style character references The number is the whole arena: nodes, the tokenizer’s event list, and the strings. Not just sizeof Node × node count. We also measure parsing time to make sure we don’t trade size for speed. Some strings had to grow. Arena allocator doesn’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’s what this change does. Luckily, most appends were done to the last string. ArenaStrAppend checks whether the string ends exactly where the arena’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. & 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 start before after vs before vs start prose 1646.1 KB 1285.9 KB 1285.9 KB +0.0% -21.9% nested lists 1067.9 KB 867.5 KB 729.2 KB -15.9% -31.7% gfm tables 2926.0 KB 2269.7 KB 2269.7 KB +0.0% -22.4% entities 660.2 KB 626.2 KB 163.8 KB -73.8% -75.2% 3. Re-order struct fields, pack the bools 5c0ce6e Unless told to pack the layout of the struct, C++ compilers align struct fields to the size of the largest primitive type. If you sandwich a bool between 2 uint64 t values, the bool will occupy 8 bytes sizeof uint64 t instead of 1 byte as it should. Our Node had such wasted space due to padding. My friend Claude was careless. A simple fix is to re-arrange fields, putting the largest first. We also had six bool field which we packed into a uint8 t flags field. Result: 168 → 144 bytes, with no padding at all. We’re beating Rust version now. shape start before after vs before vs start prose 1646.1 KB 1285.9 KB 1150.9 KB -10.5% -30.1% nested lists 1067.9 KB 729.2 KB 654.0 KB -10.3% -38.8% gfm tables 2926.0 KB 2269.7 KB 2023.6 KB -10.8% -30.8% entities 660.2 KB 163.8 KB 151.0 KB -7.8% -77.1% Free bytes: same fields, same code, different order. We compress pointer for all objects allocated in the arena, like we compressed a pointer to the string. ArenaVec<Node children held 8-byte addresses; ArenaPtr<T is a 4-byte offset into the arena’s position space, resolved by ArenaAtOffset. Zero is null, which costs nothing because no allocation ever lands at offset zero. The Node itself doesn’t change size — a vector handle is the same three words whatever it holds — so all of the saving is in the child arrays. shape start before after vs before vs start prose 1646.1 KB 1150.9 KB 1091.9 KB -5.1% -33.7% nested lists 1067.9 KB 654.0 KB 611.6 KB -6.5% -42.7% gfm tables 2926.0 KB 2023.6 KB 1866.9 KB -7.7% -36.2% entities 660.2 KB 151.0 KB 144.9 KB -4.0% -78.1% These shapes rank by children-per-node rather than by node count, which is why tables moved most. ArenaStr was an offset and a length in 8 bytes. Now it’s the offset alone — 4 bytes — and the length is varint-encoded at the beginning of the string data: varint len string bytes NUL There are many varint encoding schemes. This one is for unsigned number and codes number < 128 as a single byte. Most strings are below that threshold, so they use a single byte for the varint length, saving roughly 3 bytes per string. Node shrinks from 144 → 112 bytes. Caveat: An offset-and-length string can point at a slice of another string, and a length-prefixed one can’t. We weren’t doing it so it doesn’t apply here. Some nodes have children that were stored as a growable vector. Empty vector was 24 bytes in the node. We replaced it with a ring of compressed pointers: the parent names its last child, each child names the next one, and the last child wraps back to the first. We use a ring and not just a linked list because appending is the only thing the parser does to a child list. A single linked list requires walking the list to find the end, while a ring does not. Saving: 96 → 80 bytes. shape start before after vs before vs start prose 1646.1 KB 828.0 KB 619.0 KB -25.2% -62.4% nested lists 1067.9 KB 462.2 KB 308.8 KB -33.2% -71.1% gfm tables 2926.0 KB 1379.6 KB 898.7 KB -34.9% -69.3% entities 660.2 KB 120.0 KB 98.9 KB -17.6% -85.0% Caveat: accessing a child by index would require a walk through the ring, so indexing in a loop would be quadratic. In our code we only ask for the first or the last. For tables we were storing column alignments in a separate vector on every node, even though only Table nodes have them. Another 24 bytes per node. We switched to a compressed pointer which points to an optimized representation of the column alignments. There are four alignments left, right, center, none , so a column needs 2 bits: varint count 2 bits a column, four to a byte The whole list is known when the table is entered, so it’s counted, allocated once and filled. For an 8-column table that’s 3 bytes in the arena and a 4-byte offset in the node. Saving: 80 → 60 bytes. We saved more than the 20 bytes because with the last pointer-holding member gone alignof Node fell from 8 to 4. shape start before after vs before vs start prose 1646.1 KB 619.0 KB 519.3 KB -16.1% -68.5% nested lists 1067.9 KB 308.8 KB 256.3 KB -17.0% -76.0% gfm tables 2926.0 KB 898.7 KB 710.3 KB -21.0% -75.7% entities 660.2 KB 98.9 KB 89.2 KB -9.8% -86.5% The block is pushed byte-aligned rather than through the general allocator, which rounds to 8 and would have handed back exactly what the varint saved. We had 8 strings that were not all used by all nodes. Instead of figuring out how many strings we need at most, I created a linked list of strings in the arena. They are different than regular strings in that they carry a 4 byte compressed pointer to the next string within the arena and the kind of the strings. u32 next u8 kind varint len len bytes NUL We can add as many kinds of strings as we need but we only pay for used strings + 5 byte per-string overhead. Some nodes don’t have any strings. New records go on the head, so storing is O 1 , and the walk that finds a kind is at most 8 long and is almost always 1 or 0. In-place growth still works, because a record being the newest thing in the arena is the same condition it always was. At this point I decided that I didn’t need the position so I removed it. Other markdown parsers don’t carry it around so it doesn’t seem very useful. I reduced overhead of perKind by converting it to a record in the string list from step 12 — varint-encoded, under its own kind byte. A List, Heading or Table pays ~8 bytes for it; every other node pays nothing, where a field cost 4 bytes on all of them. Savings: 24 → 16 bytes. For safety arena allocator aligns allocations to 8 bytes but a 16 bytes Node can be allocated at 4 bytes, which we did. This reduces wasted space between allocations. shape start before after vs before vs start prose 1646.1 KB 321.2 KB 272.0 KB -15.3% -83.5% nested lists 1067.9 KB 136.5 KB 110.2 KB -19.3% -89.7% gfm tables 2926.0 KB 341.9 KB 250.5 KB -26.7% -91.4% entities 660.2 KB 70.4 KB 65.6 KB -6.8% -90.1% End results The results are pretty dramatic: sizeof Node prose nested tables entities start 232 1646.1 KB 1067.9 KB 2926.0 KB 660.2 KB end 16 272.0 KB 110.2 KB 250.5 KB 65.6 KB -93% -83.5% -89.7% -91.4% -90.1% A parse of 64 KB of prose cost 25.7× the source in arena bytes. It costs 4.2× now. The entities shape went from 10.3× to 1.02×. The speed was unchanged. Fastest of 3 runs: prose 8.47 → 8.22 ms nested 9.45 → 9.26 ms tables 12.88 → 12.92 ms entities 5.90 → 5.85 ms Those are within margin of error. The phase of building the tree got a measurable speed up: 0.397 → 0.302 ms, about 24% faster. This is from allocating less and touching fewer cache lines. This is not visible on micro benchmarks, but using less memory will slightly speed up the rest of the application. Lessons learned Arranging struct fields by size is good. It costs literally nothing. Pointer compression is good. 8 bytes become 4 bytes and the cost of converting back and forth is negligible, as Google shown in their v8 blog post and is re-inforced by our benchmarks Varint-encoding is good. Most strings are short so varint encoding can save 3 bytes per string on average. Moving rare fields out of line is good. The way we reduced 8 strings into an out-of-line list. Only pays off if savings is bigger than the cost of additional metadata. sizeof only drops when the saving crosses an alignment boundary. Two of our changes didn’t reduce size of Node struct but it paid off in later optimizations. The allocator’s alignment is part of sizeof. A 28-byte struct from an 8-aligned bump allocator is 32 bytes. We need benchmarks. You can’t improve what you can’t measure. Our benchmarks measured both memory usage and speed, to ensure we didn’t regress speed to save memory.