XML.jl v0.4

The headline cross-library figures live in the README. This document is the decomposition behind them — what XML.jl does by access pattern, and the theory that makes the lexer and parser "optimal".

The theory behind "optimal"

XML parsing splits into two language-theory levels, and v0.4 hits the asymptotic lower bound of each — the sense in which the lexer and parser are "optimal". The gap to a C library like libxml2 is constant-factor (C tuning, a leaner non-Julia-heap tree), not asymptotic — and only on the pointer-tree Node build; FlatNode builds faster than libxml2 (Table 5), and at streaming XML.jl is ~3.4× faster (Table 1).

Level 1 — lexing is finite-state

The token grammar (tags, attributes, text, comments, CDATA, PIs) is regular, so the tokenizer is a DFA (the Mode enum is its start-condition states): one pass, O(n) time, O(1) state — no lexer can do better.

The implementation hits that bound:

• a Token is isbits (a kind plus a byte range), so token emission allocates nothing (measured: 0 B) — and stays unboxed even inside small unions such as an iterator's Union{Token, Nothing}, per Julia's isbits-Union optimizations;
• delimiter scans use findnext, which for String calls the C library's memchr — a hand-vectorized (SIMD) byte search, so the hot scan runs at memory speed rather than as a byte-at-a-time Julia loop;
• whether a byte may appear in an XML name is answered by a single load from a 256-entry lookup table instead of a chain of range comparisons.

The one departure from pure finite-state scanning is the DOCTYPE body: its internal subset […] may itself contain >, so a bracket-depth counter determines which > actually closes the DOCTYPE.

Level 2 — nesting is visibly pushdown

