Re: [xsl] Re: topological sort

Subject: Re: [xsl] Re: topological sort
From: Joerg Pietschmann <joerg.pietschmann@xxxxxx>
Date: Mon, 08 Jan 2001 14:57:32 +0100

Jeni Tennison wrote:
> Hi Joerg,
> Sorry to batter on at this.
Oh, no need to be sorry...
While the optimisations are probably not worth the expense, it is
always a fascinating topic and a good opportunity to learn both basics
and advanced facts about the tools. And we can pretend to have made
some important progress for mankind ;)

> Here's a thought. [...]
> So, rather than search for 200+ structs each time, you could just
> focus on those that have field/type/refs with the same value as the
> names of the $nodes that are being processed during this iteration:
> [...]
> Adding it as a predicate like this probably buys you very little, and
> will probably actually make things worse.

It does.

> But, because you're testing
> *for* something rather than for *not* something, you can change the
> test into a call to key(), which may well make it faster.

Unfortunately, Xalan 1.0.3 (very old) apparently handles keys in a very
naive way. Processing time goes up by a *factor* of 5.

> Another thought is rather than keeping track of which nodes *have*
> been processed, you could keep track of which nodes *haven't* been
> processed.

Yet another idea i had in the beginning but forgot about because i did
not see the obvious way to realise it (bang forehead onto the desk
multiple times)

[implementation snipped]

This makes the struct processing significantly faster. In the actual
data, roughly half of the structures do not have dependencies, one has
a dependency depth of 2 and all other have a dependency depth of 1. This
means, the preparation for the last template invocation is slow using
a processed list and rather fast with the todo list. I have reasons to
believe the distribution of dependency depths will roughly stay this way.
I don't think we'll ever reach dependency depths of 3 or greater.

All optimisations to this point sum up to ca. 10% gain. I really should
work on the rest of the transformation.
Switching to a processor which optimises more will also buy something.

> Anyway, just some ideas. I'd really appreciate it if you let me know
> their effects - it's really useful to know which supposed
> optimisations fall flat on their faces.
Should i reanimate the "XSLT compilation" thread whith an essay about
XSLT optimisations i'd like to see? I've meddled with compiler building
and term rewriting systems in an earlier life...



 XSL-List info and archive:

Current Thread