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 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"/>
An intelligent pipelined XSLT processor will evaluate $all-solutions lazily, and will recognize the "" as indicating that after finding the first element in $all-solutions, no further processing is needed.
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).
However, I suspect in Sudoku that your maximum recursion depth is likely to be 81, so this is unlikely to be an issue.
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. 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.