Balanced <a>…</a> isn't regular — matching open to close needs a stack. XML's nesting structure is a nested word / visibly pushdown language — XML being the canonical example in Alur & Madhusudan's papers introducing the class: open/close tags are visible call/return markers, so the stack action is fixed by token kind alone — OPEN_TAG pushes, CLOSE_TAG and self-closing <a/> pop, the rest is internal — no lookahead, no backtracking.
So _parse is a single-pass visibly pushdown automaton (VPA): O(n) time, stack depth = nesting depth (building the output tree is a second, separable O(n) cost — the one Cursor skips entirely, and the one Table 3 prices).
Drive the same traversal event-by-event and you have the Cursor streaming API — pure Julia: no FFI call per event, unlike a libxml2-backed reader (EzXML's StreamReader), where every pulled event crosses the Julia↔C boundary.

One theoretical fine print: a textbook VPA has a finite stack alphabet, while checking that </a> really closes <a> pushes the tag name — drawn from an unbounded set of names — so the parser is formally a VPA over an unbounded stack alphabet. A nuance of classification only: each stack entry holds a tag name, the close-tag comparison is O(name length) and already inside the O(n), and every guarantee above holds.

Julia-level constant factors

The well-formedness level is a type parameter (Val{W}), so :strict/:structural checks are dead-code-eliminated when inactive (confirmed in the LLVM); Node{S} is parametric, so parse(s, Node{SubString{String}}) — a supported method, exercised by the test suite and by the benchmarks behind the zero-copy row below — keeps zero-copy views while parse(s, Node) owns Strings; a has_entities flag skips entity decoding when a token holds no &; and tokens are native byte spans — every span edge the scanner produces falls on an ASCII byte, provably a UTF-8 character boundary, so token views are rebuilt by direct field construction with no index walking.

The readers on the XMark-style document, by access pattern

Performance isn't one number — it splits by what you do with the document. The document is a 14 MB XMark-style one,¹ generated by benchmarks/XMarkGenerator.jl; XML.jl and EzXML walk the same ~882 K nodes; lower is better.

Stream — events, no tree

Cursor pulls in pure Julia — a full pass, decoded reads included, leaves the allocator untouched; EzXML's StreamReader is libxml2's reader, at one FFI call per event:

Table 1 — streaming: events only, no tree built.²

Structured pull helpers keep scans cheap without hand-tracked depth: for_each_child applies a function to the immediate children of the current node (nestable — composing calls yields a full depth-first walk), and skip_element! jumps a whole subtree in one byte-level scan, so structural walks classify nodes without tokenizing their contents.

Partial reads — LazyNode

Opening builds nothing — every document costs one probe of its prolog for entity declarations, 18 ns on this 14 MB file and allocation-free, and one held as a String costs a scan of the source for line ends on top of that, 0.21 ms here, where one held as anything else does not (Memory-mapped sources) — and nothing is ever cached: each visit re-tokenizes and rebuilds its small handles — iteration steps allocate nothing, and each child or attribute scan is one small resumable cursor object, elided when it never loops (Table 4 prices the full-scan case) — so a repeated look-up costs only its re-scan time, and costs repeat per visit. A traversal costs only the bytes it actually steps over: the child iterator defers a yielded element's subtree skip until the next sibling is requested, so descending to a target is O(bytes before it); scanning everything is the worst case, priced per reader in Table 4. What still costs: horizontal scans cost the subtrees they step past (as any index-free forward reader must), and repeated look-ups cost again — those two patterns tip the scale toward FlatNode/Node.

out = LazyNode[]                  # goal: keep the first three children
for c in eachchildnode(parent)
    push!(out, c)
    length(out) == 3 && break     # the break is in the body — no fourth fetch
end

Memory-mapped sources

The readers keep whatever string type the document arrives as, and a document not held as a String is not rewritten for its line ends — so a StringView over Mmap, the recipe for files too large to hold in memory, reaches the reader intact whatever the file's line ends. The line-end normalization the specification requires then happens on each value as it is reported, which costs a copy only for the values that carry a line end, and only for the ones actually asked for. The entry does read the prolog, to see whether the internal subset declares general entities: a document that declares and references them is expanded before the parse whatever string type holds it (XML 1.0 §4.4.2), one document-sized copy, and a document that declares none is passed through for the probe's cost alone. On the same XMark-style document, mapped instead of read, with CR LF line ends throughout — the worst case for this, since every line end is one CR to fold:

An LF file opens in the same 26.2 ns: the entry reads the prolog and not the document, so opening does not scale with the file's size and a reader that touches a fraction of a mapped document costs only that fraction. Reading all of a CR LF document allocates more than a reader working from a rewritten String would. These are short-lived strings, reclaimed by the garbage collector as the reader moves on, where the rewrite holds one document-sized block for as long as any handle into it lives. For a file larger than memory, that difference determines whether it can be read at all.³

Full DOM — parse + walk everything

libxml2 is fastest to build; XML.jl materialises an 882 K-node Julia tree, EzXML a leaner C one:

Table 2 — full-DOM extraction (parse + pull every tag/text), cross-library.²

Decomposed (XML.jl, the String variant — every row a direct measurement; the lex is the first stage inside the parse row, so their difference prices the tree build, and parse + traverse reproduces the Table 2 row within noise):

Table 3 — the XML.jl pipeline, decomposed (String variant).²

The lexer is allocation-free; the whole libxml2 gap is materialising the native tree, not scanning it — and the GC column shows where that cost lives: the allocation-free lex cannot trigger a collection, so every garbage-collector pause inside a parse falls in the build, the toll of 882 K fresh objects.

Traversal of a pre-built tree stays off the allocator where it counts — iteration steps are free for all three readers, and the allocation column is measured, not assumed. Node and FlatNode allocate nothing at all; LazyNode allocates one small object per container node — its resumable child cursor, elided by the compiler wherever a container is empty:

Table 4 — whole-tree traversal per reader: one child iterator and a tag + value read per visited node (the spreadsheet hot-loop shape). LazyNode re-tokenizes everything it steps over — a cost per visit by design; see the partial-reads section for the access patterns it suits.²

FlatNode (v0.4.2, experimental)

One contiguous array of isbits records with index links instead of per-node pointers — an eager read-only alternative to the pointer-tree Node.

Most of its advantage is a better constant factor: it does the same O(n) work as the Node build, just with denser packing, no per-node allocation, and no Julia-GC mark-rescan of millions of objects.

The asymptotics change only in the external-memory model (Aggarwal–Vitter 1988) — the model of a two-level memory hierarchy, formulated for disk vs RAM and applied here to CPU cache vs RAM: it counts memory-block transfers instead of instructions, with B defined as how many records fit in one transferred block. A document-order scan of a contiguous store moves Θ(n/B) blocks — one per block-full of records — while a pointer tree scattered across the heap can move up to Θ(n), one per node.

Concretely, a _FlatRec is 40 bytes — ten Int32-sized fields (kind, three tree links, tag span, value span, attribute range; 32-bit throughout because the 2 GiB source bound lets every offset and index fit an Int32, halving the store) — so a 64–128-byte cache line carries one to three records.

And the scan is cache-oblivious (Frigo et al. 1999): sequential access is Θ(n/B) for every B simultaneously, so neither the code nor the analysis needs the actual line size — the bound holds at each level of the cache hierarchy at once, hardware prefetchers included.

Measured on the same XMark-style document:

Table 5 — per-reader full-DOM comparison; build is the whole parse call, and DOM size is the retained live tree (Base.summarysize), not allocations.⁴

Build allocations: 42.2 MiB (FlatNode) vs 99.8 MiB (Node), and on the build FlatNode is ~1.4× faster than libxml2 itself, Node ~1.8× slower than the C library. The GC cells say why FlatNode builds so cheaply: its build allocates a handful of arrays instead of 882 K objects, so its median GC share is ~0.1 ms where Node's is ~21 ms. Access on the finished stores: whole-tree walks are close (2.96 vs 3.36 ms — exact-size children vectors keep Node's locality sharp), parent/depth stay O(1) index hops on FlatNode where Node must search down from the root, and pure value extraction is close too, flat store slightly faster (3.1 vs 3.6 ms — a per-value SubString view costs two integer stores).

