Re: [xml-dev] Schematron tip: Use only one pattern

[Michael Kay <mike@saxonica.com>]

Traditionally Saxon organizes patterns into groups based on the element name. If we can tell statically what element name the pattern matches, and if there are relatively few patterns for each element name, then you get very good matching performance. If there are many patterns for a given element name, or where the element name is not known (*), then you get a linear search through those patterns.

In Saxon-EE 9.8 we try to do a bit better than this. Here's the description in the release notes:

<quote>
The experimental code in Saxon 9.7 for optimizing searching of large sets of XSLT template rules has been rewritten and productized. The new code is designed to handle sets of rules making extensive use of similar predicates, for example match="*[XXX = 'constant'] where XXX is the same expression in every rule, and 'constant' is a different constant in every rule. The main benefit comes from only evaluating the expression XXX once for each rule in the set; in addition many matches can be quickly eliminated by comparing integer hash codes rather than the full strings.

The optimization pays particular attention to the kind of pattern found throughout the DITA-OT stylesheets, which make extensive use of predicates of the form match="*[contains(@class, ' topic/abc ']/*[contains(@class, ' topic/def ')]. These are processed using the following logic:

	• First, where several rules share the same parent pattern (here *[contains(@class, ' topic/abc ']), this parent pattern is only evaluated once, and if it fails to match, all rules using this qualifier are automatically eliminated from the search.
	• The particular call on contains() with a second argument comprising a token wrapped between space characters is recognized as one that can be efficiently evaluated by tokenizing the value of the @class attribute on whitespace boundaries. In effect, it is evaluated as tokenize(@class) = 'topic/def'; but with the extra refinements that the tokenization of the @class attribute is only done once for all rules in the set, and further that this set of tokens is converted to a set of integer hash codes which can then be compared with the integer hash code computed at compile time for the search target topic/def.
</quote>

As you can see, we've identified one or two special cases of constructs that occur across a set of rules, where one can evaluate the shared construct once and use it to eliminate multiple rules from consideration. There's a lot of scope for making this smarter, but as always the problem with optimization is finding out what coding patterns occur frequently enough to make them worth recognizing.

Michael Kay
Saxonica


> On 12 Jan 2018, at 08:58, Jirka Kosek <jirka@kosek.cz> wrote:
> 
> On 22.12.2017 13:53, Costello, Roger L. wrote:
>> It's no wonder that validation was so slow.
>> 
>> My fix was to get rid of 29 patterns and put all the rules into one pattern. After doing that validation ran much faster.
> 
> Alternative solution is to rewrite way how Schematron gets compiled into
> XSLT. I have faced same issue and writing alternative compiler is on my
> todo list.
> 
> However as Mike wrote -- first you have to measure what is the
> bottleneck and whether there is a more generic fix.*
> 
> 			Jirka
> 
> * Commercial info -- there will be talk related to improvement
> performance of processing mostly identity stylesheets at XML Prague.
> 
> -- 
> ------------------------------------------------------------------
>  Jirka Kosek      e-mail: jirka@kosek.cz      http://xmlguru.cz
> ------------------------------------------------------------------
>     Professional XML and Web consulting and training services
> DocBook/DITA customization, custom XSLT/XSL-FO document processing
> ------------------------------------------------------------------
>    Bringing you XML Prague conference    http://xmlprague.cz
> ------------------------------------------------------------------
>