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

[Alain <alainb06@xxxxxxx>]

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

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:variable>
> <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
CPU-meter).

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.