Beyond the plain document: references, normalization, markup, and the wellformed levels

The tables above measure one document, and XMark leaves out by design what the next two subsections put back: the constructions that document lacks, measured against twins of the same structure, and the checks that wellformed = :strict adds over :structural.

The constructions the document lacks

XMark limits its documents to a restricted set of XML features by design: no entities or notations, character data never marked as CDATA, seven-bit ASCII (§4.4 of the paper). The generator here inherits that choice, and the document above carries no reference, no attribute value that needs normalizing, no comment, no CDATA section, no processing instruction and no DOCTYPE, so none of the rows above measures what those cost. Two twins are generated beside it through the generator's opt-in features (XMarkGenerator.Features), each keeping the document's elements and attributes in the same order, so that a difference between columns belongs to the construction alone. The escaped twin replaces one drawn word in ten by one carrying a predefined entity or a character reference, and gives every item and person a note attribute that needs decoding or §3.3.3 white-space normalization: 8 % of its text tokens and 8 % of its attribute values carry a &, 81,799 references in all. The markup twin writes one text child per item and person as a CDATA section followed by a comment and a processing instruction, under a DOCTYPE holding the schema's 74 element and 14 attribute-list declarations and no entity: 16,002 nodes more than the document, 882,026 → 898,028.

Table 6 — the same operations over the XMark-style document and its two twins: time (incl. GC) · allocations. The three columns of a row come from one run, and the differences between them are the point. The libxml2 DOM lives in the C heap, where the allocation column does not apply.⁵

