Re: [xsl] [XSL] Accessing part of the result tree illustrated with "The Sudoku solver" example.

Subject: Re: [xsl] [XSL] Accessing part of the result tree illustrated with "The Sudoku solver" example.
From: Alain <alainb06@xxxxxxx>
Date: Thu, 06 Sep 2007 19:41:55 +0200
Such a construct would only really be useful if you could rely on the
processor evaluating all the items  in a for-each in order, but that is
explictly not the case. One of the benefits of a side effect free
language is that it is naturally parallelisable. It's best to assume
that all the items in a for-each are evaluated in parallel, and the
results assembled at the end and passed on. If you view it this way the
fact that you can't "stop" a for-each based on the processing of one of
the items should seem far more natural. If you need the processing of
one item to depend on the result of processing another, don't use
for-each, use a recursive template that processes the item and then just
conditionally processes the next item if needed.

I'm just wondering now why this explanation is not given with the W3C norm. That made clear, I did a giant step to the understanding of XSL and I'm even more impressed by the opportunities this might bring (I mean optimizing business things, not the Sudoku that was just for fun !)

A Sudoku puzzle can in general have more than one solution, and I think,
without studying it in detail, that your code is written to find all the

Yes indeed, my code will find all the solutions, but as Andrew wrote, a "proper" Sudoku MUST have only one solution.

If you only want the first solution, the answer is to do:

<xsl:variable name="all-solutions" as="...">
 ... your algorithm here ...
<xsl:sequence select="$all-solutions[1]"/>

An intelligent pipelined XSLT processor will evaluate $all-solutions lazily,
and will recognize the "[1]" as indicating that after finding the first
element in $all-solutions, no further processing is needed.

Michael Kay

That, added to the explanation of David makes sense. I can imagine you have multiple threads (or process) recursively calculating, one of them ouput something (the solution) it goes down the "pipeline" and you catch the first sequence, output it and exit.

It seamed too magical for me, as if you parallelise you have Rendez-vous points
and you will somewhere wait for other processes to end. Exiting (or doing other
XSL instructions) would mean killing all the running process that didn't find
a solution, and may be a queue of stacked items waiting for a free process.

And indeed it does not work !..
Well it finds a solution but the time involved is the same as computing
every possibility.

But that might be a limitation that comes with Windows XP/JRE 1.6.0_02 as
a side effect of the still very bad parallelism capabilities of Windows.

I have another limitation: on my laptop with Pentium M 2GHz, Saxon (Java)
takes 100% CPU when calculating things like Sudoku, and you would expect that !
But on my Core 2 Duo desktop, it does not go above 50%, although it takes
CPU on both sides of the processor (according to the Microsoft standard

I don't know if it's relevant to Saxon parallelisation style or if it is a
Sun/Java JRE issue... or Windows XP issue.
Did anyone already reported the same issue (limitation to 50% CPU on Core 2 Duo), or should I open a "ticket" on Saxon list ?

[I will try the .Net version to see if it has the same CPU limit]

However, I suspect in Sudoku that your maximum recursion depth is likely to
be 81, so this is unlikely to be an issue.

Michael Kay

That's correct if you have a "proper" Sudoku. But if you start with the empty Sudoku, as you have billions of solutions you will run for a while and get a nice Java stack : out-of-heap. That's with "standard 64MB" JVM (eq no options given to Java.exe).

And when you run that empty Sudoku, Saxon outputs nothing with the
modifications you suggested : solution[1]. If it was pipelined with no
parallisation/recursing side effect it would have output something, even if
then it hangs waiting for termination of other threads. It might still be
pipelined... but then the pipe is waiting for something (may be it has no
available thread to run !), as when the heap exception occurs the output
file is not even created.

The better XSLT processors will implement "tail call optimization" so that a
recursive call done as the last thing before a function exits reuses the
existing stack-frame rather than creating a new one.

That works perfectly. I moved my recursive part in program 2 to the end of the template (as Andrew had already done with his) and the memory used by the program went down from 4MB to 2,6MB.

Many thanks to all for all your advices.

Current Thread