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

I solve multiple dependency critical path method problems using pure XSL recursion without saxon:assign.

I'm not exactly sure what this network graph is but the gantt chart critical path method demands finding a single path to a final destination. In my typical case there are a possible 114 paths through 31 nodes. I must evaluate each possible path to each node to find the *longest* accumulated time duration at each node which is a task that some one or some process will take time to execute.

Although some tasks can be executed simulaneously, the critical path solution is the accumulation of the longest simultaneous tasks. The result is not just a single value but the set of critical path points in time to arrive at any single task in the entire gantt chart. And, there is also the possibility of an uncontrolled loop here so I do keep track of where I've been so I don't go down the same path twice.

Frankly, I agree that procedural coding for this type of problem looks like a mess but I believe plenty of people do it. However, I have what I believe to be proof that such a problem can be solved with a pure function without rewriting to any variable.

A technical point: This works in Saxon 7.8 but not Saxon 8.3. If the problem is memory as Mike suggests, that can be eliminated in my case. The entire process runs in about 250ms on a 1.6GHZ AMD chip.

Roger Kovack

Dimitre Novatchev wrote:

Hi Andre,

  

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.
    

The information provided is not at all convincing that a pure XSLT
solution does not exist or that an XSLT solution will be significantly
less efficient than one using saxon:assign.


Be informed that there exist pure XSLT solutions to the problem of
finding a path between two nodes of a multigraph -- I have my own
solutions and wouldn't be surprised if other people have developed
theirs.

I would be glad to demonstrate such a solution on a sample graph,
provided by anyone interested.

  

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.
    

I am not interested in being hired to work on this or in getting money.

What I just want is that people are not misinformed about the alleged
impossibility (or inefficiency) of solving this problem in a pure
functional (without modification of values of variables) way.

Unfortunately, from this thread until now it seems that you cannot
stand up to the challenge and provide a concrete example of the
problem that would support your statements.


Thanks,
Dimitre

On 6/18/05, Andre Cusson <ac-ncSKzJSyWVNl57MIdRCFDg@xxxxxxxxxxxxxxxx> wrote:
  

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
_______________________________________________
saxon-help mailing list
saxon-help-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@xxxxxxxxxxxxxxxx
https://lists.sourceforge.net/lists/listinfo/saxon-help

    

-------------------------------------------------------
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_idt77&alloc_id492&opÌk
_______________________________________________
saxon-help mailing list
saxon-help-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@xxxxxxxxxxxxxxxx
https://lists.sourceforge.net/lists/listinfo/saxon-help


  

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