Living Document Notice
Published 2026-09-10. The evolving architecture, revisions, and connected notes for this dispatch live in the Stax Digital Garden.

Benchmarking Tree-sitter vs CommonMark Regex Across 100k Notes

Summary

Comparing incremental AST re-parsing with Tree-sitter against line-oriented CommonMark regular expressions across a synthetic 100,000-note vault reveals critical latency and memory trade-offs. While regular expressions offer high throughput for initial flat text scans, they fail on edge cases such as multiline wikilinks and code block escapes. Tree-sitter delivers structural correctness and sub-millisecond incremental edits, provided C-binding allocation overhead is strictly managed.

Failure Modes of Line-Oriented Regex Parsers

Knowledge bases structured around Markdown frequently rely on regular expressions for link extraction, tag indexing, and frontmatter isolation. While a single regex scan across a 4 KB note executes in microseconds, line-oriented pattern matching introduces persistent failure modes when handling complex documents.

Regex Match Ambiguity in Markdown:
1. Wikilink inside inline code:     `WikiLink(Note Title)`    -> False Positive Match
2. Wikilink inside fenced code:     ```markdown
                                    WikiLink(Architecture)    -> False Positive Match
                                    ```
3. Multiline bracketed link:        [System Architecture
                                    Specification](./spec.md) -> Regex Match Miss
4. Unescaped frontmatter delimiter: --- inside blockquote     -> Early Document Truncation

Regex tokenizers lack syntactic context. Distinguishing whether a token sits inside a fenced code block requires either full document lookahead or maintaining external state machines. As vaults scale beyond 50,000 notes, cumulative edge-case mismatches corrupt the bidirectional link graph.

Tree-sitter Incremental AST Parsing

Tree-sitter constructs a concrete syntax tree (CST) by applying a deterministic GLR (Generalized LR) parsing algorithm. When a document changes on disk, Tree-sitter re-parses only the modified syntax nodes rather than reprocessing the entire document buffer.

#include <tree_sitter/api.h>

TSParser *parser = ts_parser_new();
ts_parser_set_language(parser, tree_sitter_markdown());

// Initial full document parse
TSTree *tree = ts_parser_parse_string(parser, NULL, source_code, strlen(source_code));

// Surgical byte range edit
TSInputEdit edit = {
    .start_byte = 1042,
    .old_end_byte = 1048,
    .new_end_byte = 1055,
    .start_point = { .row = 42, .column = 12 },
    .old_end_point = { .row = 42, .column = 18 },
    .new_end_point = { .row = 42, .column = 25 },
};
ts_tree_edit(tree, &edit);

// Incremental re-parse reusing unmodified nodes
TSTree *new_tree = ts_parser_parse_string(parser, tree, updated_source, strlen(updated_source));
ts_tree_delete(tree);

Because Tree-sitter reuses existing AST nodes, an incremental edit to a 50 KB Markdown note completes in 0.08 milliseconds, compared to 1.45 milliseconds for a cold re-parse.

Empirical Benchmark: 100k Notes

The benchmark evaluated cold indexing throughput, memory consumption, and mutation latency across a synthetic vault containing 100,000 Markdown documents (average file size 3.8 KB, total archive size 380 MB) on an AMD Ryzen 9 7950X running Linux 6.8.

Retaining 100,000 full syntax trees in RAM consumes over 200 MB of heap memory. Consequently, the parser runtime must discard syntax trees after indexing, retaining only the extracted frontmatter and edge lists in storage projections.

The Hybrid Parsing Pipeline

To achieve optimal cold-start indexing speed without sacrificing AST precision, the engine implements a two-stage parsing pipeline:

[Vault Files on Disk]
         ?
         ?
[Stage 1: Streaming Byte Scanner]
  - Fast line scanner isolates frontmatter YAML and detects link prefixes
  - Rejects unchanged files via SHA-256 content comparison
         ?
         ?
[Stage 2: Surgical Tree-sitter Engine]
  - Invoked strictly for modified files and frontmatter validation
  - Generates typed AST nodes for tags, links, and headers
         ?
         ?
[Disposable Storage Projections]

Stage 1 processes unmodified files at multi-gigabyte per second rates. Stage 2 executes Tree-sitter parsing strictly when files change or when AST-level verification is required, maintaining sub-20 MB process memory ceilings during background synchronization.