TreeNode weak-parent side tables cost ~9% of parse: needs a design decision #8

New Issue

2026-07-12T11:14:09Z

Mihaela commented

2026-07-12 11:14:09 +00:00

(Migrated from codeberg.org)

Status (2026-07-12)

Open. Found by sample-profiling the parse path during the #139 pass 27-28
rounds; documented in docs/benchmarks.md under "Known structure of the gap".
Filed as its own issue because recovering the cost needs a design decision,
not an optimization pass, and the optimization log is the wrong place for
that conversation.

The finding

TreeNode.init(adopting:)'s child.parent = self runs swift_weakAssign
once per child, and the first weak reference to any object makes the Swift
runtime allocate a side table on it. So during tree building every parent
node pays a side-table allocation, every child pays the weak-assign runtime
call (~9% of total parse time in the pass-28 profile, the largest single
non-scanning cost), and at teardown every parent releases through the slow
side-table path (doDecrementSlow, visible as ~20% of a parse-and-discard
profile's samples).

Why it is not an optimization pass

TreeNode.parent is public API declared weak, and its nil-after-release
behavior is documented and load-bearing: "a detached subtree is freed once no
one references it" and "a child held on its own loses its ancestry the moment
the rest of the tree is released" (TreeNode.swift's doc comments). The
alternatives all change observable semantics or safety:

unowned avoids the side table (it uses the object header's unowned
refcount) but trades nil-after-release for a trap: any consumer that today
legitimately reads parent == nil after dropping the tree would crash
instead. A documented public behavior change.
unowned(unsafe) is a dangling pointer: memory-unsafe, contradicts the
package's never-crash posture outright.
A strong parent reference is a retain cycle: the tree leaks wholesale.

Options to evaluate

Arena/index-based tree: nodes live in one owned storage block and
parent is an index; no per-node weak machinery at all, teardown is one
deallocation. Largest win, largest change: TreeNode is a reference type
whose identity semantics (===, mutation through shared references) are
public API, so this likely means a parallel type or a major version.
API-versioned semantics change to unowned with a documented
migration: cheap to implement, but every existing consumer relying on
nil-after-release breaks at runtime, the worst kind of break.
Accept and document (status quo): the ~9% is the price of the safe,
ergonomic design; keep it, and point performance-critical consumers at the
event stream (EventReader) which builds no tree.

Option 3 is the current de-facto state and is defensible; this issue exists
so the choice is made deliberately against measurements, not by default.

Measurements and profile details: docs/benchmarks.md, "Known structure of
the gap".

## Status (2026-07-12) Open. Found by sample-profiling the parse path during the #139 pass 27-28 rounds; documented in `docs/benchmarks.md` under "Known structure of the gap". Filed as its own issue because recovering the cost needs a design decision, not an optimization pass, and the optimization log is the wrong place for that conversation. ## The finding `TreeNode.init(adopting:)`'s `child.parent = self` runs `swift_weakAssign` once per child, and the first weak reference to any object makes the Swift runtime allocate a side table on it. So during tree building every parent node pays a side-table allocation, every child pays the weak-assign runtime call (~9% of total parse time in the pass-28 profile, the largest single non-scanning cost), and at teardown every parent releases through the slow side-table path (`doDecrementSlow`, visible as ~20% of a parse-and-discard profile's samples). ## Why it is not an optimization pass `TreeNode.parent` is public API declared `weak`, and its nil-after-release behavior is documented and load-bearing: "a detached subtree is freed once no one references it" and "a child held on its own loses its ancestry the moment the rest of the tree is released" (TreeNode.swift's doc comments). The alternatives all change observable semantics or safety: - `unowned` avoids the side table (it uses the object header's unowned refcount) but trades nil-after-release for a trap: any consumer that today legitimately reads `parent == nil` after dropping the tree would crash instead. A documented public behavior change. - `unowned(unsafe)` is a dangling pointer: memory-unsafe, contradicts the package's never-crash posture outright. - A strong parent reference is a retain cycle: the tree leaks wholesale. ## Options to evaluate 1. **Arena/index-based tree**: nodes live in one owned storage block and `parent` is an index; no per-node weak machinery at all, teardown is one deallocation. Largest win, largest change: `TreeNode` is a reference type whose identity semantics (`===`, mutation through shared references) are public API, so this likely means a parallel type or a major version. 2. **API-versioned semantics change to `unowned`** with a documented migration: cheap to implement, but every existing consumer relying on nil-after-release breaks at runtime, the worst kind of break. 3. **Accept and document** (status quo): the ~9% is the price of the safe, ergonomic design; keep it, and point performance-critical consumers at the event stream (`EventReader`) which builds no tree. Option 3 is the current de-facto state and is defensible; this issue exists so the choice is made deliberately against measurements, not by default. Measurements and profile details: `docs/benchmarks.md`, "Known structure of the gap".

Mihaela commented

2026-07-12 12:10:01 +00:00

(Migrated from codeberg.org)

Decision (2026-07-12): option 3, accept for now; option 1 is the designed future path; option 2 rejected outright.

Reasoning, from the measurements rather than preference:

Option 2 (unowned) is rejected permanently. A trap on parent access after the tree is released contradicts the package's never-crash posture (docs/production-readiness.md, stopper 4) and breaks the documented nil-after-release contract that existing consumers may legitimately rely on. A runtime break of that kind is the worst failure mode this project defines for itself; no performance win at this size justifies it.
Option 1 (arena/index-based tree) is right but mis-sequenced today. It recovers this finding's ~9% plus the side-table teardown cost, and it is the honest Swift equivalent of libxml2's memory model. But it is a large, correctness-sensitive change to the package's most load-bearing public type, and the same profile shows scanning carrying ~47% of parse. Taking the big risky change for the smaller lever, while the bigger lever is untouched, is the wrong order. The arena becomes worth designing when the scanning-architecture work has landed and the residual gap still justifies it.
Option 3 (accept and document) is therefore the standing state. The cost is recorded in docs/benchmarks.md under Known structure of the gap, together with this decision and the explicit reopening condition. Performance-critical consumers who need no tree already have the event stream (EventReader), which never pays this cost.

Closing as decided. Reopen when the scanning-architecture lever (epic #6) has landed and the remaining parse gap makes the arena's cost/benefit favorable.

## Decision (2026-07-12): option 3, accept for now; option 1 is the designed future path; option 2 rejected outright. Reasoning, from the measurements rather than preference: - **Option 2 (`unowned`) is rejected permanently.** A trap on `parent` access after the tree is released contradicts the package's never-crash posture (`docs/production-readiness.md`, stopper 4) and breaks the documented nil-after-release contract that existing consumers may legitimately rely on. A runtime break of that kind is the worst failure mode this project defines for itself; no performance win at this size justifies it. - **Option 1 (arena/index-based tree) is right but mis-sequenced today.** It recovers this finding's ~9% plus the side-table teardown cost, and it is the honest Swift equivalent of libxml2's memory model. But it is a large, correctness-sensitive change to the package's most load-bearing public type, and the same profile shows scanning carrying ~47% of parse. Taking the big risky change for the smaller lever, while the bigger lever is untouched, is the wrong order. The arena becomes worth designing when the scanning-architecture work has landed and the residual gap still justifies it. - **Option 3 (accept and document) is therefore the standing state.** The cost is recorded in `docs/benchmarks.md` under Known structure of the gap, together with this decision and the explicit reopening condition. Performance-critical consumers who need no tree already have the event stream (`EventReader`), which never pays this cost. Closing as decided. Reopen when the scanning-architecture lever (epic #6) has landed and the remaining parse gap makes the arena's cost/benefit favorable.

Sign in to join this conversation.

No Label

No Milestone

No project

No Assignees

1 Participants

Notifications

Due Date

The due date is invalid or out of range. Please use the format 'yyyy-mm-dd'.

No due date set.

Dependencies

No dependencies set.

Reference: NodetteHQ/PureXML#8