Re: [xsl] Efficient XSLT range lookups / questions

[Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx>]

Michael,

I tried your suggestion, but creating the xs:integer
variable seems to add a minimal overhead and runtime
increased by that (very little).

            xsl
lookups  bin  bin2  (with xs:integer)
  4094  1.389 1.391 s
  8190  1.547 1.579 s
 16382  1.910 1.949 s
 32766  2.633 2.709 s


I converted the stylesheets to XSLT 2.0 and together
with the files needed you may get them from [1].

Here is how to use them:
$ saxon gent.xsl 10.xml >4094.xml
$ saxon gen2.xsl 10.xml >10.2.xsl
$ time saxon 10.2.xsl 4094.xml >/dev/null

real    0m2.982s
user    0m3.264s
sys     0m0.283s
$ ll
total 316
-rw-rw-r-- 1 stammw stammw 242937 Oct  7 13:13 10.2.xsl
-rw-rw-r-- 1 stammw stammw     10 Oct  7 12:59 10.xml
-rw-rw-r-- 1 stammw stammw     10 Oct  7 13:01 11.xml
-rw-rw-r-- 1 stammw stammw     10 Oct  7 13:01 12.xml
-rw-rw-r-- 1 stammw stammw     10 Oct  7 13:01 13.xml
-rw-rw-r-- 1 stammw stammw  43972 Oct  7 13:12 4094.xml
-rw-rw-r-- 1 stammw stammw   2806 Oct  7 12:58 gen2.xsl
-rw-rw-r-- 1 stammw stammw   1536 Oct  7 12:56 gent.xsl
-rw-rw-r-- 1 stammw stammw    143 Oct  7 13:11 table.txt
$


[1]  http://stamm-wilbrandt.de/en/xsl-list/range2.zip


Mit besten Gruessen / Best wishes,

Hermann Stamm-Wilbrandt
Developer, XML Compiler, L3
Fixpack team lead
WebSphere DataPower SOA Appliances
----------------------------------------------------------------------
IBM Deutschland Research & Development GmbH
Vorsitzender des Aufsichtsrats: Martin Jetter
Geschaeftsfuehrung: Dirk Wittkopp
Sitz der Gesellschaft: Boeblingen
Registergericht: Amtsgericht Stuttgart, HRB 243294


From:       Michael Kay <mike@xxxxxxxxxxxx>
To:         xsl-list@xxxxxxxxxxxxxxxxxxxxxx
Date:       10/05/2010 11:17 PM
Subject:    Re: [xsl] Efficient XSLT range lookups / questions



  It would be interesting to see how much speed-up you can get by using
integer comparisons rather than untypedAtomic/double comparison. I would
imagine that doing

<xsl:for-each select="t">
<xsl:variable name="t" select="xs:integer(.)"/>
<xsl:choose>
<xsl:when test="$t lt 15">
       etc

could give a significant improvement.

Michael Kay
Saxonica

On 05/10/2010 6:58 PM, Hermann Stamm-Wilbrandt wrote:
> Hello,
>
> I got notice of an interesting scenario needing a huge amount of range
> lookups in XSLT (billions per year with more than 20000 different
ranges).
>
>
> My web searches prior to this only showed range lookups of complexity
> linear in the number of ranges to be searched. I am sure that my searches
> are not perfect and I just missed relevant postings.
> Are there any relevant postings?
>
>
> Since the ranges change rarely precomputing was a good option.
>
> I compared binary search trees against stylesheets with a binary search
> structure.
>
> Findings based on experiments with saxon9he and DataPower XSLT processor
> [1]:
> - binary outperforms linear
> - binary stylesheets outperform binary XML searchtrees
> - in case the XSLT processor supports document and/or stylesheet caching
>    the lookup performance remains good even for single lookups
(logarithmic
>    in depth of search tree; DataPower supports both, and web searches
> indicate
>    that .net framework also supports document/stylesheet caching)
>
> Are there even better alternatives for doing quick range lookups?
>
>
> [1] "Efficient XSLT range lookups"
>
https://www.ibm.com/developerworks/forums/thread.jspa?threadID=348576&tstart=0

>
>
> Mit besten Gruessen / Best wishes,
>
> Hermann Stamm-Wilbrandt
> Developer, XML Compiler, L3
> Fixpack team lead
> WebSphere DataPower SOA Appliances
> ----------------------------------------------------------------------
> IBM Deutschland Research&  Development GmbH
> Vorsitzender des Aufsichtsrats: Martin Jetter
> Geschaeftsfuehrung: Dirk Wittkopp
> Sitz der Gesellschaft: Boeblingen
> Registergericht: Amtsgericht Stuttgart, HRB 243294