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.