The escaped column is the decode path. A decoded value allocates once, the result string, the same +46,583 on Cursor, LazyNode and FlatNode for the 46,583 text tokens that carry a reference: unescape decodes in one pass over the bytes into a scratch buffer kept per task, then copies out exactly the decoded bytes. Node{SubString} does not decode, and its +12,801 are the §3.3.3 normalization of the 3,200 attribute values that carry a literal tab or newline, four allocations each. The markup column costs its extra nodes and nothing more, plus the prolog probe of a DOCTYPE that declares no entity, four allocations and 6 µs at every entry, which is why Cursor streams that twin in five. Parsing that DOCTYPE's 88 declarations with parse_dtd takes 7.8 µs and 372 allocations.

The two libxml2 rows put the C library on the same three documents. Its reader touches node names only, so its escaped column carries the lexing of a reference and not its decoding. Its DOM build decodes for 8 ms over the plain build, the same 8 ms parse → Node takes over its own. The markup twin's comments, processing instructions, CDATA sections and DOCTYPE cost the C library 8 ms over the plain build, where parse → Node takes 1.6 ms more, its extra nodes. Every libxml2 cell frees its tree per sample outside the timing: EzXML attaches its finalizer to the document's node, so a cell that finalizes the document frees nothing, and a benchmark loop never wakes the collector.

Well-formedness levels

:strict adds two checks over :structural: a character-range scan of every text, attribute value, comment, CDATA section and processing-instruction body, and a check of every reference in a token that carries one, against the character range for a numeric reference and against the five predefined names for a named one, every declared entity having been included by then. The first is read by the span. A long text goes through a loop that checks 64 bytes at a time with vector instructions; a short span, 16 bytes or less, an attribute value or the white space between two tags, is checked as two 8-byte words without any loop. It costs by the number of spans more than by the bytes. The second costs in proportion to the reference density, and the XMark-style document, which has no reference at all, measures the first alone. :lenient and :structural differ only in the document-shape checks, whose cost does not separate from the run-to-run spread: 49.8 and 49.1 ms on the document.

Table 7 — what :strict adds, by document shape; the ratio is taken on the time net of the GC share, the part that reproduces.⁵

Neither check allocates. The character-range scan reads the bytes of a span and decodes only a byte at or above 0x80, by the string's own Char iteration. The reference check reads the bytes of a token that carries a & and copies only a reference it rejects, into its message, so :strict allocates exactly what :structural does on every document.

libxml2 has no levels: it always enforces well-formedness in full. Its DOM build takes 38 ms on the plain document, 45 ms on the escaped twin and 3.9 ms on its character data alone. On pure text the :strict character-range scan adds 0.3 ms to the parse, about a twelfth of the time the C library takes to parse, check and build from the same bytes.

The other entry points

sourcespan, splicetext, issamenode, depth, siblings, foreach_attr, xpath and parse_dtd appear in no table above. On one item element, the 1000th of the XMark-style document, four levels below its document node, the same node in every reader:

Table 8 — the entry points no other table covers.⁶

FlatNode answers sourcespan and depth from its store; LazyNode has to find the element's end for the first, and Node, which keeps no parent link, has to search down from the root for the second and for siblings. splicetext returns the whole document with one node replaced, so it costs a copy of the document whichever reader asks. foreach_attr yields raw tokens and eachattribute decoded pairs; on an element whose attributes need no decoding, both are allocation-free, the decoded pairs costing about twice the raw tokens. xpath over the descendant axis allocates 17 MiB on this tree.

Choosing a reader

Stream / low-memory / read-only full-DOM / repeated traversal → XML.jl; FlatNode builds ~1.4× faster than the libxml2 binder (26.0 vs 37.3 ms), and the C library's one advantage is the one-shot Node build-and-extract (~1.3× end-to-end, Table 2) — either way, pure Julia, no C dependency. Against its own past, v0.4 is ~7× faster and ~14× leaner than 0.3.9 (530 → 73 ms and ~1.4 GiB → 100 MiB on this file, Table 2) — see benchmarks/profile.jl, benchmarks/profile_vs_039.jl, benchmarks/compare.jl.