Per-document string interning in the Node build: tag names, attribute names, formatting blanks

[mathieu17g]

The Node build's string workload is a large multiset over a tiny support: on the 14 MB benchmark document it materializes 313,452 tag Strings over 74 distinct names, 54,981 attribute-name Strings over 11, and 326,940 formatting-blank text runs over 96 distinct strings — about 695 K allocations (a quarter of the build's allocation count, ~21 MiB of garbage per parse), and the finished tree retains every duplicate for as long as it lives.

Every one of those copies crosses a single boundary:

XML.jl/src/parse.jl

Line 58 in 0f491e6

_to(::Type{String}, s::AbstractString) = String(s)

I propose probing a per-document intern table at that boundary before copying:

• Layout — open addressing over a power-of-two table, parallel Vector{UInt32}/Vector{String}; the stored 32-bit hash is compared before any byte comparison.
• Hash — an inline FNV-1a over the span's bytes, seeded per document and XOR-folded before masking (a multiply only carries upward, while the low bits index the table).
• Lifetime — a miss materializes once and inserts; the table dies with the parse. No cross-document retention, no locking.
• Bound — past a size cap the pool retires itself and every later string materializes as today, so a hostile document flooding the parse with distinct colliding names degrades to the current behavior instead of quadratic probing.
• Text gate — text nodes probe only under libxml2's gate (length ≤ 3, or < 60 bytes and all-blank); everything else materializes exactly as today.

This transposes libxml2's xmlDict, which is on by default there (parser.c:11367-11368):

• bump-pointer string pools (dict.c:129-183);
• hash and length computed in one scan, the high bit set so a stored hash never collides with the empty-slot 0 (dict.c:442-457, GoodOAAT);
• Robin-Hood lookup comparing the stored hash before the bytes (dict.c:536-588);
• the "intern the formatting blanks found between tags, or the very short strings" gate (SAX2.c:1802-1837);
• nodes storing the interned pointer directly (SAX2.c:2215-2216);
• hardening against hostile input: a random per-dictionary seed (dict.c:269) plus a size limit (dict.c:401-407).

GC replaces the dictionary's refcounted handoff.

A gate microbench (BenchmarkTools medians on Julia 1.12.6, GC excluded from samples, replaying the document's real token-span stream; two passes agree within 4 %) shows the probe does not invert the lever:

family (occurrences → distinct)	copy	intern	Δ work	garbage avoided
tag names (313,452 → 74)	2.18 ms	1.90 ms	−0.28 ms	9.6 MiB
attribute names (54,981 → 11)	0.50 ms	0.41 ms	−0.08 ms	1.7 MiB
gated blanks (326,940 of 568,572 → 96)	5.18 ms	5.70 ms	+0.52 ms	10.0 MiB
in scope			+0.16 ms	−21.2 MiB, −695 K allocs
attribute values (54,981 → 12,988) — excluded	0.56 ms	1.19 ms	+0.63 ms	0.6 MiB

Net work is +0.16 ms on a 70 ms build — inside the run-to-run band — and the value sits elsewhere: −695 K allocations and −21.2 MiB of garbage per parse, a retained tree that stops holding duplicate strings (the PR will measure the reduction; the 71.6 MiB DOM is expected to lose ~10 MiB), and same-tag nodes holding the same String object, so tag comparison downstream is ===-fast. The blank-run +0.52 ms is an upper bound: the microbench scans cold spans, while the real TEXT branch re-reads bytes the tokenizer just scanned.

Attribute values stay out of scope: 12,988 distinct over 54,981 occurrences leave a 76 % hit rate, and on a hit the confirming byte comparison reads about as many bytes as the copy it avoids — +0.63 ms to save 0.6 MiB.

One control shaped the design: the same interning through Dict{SubString{String},String}/Base.hash costs 3.95 ms on the tag family alone — on Julia 1.12, Base.hash's memhash ccall is more expensive than the copies it would deduplicate. The custom table is load-bearing, not a flourish.

Julia 1.13 changes that arithmetic: hash(::AbstractString) becomes a zero-copy algorithm built on codeunit/iterate, and hash values change (NEWS.md § Language changes; JuliaLang/julia#57509, JuliaLang/julia#59691). The pool is insensitive by construction — it never calls Base.hash, depends on no hash values, and adds no hash specialization that the 1.13 migration would ask us to delete — but the Dict control above is a 1.12 figure and worth re-running on 1.13, where the gap should narrow.

Alternatives considered, and why not:

alternative	mechanism	why not here
InternedStrings.jl	global per-type pool behind a lock, WeakRef-tracked entries, probes via Base.hash	a per-node lock plus the memhash cost above; a global weak lifetime, where this design wants a table that dies with the parse
CRC32c (stdlib)	hardware-instruction hash, accepts SubString{String}	CRC is linear — for equal-length inputs the seed cancels out of collisions (crc_s(m1) == crc_s(m2) iff crc_0(m1 ⊻ m2) == 0), so a precomputed colliding name set survives per-document seeding; and a ccall per probe
MurmurHash3.jl	pure-Julia seedable hash	would become XML.jl's first hard dependency, in exchange for hash-quality margin that the stored-hash filter plus byte-compare confirmation does not need
XXhash.jl	C binding to xxHash	a ccall per hash, and a dependency too
InlineStrings.jl	isbits strings (String1…String255), no heap strings at all	Node{String}'s fields are String — a breaking type change, out of scope here

API and contract:

• an intern::Bool = true keyword on the four Node entry points (read from file or IO, parse in both argument orders), mirroring XML_PARSE_NODICT as the opt-out: intern = false disables the whole pool (all three families) and restores today's behavior of materializing every string fresh;
• interning changes object identity only, never content or equality; Node{SubString{String}} (zero-copy mode) and FlatNode (no per-node strings at build time) are untouched;
• the PR pins unchanged semantics, dedup identity, and the capped fallback in tests, and measures the retained-tree delta.

[mathieu17g]

Parking the implementation for now. The design above is complete and benchmark-gated, but its work axis is neutral by construction — the value is retained memory, parse garbage, and ===-comparable tags — and nothing I currently run is memory-bound on retained DOMs.

If you hit a case where the duplicate strings hurt — large trees held in memory, GC pressure from parse garbage — please say so here: a concrete workload is exactly what this needs to move up.