Re: [xsl] Efficient XSLT range lookups / questions

[Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx>]

Dimitre,

> Are the regions non overlapping (as in the examples in [1]) ?
from what I heard about the customer scenario, yes.

The implementation in [1] returns the @value of "a" range it lies
in (in case of overlapping ranges).

So for performance comparison non-overlapping can be assumed.


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:       Dimitre Novatchev <dnovatchev@xxxxxxxxx>
To:         xsl-list@xxxxxxxxxxxxxxxxxxxxxx
Date:       10/07/2010 07:25 PM
Subject:    Re: [xsl] Efficient XSLT range lookups / questions



Hermann,

Are the regions non overlapping (as in the examples in [1]) ?



On Thu, Oct 7, 2010 at 4:33 AM, Hermann Stamm-Wilbrandt
<STAMMW@xxxxxxxxxx> wrote:
> Dimitre,
>
>> Have you compared these to using just a single binary search function,
>> as the one offered by FXSL for at least the last six years?
>
> because I wanted to compare optimal performance I did the minimal
> binary search implementation for the problem myself.
>
> In [1] I describe a simple input format and provide a stylesheet for
> generating the optimal binary decision stylesheet from that (by
> the measurements done that outperforms binary search on a XML tree).
>
> Remember that the investigation was for XSLT 1 and XSLT 2 processors.
>
> May you please point out on how to setup a test with f:binSearch()
> on the simple range lookup input format in [1]?
>
> Since it works on XSLT 2.0 sequences probably that will get better
> results than my binary search based on nodesets.
>
>
> [1]
>
https://www.ibm.com/developerworks/forums/thread.jspa?threadID=348576#1453965
6

>
>
> 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:       Dimitre Novatchev <dnovatchev@xxxxxxxxx>
> To:         xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Date:       10/05/2010 09:58 PM
> Subject:    Re: [xsl] Efficient XSLT range lookups / questions
>
>
>
> Have you compared these to using just a single binary search function,
> as the one offered by FXSL for at least the last six years?
>
>
http://fxsl.cvs.sourceforge.net/viewvc/fxsl/fxsl-xslt2/f/func-binSearch.xsl?r
evision=1.4&view=markup

>
>
>
>  <xsl:function name="f:binSearch" as="xs:boolean">
>   <xsl:param name="pSeq" as="item()+"/>
>   <xsl:param name="pVal" as="item()"/>
>   <xsl:param name="pStart" as="item()"/>
>   <xsl:param name="pEnd" as="item()"/>
>
>   <xsl:sequence select=
>    "if($pStart gt $pEnd) then false()
>       else
>        for $mid in ($pStart + $pEnd) idiv 2,
>             $sVal in $pSeq[$mid]
>           return
>             if($sVal eq $pVal) then true()
>             else
>                if($sVal lt $pVal)
>                   then f:binSearch($pSeq, $pVal, $mid+1, $pEnd)
>                else
>                  f:binSearch($pSeq, $pVal, $pStart, $mid - 1)
>       "/>
>  </xsl:function>
>
>
> --
> Cheers,
> Dimitre Novatchev
> ---------------------------------------
> Truly great madness cannot be achieved without significant intelligence.
> ---------------------------------------
> To invent, you need a good imagination and a pile of junk
> -------------------------------------
> Never fight an inanimate object
> -------------------------------------
> You've achieved success in your field when you don't know whether what
> you're doing is work or play
>
>
>
>
> On Tue, Oct 5, 2010 at 10:58 AM, Hermann Stamm-Wilbrandt
> <STAMMW@xxxxxxxxxx> 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
>
>



--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
I enjoy the massacre of ads. This sentence will slaughter ads without
a messy bloodbath.