Re: Re: topological sort

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...

Thanks

J.Pietschmann

 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list