Project

Profile

Help

Optimization of nested loops...

Added by Anonymous over 18 years ago

Legacy ID: #3657046 Legacy Poster: lolo77 (lolo77)

hi all, i am very new to Saxon - sorry for stupid questions. i have two nested loops (2 instructions xsl:for-each, inner loop has select="../SITE[PARENT_SITE[1]/@ExternId=$customerId]", where $customerId depends on the outer loop) and i am running this transformation on Saxon-B and on evaluation copy of Saxon-SA. i would expect Saxon-SA can sort ../SITE sequence according SITE/PARENT_SITE[1]/@ExternId and using binary searching (or something similar) to perform whole operation in O(n*log(n)). my questions are: 1) does Saxon-SA do this? (probably yes) 2) is this compile time optimization? (when I use great Saxon's feature saxon:explain - Saxon-SA and Saxon-B returns similar results.) 2b) if yes, what should be on explain plan output? (is there any documentation about saxon:explain output items?) thanks a lot.


Replies (4)

Please register to reply

RE: Optimization of nested loops... - Added by Anonymous over 18 years ago

Legacy ID: #3657108 Legacy Poster: Michael Kay (mhkay)

Saxon-SA attempts to do this kind of optimisation when it can. Unfortunately the precise conditions where it works are hard to specify: there are many little things that can get in the way. Also, I'm afraid the "explain" output is not documented. Writing a guide to Saxon optimisation has been on my "todo" list for quite a while. The best way of finding out whether the construct is being optimised is to measure the actual performance against input files of different sizes; and in XSLT, if this kind of construct isn't being optimized, then frankly the simplest thing to do about it is to force the issue by using explicit keys. Generally there are two things Saxon-SA tries to do. (1) If there's a filter expression of the form //exp[P=C] where the expression being filtered is rooted at a document node, and where P depends on the context node but C doesn't (or vice versa of course), then Saxon defines an implicit key and generates a call on the key() function. You will see this call in the explain output. (2) If there's an expression of the form $exp[P=C] ($exp is not necessarily written as a variable, the variable might be internally allocated) then Saxon tries to define a transient index on the variable, which lives only as long as the variable (typically, for the life of an outer loop). This optimisation is a bit less robust than the other, in terms of the number of factors it depends on. I'm always interested to see how well the optimizer is coping with real-life use cases, so feel free to send this one in for me to take a look at. Michael Kay

RE: Optimization of nested loops... - Added by Anonymous over 18 years ago

Legacy ID: #3657573 Legacy Poster: lolo77 (lolo77)

  1. Thanks for your answer. It seems point (2) could work in my example (depending on other factors). You are right - I can use explicit keys. 2) I wanted to send you our real-world example, but it is not possible to sent ZIP file on your sourceforge e-mail account.

RE: Optimization of nested loops... - Added by Anonymous over 18 years ago

Legacy ID: #3661317 Legacy Poster: lolo77 (lolo77)

I have improved performance by using xsl:key. But it seems xsl:key section is not included to 'total time' on profile output. It shows me different time than my stopwatch :)

RE: Optimization of nested loops... - Added by Anonymous over 18 years ago

Legacy ID: #3661417 Legacy Poster: Michael Kay (mhkay)

An index (actually a hash table) to support xsl:key is built for a particular document the first time that the key() function is called to search that document, and the time taken to build the index is included in the profile as part of the cost of the template or function in which this call of key() occurs. This is also true for global variables, which are evaluated on first reference. The main thing that isn't included in the profile is startup cost - the cost of initializing the JVM, compiling the stylesheet, and loading the source document. This can be a significant proportion of the whole, as the -t output on the command line often demonstrates.

    (1-4/4)

    Please register to reply