I'm porting [gpui-component](https://github.com/longbridge/gpui-component) (a Rust UI component library built on GPUI) to C++ as [gpui-cpp](https://github.com/kjk/gpui-cpp). By which I mean: my friend Claude does the porting, I'm just directing.

It uses [markdown-rs](https://github.com/wooorm/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:

<svg viewBox="0 0 700 150" width="100%" style="max-width:700px" xmlns="http://www.w3.org/2000/svg" font-family="ui-monospace, SFMono-Regular, Menlo, monospace" font-size="11">
  <text x="0" y="14" fill="#1f2937" font-size="12" font-weight="bold">Node, 232 bytes</text>
  <g stroke="#374151" stroke-width="1">
    <rect x="0" y="24" width="20" height="34" fill="#e5e7eb"/>
    <rect x="20" y="24" width="62" height="34" fill="#bfdbfe"/>
    <rect x="82" y="24" width="62" height="34" fill="#fecaca"/>
    <rect x="144" y="24" width="20" height="34" fill="#e5e7eb"/>
    <rect x="164" y="24" width="332" height="34" fill="#fde68a"/>
    <rect x="496" y="24" width="62" height="34" fill="#bfdbfe"/>
    <rect x="558" y="24" width="42" height="34" fill="#e5e7eb"/>
  </g>
  <text x="2" y="45" fill="#1f2937">k</text>
  <text x="24" y="45" fill="#1f2937">children 24</text>
  <text x="86" y="45" fill="#1f2937">position 24</text>
  <text x="168" y="45" fill="#1f2937">8 string fields — 128 bytes</text>
  <text x="500" y="45" fill="#1f2937">align 24</text>
  <text x="560" y="45" fill="#1f2937">nums 16</text>
  <text x="0" y="76" fill="#6b7280">grey = padding and small fields · blue = growable vector · yellow = pointer+length strings</text>
  <text x="0" y="106" fill="#1f2937" font-size="12" font-weight="bold">Node, 16 bytes (same scale)</text>
  <g stroke="#374151" stroke-width="1">
    <rect x="0" y="116" width="10" height="26" fill="#bbf7d0"/>
    <rect x="10" y="116" width="10" height="26" fill="#bbf7d0"/>
    <rect x="20" y="116" width="10" height="26" fill="#fde68a"/>
    <rect x="30" y="116" width="10" height="26" fill="#e5e7eb"/>
  </g>
  <text x="48" y="133" fill="#1f2937">lastKid · sibling · firstStr · kind+flags</text>
</svg>

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 `bool`s 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 `&amp;`-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.

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](https://github.com/kjk/gpui-cpp/commit/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](https://v8.dev/blog/pointer-compression). Reduced memory usage and increased speed.

Our string type is the simplest possible string:

```c++
struct Str {
    char* data;
    size_t len;
};
```

That'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'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 | start | before | after | vs before | vs start |
|---|---|---|---|---|---|
| prose | 1646.1 KB | 1646.1 KB | **1285.9 KB** | -21.9% | -21.9% |
| nested lists | 1067.9 KB | 1067.9 KB | **867.5 KB** | -18.8% | -18.8% |
| gfm tables | 2926.0 KB | 2926.0 KB | **2269.7 KB** | -22.4% | -22.4% |
| entities | 660.2 KB | 660.2 KB | **626.2 KB** | -5.1% | -5.1% |

## 2. Growing arena strings in place ([a9d4f3a](https://github.com/kjk/gpui-cpp/commit/a9d4f3a))

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. `&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 | 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](https://github.com/kjk/gpui-cpp/commit/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.

<svg viewBox="0 0 700 120" width="100%" style="max-width:700px" xmlns="http://www.w3.org/2000/svg" font-family="ui-monospace, SFMono-Regular, Menlo, monospace" font-size="11">
  <text x="0" y="14" fill="#1f2937">declaration order: bool after vector = 7 bytes of padding, six times over</text>
  <g stroke="#374151" stroke-width="1">
    <rect x="0" y="22" width="120" height="26" fill="#bfdbfe"/>
    <rect x="120" y="22" width="16" height="26" fill="#fca5a5"/>
    <rect x="136" y="22" width="112" height="26" fill="#e5e7eb"/>
    <rect x="248" y="22" width="120" height="26" fill="#fde68a"/>
    <rect x="368" y="22" width="16" height="26" fill="#fca5a5"/>
    <rect x="384" y="22" width="112" height="26" fill="#e5e7eb"/>
  </g>
  <text x="4" y="39" fill="#1f2937">vector</text>
  <text x="124" y="39" fill="#1f2937">b</text>
  <text x="140" y="39" fill="#6b7280">padding</text>
  <text x="252" y="39" fill="#1f2937">strings</text>
  <text x="372" y="39" fill="#1f2937">b</text>
  <text x="388" y="39" fill="#6b7280">padding</text>
  <text x="0" y="76" fill="#1f2937">largest first, bools in one byte: no padding</text>
  <g stroke="#374151" stroke-width="1">
    <rect x="0" y="84" width="120" height="26" fill="#bfdbfe"/>
    <rect x="120" y="84" width="240" height="26" fill="#fde68a"/>
    <rect x="360" y="84" width="40" height="26" fill="#bbf7d0"/>
    <rect x="400" y="84" width="16" height="26" fill="#fca5a5"/>
  </g>
  <text x="4" y="101" fill="#1f2937">vectors</text>
  <text x="124" y="101" fill="#1f2937">strings</text>
  <text x="364" y="101" fill="#1f2937">nums</text>
  <text x="404" y="101" fill="#1f2937">f</text>
</svg>

| 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.

## 4. Pointer compression for everything ([07ec80f](https://github.com/kjk/gpui-cpp/commit/07ec80f))

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.

## 5. Varint encoding string length ([f9ebc34](https://github.com/kjk/gpui-cpp/commit/f9ebc34))

`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:

```txt
[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.**

<svg viewBox="0 0 700 160" width="100%" style="max-width:700px" xmlns="http://www.w3.org/2000/svg" font-family="ui-monospace, SFMono-Regular, Menlo, monospace" font-size="11">
  <text x="0" y="14" fill="#1f2937">Str — pointer + length, 16 bytes per field</text>
  <g stroke="#374151" stroke-width="1">
    <rect x="0" y="22" width="128" height="24" fill="#fde68a"/>
    <rect x="128" y="22" width="128" height="24" fill="#fde68a"/>
  </g>
  <text x="4" y="38" fill="#1f2937">char* s</text>
  <text x="132" y="38" fill="#1f2937">int64 len</text>
  <text x="0" y="70" fill="#1f2937">ArenaStr — offset + length, 8 bytes</text>
  <g stroke="#374151" stroke-width="1">
    <rect x="0" y="78" width="64" height="24" fill="#fde68a"/>
    <rect x="64" y="78" width="64" height="24" fill="#fde68a"/>
  </g>
  <text x="4" y="94" fill="#1f2937">u32 off</text>
  <text x="68" y="94" fill="#1f2937">u32 len</text>
  <text x="0" y="126" fill="#1f2937">ArenaStr — offset alone, 4 bytes; the length lives in the arena</text>
  <g stroke="#374151" stroke-width="1">
    <rect x="0" y="134" width="64" height="24" fill="#fde68a"/>
    <rect x="200" y="134" width="24" height="24" fill="#bbf7d0"/>
    <rect x="224" y="134" width="140" height="24" fill="#e5e7eb"/>
    <rect x="364" y="134" width="16" height="24" fill="#bbf7d0"/>
  </g>
  <text x="4" y="150" fill="#1f2937">u32 off</text>
  <text x="204" y="150" fill="#1f2937">len</text>
  <text x="228" y="150" fill="#1f2937">characters</text>
  <text x="368" y="150" fill="#1f2937">0</text>
  <path d="M 64 146 L 196 146" stroke="#374151" stroke-width="1" fill="none" marker-end="url(#ah)"/>
  <defs><marker id="ah" markerWidth="8" markerHeight="8" refX="7" refY="3" orient="auto"><path d="M0,0 L7,3 L0,6 z" fill="#374151"/></marker></defs>
</svg>

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.

| shape | start | before | after | vs before | vs start |
|---|---|---|---|---|---|
| prose | 1646.1 KB | 1091.9 KB | **918.0 KB** | -15.9% | -44.2% |
| nested lists | 1067.9 KB | 611.6 KB | **512.3 KB** | -16.2% | -52.0% |
| gfm tables | 2926.0 KB | 1866.9 KB | **1543.6 KB** | -17.3% | -47.2% |
| entities | 660.2 KB | 144.9 KB | **128.5 KB** | -11.3% | -80.5% |

## 6. Fusing exclusive fields ([5467a18](https://github.com/kjk/gpui-cpp/commit/5467a18))

A `List` has a `start` number. A `Heading` has a `depth`. No node is ever both, so they became one `uint32_t startOrDepth` and `kind` says which it means.

It didn't shrink the size of `Node` due to the alignment padding but we did it anyway hoping that future optimization would shrink below padding.

| shape | start | before | after | vs before | vs start |
|---|---|---|---|---|---|
| prose | 1646.1 KB | 918.0 KB | **918.0 KB** | +0.0% | -44.2% |
| nested lists | 1067.9 KB | 512.3 KB | **512.3 KB** | +0.0% | -52.0% |
| gfm tables | 2926.0 KB | 1543.6 KB | **1543.6 KB** | +0.0% | -47.2% |
| entities | 660.2 KB | 128.5 KB | **128.5 KB** | +0.0% | -80.5% |

## 7. Compressing text position ([ed5e807](https://github.com/kjk/gpui-cpp/commit/ed5e807))

Each `Node` carried the info about its position in parsed text.

It was expensive because it was stored as `start` and `end` fields and each of them was:
* a `uint32_t` line
* a `uint32_t` column
* a `uint32_t` offset

That's 4*3*2 = 24 bytes.

I assume this info is for debugging so not important for me.

I replaced it with 2 `uint32_t` offsets into a source markdown string, `srcStart` and `srcEnd`.

We can reconstruct the line/column position from that and the source string.

| shape | start | before | after | vs before | vs start |
|---|---|---|---|---|---|
| prose | 1646.1 KB | 918.0 KB | **828.0 KB** | -9.8% | -49.7% |
| nested lists | 1067.9 KB | 512.3 KB | **462.2 KB** | -9.8% | -56.7% |
| gfm tables | 2926.0 KB | 1543.6 KB | **1379.6 KB** | -10.6% | -52.9% |
| entities | 660.2 KB | 128.5 KB | **120.0 KB** | -6.6% | -81.8% |

## 8. Further compression text position ([6a558c4](https://github.com/kjk/gpui-cpp/commit/6a558c4))

`srcEnd` is always after `srcStart` so we can delta-encode it and shrink to `uint16_t`.

What if it's bigger than 64 KB? I don't care, we store it as 65535.

This is another case where due to padding we didn't shrink the struct size. But wait for it.

| shape | start | before | after | vs before | vs start |
|---|---|---|---|---|---|
| prose | 1646.1 KB | 828.0 KB | **828.0 KB** | +0.0% | -49.7% |
| nested lists | 1067.9 KB | 462.2 KB | **462.2 KB** | +0.0% | -56.7% |
| gfm tables | 2926.0 KB | 1379.6 KB | **1379.6 KB** | +0.0% | -52.9% |
| entities | 660.2 KB | 120.0 KB | **120.0 KB** | +0.0% | -81.8% |

## 9. Optimizing storing children ([d6c4abc](https://github.com/kjk/gpui-cpp/commit/d6c4abc))

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.

<svg viewBox="0 0 700 190" width="100%" style="max-width:700px" xmlns="http://www.w3.org/2000/svg" font-family="ui-monospace, SFMono-Regular, Menlo, monospace" font-size="11">
  <defs><marker id="a2" markerWidth="8" markerHeight="8" refX="7" refY="3" orient="auto"><path d="M0,0 L7,3 L0,6 z" fill="#374151"/></marker></defs>
  <text x="0" y="14" fill="#1f2937">vector: 24 bytes in the node + a separate array of links</text>
  <g stroke="#374151" stroke-width="1">
    <rect x="0" y="22" width="150" height="28" fill="#bfdbfe"/>
    <rect x="260" y="22" width="50" height="28" fill="#e5e7eb"/>
    <rect x="310" y="22" width="50" height="28" fill="#e5e7eb"/>
    <rect x="360" y="22" width="50" height="28" fill="#e5e7eb"/>
    <rect x="410" y="22" width="50" height="28" fill="#f3f4f6"/>
    <rect x="460" y="22" width="50" height="28" fill="#f3f4f6"/>
  </g>
  <text x="4" y="40" fill="#1f2937">ptr · len · cap</text>
  <text x="272" y="40" fill="#1f2937">kid0</text>
  <text x="322" y="40" fill="#1f2937">kid1</text>
  <text x="372" y="40" fill="#1f2937">kid2</text>
  <text x="418" y="40" fill="#6b7280">spare</text>
  <text x="468" y="40" fill="#6b7280">spare</text>
  <path d="M 150 36 L 256 36" stroke="#374151" stroke-width="1" fill="none" marker-end="url(#a2)"/>
  <text x="0" y="94" fill="#1f2937">ring: 4 bytes in the parent, 4 in each child, nothing else allocated</text>
  <g stroke="#374151" stroke-width="1">
    <rect x="0" y="106" width="90" height="28" fill="#bbf7d0"/>
    <rect x="160" y="150" width="90" height="28" fill="#e5e7eb"/>
    <rect x="300" y="150" width="90" height="28" fill="#e5e7eb"/>
    <rect x="440" y="150" width="90" height="28" fill="#e5e7eb"/>
  </g>
  <text x="6" y="124" fill="#1f2937">parent</text>
  <text x="170" y="168" fill="#1f2937">kid0</text>
  <text x="310" y="168" fill="#1f2937">kid1</text>
  <text x="450" y="168" fill="#1f2937">kid2</text>
  <path d="M 90 120 C 300 120, 470 122, 486 146" stroke="#374151" stroke-width="1" fill="none" marker-end="url(#a2)"/>
  <text x="180" y="116" fill="#6b7280">lastKid</text>
  <path d="M 250 164 L 296 164" stroke="#374151" stroke-width="1" fill="none" marker-end="url(#a2)"/>
  <path d="M 390 164 L 436 164" stroke="#374151" stroke-width="1" fill="none" marker-end="url(#a2)"/>
  <path d="M 486 178 C 440 192, 210 192, 200 182" stroke="#374151" stroke-width="1" fill="none" marker-end="url(#a2)"/>
</svg>

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.

## 10. Compressing table alignments info ([ca0818c](https://github.com/kjk/gpui-cpp/commit/ca0818c))

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:

```txt
[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.

## 11. Fusing exclusive fields ([07444d6](https://github.com/kjk/gpui-cpp/commit/07444d6))

Previously we fused exclusive fields `start` of a List node and `depth` of a Heading node into a single `uint32_t`.

We fused Table node column alignments info from previous optimization into the same field.

We called it `uint32_t perKind`, and `kind` says what kind of value it is.

Saving: **60 → 56 bytes.**

| shape | start | before | after | vs before | vs start |
|---|---|---|---|---|---|
| prose | 1646.1 KB | 519.3 KB | **483.9 KB** | -6.8% | -70.6% |
| nested lists | 1067.9 KB | 256.3 KB | **233.7 KB** | -8.8% | -78.1% |
| gfm tables | 2926.0 KB | 710.3 KB | **646.1 KB** | -9.0% | -77.9% |
| entities | 660.2 KB | 89.2 KB | **86.1 KB** | -3.5% | -87.0% |

## 12. Optimizing eight strings ([521e32e](https://github.com/kjk/gpui-cpp/commit/521e32e))

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.

```txt
[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.

<svg viewBox="0 0 700 150" width="100%" style="max-width:700px" xmlns="http://www.w3.org/2000/svg" font-family="ui-monospace, SFMono-Regular, Menlo, monospace" font-size="11">
  <defs><marker id="a3" markerWidth="8" markerHeight="8" refX="7" refY="3" orient="auto"><path d="M0,0 L7,3 L0,6 z" fill="#374151"/></marker></defs>
  <text x="0" y="14" fill="#1f2937">8 fields: 32 bytes on every node, 7 of them empty on almost all of them</text>
  <g stroke="#374151" stroke-width="1">
    <rect x="0" y="22" width="40" height="26" fill="#fde68a"/>
    <rect x="40" y="22" width="40" height="26" fill="#f3f4f6"/>
    <rect x="80" y="22" width="40" height="26" fill="#f3f4f6"/>
    <rect x="120" y="22" width="40" height="26" fill="#f3f4f6"/>
    <rect x="160" y="22" width="40" height="26" fill="#f3f4f6"/>
    <rect x="200" y="22" width="40" height="26" fill="#f3f4f6"/>
    <rect x="240" y="22" width="40" height="26" fill="#f3f4f6"/>
    <rect x="280" y="22" width="40" height="26" fill="#f3f4f6"/>
  </g>
  <text x="4" y="39" fill="#1f2937">value</text>
  <text x="44" y="39" fill="#9ca3af">url</text>
  <text x="84" y="39" fill="#9ca3af">title</text>
  <text x="124" y="39" fill="#9ca3af">alt</text>
  <text x="164" y="39" fill="#9ca3af">ident</text>
  <text x="204" y="39" fill="#9ca3af">label</text>
  <text x="244" y="39" fill="#9ca3af">lang</text>
  <text x="284" y="39" fill="#9ca3af">meta</text>
  <text x="0" y="86" fill="#1f2937">1 field: 4 bytes, and a record only for what the node actually carries</text>
  <g stroke="#374151" stroke-width="1">
    <rect x="0" y="94" width="40" height="26" fill="#fde68a"/>
    <rect x="150" y="94" width="34" height="26" fill="#bbf7d0"/>
    <rect x="184" y="94" width="26" height="26" fill="#bfdbfe"/>
    <rect x="210" y="94" width="22" height="26" fill="#bbf7d0"/>
    <rect x="232" y="94" width="130" height="26" fill="#e5e7eb"/>
    <rect x="362" y="94" width="14" height="26" fill="#bbf7d0"/>
  </g>
  <text x="4" y="111" fill="#1f2937">first</text>
  <text x="154" y="111" fill="#1f2937">next</text>
  <text x="188" y="111" fill="#1f2937">kind</text>
  <text x="214" y="111" fill="#1f2937">len</text>
  <text x="236" y="111" fill="#1f2937">characters</text>
  <text x="366" y="111" fill="#1f2937">0</text>
  <path d="M 40 107 L 146 107" stroke="#374151" stroke-width="1" fill="none" marker-end="url(#a3)"/>
  <text x="150" y="140" fill="#6b7280">a stored string costs 5 bytes more · a node storing none saves 28</text>
</svg>

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.

Saving: **56 → 28 bytes.**

| shape | start | before | after | vs before | vs start |
|---|---|---|---|---|---|
| prose | 1646.1 KB | 483.9 KB | **358.3 KB** | -26.0% | -78.2% |
| nested lists | 1067.9 KB | 233.7 KB | **159.1 KB** | -31.9% | -85.1% |
| gfm tables | 2926.0 KB | 646.1 KB | **402.9 KB** | -37.6% | -86.2% |
| entities | 660.2 KB | 86.1 KB | **73.7 KB** | -14.4% | -88.8% |

## 13. Fusing two enums into one ([f3c14b9](https://github.com/kjk/gpui-cpp/commit/f3c14b9))

As it happened we had two enums:
* one needed 6 bits
* another needed 2 bits

We fused them from 2 bytes to 1 byte.

Because this 1 byte saving dropped below padding we saved 4 bytes and went from **28 → 24 bytes**.

| shape | start | before | after | vs before | vs start |
|---|---|---|---|---|---|
| prose | 1646.1 KB | 358.3 KB | **321.2 KB** | -10.4% | -80.5% |
| nested lists | 1067.9 KB | 159.1 KB | **136.5 KB** | -14.2% | -87.2% |
| gfm tables | 2926.0 KB | 402.9 KB | **341.9 KB** | -15.1% | -88.3% |
| entities | 660.2 KB | 73.7 KB | **70.4 KB** | -4.5% | -89.3% |

## 14. Remove position, reduce allocator's alignment ([861c803](https://github.com/kjk/gpui-cpp/commit/861c803))

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.