Balisage Bard: On performance, persistence, and pointe

For those who weren't there, and those who were and can bear hearing it again,
here's my contribution to the famous Balisage Bard session.

It's an abridged version of my XML Prague 2018 paper, and describes work done
during the development of the XSLT compiler now released as part of Saxon-JS
2.

On performance, persistence, and pointers to parents

We wrote a compiler for XSLT
Like any compiler, its heart is a tree.
In each of its phases it transforms this tree
And the transforms are written in XSLT.

If the input and output compare line by line,
Then an XSL transform takes linear time.
Though the changes you make may be local and small
You still pay the price of transforming it all.

The reason it's costly is easy to see:
The non-changing content itself is a tree.
Not only do nodes point to children, to boot,
They also link up to the document root.
When subtrees are used in a new destination,
These pointers are switched to a brand new location.
The larger the corpus, the longer it takes;
Work needed just for consistency's sake.

In a functional programming language like Scheme,
You don't have this problem: it works like a dream.
With immutable structures like binary trees,
Making many small changes is fast as the breeze.
It works much more quickly because it's arranged
So you only touch branches whose content has changed.

That's why JSON works so well:
With JSON trees (I have to tell),
Parent pointers are not needed:
Copy speed is not impeded.

But the pointers to parents are there for a purpose,
It cannot be said that their presence is worthless.
The freedom to navigate upwards and down
Means the rules for transforming each fragment of prose
Can depend on its context (whence it arose).
So if xml:lang says your paragraph's Dutch,
This may affect formats for numbers and such,
But to know just what language applies at your focus,
You need to go up to establish its locus.

The point of this poem is perfectly plain,
So let's wrap it up and repeat it again:
Decisions you make when designing your data
Determine the speed of all that comes later.
While pointers to parents have justification,
They stultify subsequent optimization.