Re: Template recursion, StackOverflowError, saxon:while a nd variable assignability

Hi Dimitre,

Our application has over 25K lines of XSLT, apart from the Java code 
working with it.  There are about 15 man/years of development from 
experienced developers with an average of over 20 years experience each, in 
the field.  By the way every one of them dislikes assign but all agree that 
it is the best available solution.  Re-designing and re-writing the code 
will not be trivial and if you want to do it we could always try to workout 
agreements, but there is no money.

If our code and design are "wrong" because they are based on assign and if, 
as I understand it, an assign-based design is what you are trying to avoid, 
our code implementing our (faulty) design is probably not the best place to 
start.

On the other hand, I am surprised that the information provided and the 
problem description is not sufficient yet, that is more then I had when I 
figured it out in the first place.  Also, if XSLT has the proper constructs 
for this, it should be easy to work out an acceptable solution, shouldn't 
it ?  Isn't there a design pattern for avoiding circular references in a 
circular net in a high-performance Web context ?

My feeling is that, rather than trying to patch the current design, the 
best thing to do is to start back from the specs and work out a design 
approach that meets the requirements and does not use assign.

I tried to provide the specs and requirements and I would be happy to 
provide further support there, as well as to try to work out an alternate 
solution with whoever is interested.

If we come-up with a better solution, we will undertake retro-fitting it to 
our application but if no one can provide a better solution, please allow 
me to believe that XSLT would be lacking without assign.

Thank you.

Cheers,
Andre





