{"id":8123,"date":"2026-02-11T10:38:42","date_gmt":"2026-02-11T09:38:42","guid":{"rendered":"https:\/\/launix.de\/launix\/?p=8123"},"modified":"2026-02-11T10:38:43","modified_gmt":"2026-02-11T09:38:43","slug":"doubling-memcp-parser-speed-heres-how","status":"publish","type":"post","link":"https:\/\/launix.de\/launix\/en\/doubling-memcp-parser-speed-heres-how\/","title":{"rendered":"Doubling MemCP Parser Speed – Here’s How"},"content":{"rendered":"\n

Why Parser Speed Matters for OLTP<\/h2>\n\n\n\n

MemCP is an in-memory, MySQL-compatible database. It handles two kinds of workloads: analytics queries that scan millions of rows, and OLTP queries \u2014 small INSERTs, UPDATEs, DELETEs, and SELECTs coming in rapid fire from applications.<\/p>\n\n\n\n

For OLTP \/ analytics queries, parsing a 1000-character SELECT takes milliseconds against a query that runs for seconds or minutes. Nobody cares. For OLTP, every microsecond in the parser is a microsecond added to every request. A web application doing 10,000 INSERT\/s spends more time parsing SQL than executing it if the parser is slow.<\/p>\n\n\n\n

The queries that matter for parser performance are the ones that come in high volume: single-row inserts, point updates, key lookups. And bulk inserts \u2014 INSERT INTO t VALUES (...)<\/code> and SELECT a,b,c FROM t<\/code> with hundreds or thousands of rows \u2014 where the parser processes the same value-tuple grammar thousands of times in a single call.<\/p>\n\n\n\n

Packrat Parsing and Why MemCP Uses It<\/h2>\n\n\n\n

MemCP’s SQL parser is built on go-packrat<\/a>, a packrat parser combinator library. A packrat parser works by combining small parsers (atoms, regex matchers) into larger ones through combinators: And<\/code> (sequence), Or<\/code> (alternatives), Kleene<\/code> (repetition). The grammar for INSERT INTO t VALUES (1,'a'), (2,'b')<\/code> is built from:<\/p>\n\n\n\n

insertStmt = And(INSERT, INTO, tableName, VALUES, tupleList)\ntupleList  = Many(tuple, comma)\ntuple      = And(lparen, valueList, rparen)\nvalueList  = Many(value, comma)\nvalue      = Or(integer, string, null, ...)<\/code><\/pre>\n\n\n\n
Packrat parsing guarantees O(n) time through memoization: every parser result at every input position is cached, so no work is done twice. This matters for grammars with backtracking \u2014 if Or<\/code> tries alternative A and it fails at position 50, the partial results from positions 0-49 are cached and reused when alternative B is tried.<\/p>\n\n\n\n
MemCP uses packrat combinators instead of a generated parser (like yacc) for a specific reason: extensibility<\/strong>. MemCP’s Scheme runtime lets libraries define new SQL syntax by constructing parser trees at runtime:<\/p>\n\n\n\n
(define my-parser (sql-and (sql-atom \"CUSTOM\") (sql-atom \"KEYWORD\") sql-expr))\n(register-syntax \"custom_stmt\" my-parser)<\/code><\/pre>\n\n\n\n
A generated parser would require a build step and recompilation. Combinator parsers are data structures \u2014 they can be constructed, composed, and extended at runtime.<\/p>\n\n\n\n
The Problem<\/h2>\n\n\n\n
Profiling a bulk INSERT showed the parser responsible for tens of thousands of heap allocations per query. Each allocation is cheap individually, but at OLTP volumes they add up: GC pressure, cache misses, wasted cycles.<\/p>\n\n\n\n
We optimized go-packrat across five versions. The results were surprising \u2014 reducing allocations doesn’t always make things faster. In the end, choosing the right changes got us a 2x speedup.<\/p>\n\n\n\n
Measurements<\/h2>\n\n\n\n
All measurements: (time (parse_sql ...))<\/code> in MemCP, median of multiple runs. The input is INSERT INTO t VALUES('a','b'), ...<\/code> with 3, 100, 1000, and 10000 rows.<\/p>\n\n\n\n
Absolute times:<\/strong><\/p>\n\n\n\n
Version<\/th>x3<\/th>x100<\/th>x1000<\/th>x10000<\/th><\/tr><\/thead>
v2.1.15 (baseline)<\/td>1143 us<\/td>14.6 ms<\/td>150.9 ms<\/td>1267.6 ms<\/td><\/tr>
v2.1.16<\/td>542 us<\/td>10.2 ms<\/td>78.9 ms<\/td>727.4 ms<\/td><\/tr>
v2.1.17<\/td>639 us<\/td>10.6 ms<\/td>99.7 ms<\/td>1013.2 ms<\/td><\/tr>
v2.1.18<\/td>978 us<\/td>22.7 ms<\/td>214.1 ms<\/td>2115.6 ms<\/td><\/tr>
v2.1.19<\/strong><\/td>577 us<\/strong><\/td>9.0 ms<\/strong><\/td>73.0 ms<\/strong><\/td>675.8 ms<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Relative to v2.1.15 baseline:<\/strong><\/p>\n\n\n\n
Version<\/th>x3<\/th>x100<\/th>x1000<\/th>x10000<\/th><\/tr><\/thead>
v2.1.15<\/td>1.0x<\/td>1.0x<\/td>1.0x<\/td>1.0x<\/td><\/tr>
v2.1.16<\/td>2.1x<\/td>1.4x<\/td>1.9x<\/td>1.7x<\/td><\/tr>
v2.1.17<\/td>1.8x<\/td>1.4x<\/td>1.5x<\/td>1.3x<\/td><\/tr>
v2.1.18<\/td>1.2x<\/td>0.6x<\/td>0.7x<\/td>0.6x<\/td><\/tr>
v2.1.19<\/strong><\/td>2.0x<\/strong><\/td>1.6x<\/strong><\/td>2.1x<\/strong><\/td>1.9x<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Per-row cost<\/strong> (median \/ row count):<\/p>\n\n\n\n
Version<\/th>x3<\/th>x100<\/th>x1000<\/th>x10000<\/th><\/tr><\/thead>
v2.1.15<\/td>381 us<\/td>146 us<\/td>151 us<\/td>127 us<\/td><\/tr>
v2.1.16<\/td>181 us<\/td>102 us<\/td>79 us<\/td>73 us<\/td><\/tr>
v2.1.17<\/td>213 us<\/td>106 us<\/td>100 us<\/td>101 us<\/td><\/tr>
v2.1.18<\/td>326 us<\/td>227 us<\/td>214 us<\/td>212 us<\/td><\/tr>
v2.1.19<\/strong><\/td>192 us<\/strong><\/td>90 us<\/strong><\/td>73 us<\/strong><\/td>68 us<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
v2.1.19 achieves the best per-row cost at scale: 68 us\/row at 10,000 rows, 7-11% faster than v2.1.16 and nearly 2x the baseline. Its per-row cost drops with scale (192 -> 68 us), showing good amortization of fixed overhead.<\/p>\n\n\n\n
What Changed \u2014 and What We Learned<\/h2>\n\n\n\n
v2.1.16: Replacing Expensive Operations (2x speedup)<\/h3>\n\n\n\n
Seven internal changes, all pure wins:<\/p>\n\n\n\n
    \n
  1. Keyword matching without regex.<\/strong> Every SQL keyword was matched via (?i)^SELECT<\/code> with FindStringSubmatch<\/code>. Replaced with strings.EqualFold<\/code> for case-insensitive, ==<\/code> for case-sensitive. With 313 atom parsers in the grammar, this was the highest-impact single change.<\/li>\n\n\n\n
  2. Word boundaries as []bool<\/code> instead of map[int]bool<\/code>.<\/strong> Flat slice indexed by position, one allocation instead of thousands of map buckets.<\/li>\n\n\n\n
  3. Whitespace skip fast-path.<\/strong> A byte check (<= ' '<\/code> or == '\/'<\/code>) gates the regex call. ~80% of positions have no whitespace, so Skip()<\/code> becomes a single comparison.<\/li>\n\n\n\n
  4. Flat memoization.<\/strong> map[int]map[Parser]*MemoEntry<\/code> flattened to []map[Parser]*MemoEntry<\/code>. One array index replaces one hash lookup for the outer dimension.<\/li>\n\n\n\n
  5. Lr object pooling.<\/strong> Left-recursion markers recycled via sync.Pool<\/code>.<\/li>\n\n\n\n
  6. Slice pre-allocation.<\/strong> And\/Kleene\/ManyParser<\/code> pre-allocate result slices instead of growing from nil.<\/li>\n\n\n\n
  7. Specialized regex matchers.<\/strong> MemCP’s 9 regex patterns are recognized at construction time and replaced with hand-written func(string) int<\/code> matchers. Identifiers use a 256-bit bitmap lookup. Integers and floats use byte loops. String bodies use a backslash-skip loop. regexp.Regexp<\/code> is never compiled for these patterns.<\/li>\n<\/ol>\n\n\n\n
    Every one of these replaces an expensive operation with a cheaper one. The replacement is faster AND allocates less.<\/p>\n\n\n\n
    And the best: The user interface didn’t change. The user still declares his regex-based grammar and we replace common patterns in the regex with faster parsers.<\/p>\n\n\n\n
    v2.1.17-18: The Allocation Trap (1.4-2.9x regression)<\/h3>\n\n\n\n
    These versions pursued allocation reduction further \u2014 replacing the inner map[Parser]*MemoEntry<\/code> with a linked list through slab-allocated entries (v2.1.17), then packing the per-position data into a uint32 with multi-slab indirection (v2.1.18).<\/p>\n\n\n\n
    Allocations dropped from ~630 to ~30 (v2.1.17) to ~7 (v2.1.18). Real-world performance went in the opposite direction.<\/p>\n\n\n\n
    What went wrong:<\/p>\n\n\n\n