![\\\"a](\\\"diagram.png\\\")
test code.\"\n\n(org->markdown \"This is ~test~ code.\")\n;; => \"This is `test` code.\"\n\n;; parse once, render as often as you like\n(define ast (org->ast \"* Hello\\nA *bold* line.\\n\"))\n(org-ast->html ast)\n(org-ast->markdown ast)\n```\n\nThe rest of this article is about what happens between those calls.\n\n## Teaching the parser more of Org [#](#teaching-the-parser-more-of-org)\n\n“Supporting Org” hides a lot of work, because Org isn’t a markup language with a tidy grammar. It’s a pile of conventions accumulated over years of a GNU Emacs major mode, some of them deliberately informal, and each one has to be considered on its own terms. Every feature below started as a sentence in the Org manual, became a grammar pattern, then became a test.\n\n### Links: decide once, in the parser [#](#links-decide-once-in-the-parser)\n\nAn Org link’s target says what kind of link it is. A target starting with `https://` is external. `file:photo.png` is a file, and so is a bare `notes.org`. `#custom-id` points inside the document, `*Heading` at a heading, and a `::search` suffix says where inside the target you land.\n\nThe old code let each renderer read the target and decide for itself, which is exactly how two back ends drift apart. HTML grows a special case for image extensions, Markdown grows a slightly different one, and after a year of small repairs the same document means two things depending on which function you call. A user who notices won’t know which one is right, and will be right not to trust either.\n\nSo classification moved into the parser, where it happens once.\n\n```\n(org-link-parts \"https://example.org/a\") ;; => (https . \"//example.org/a\")\n(org-link-parts \"file:photo.png\") ;; => (file . \"photo.png\")\n(org-link-parts \"notes.org\") ;; => (file . \"notes.org\")\n(org-link-parts \"#custom-id\") ;; => (internal . \"custom-id\")\n(org-link-parts \"*My Section\") ;; => (heading . \"My Section\")\n(org-link-parts \"notes.org::*Heading\") ;; => (file . \"notes.org\")\n(org-link-search \"notes.org::*Heading\") ;; => \"*Heading\"\n(org-image-link? \"photo.jpeg?raw=1\") ;; => #t\n```\n\nBoth renderers then ask the same questions and follow the same answer.\n\n| Org | HTML | Markdown |\n| --- | --- | --- |\n| `[[file:photo.png][a photo]]` | `![\"a](\"photo.png\")
` | `` |\n| `[[images/diagram.svg]]` | `![\"...\"](\"images/diagram.svg\")
` | `` |\n| `[[file:notes.org][notes]]` | `notes` | `[notes](notes.org)` |\n| `[[#custom-id][there]]` | `there` | `[there](#custom-id)` |\n| `[[*My Section][up]]` | `up` | `[up](#my-section)` |\n| `[[https://gnu.org][GNU]]` | `GNU` | `[GNU](https://gnu.org)` |\n\nTwo details deserve a sentence each. The `::search` suffix is set aside before the path is used as a file name, so `file:notes.org::*Heading` doesn’t produce a broken file name. And `C:/tmp/x.txt` isn’t mistaken for a link with a scheme named `c`, because a real scheme is lower case. Small stuff, but it’s the kind of small stuff that decides whether a program is pleasant to use on somebody else’s computer.\n\n### Figures [#](#figures)\n\nOrg gives the element after a `#+CAPTION:` or `#+NAME:` keyword a caption and a name. When that element is a link to an image, the three things are one object: a figure. The parser folds them together, so renderers get a single node instead of three neighbors they have to guess about.\n\n```\n(org->html \"#+NAME: fig:arch\\n#+CAPTION: The architecture\\n[[file:diagram.png][a diagram]]\\n\")\n;; => \"See fig:arch.
\"\n```\n\nMarkdown has no `figure` element, so it gets the image, the caption as an emphasised line, and an explicit anchor for the cross-reference. What counts as a figure is deliberately narrow: the keywords must sit immediately before a paragraph holding exactly one image link and nothing else. Everything else stays a keyword line. Inventing a caption for an element this parser doesn’t caption is worse than saying nothing, because the reader would never learn that something got silently dropped.\n\n### Named elements [#](#named-elements)\n\nA figure is the image case of a more general rule. A `#+NAME:` line names the element after it, and anything that renders as something a link can land on can be named: a table, a source block, a quote, a list, a separator, a paragraph.\n\n```\n(org->html \"#+NAME: tbl:users\\n| Users | 1024 |\\n\\nSee [[tbl:users]].\\n\")\n;; => \"See tbl:users.
\"\n```\n\nHTML puts the identifier on the element itself. Markdown has nothing to hang it on, so it emits an anchor in front, same as for a figure. A bare target that matches the name of an element in the same document resolves as a cross-reference, which is why `[[tbl:users]]` and `[[notes]]` work. A target that already says what it is — a scheme, a `file:` prefix, a leading `#` or `*`, or a `::search` suffix — keeps the meaning it wrote.\n\nOne asymmetry, documented rather than hidden: a `#+CAPTION:` in front of a named table isn’t folded into it, because captions on tables aren’t rendered yet. The line stays an ordinary keyword line where the writer put it.\n\n### Tables, read by their bars [#](#tables-read-by-their-bars)\n\nTables looked finished until I looked at the edges. What should `|` on a line of its own be? What is `| a ||`? What happens to a row that ends the input with no newline?\n\nThe old pattern counted separators and made one cell for each, which meant a row with no cells could raise an error, and a row that ended the input got a phantom empty cell from the newline it didn’t have. The rewrite reads a row the way Org does: by the bars that separate the cells, where a bar closes a row when nothing but the end of the line follows it. That one rule answers all three questions.\n\n- A line that is only its closing bar (`|` on its own) is a row of **one empty cell**, not a row with no cells.\n- `| a ||` is a row of **two cells**, the second of them empty, rather than a paragraph.\n- A row that ends the input keeps exactly the cells that were written.\n\nAn empty cell also keeps its column, because an empty value is now the empty string instead of the bare tag symbol that an empty `(* ...)` match leaves behind. The difference sounds academic until it is your table.\n\n### Lists that mix and nest [#](#lists-that-mix-and-nest)\n\nOrg lets a list change its bullet type part-way through, and it lets a nested list use a different kind from its parent. So the grammar stopped having three separate list productions and grew one.\n\n```\n(define-peg-pattern org-list all\n (+ (or desc-item unordered-item ordered-item)))\n```\n\nThe renderers group consecutive items of the same kind into the proper element, which is what makes `- outer` with `1. nested` inside it come out as an unordered list containing an ordered one. Checkboxes, description items and arbitrary nesting depth follow from the same rule.\n\n### The rest of the surface [#](#the-rest-of-the-surface)\n\nBetween those features and the earlier work, the supported set is now: headings with TODO keywords, priorities and tags; paragraphs; unordered, ordered and description lists in any mixture and at any depth; checkboxes; tables with empty cells; source, example, quote, verse, center, export and comment blocks; keywords and in-buffer settings; comments; fixed-width lines; separators; footnotes, whether references, definitions or inline; bold, italic, underline, strikethrough, code, verbatim, superscript, subscript, escaped markup and forced line breaks; links with and without descriptions, bare URLs, images, figures, named elements and heading anchors.\n\nThat’s most of what people actually write. Not all of Org, and the manual has a section listing the gaps instead of hiding them, because a library that lies about its coverage just wastes everyone’s time.\n\n## Measuring the work [#](#measuring-the-work)\n\nBefore optimizing anything I wanted a benchmark that could tell me whether a change helped, and that couldn’t be fooled by the change itself.\n\nThe benchmarks live in `test/veritas/benchmark/scope.scm`. They use the same [Veritas](https://codeberg.org/jjba23/veritas) framework as the unit suite, selected by test type so they never slow down `maak test`.\n\n```\nVERITAS_TEST_TYPE=benchmark \\\nguix shell -m manifest.scm -- guile -L ./src -L ./test \\\n -c '((@ (veritas runner) run-tests))'\n```\n\nThe suite measures five workloads and prints three tables — wall clock, allocation, and the collapse pass — formatted as Markdown, ready to paste into the manual. That last part matters: a number you have to retype by hand quietly stops being true.\n\n| Workload | What it exercises |\n| --- | --- |\n| Parse the feature fixture | every construct the parser knows, in 1.8 KB |\n| Parse README.org | a real 58 KB document with prose, tables and code blocks |\n| Render the feature fixture to HTML | parsing plus the HTML renderer |\n| Render the feature fixture to Markdown | parsing plus the Markdown renderer |\n| Parse a 50-clause inline paragraph | the inline grammar, under maximum pressure |\n\n### Five runs, keep the fastest [#](#five-runs-keep-the-fastest)\n\nOne wall clock reading on a laptop isn’t a measurement, it’s a rumor. The suite runs each workload five times and reports the fastest, on the theory that the other four got interrupted by a browser, a compiler, or the collector arriving at a bad moment.\n\nIt’s not statistically pure and I won’t pretend it is. It’s a lower bound on the cost of the work, measured on a machine that’s also doing other things. Allocation is the stable half and stays within a few percent; wall clock moves 10–20% between sessions. Repeat it and get a different number and you’ve found the noise, not an error. Be suspicious of anyone who reports wall clock figures without it.\n\n### Allocation, not only time [#](#allocation-not-only-time)\n\nGuile’s collector is good enough that you can write a parser allocating a megabyte per kilobyte of input and still call it fast, right up until it’s in a server serving several documents at once. So the suite measures the heap too. The heap is collected before each workload, and what’s reported is `heap-total-allocated`: everything the workload asked for, including garbage it dropped immediately. That’s allocation pressure, the thing that triggers collections, not the memory a result keeps.\n\nThe last column is Guile’s `gc-time-taken`, which is collector **processor** time. Guile sums its marker threads, so one full collection of a big heap can be reported as several times its wall clock cost on a many-core machine. Read it as how much collector work a workload causes, not as a share of the clock. Same note is in the benchmark’s docstring, because an easy-to-misread number will get misread.\n\n### Fragments and the collapse pass [#](#fragments-and-the-collapse-pass)\n\nThe last measurement in the suite is the one that eventually explained everything: how many string **fragments** a parse hands to the pass that merges them, and how long the merging takes.\n\nTake a pattern written as `(* (and (not-followed-by eol) peg-any))`, meaning “consume characters until the newline”. The compiled pattern produces one parse object and one string fragment per character. A line of `n` characters costs `n` one-character substrings, `n` list cells, and a merge over all of them. On a document of short lines nobody notices; on a 45 KB line it’s the whole program.\n\nThe fragment table made that visible with no profiling at all.\n\n| Document | Fragments handed to the collapse pass | Collapse (ms) |\n| --- | --- | --- |\n| Feature fixture (1.8 KB) | 82 | 0.04 |\n| README.org (58 KB) | 1,264 | 0.39 |\n| Plain prose (32 KB) | 400 | 0.22 |\n| One 45 KB line | 1 | 0.005 |\n\nThe last row is the interesting one. Forty-five kilobytes of text arrive as a single fragment, because a run scanner took them in one substring instead of forty-five thousand. The README, 58 KB of input, arrives as about 1,300 fragments — roughly one per line of prose instead of one per character.\n\n## What the profile said [#](#what-the-profile-said)\n\nVeritas profiles every benchmark with Guile’s `statprof`, and that’s what turned a vague feeling that big files were slow into a statement about one procedure.\n\nI fed the old parser a document made of one 40 KB line and looked at the profile.\n\n```\n% cumulative self procedure\n 97.55 1.77 1.77 list?\n 0.61 115.98 0.01 ice-9/boot-9.scm:220:5:map1\n 0.61 0.03 0.01 orgwebalchemy/peg.scm:339:0\n 0.61 0.01 0.01 reverse\n 0.00 23786.61 0.00 ice-9/peg/simplify-tree.scm:48:0:string-group\n 0.00 3.56 0.00 ice-9/peg/simplify-tree.scm:65:0:string-collapse\n```\n\n97.5% of the time is inside `list?`. Not the grammar, not the renderers, not any of my own code: one predicate, called by Guile’s own tree simplifier.\n\nMy hypothesis was that the PEG engine was slow. The truth was a helper in `(ice-9 peg simplify-tree)` asking `(list? lst)` of the rest of the list at every level of its recursion, which walks the list quadratically.\n\nHere is the relevant part of `string-group`.\n\n```\n(define (string-group lst)\n (if (not (list? lst)) ;; <- O(length) at every level\n lst\n (if (null? lst)\n '()\n (let ((next (string-group (cdr lst)))) ;; non-tail recursion\n ...))))\n```\n\nFor a run of `n` fragments that’s about `n²/2` list steps. A line of 40,000 characters means 800 million of them, which is exactly the 1.77 seconds in the profile. Doubling the line quadruples the bill, and the measurements agree: 20 KB took about 420 ms, 40 KB about 1,760 ms.\n\nSo there were two problems and only one was mine. My grammar produced one fragment per character, handing the quadratic pass an enormous run to chew on. And the collapse pass was quadratic in the length of a run, so even a modest run cost more than it should. Fix only the first and a slow path waits for anyone who writes a long line; fix only the second and you still allocate megabytes for nothing. Both had to go.\n\n## The two rounds of repair [#](#the-two-rounds-of-repair)\n\n### First round: fast paths in the grammar [#](#first-round-fast-paths-in-the-grammar)\n\nThe first round was micro-optimization of the grammar. It helped, though not where I expected.\n\nThe scheme alternation used to be fifteen whole-string comparisons.\n\n```\n(define-peg-pattern url-scheme all\n (or \"http://\" \"https://\" \"ftp://\" \"ftps://\"\n \"file://\" \"ssh://\" \"sftp://\" \"ws://\" \"wss://\"\n \"git://\" \"gopher://\" \"tel:\" \"mailto:\"\n \"irc://\" \"ircs://\"))\n```\n\nGrouping the alternatives by first character means a position that can’t begin a scheme fails after one comparison instead of fifteen.\n\n```\n(define-peg-pattern url-scheme all\n (or (and \"h\" (or \"ttps://\" \"ttp://\"))\n (and \"f\" (or \"tps://\" \"tp://\" \"ile://\"))\n (and \"s\" (or \"sh://\" \"ftp://\"))\n (and \"w\" (or \"ss://\" \"s://\"))\n (and \"g\" (or \"opher://\" \"it://\"))\n \"tel:\"\n \"mailto:\"\n (and \"i\" (or \"rcs://\" \"rc://\"))))\n```\n\nThe alternation of inline constructs was badly ordered too. It tried the multi-character constructs, footnotes, links and the scheme scan before the single-character markers, so a line full of `*bold*` and `/italic/` paid for the expensive branches first. Putting the one-character markers first and the link and URL machinery last costs nothing.\n\n```\n(define-peg-pattern inline-special body\n (or inline-bold inline-italic inline-code inline-verbatim\n inline-underline inline-strike\n inline-superscript inline-subscript\n inline-line-break inline-escape\n inline-footnote-inline inline-footnote-def inline-footnote-ref\n inline-link-with-desc inline-link-no-desc\n inline-raw-url))\n```\n\nI also added a hand-written class for plain characters, so ordinary text gets taken with a few range tests instead of a `not-followed-by` check against the whole inline grammar at every position.\n\nThe result: the inline benchmark doubled, the document benchmarks improved by about a third, and **the single-line case didn’t move at all**. That last bit was the useful part, because it said the remaining cost wasn’t in the grammar.\n\n### Second round: run scanners [#](#second-round-run-scanners)\n\nA compiled PEG pattern in Guile is just a procedure of `(string length position)` returning `(end . body)` or `#f`. Nothing stops you writing that procedure by hand and naming it in the grammar like any other pattern. That’s the whole idea of the run scanners: find the end of the run in one C-level scan with `string-index` and return a single substring.\n\n```\n(define (run-end str len pos stop-chars stop?)\n \"Return the end of the run from POS that stops at the first character\nof STOP-CHARS at which STOP? holds, or at LEN.\"\n (let loop ((i pos))\n (let ((candidate (or (string-index str stop-chars i len) len)))\n (if (or (>= candidate len) (stop? str len candidate))\n candidate\n (loop (1+ candidate))))))\n\n(define (text-run str len pos stop-chars stop?)\n (let ((end (run-end str len pos stop-chars stop?)))\n (list end (substring str pos end))))\n\n(define (line-text-scanner str len pos)\n \"Consume the rest of the line as one string.\"\n (text-run str len pos nl-chars always-stop))\n\n(define-peg-pattern line-content all line-text-scanner)\n```\n\nThere are thirteen such scanners now, one for each construct whose body is “text up to a delimiter”: a line, a table cell, a link target, a link description, a footnote body, a keyword value, the body of a source block, a description key, the body of a raw URL.\n\nThe delicate part is the `stop?` predicate. For a line, every newline really does end the run. For inline text, an asterisk ends the run only if `inline-special` really matches there; otherwise it’s an asterisk in the middle of a sentence. So the scanner stops at every candidate, asks the grammar whether something begins there, and if not, continues past that character. Still one `string-index` call per candidate, and there’s at most one candidate per markup character in a line.\n\nThirteen scanners would be a maintenance problem if each had its own idea of where text ends, so the character sets live in one place, each with a comment saying who stops there.\n\n```\n(define nl-chars (char-set #\\newline #\\return))\n(define table-stop-chars (char-set #\\| #\\newline #\\return))\n(define inline-stop-chars\n ;; every character that can begin an inline construct: the markup markers,\n ;; the letters a raw URL scheme can start with, and the newline\n (char-set #\\* #\\/ #\\~ #\\= #\\_ #\\+ #\\^ #\\\\ #\\[\n #\\h #\\f #\\s #\\w #\\g #\\t #\\m #\\i #\\r\n #\\newline #\\return))\n(define link-stop-chars (char-set #\\] #\\newline #\\return))\n```\n\n### Second round, second part: a linear collapse pass [#](#second-round-second-part-a-linear-collapse-pass)\n\nThe other half was dropping the quadratic `string-collapse`. The library now has its own `collapse-tree`, keeping the exact contract of Guile’s procedure: children collapsed before their parent, a maximal run of adjacent strings concatenated, a list of strings not joining the run around it, a one-element result unwrapped. The difference is that grouping happens in one pass with one `reverse`.\n\n```\n(define (string-group-linear lst)\n (let loop ((nodes lst) (run '()) (out '()))\n (cond\n ((null? nodes)\n (reverse (if (null? run) out (cons (reverse run) out))))\n ((string? (car nodes))\n (loop (cdr nodes) (cons (car nodes) run) out))\n (else\n (loop (cdr nodes) '()\n (if (null? run)\n (cons (car nodes) out)\n (cons (car nodes) (cons (reverse run) out))))))))\n```\n\nSame contract, not merely a similar one, so it produces identical trees. That’s what let me prove the rewrite safe instead of hoping it was. On its own it’s about 530× faster at 32,000 fragments.\n\n## The measurements [#](#the-measurements)\n\nEverything below was measured in the project’s Guix shell with Guile 3.0.9, on the Ryzen 5 7640U laptop I write on, with a browser open. Five runs per workload, fastest reported. Three columns: before any optimization, after the grammar fast paths, and now.\n\n| Workload | Before (µs) | Fast paths (µs) | Now (µs) | Total speed-up |\n| --- | --- | --- | --- | --- |\n| Parse the feature fixture (1.8 KB) | 790 | 590 | 320 | 2.5× |\n| Parse README.org (58 KB) | 32,200 | 23,600 | 5,070 | 6.4× |\n| Render the fixture to HTML | 3,480 | 2,360 | 1,840 | 1.9× |\n| Render the fixture to Markdown | 3,090 | 2,250 | 1,690 | 1.8× |\n| Parse a 50-clause inline paragraph | 6,010 | 3,070 | 2,270 | 2.7× |\n\nThe allocation table tells the same story from the other side.\n\n| Workload | Before (KiB/op) | Fast paths (KiB/op) | Now (KiB/op) |\n| --- | --- | --- | --- |\n| Parse the feature fixture | 900 | 620 | 230 |\n| Parse README.org | 30,300 | 19,700 | 3,890 |\n| Render the fixture to HTML | 3,310 | 2,200 | 1,360 |\n| Render the fixture to Markdown | 3,140 | 2,160 | 1,360 |\n| Parse the 50-clause inline paragraph | 5,660 | 2,740 | 1,690 |\n\nParsing the 58 KB README now allocates about 68 bytes per input byte, where it used to allocate roughly 530. That’s the difference between a parse that reliably triggers a collection of its own and one that often doesn’t.\n\n### One long line: from eight seconds to a third of a millisecond [#](#one-long-line-from-eight-seconds-to-a-third-of-a-millisecond)\n\nThe clearest way to see the quadratic is to hold everything else constant and grow a single line. Here’s a document whose entire content is one line of plain prose.\n\n| Line length | Before (ms) | Fast paths (ms) | Now (ms) |\n| --- | --- | --- | --- |\n| 5 KB | 26.4 | 26.3 | 0.07 |\n| 10 KB | 109 | 105 | 0.08 |\n| 20 KB | 423 | 408 | 0.12 |\n| 40 KB | 1,760 | 1,630 | 0.22 |\n| 80 KB | 8,180 | 7,110 | 0.37 |\n\nRead the first two columns: each doubling of the line multiplies the time by four. That’s a quadratic curve, and the grammar fast paths barely dented it, because per-character fragments and a quadratic merge are exactly what grammar fast paths don’t touch. Now the third column: each doubling roughly doubles the time, because `string-index` runs at memory speed and there’s one fragment per line instead of one per character.\n\nAt 80 KB that’s a factor of about 22,000. That’s the extreme end of the curve, though. The realistic headline is the 6.4× on the README, where the time is spread over a whole document instead of concentrated in one pathological line.\n\n### The collapse pass on its own [#](#the-collapse-pass-on-its-own)\n\nTo separate the two effects I benchmarked Guile’s `string-collapse` against the library’s `collapse-tree` on plain lists of string fragments, with no parser and no renderers involved.\n\n| Fragments | `string-collapse` (ms) | `collapse-tree` (ms) |\n| --- | --- | --- |\n| 2,000 | 3.8 | 0.09 |\n| 4,000 | 15.4 | 0.17 |\n| 8,000 | 58.6 | 0.37 |\n| 16,000 | 241 | 0.72 |\n| 32,000 | 1,000 | 1.9 |\n\nFour times per doubling on the left, two on the right. That’s the whole profile in one table.\n\n### What the profile looks like now [#](#what-the-profile-looks-like-now)\n\nThe point of a rewrite is that the profile stops pointing at one thing. Parsing the README two hundred times now gives this.\n\n```\n% cumulative self procedure\n 26.32 0.75 0.75 %after-gc-thunk\n 8.27 0.41 0.24 string-append\n 6.02 0.17 0.17 string=\n 4.51 0.24 0.13 orgwebalchemy/peg.scm:99:0\n 4.51 0.15 0.13 reverse\n 3.76 0.15 0.11 string-group-linear\n 3.01 1.43 0.09 orgwebalchemy/peg.scm:375:0\n 2.26 1.86 0.06 collapse-tree\n```\n\nThe biggest entry now is the collector itself, about a quarter of the time. Then the string work that building a tree implies, then the collapse pass at a few percent, then a long tail of small pattern procedures. No more 97%. Further gains have to come from allocating less, not from finding another bottleneck.\n\n## Why you can believe the measurements [#](#why-you-can-believe-the-measurements)\n\nSpeed is easy to claim and easy to fake, because you can make any parser faster by making it wrong. Since the work touched the scanners that decide where text ends, I needed a way to show the language hadn’t changed.\n\n### Equivalence with the previous parser [#](#equivalence-with-the-previous-parser)\n\nThe test suites can’t express “the parser still does what it did before”, because they encode what it ought to do. So there’s a separate check that loads the old parser and the new one into one process — the old one under renamed modules pulled out with `git show REV:src/orgwebalchemy/peg.scm` and its neighbors — and compares six results for every input: the document tree, the inline tree, and the HTML and Markdown each renderer writes.\n\nThe scanner rewrite was checked this way on about 70,000 inputs. Those included every pair of interesting characters (printable ASCII, tab, newline, carriage return, the other control characters and two multi-byte characters) as documents, as inline text, and inside a link, a footnote and a description list; the README; the test fixtures; hand-written edge cases such as markup at every position, tables with empty cells and lines without a newline; and about 6,000 randomly generated documents.\n\nThe empty-value change was checked again on about 38,000 of those inputs. It reported about 230 differences, every one of them a change I’d made on purpose. More interesting: it found no input that raised an error on the new side, where the old code raised on 21 of them, each a table row with no cells in it. That’s how a bug fix should show up — as a difference you can name and explain.\n\nThe table change was checked on about 38,000 inputs and found 16 that parse differently. All 16 were table lines whose last bar is followed by nothing but the end of the line, which is exactly what changed.\n\n### The stop set [#](#the-stop-set)\n\nA run scanner may leap over a character only if it’s sure that character can’t begin a construct. Get that set wrong by one character and the scanner silently swallows the beginning of a link or a footnote, and no equivalence test against the previous parser would catch it, because the previous parser had no scanners at all.\n\nSo `inline-stop-chars` is checked against the grammar itself: at every position where `inline-special` really matches, the character that begins it must be in the set. Sweeping about 390,000 positions of the README, the fixtures, every pair of bytes and some random markup found about 6,000 constructs and no gap.\n\n### Three deliberate differences [#](#three-deliberate-differences)\n\nThree differences came out of these runs, all now pinned down by tests.\n\n1. A run of two or more `#+CAPTION:` or `#+NAME:` lines before an element that isn’t a figure used to come out of the folding step in reverse order. It now keeps document order, which is what the docs always claimed and what a reader expects of anything called a sequence.\n2. The text of something empty is now the empty string, instead of the bare tag symbol an empty match leaves behind. This is what keeps an empty cell in its column, keeps a source block without a language rendering as a source block, and keeps an empty keyword, comment, fixed-width line, footnote or block in the document instead of letting it vanish.\n3. A table row is read by its bars, as described above.\n\nEverything else produces identical output, and the naming feature is an addition to the language, so it’s covered by tests rather than equivalence.\n\n### A trap when adding tests [#](#a-trap-when-adding-tests)\n\nOne trap is worth recording, because I lost an afternoon to it. Veritas collects a test’s assertions by filtering the body for procedures, so assertions wrapped in a `let`, a `when` or a `parameterize` are silently reduced to the last one. Keep every assertion at the top level of the test body, and call a helper when you need a parameterization. The tests for the class parameters show the pattern.\n\n## What is still expensive [#](#what-is-still-expensive)\n\nHonesty is part of the design, so here’s what these numbers don’t say.\n\n- **Inline parsing is the most expensive stage per byte.** A 50-clause paragraph of inline markup, 4.1 KB, takes 2.3 ms, about 1.8 MB per second, against 11 MB per second for a whole document of prose. Some of that is inherent in a grammar where every position has to try the alternatives. Still, it’s the number I’d attack next.\n- **Allocation is still dominated by the tree.** About 68 bytes of allocation per input byte, and a quarter of the parse is the collector. A cheaper node representation, or flattening parts of the tree while parsing, would buy real time.\n- **There’s no incremental path.** A changed document is parsed from the beginning. For an editor or a live preview, that’s the feature that would matter most, and the one I most want to write.\n- **The benchmarks measure this implementation on its own.** They don’t compare it with other Org implementations, and they don’t measure the incremental case. Both would be welcome additions.\n\n## What Org has that this library does not [#](#what-org-has-that-this-library-does-not)\n\nThe manual has a “Current limitations” section so this article doesn’t have to pretend. The known gaps:\n\n- **Captions on non-figures.** A `#+CAPTION:` before a table, a source block or a block quote is still an ordinary keyword line, because those captions aren’t rendered yet. Figures are the exception, and they’re done.\n- **Bare superscripts and subscripts.** Only the braced forms, `x^{2}` and `H_{2}O`, are recognized. Bare forms like `x^2` are not, deliberately, since they can’t always be told apart from ordinary text.\n- **Babel, the agenda, the export dispatcher.** OrgWebAlchemy is a library, not an Emacs package. It parses Org; it doesn’t execute code blocks and doesn’t hook into Org’s export machinery.\n- **The long tail.** Org has years of conventions in it: `#+ATTR_HTML`, `#+RESULTS`, column width cookies, archived subtrees, custom TODO sequences read from the document, and more. Each one needs a decision about whether to parse it, render it or leave it as text, and this library would rather leave it as text than guess.\n\nIf one of these gets in your way, that’s exactly the kind of report worth sending, ideally with the smallest Org snippet that shows the problem.\n\n## Distribution [#](#distribution)\n\nA library nobody can install is a library nobody uses, so packaging caught up too.\n\n- **Guix.** A self-contained package recipe is in the manual, pinned at version 1.2.1 with its hash, and the project is on its way into Guix itself as `guile-orgwebalchemy`.\n- **Nix.** A `flake.nix` and a `default.nix` build the working tree with the same derivation as the nixpkgs package, so a change that breaks one breaks the other for the same reason. They cover x86\\_64 and aarch64, on GNU/Linux and on Darwin.\n- **Continuous integration.** Pushes to `trunk` trigger a Woodpecker pipeline that submits the `maak-test` and `maak-deploy` tasks to [Byggsteg](https://byggsteg.jointhefreeworld.org), my own CI system, itself written in Scheme.\n- **Documentation.** The manual is the library’s README, and the API reference is generated from the docstrings in the source with `guile-documenta`: [the OrgWebAlchemy API documentation](https://jointhefreeworld.org/api-docs/orgwebalchemy/API.html).\n\n## Reproduce the measurements [#](#reproduce-the-measurements)\n\nEvery number here comes from the repository and from commands the manual documents. If you want to check my work:\n\n```\ngit clone https://codeberg.org/jjba23/orgwebalchemy.git\ncd orgwebalchemy\n\n# the unit suite\nguix shell -m manifest.scm -- guile -L ./src -L ./test \\\n -c '((@ (veritas runner) run-tests))'\n\n# the benchmarks (they print the tables above)\nVERITAS_TEST_TYPE=benchmark \\\nguix shell -m manifest.scm -- guile -L ./src -L ./test \\\n -c '((@ (veritas runner) run-tests))'\n```\n\nRun them yourself. If your numbers differ a lot from mine, I’d like to know — a parser that’s fast on one laptop and slow on another has a wrong assumption hidden in it.\n\n## What I take from this [#](#what-i-take-from-this)\n\nThe lesson I keep relearning here is that correctness and speed aren’t two phases of the work. Writing the scanners forced me to state exactly which characters can begin a construct, and that list is now a specification a test sweeps about 390,000 positions. The equivalence harness that showed the rewrite was safe is also the reason I dared attempt it.\n\nWhich brings me to the larger point, the reason I care about parsing Org at all. Org mode is one of the good ideas of our time: plain text people can read and write without special software, meaning that survives the programs, grown inside a free editor where its users could extend it. Every program that can read Org makes the format a bit more useful, and a format more programs can read is one people can trust with years of their writing.\n\nThis library is a small contribution to that. It lets a Scheme program read what you wrote in Org, render it as HTML a browser can show without running anyone else’s code, or as Markdown other tools understand — under a free license, on your machine, with source you can read. The web has no shortage of ways to take a document away from its author. I’d like to add one more way to give it back.\n\n## Links [#](#links)\n\n- Source code:OrgWebAlchemy is a Guile library that parses Org mode with a Parsing Expression Grammar and renders it to HTML, Markdown, or SXML. I wrote an earlier article about why a PEG is the right tool for Org: the grammar describes the language, the parser builds a tree, the renderers turn that tree into output.
\nThis is the follow-up, and it turned into a harder question than I expected: how do you make a parser fast without making it wrong? I didn’t want something that’s quick on my test files and quietly behaves differently on yours.
\nSo: the features I added, how I measured them, what the profiler said, the two rounds of fixes, and how I checked the language didn’t change. Every number below comes with a way to reproduce it, because a number you can’t check is advertising, not evidence.
\nTLDR; Here is the whole article in five sentences:
\n![\"One](\"https://codeberg.org/jjba23/orgwebalchemy/media/branch/trunk/assets/orgwebalchemy-demo.gif\")
OrgWebAlchemy is free software under the GNU Lesser General Public License, version 3 or later, with this documentation under the GNU Free Documentation License. Run it, study it, change it, ship your changed versions.
\nIt could have been a service instead: you send your Org file to a server you don’t control, and get HTML back. That can be convenient, and it can even be gratis, but it leaves you helpless in the ways that matter. You can’t study it, can’t fix it, and can’t keep using it when the operator loses interest or changes the terms. A library goes into your program, on your machine, under your control.
\nThe LGPL is a compromise, and I’ll name it as one. The GPL would keep every program that uses this code free too, and that’s the stronger guarantee for users. For libraries the GNU Project has long accepted a weaker license so that more programs can use them, including some that aren’t free, and I’ve followed that tradition. Use it in a free program and you’re helping the community; use it in a nonfree one and I’d rather you made that program free.
\nThere’s a second reason it’s a library. Org mode is a language, and a language is worth as much as the number of programs that can read it. A parser only Emacs can use is a parser for one program. One that any Guile program can call is a parser for a text editor, a static site generator, a wiki, a notebook, a mail archiver, a package’s docs build, or something nobody has written yet. I don’t know what you’ll build with it, and that’s the point.
\nAnd a word on what it isn’t: it’s not Emacs and doesn’t try to be. Emacs is where Org lives, where it gets edited, and where its export machinery started. OrgWebAlchemy doesn’t replace that, it just lets other Scheme programs read the same files. When it disagrees with Emacs about some corner of the syntax, Emacs is right and this is a bug.
\nOrgWebAlchemy is still three small modules. What changed is how much of the language each one covers.
\n| Module | Lines | What it owns |
|---|---|---|
(orgwebalchemy peg) | 1,700 | the grammar, the AST, the run scanners, link classification, name resolution |
(orgwebalchemy html) | 720 | rendering to HTML and SXML, and every CSS class parameter |
(orgwebalchemy markdown) | 430 | rendering the same AST to Markdown |
| Test suite | 1,670 | 155 test definitions and 281 assertions, many of them table-driven |
The API is still small enough to hold in your head.
\n(use-modules (orgwebalchemy html)\n (orgwebalchemy markdown)\n (orgwebalchemy peg))\n\n(org->html "This is ~test~ code.")\n;; => "This is <code>test</code> code."\n\n(org->markdown "This is ~test~ code.")\n;; => "This is `test` code."\n\n;; parse once, render as often as you like\n(define ast (org->ast "* Hello\\nA *bold* line.\\n"))\n(org-ast->html ast)\n(org-ast->markdown ast)The rest of this article is about what happens between those calls.
\n“Supporting Org” hides a lot of work, because Org isn’t a markup language with a tidy grammar. It’s a pile of conventions accumulated over years of a GNU Emacs major mode, some of them deliberately informal, and each one has to be considered on its own terms. Every feature below started as a sentence in the Org manual, became a grammar pattern, then became a test.
\nAn Org link’s target says what kind of link it is. A target starting with https:// is external. file:photo.png is a file, and so is a bare notes.org. #custom-id points inside the document, *Heading at a heading, and a ::search suffix says where inside the target you land.
The old code let each renderer read the target and decide for itself, which is exactly how two back ends drift apart. HTML grows a special case for image extensions, Markdown grows a slightly different one, and after a year of small repairs the same document means two things depending on which function you call. A user who notices won’t know which one is right, and will be right not to trust either.
\nSo classification moved into the parser, where it happens once.
\n(org-link-parts "https://example.org/a") ;; => (https . "//example.org/a")\n(org-link-parts "file:photo.png") ;; => (file . "photo.png")\n(org-link-parts "notes.org") ;; => (file . "notes.org")\n(org-link-parts "#custom-id") ;; => (internal . "custom-id")\n(org-link-parts "*My Section") ;; => (heading . "My Section")\n(org-link-parts "notes.org::*Heading") ;; => (file . "notes.org")\n(org-link-search "notes.org::*Heading") ;; => "*Heading"\n(org-image-link? "photo.jpeg?raw=1") ;; => #tBoth renderers then ask the same questions and follow the same answer.
\n| Org | HTML | Markdown |
|---|---|---|
[[file:photo.png][a photo]] | <img src="photo.png" alt="a photo" /> |  |
[[images/diagram.svg]] | <img src="images/diagram.svg" alt="..." /> |  |
[[file:notes.org][notes]] | <a href="notes.org">notes</a> | [notes](notes.org) |
[[#custom-id][there]] | <a href="#custom-id">there</a> | [there](#custom-id) |
[[*My Section][up]] | <a href="#my-section">up</a> | [up](#my-section) |
[[https://gnu.org][GNU]] | <a href="https://gnu.org">GNU</a> | [GNU](https://gnu.org) |
Two details deserve a sentence each. The ::search suffix is set aside before the path is used as a file name, so file:notes.org::*Heading doesn’t produce a broken file name. And C:/tmp/x.txt isn’t mistaken for a link with a scheme named c, because a real scheme is lower case. Small stuff, but it’s the kind of small stuff that decides whether a program is pleasant to use on somebody else’s computer.
Org gives the element after a #+CAPTION: or #+NAME: keyword a caption and a name. When that element is a link to an image, the three things are one object: a figure. The parser folds them together, so renderers get a single node instead of three neighbors they have to guess about.
(org->html "#+NAME: fig:arch\\n#+CAPTION: The architecture\\n[[file:diagram.png][a diagram]]\\n")\n;; => "<figure id=\\"fig:arch\\"><img src=\\"diagram.png\\" alt=\\"a diagram\\" /><figcaption>The architecture</figcaption></figure>"The name the figure carries is the identifier that a [[fig:arch]] link resolves to, so the cross-reference can’t break. Both facts come from one place, and one place can’t disagree with itself.
(org->html "#+NAME: fig:arch\\n#+CAPTION: The arch\\n[[file:a.png]]\\n\\nSee [[fig:arch]].\\n")\n;; => "<figure id=\\"fig:arch\\">...</figure><p>See <a href=\\"#fig:arch\\">fig:arch</a>.</p>"Markdown has no figure element, so it gets the image, the caption as an emphasised line, and an explicit anchor for the cross-reference. What counts as a figure is deliberately narrow: the keywords must sit immediately before a paragraph holding exactly one image link and nothing else. Everything else stays a keyword line. Inventing a caption for an element this parser doesn’t caption is worse than saying nothing, because the reader would never learn that something got silently dropped.
A figure is the image case of a more general rule. A #+NAME: line names the element after it, and anything that renders as something a link can land on can be named: a table, a source block, a quote, a list, a separator, a paragraph.
(org->html "#+NAME: tbl:users\\n| Users | 1024 |\\n\\nSee [[tbl:users]].\\n")\n;; => "<table id=\\"tbl:users\\">...</table><p>See <a href=\\"#tbl:users\\">tbl:users</a>.</p>"HTML puts the identifier on the element itself. Markdown has nothing to hang it on, so it emits an anchor in front, same as for a figure. A bare target that matches the name of an element in the same document resolves as a cross-reference, which is why [[tbl:users]] and [[notes]] work. A target that already says what it is — a scheme, a file: prefix, a leading # or *, or a ::search suffix — keeps the meaning it wrote.
One asymmetry, documented rather than hidden: a #+CAPTION: in front of a named table isn’t folded into it, because captions on tables aren’t rendered yet. The line stays an ordinary keyword line where the writer put it.
Tables looked finished until I looked at the edges. What should | on a line of its own be? What is | a ||? What happens to a row that ends the input with no newline?
The old pattern counted separators and made one cell for each, which meant a row with no cells could raise an error, and a row that ended the input got a phantom empty cell from the newline it didn’t have. The rewrite reads a row the way Org does: by the bars that separate the cells, where a bar closes a row when nothing but the end of the line follows it. That one rule answers all three questions.
\n| on its own) is a row of one empty cell, not a row with no cells.| a || is a row of two cells, the second of them empty, rather than a paragraph.An empty cell also keeps its column, because an empty value is now the empty string instead of the bare tag symbol that an empty (* ...) match leaves behind. The difference sounds academic until it is your table.
Org lets a list change its bullet type part-way through, and it lets a nested list use a different kind from its parent. So the grammar stopped having three separate list productions and grew one.
\n(define-peg-pattern org-list all\n (+ (or desc-item unordered-item ordered-item)))The renderers group consecutive items of the same kind into the proper element, which is what makes - outer with 1. nested inside it come out as an unordered list containing an ordered one. Checkboxes, description items and arbitrary nesting depth follow from the same rule.
Between those features and the earlier work, the supported set is now: headings with TODO keywords, priorities and tags; paragraphs; unordered, ordered and description lists in any mixture and at any depth; checkboxes; tables with empty cells; source, example, quote, verse, center, export and comment blocks; keywords and in-buffer settings; comments; fixed-width lines; separators; footnotes, whether references, definitions or inline; bold, italic, underline, strikethrough, code, verbatim, superscript, subscript, escaped markup and forced line breaks; links with and without descriptions, bare URLs, images, figures, named elements and heading anchors.
\nThat’s most of what people actually write. Not all of Org, and the manual has a section listing the gaps instead of hiding them, because a library that lies about its coverage just wastes everyone’s time.
\nBefore optimizing anything I wanted a benchmark that could tell me whether a change helped, and that couldn’t be fooled by the change itself.
\nThe benchmarks live in test/veritas/benchmark/scope.scm. They use the same Veritas framework as the unit suite, selected by test type so they never slow down maak test.
VERITAS_TEST_TYPE=benchmark \\\nguix shell -m manifest.scm -- guile -L ./src -L ./test \\\n -c '((@ (veritas runner) run-tests))'The suite measures five workloads and prints three tables — wall clock, allocation, and the collapse pass — formatted as Markdown, ready to paste into the manual. That last part matters: a number you have to retype by hand quietly stops being true.
\n| Workload | What it exercises |
|---|---|
| Parse the feature fixture | every construct the parser knows, in 1.8 KB |
| Parse README.org | a real 58 KB document with prose, tables and code blocks |
| Render the feature fixture to HTML | parsing plus the HTML renderer |
| Render the feature fixture to Markdown | parsing plus the Markdown renderer |
| Parse a 50-clause inline paragraph | the inline grammar, under maximum pressure |
One wall clock reading on a laptop isn’t a measurement, it’s a rumor. The suite runs each workload five times and reports the fastest, on the theory that the other four got interrupted by a browser, a compiler, or the collector arriving at a bad moment.
\nIt’s not statistically pure and I won’t pretend it is. It’s a lower bound on the cost of the work, measured on a machine that’s also doing other things. Allocation is the stable half and stays within a few percent; wall clock moves 10–20% between sessions. Repeat it and get a different number and you’ve found the noise, not an error. Be suspicious of anyone who reports wall clock figures without it.
\nGuile’s collector is good enough that you can write a parser allocating a megabyte per kilobyte of input and still call it fast, right up until it’s in a server serving several documents at once. So the suite measures the heap too. The heap is collected before each workload, and what’s reported is heap-total-allocated: everything the workload asked for, including garbage it dropped immediately. That’s allocation pressure, the thing that triggers collections, not the memory a result keeps.
The last column is Guile’s gc-time-taken, which is collector processor time. Guile sums its marker threads, so one full collection of a big heap can be reported as several times its wall clock cost on a many-core machine. Read it as how much collector work a workload causes, not as a share of the clock. Same note is in the benchmark’s docstring, because an easy-to-misread number will get misread.
The last measurement in the suite is the one that eventually explained everything: how many string fragments a parse hands to the pass that merges them, and how long the merging takes.
\nTake a pattern written as (* (and (not-followed-by eol) peg-any)), meaning “consume characters until the newline”. The compiled pattern produces one parse object and one string fragment per character. A line of n characters costs n one-character substrings, n list cells, and a merge over all of them. On a document of short lines nobody notices; on a 45 KB line it’s the whole program.
The fragment table made that visible with no profiling at all.
\n| Document | Fragments handed to the collapse pass | Collapse (ms) |
|---|---|---|
| Feature fixture (1.8 KB) | 82 | 0.04 |
| README.org (58 KB) | 1,264 | 0.39 |
| Plain prose (32 KB) | 400 | 0.22 |
| One 45 KB line | 1 | 0.005 |
The last row is the interesting one. Forty-five kilobytes of text arrive as a single fragment, because a run scanner took them in one substring instead of forty-five thousand. The README, 58 KB of input, arrives as about 1,300 fragments — roughly one per line of prose instead of one per character.
\nVeritas profiles every benchmark with Guile’s statprof, and that’s what turned a vague feeling that big files were slow into a statement about one procedure.
I fed the old parser a document made of one 40 KB line and looked at the profile.
\n% cumulative self procedure\n 97.55 1.77 1.77 list?\n 0.61 115.98 0.01 ice-9/boot-9.scm:220:5:map1\n 0.61 0.03 0.01 orgwebalchemy/peg.scm:339:0\n 0.61 0.01 0.01 reverse\n 0.00 23786.61 0.00 ice-9/peg/simplify-tree.scm:48:0:string-group\n 0.00 3.56 0.00 ice-9/peg/simplify-tree.scm:65:0:string-collapse97.5% of the time is inside list?. Not the grammar, not the renderers, not any of my own code: one predicate, called by Guile’s own tree simplifier.
My hypothesis was that the PEG engine was slow. The truth was a helper in (ice-9 peg simplify-tree) asking (list? lst) of the rest of the list at every level of its recursion, which walks the list quadratically.
Here is the relevant part of string-group.
(define (string-group lst)\n (if (not (list? lst)) ;; <- O(length) at every level\n lst\n (if (null? lst)\n '()\n (let ((next (string-group (cdr lst)))) ;; non-tail recursion\n ...))))For a run of n fragments that’s about n²/2 list steps. A line of 40,000 characters means 800 million of them, which is exactly the 1.77 seconds in the profile. Doubling the line quadruples the bill, and the measurements agree: 20 KB took about 420 ms, 40 KB about 1,760 ms.
So there were two problems and only one was mine. My grammar produced one fragment per character, handing the quadratic pass an enormous run to chew on. And the collapse pass was quadratic in the length of a run, so even a modest run cost more than it should. Fix only the first and a slow path waits for anyone who writes a long line; fix only the second and you still allocate megabytes for nothing. Both had to go.
\nThe first round was micro-optimization of the grammar. It helped, though not where I expected.
\nThe scheme alternation used to be fifteen whole-string comparisons.
\n(define-peg-pattern url-scheme all\n (or "http://" "https://" "ftp://" "ftps://"\n "file://" "ssh://" "sftp://" "ws://" "wss://"\n "git://" "gopher://" "tel:" "mailto:"\n "irc://" "ircs://"))Grouping the alternatives by first character means a position that can’t begin a scheme fails after one comparison instead of fifteen.
\n(define-peg-pattern url-scheme all\n (or (and "h" (or "ttps://" "ttp://"))\n (and "f" (or "tps://" "tp://" "ile://"))\n (and "s" (or "sh://" "ftp://"))\n (and "w" (or "ss://" "s://"))\n (and "g" (or "opher://" "it://"))\n "tel:"\n "mailto:"\n (and "i" (or "rcs://" "rc://"))))The alternation of inline constructs was badly ordered too. It tried the multi-character constructs, footnotes, links and the scheme scan before the single-character markers, so a line full of *bold* and /italic/ paid for the expensive branches first. Putting the one-character markers first and the link and URL machinery last costs nothing.
(define-peg-pattern inline-special body\n (or inline-bold inline-italic inline-code inline-verbatim\n inline-underline inline-strike\n inline-superscript inline-subscript\n inline-line-break inline-escape\n inline-footnote-inline inline-footnote-def inline-footnote-ref\n inline-link-with-desc inline-link-no-desc\n inline-raw-url))I also added a hand-written class for plain characters, so ordinary text gets taken with a few range tests instead of a not-followed-by check against the whole inline grammar at every position.
The result: the inline benchmark doubled, the document benchmarks improved by about a third, and the single-line case didn’t move at all. That last bit was the useful part, because it said the remaining cost wasn’t in the grammar.
\nA compiled PEG pattern in Guile is just a procedure of (string length position) returning (end . body) or #f. Nothing stops you writing that procedure by hand and naming it in the grammar like any other pattern. That’s the whole idea of the run scanners: find the end of the run in one C-level scan with string-index and return a single substring.
(define (run-end str len pos stop-chars stop?)\n "Return the end of the run from POS that stops at the first character\nof STOP-CHARS at which STOP? holds, or at LEN."\n (let loop ((i pos))\n (let ((candidate (or (string-index str stop-chars i len) len)))\n (if (or (>= candidate len) (stop? str len candidate))\n candidate\n (loop (1+ candidate))))))\n\n(define (text-run str len pos stop-chars stop?)\n (let ((end (run-end str len pos stop-chars stop?)))\n (list end (substring str pos end))))\n\n(define (line-text-scanner str len pos)\n "Consume the rest of the line as one string."\n (text-run str len pos nl-chars always-stop))\n\n(define-peg-pattern line-content all line-text-scanner)There are thirteen such scanners now, one for each construct whose body is “text up to a delimiter”: a line, a table cell, a link target, a link description, a footnote body, a keyword value, the body of a source block, a description key, the body of a raw URL.
\nThe delicate part is the stop? predicate. For a line, every newline really does end the run. For inline text, an asterisk ends the run only if inline-special really matches there; otherwise it’s an asterisk in the middle of a sentence. So the scanner stops at every candidate, asks the grammar whether something begins there, and if not, continues past that character. Still one string-index call per candidate, and there’s at most one candidate per markup character in a line.
Thirteen scanners would be a maintenance problem if each had its own idea of where text ends, so the character sets live in one place, each with a comment saying who stops there.
\n(define nl-chars (char-set #\\newline #\\return))\n(define table-stop-chars (char-set #\\| #\\newline #\\return))\n(define inline-stop-chars\n ;; every character that can begin an inline construct: the markup markers,\n ;; the letters a raw URL scheme can start with, and the newline\n (char-set #\\* #\\/ #\\~ #\\= #\\_ #\\+ #\\^ #\\\\ #\\[\n #\\h #\\f #\\s #\\w #\\g #\\t #\\m #\\i #\\r\n #\\newline #\\return))\n(define link-stop-chars (char-set #\\] #\\newline #\\return))The other half was dropping the quadratic string-collapse. The library now has its own collapse-tree, keeping the exact contract of Guile’s procedure: children collapsed before their parent, a maximal run of adjacent strings concatenated, a list of strings not joining the run around it, a one-element result unwrapped. The difference is that grouping happens in one pass with one reverse.
(define (string-group-linear lst)\n (let loop ((nodes lst) (run '()) (out '()))\n (cond\n ((null? nodes)\n (reverse (if (null? run) out (cons (reverse run) out))))\n ((string? (car nodes))\n (loop (cdr nodes) (cons (car nodes) run) out))\n (else\n (loop (cdr nodes) '()\n (if (null? run)\n (cons (car nodes) out)\n (cons (car nodes) (cons (reverse run) out))))))))Same contract, not merely a similar one, so it produces identical trees. That’s what let me prove the rewrite safe instead of hoping it was. On its own it’s about 530× faster at 32,000 fragments.
\nEverything below was measured in the project’s Guix shell with Guile 3.0.9, on the Ryzen 5 7640U laptop I write on, with a browser open. Five runs per workload, fastest reported. Three columns: before any optimization, after the grammar fast paths, and now.
\n| Workload | Before (µs) | Fast paths (µs) | Now (µs) | Total speed-up |
|---|---|---|---|---|
| Parse the feature fixture (1.8 KB) | 790 | 590 | 320 | 2.5× |
| Parse README.org (58 KB) | 32,200 | 23,600 | 5,070 | 6.4× |
| Render the fixture to HTML | 3,480 | 2,360 | 1,840 | 1.9× |
| Render the fixture to Markdown | 3,090 | 2,250 | 1,690 | 1.8× |
| Parse a 50-clause inline paragraph | 6,010 | 3,070 | 2,270 | 2.7× |
The allocation table tells the same story from the other side.
\n| Workload | Before (KiB/op) | Fast paths (KiB/op) | Now (KiB/op) |
|---|---|---|---|
| Parse the feature fixture | 900 | 620 | 230 |
| Parse README.org | 30,300 | 19,700 | 3,890 |
| Render the fixture to HTML | 3,310 | 2,200 | 1,360 |
| Render the fixture to Markdown | 3,140 | 2,160 | 1,360 |
| Parse the 50-clause inline paragraph | 5,660 | 2,740 | 1,690 |
Parsing the 58 KB README now allocates about 68 bytes per input byte, where it used to allocate roughly 530. That’s the difference between a parse that reliably triggers a collection of its own and one that often doesn’t.
\nThe clearest way to see the quadratic is to hold everything else constant and grow a single line. Here’s a document whose entire content is one line of plain prose.
\n| Line length | Before (ms) | Fast paths (ms) | Now (ms) |
|---|---|---|---|
| 5 KB | 26.4 | 26.3 | 0.07 |
| 10 KB | 109 | 105 | 0.08 |
| 20 KB | 423 | 408 | 0.12 |
| 40 KB | 1,760 | 1,630 | 0.22 |
| 80 KB | 8,180 | 7,110 | 0.37 |
Read the first two columns: each doubling of the line multiplies the time by four. That’s a quadratic curve, and the grammar fast paths barely dented it, because per-character fragments and a quadratic merge are exactly what grammar fast paths don’t touch. Now the third column: each doubling roughly doubles the time, because string-index runs at memory speed and there’s one fragment per line instead of one per character.
At 80 KB that’s a factor of about 22,000. That’s the extreme end of the curve, though. The realistic headline is the 6.4× on the README, where the time is spread over a whole document instead of concentrated in one pathological line.
\nTo separate the two effects I benchmarked Guile’s string-collapse against the library’s collapse-tree on plain lists of string fragments, with no parser and no renderers involved.
| Fragments | string-collapse (ms) | collapse-tree (ms) |
|---|---|---|
| 2,000 | 3.8 | 0.09 |
| 4,000 | 15.4 | 0.17 |
| 8,000 | 58.6 | 0.37 |
| 16,000 | 241 | 0.72 |
| 32,000 | 1,000 | 1.9 |
Four times per doubling on the left, two on the right. That’s the whole profile in one table.
\nThe point of a rewrite is that the profile stops pointing at one thing. Parsing the README two hundred times now gives this.
\n% cumulative self procedure\n 26.32 0.75 0.75 %after-gc-thunk\n 8.27 0.41 0.24 string-append\n 6.02 0.17 0.17 string=\n 4.51 0.24 0.13 orgwebalchemy/peg.scm:99:0\n 4.51 0.15 0.13 reverse\n 3.76 0.15 0.11 string-group-linear\n 3.01 1.43 0.09 orgwebalchemy/peg.scm:375:0\n 2.26 1.86 0.06 collapse-treeThe biggest entry now is the collector itself, about a quarter of the time. Then the string work that building a tree implies, then the collapse pass at a few percent, then a long tail of small pattern procedures. No more 97%. Further gains have to come from allocating less, not from finding another bottleneck.
\nSpeed is easy to claim and easy to fake, because you can make any parser faster by making it wrong. Since the work touched the scanners that decide where text ends, I needed a way to show the language hadn’t changed.
\nThe test suites can’t express “the parser still does what it did before”, because they encode what it ought to do. So there’s a separate check that loads the old parser and the new one into one process — the old one under renamed modules pulled out with git show REV:src/orgwebalchemy/peg.scm and its neighbors — and compares six results for every input: the document tree, the inline tree, and the HTML and Markdown each renderer writes.
The scanner rewrite was checked this way on about 70,000 inputs. Those included every pair of interesting characters (printable ASCII, tab, newline, carriage return, the other control characters and two multi-byte characters) as documents, as inline text, and inside a link, a footnote and a description list; the README; the test fixtures; hand-written edge cases such as markup at every position, tables with empty cells and lines without a newline; and about 6,000 randomly generated documents.
\nThe empty-value change was checked again on about 38,000 of those inputs. It reported about 230 differences, every one of them a change I’d made on purpose. More interesting: it found no input that raised an error on the new side, where the old code raised on 21 of them, each a table row with no cells in it. That’s how a bug fix should show up — as a difference you can name and explain.
\nThe table change was checked on about 38,000 inputs and found 16 that parse differently. All 16 were table lines whose last bar is followed by nothing but the end of the line, which is exactly what changed.
\nA run scanner may leap over a character only if it’s sure that character can’t begin a construct. Get that set wrong by one character and the scanner silently swallows the beginning of a link or a footnote, and no equivalence test against the previous parser would catch it, because the previous parser had no scanners at all.
\nSo inline-stop-chars is checked against the grammar itself: at every position where inline-special really matches, the character that begins it must be in the set. Sweeping about 390,000 positions of the README, the fixtures, every pair of bytes and some random markup found about 6,000 constructs and no gap.
Three differences came out of these runs, all now pinned down by tests.
\n#+CAPTION: or #+NAME: lines before an element that isn’t a figure used to come out of the folding step in reverse order. It now keeps document order, which is what the docs always claimed and what a reader expects of anything called a sequence.Everything else produces identical output, and the naming feature is an addition to the language, so it’s covered by tests rather than equivalence.
\nOne trap is worth recording, because I lost an afternoon to it. Veritas collects a test’s assertions by filtering the body for procedures, so assertions wrapped in a let, a when or a parameterize are silently reduced to the last one. Keep every assertion at the top level of the test body, and call a helper when you need a parameterization. The tests for the class parameters show the pattern.
Honesty is part of the design, so here’s what these numbers don’t say.
\nThe manual has a “Current limitations” section so this article doesn’t have to pretend. The known gaps:
\n#+CAPTION: before a table, a source block or a block quote is still an ordinary keyword line, because those captions aren’t rendered yet. Figures are the exception, and they’re done.x^{2} and H_{2}O, are recognized. Bare forms like x^2 are not, deliberately, since they can’t always be told apart from ordinary text.#+ATTR_HTML, #+RESULTS, column width cookies, archived subtrees, custom TODO sequences read from the document, and more. Each one needs a decision about whether to parse it, render it or leave it as text, and this library would rather leave it as text than guess.If one of these gets in your way, that’s exactly the kind of report worth sending, ideally with the smallest Org snippet that shows the problem.
\nA library nobody can install is a library nobody uses, so packaging caught up too.
\nguile-orgwebalchemy.flake.nix and a default.nix build the working tree with the same derivation as the nixpkgs package, so a change that breaks one breaks the other for the same reason. They cover x86_64 and aarch64, on GNU/Linux and on Darwin.trunk trigger a Woodpecker pipeline that submits the maak-test and maak-deploy tasks to Byggsteg, my own CI system, itself written in Scheme.guile-documenta: the OrgWebAlchemy API documentation.Every number here comes from the repository and from commands the manual documents. If you want to check my work:
\ngit clone https://codeberg.org/jjba23/orgwebalchemy.git\ncd orgwebalchemy\n\n# the unit suite\nguix shell -m manifest.scm -- guile -L ./src -L ./test \\\n -c '((@ (veritas runner) run-tests))'\n\n# the benchmarks (they print the tables above)\nVERITAS_TEST_TYPE=benchmark \\\nguix shell -m manifest.scm -- guile -L ./src -L ./test \\\n -c '((@ (veritas runner) run-tests))'Run them yourself. If your numbers differ a lot from mine, I’d like to know — a parser that’s fast on one laptop and slow on another has a wrong assumption hidden in it.
\nThe lesson I keep relearning here is that correctness and speed aren’t two phases of the work. Writing the scanners forced me to state exactly which characters can begin a construct, and that list is now a specification a test sweeps about 390,000 positions. The equivalence harness that showed the rewrite was safe is also the reason I dared attempt it.
\nWhich brings me to the larger point, the reason I care about parsing Org at all. Org mode is one of the good ideas of our time: plain text people can read and write without special software, meaning that survives the programs, grown inside a free editor where its users could extend it. Every program that can read Org makes the format a bit more useful, and a format more programs can read is one people can trust with years of their writing.
\nThis library is a small contribution to that. It lets a Scheme program read what you wrote in Org, render it as HTML a browser can show without running anyone else’s code, or as Markdown other tools understand — under a free license, on your machine, with source you can read. The web has no shortage of ways to take a document away from its author. I’d like to add one more way to give it back.
\nIf you build something with OrgWebAlchemy, send a link — it’s always good to see where the library travels. And if this is worth supporting, you can buy me a cup of coffee ☕ so I can keep at it.
","headings":[{"level":1,"text":"OrgWebAlchemy: Benchmarking, Profiling, and the Long Road to Real Org Support","id":"orgwebalchemy-benchmarking-profiling-and-the-long-road-to-real-o"},{"level":2,"text":"Free software, and why this is a library #","id":"free-software-and-why-this-is-a-library"},{"level":2,"text":"What the program is now #","id":"what-the-program-is-now"},{"level":2,"text":"Teaching the parser more of Org #","id":"teaching-the-parser-more-of-org"},{"level":3,"text":"Links: decide once, in the parser #","id":"links-decide-once-in-the-parser"},{"level":3,"text":"Figures #","id":"figures"},{"level":3,"text":"Named elements #","id":"named-elements"},{"level":3,"text":"Tables, read by their bars #","id":"tables-read-by-their-bars"},{"level":3,"text":"Lists that mix and nest #","id":"lists-that-mix-and-nest"},{"level":3,"text":"The rest of the surface #","id":"the-rest-of-the-surface"},{"level":2,"text":"Measuring the work #","id":"measuring-the-work"},{"level":3,"text":"Five runs, keep the fastest #","id":"five-runs-keep-the-fastest"},{"level":3,"text":"Allocation, not only time #","id":"allocation-not-only-time"},{"level":3,"text":"Fragments and the collapse pass #","id":"fragments-and-the-collapse-pass"},{"level":2,"text":"What the profile said #","id":"what-the-profile-said"},{"level":2,"text":"The two rounds of repair #","id":"the-two-rounds-of-repair"},{"level":3,"text":"First round: fast paths in the grammar #","id":"first-round-fast-paths-in-the-grammar"},{"level":3,"text":"Second round: run scanners #","id":"second-round-run-scanners"},{"level":3,"text":"Second round, second part: a linear collapse pass #","id":"second-round-second-part-a-linear-collapse-pass"},{"level":2,"text":"The measurements #","id":"the-measurements"},{"level":3,"text":"One long line: from eight seconds to a third of a millisecond #","id":"one-long-line-from-eight-seconds-to-a-third-of-a-millisecond"},{"level":3,"text":"The collapse pass on its own #","id":"the-collapse-pass-on-its-own"},{"level":3,"text":"What the profile looks like now #","id":"what-the-profile-looks-like-now"},{"level":2,"text":"Why you can believe the measurements #","id":"why-you-can-believe-the-measurements"},{"level":3,"text":"Equivalence with the previous parser #","id":"equivalence-with-the-previous-parser"},{"level":3,"text":"The stop set #","id":"the-stop-set"},{"level":3,"text":"Three deliberate differences #","id":"three-deliberate-differences"},{"level":3,"text":"A trap when adding tests #","id":"a-trap-when-adding-tests"},{"level":2,"text":"What is still expensive #","id":"what-is-still-expensive"},{"level":2,"text":"What Org has that this library does not #","id":"what-org-has-that-this-library-does-not"},{"level":2,"text":"Distribution #","id":"distribution"},{"level":2,"text":"Reproduce the measurements #","id":"reproduce-the-measurements"},{"level":2,"text":"What I take from this #","id":"what-i-take-from-this"},{"level":2,"text":"Links #","id":"links"}]}}