At 17:30 2005-06-17, you wrote:
> Andre,
>
> > For now at least, I maintain that assign is indispensable to the problem
> > solution and that since this problem should be relatively common and that
> > there is bound to be more like this, that XSLT would be lacking without
> > assign, implying that assign should be considered as a standard "extension"
> > and complement to the language.
>
>
> This will remain an unconfirmed statement (therefore, most probably
> false) unless an example is provided -- a sample source xml document
> and the solution that uses saxon:assign. Then people may be able to
> provide a pure XSLT solution and compare the two solutions.
>
>
> Cheers,
> Dimitre Novatchev
>
>
> On 6/18/05, Andre Cusson <ac-ncSKzJSyWVNl57MIdRCFDg@xxxxxxxxxxxxxxxx> wrote:
> > Hi Ed  and Dimitre,
> >
> > Each node in the network is really a tree, as each "database model" record
> > is itself a document.
> > The network is not usually a complete network but could be and two adjacent
> > nodes can have multiple arcs between them.
> >
> > The "database" contents change constantly, based on update requests,
> > sometimes fast, sometime slow.
> > Not all requests are for update but in any case (ie. read or read/write),
> > the network analysis has to be performed as inside and outside conditions
> > can change.
> >
> > Triggered by a request passing it request parameter nodeset specifying the
> > required processing conditions, source, targets, etc., used throughout the
> > traversal, the analysis currently does a single pass forward traversal of
> > the required paths without any back axis access.  Also, a node is never
> > processed twice.
> >
> > Currently, as the traversal progresses nothing is changed in the network
> > but some information is accumulated in a variable, using assign, and the
> > traversal process further refers to this variable as it
> > progresses.  Currently the "analysis" model variable is a single string and
> > referral to it uses regular expressions.
> >
> > Replacing the "analysis" string variable, with a dynamically evolving key()
> > may work, It would probably be larger, more elaborate, and possibly slower,
> > but the key() structure would also have to be assignable ...
> >
> > As for Dimitre's quoted solution, it is interesting, and granted, it does
> > not get tangled in a loop, but the sample graph used has no loops and it
> > only has a single arc between adjacent nodes.  But the main issues here are
> > related to performance and memory as the network has to be traversed
> > multiple times (ex: building the key structure) and the keys would have to
> > hold all the nodes in the "database" and many of them multiple
> > times.  Then, the whole structure has to be processed recursively and nodes
> > have to be copied again.  My feeling is that we are orders of magnitude
> > slower than the current solution and memory is going to burst.  Also, if
> > the request is read-only, and most requests are, we have copied most of the
> > nodes for nothing.
> >
> > We need to improve performance, not slow it down, as it can never be fast
> > enough.  Same with memory usage. And here, we are still talking of a
> > simplified problem.
> >
> > For now at least, I maintain that assign is indispensable to the problem
> > solution and that since this problem should be relatively common and that
> > there is bound to be more like this, that XSLT would be lacking without
> > assign, implying that assign should be considered as a standard "extension"
> > and complement to the language.  Yet, I think that assign should be avoided
> > and used exclusively when it is by far the best approach to solving a 
> problem.
> >
> > This reminds me a lot of the goto statement in a language like Pascal:
> > counter-architectural but indispensable for processing recursive structures
> > without using recursion, for example, in cases where the level of recursion
> > would burst the memory/stack
> >
> > We have been working on this for a while, about 3 decades for me, and I
> > would be very happy to find or learn a better solution, but it has to be
> > both: better and a solution, before we can drop the old.
> >
> > Thank you for your interest and consideration.
> > Regards,
> > Andre
> >
> >
> >
> > At 05:07 2005-06-17, you wrote:
> > >Hi Andre
> > >
> > >Am I right in saying your problem _could_ be equivalent to the following
> > >
> > >You have two input models.
> > >         - your large database model
> > >         - your problem goal
> > >You perform a side-effect free analysis to compute
> > >         - a goal-specific change request model
> > >The change request model then controls an update of the database model?
> > >
> > >This is typical of many graph analysis problems, and it is often
> > >convenient for a non-side-effect free analysis to leave marks
> > >and other temporaries within the source database model. This avoids
> > >any allocation/location issues for the working memory.
> > >
> > >Analysis
> > >--------
> > >
> > >A possible solution within XSLT is to maintain the marks in an
> > >analysis model that accompanies and references the database model.
> > >You are then dependent on efficient key() functionality to
> > >navigate randomly from database model to analysis model.
> > >Separating the read-only and read-write functionality will have
> > >considerable advantages in resolving re-entrancy issues.
> > >
> > >A possible extension to XSLT might be to support a form of
> > >node extension, so that each output document node could comprise
> > >the 'copied' input node plus the appended working extension. This
> > >could avoid the performance limitations of key().
> > >
> > >Update
> > >------
> > >
> > >The controlled update of the large model in response to a change
> > >request model is a straightforward challenge for Michael and other
> > >XSLT compiler implementers. The compiler should recognise that,
> > >subject to minimal constraints, an in-place update can be performed.
> > >
> > >Perhaps XSLT could have a keyword that indicates that this is the
> > >programmers intent, so that the compiler can explain why the intent
> > >is not fulfilled.
> > >
> > >         Regards
> > >
> > >                 Ed Willink
> > >
> > > > -----Original Message-----
> > > > From: Andre Cusson [mailto:ac-ncSKzJSyWVNl57MIdRCFDg@xxxxxxxxxxxxxxxx]
> > > > Sent: 17 June 2005 06:40
> > > > To: saxon-help-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@xxxxxxxxxxxxxxxx
> > > > Subject: Re: [saxon] Template recursion, StackOverflowError,
> > > > saxon:while
> > > > a nd variable assignability
> > > >
> > > >
> > > > Hi Dimitre,
> > > >
> > > > The graph is a (generic) capacity network (multi-digraph) and
> > > > one of the
> > > > tasks, for example, is to follow every path between node A
> > > > and node B,
> > > > weighting the arcs and processing, while not getting tangled
> > > > in a loop,
> > > > very quickly, very often, on possibly huge graphs, all in XSLT.  No
> > > > (significant) heuristics are currently used, only plain
> > > > crunching, and
> > > > saxon:assign.  Of course, as paths are traversed and
> > > > processed, some may be
> > > > found to be uninteresting at the time and further processing
> > > > of that path
> > > > is skipped, for now.
> > > >
> > > > How would you do it in XSLT, without using saxon:assign ?
> > > >
> > > > Thank you,
> > > > Andre
> > > >
> > > >
> > > >
> > > > It happens that I already have this done :o)  -- more than an year ago
> > > > >I implemented in XSLT some generic graph (multigraph) operations like
> > > > >Eulerisation and the street sweeper / NY postman algorithm.
> > > > >
> > > > >
> > > > >Of course, full graph traversal is NP-complete (regardless if assign
> > > > >is used or not), so with deep graphs one would inevitably try some
> > > > >euristics.
> > > > >
> > > > >
> > > > >Cheers,
> > > > >Dimitre Novatchev.
> > > >
> > > >
> > > >
> > > > At 00:28 2005-06-17, you wrote:
> > > > On 6/17/05, Andre Cusson <ac-ncSKzJSyWVNl57MIdRCFDg@xxxxxxxxxxxxxxxx> 
> wrote:
> > > >  > Hi,
> > > >  >
> > > >  > Simple?
> > > >  > How would you avoid getting stuck in a circular loop while
> > > > processing a
> > > >  > general directional graph with XSLT, without using assign ?
> > > >  >
> > > >  > Thank you
> > > >  > Andre
> > > >
> > > >
> > > >
> > > > > >
> > > > > >
> > > > > > At 23:31 2005-06-16, you wrote:
> > > > > > >So how about an (simple, please) example?
> > > > > > >
> > > > > > >Maybe someone will come up with comparable efficient
> > > > solution without
> > > > > > >using saxon:assign?
> > > > > > >
> > > > > > >
> > > > > > >Cheers,
> > > > > > >Dimitre Novatchev
> > > > > > >
> > > > > > >On 6/17/05, Andre Cusson 
> <ac-ncSKzJSyWVNl57MIdRCFDg@xxxxxxxxxxxxxxxx> wrote:
> > > > > > > > Hi,
> > > > > > > >
> > > > > > > > Definitely a graph and one of the issues is dealing
> > > > with circular
> > > > > > > > references, in a strained performance environment.
> > > > > > > > It has been working fine for a few years already and
> > > > uses assign.
> > > > > > > >
> > > > > > > > Andre
> > > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > > > > At 11:40 2005-06-16, you wrote:
> > > > > > > > >Hi Andre
> > > > > > > > >
> > > > > > > > >...
> > > > > > > > > > by a graph processing
> > > > > > > > >...
> > > > > > > > >
> > > > > > > > >Do you really mean graph or tree?
> > > > > > > > >
> > > > > > > > >For a tree-structured problem one can envisage a very simple
> > > > > transform,
> > > > > > > > >that declaratively takes in the entire data-base
> > > > plus a change request
> > > > > > > > >and returns the updated database. If the change
> > > > request applies
> > > > > > > > >to some low level branches, then multiple changes
> > > > can be safely
> > > > > > > > >executed in parallel on multiple processors. The
> > > > XSLT compiler
> > > > > > > > >needs to recognise the tunneling down to the
> > > > branches idiom to
> > > > > > > > >identify that the transform has a very controlled
> > > > change domain
> > > > > > > > >within which an assign rather than copy can be performed.
> > > > > > > > >
> > > > > > > > >It then 'just' requires the XSLT compiler to manage
> > > > the on-demand
> > > > > > > > >re-distribution of data nodes to processors, so that
> > > > you run one
> > > > > > > > >massively parallel XSLT session rather than one per process.
> > > > > > > > >
> > > > > > > > >If your problem is really a graph, then there must
> > > > be significant
> > > > > > > > >issues with determining the extent of the change, and more
> > > > > significantly
> > > > > > > > >ensuring that the concurrent execution of 'assign'-optimised
> > > > > transforms
> > > > > > > > >is deterministic. I don't think that XSLT as it
> > > > stands, will allow
> > > > > for the
> > > > > > > > >real life indeterminism that you currently have. You
> > > > don't mind which
> > > > > > > > >record is updated first, just so long as the updates
> > > > are consistent.
> > > > > > > > >But achieving this consistency probably means that
> > > > you already have
> > > > > > > > >a policy that constrains the potential graph
> > > > anarchy, and this could
> > > > > > > > >be exploited by XSLT to do what you do manually.
> > > > > > > > >
> > > > > > > > >         Regards
> > > > > > > > >
> > > > > > > > >                 Ed Willink
> > > > > > > > >



-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_id=7477&alloc_id=16492&op=click