[xquery-talk] Matrix Multiplication (JSONiq)

Hermann Stamm-Wilbrandt STAMMW at de.ibm.com
Mon Feb 3 09:26:05 PST 2014


Hi Christian,

> I'd like to point out that the loop around the calculation (for $h in 1
to $N) might be optimized away by a query compiler.
>
agreed, but I did test with different values of $N and the reported times
increased.

The easiest way of disallowing the optimizer to kick in would be to compute
the matrix A^{2^N} by N repeated matrix square operations, in that case
nothing can be optimized away.


Mit besten Gruessen / Best wishes,

Hermann Stamm-Wilbrandt
Level 3 support for XML Compiler team and Fixpack team lead
WebSphere DataPower SOA Appliances
https://www.ibm.com/developerworks/mydeveloperworks/blogs/HermannSW/
https://twitter.com/HermannSW/
http://stamm-wilbrandt.de/GraphvizFiddle/
----------------------------------------------------------------------
IBM Deutschland Research & Development GmbH
Vorsitzende des Aufsichtsrats: Martina Koederitz
Geschaeftsfuehrung: Dirk Wittkopp
Sitz der Gesellschaft: Boeblingen
Registergericht: Amtsgericht Stuttgart, HRB 243294


                                                                                                                                                
  From:       Christian Grün <christian.gruen at gmail.com>                                                                                        
                                                                                                                                                
  To:         Hermann Stamm-Wilbrandt/Germany/IBM at IBMDE,                                                                                        
                                                                                                                                                
  Cc:         David Carlisle <davidc at nag.co.uk>, "talk at x-query.com" <talk at x-query.com>                                                          
                                                                                                                                                
  Date:       02/03/2014 03:36 PM                                                                                                               
                                                                                                                                                
  Subject:    Re: [xquery-talk] Matrix Multiplication (JSONiq)                                                                                  
                                                                                                                                                





Hi Hermann,

thanks for your interesting comparison. I'd like to point out that the
loop around the calculation (for $h in 1 to $N) might be optimized
away by a query compiler. If this happens, the only thing that would
be measured in the query would be the concatenation of 10 million
results.

But I completely agree that it's difficult to formulate an example
that is easy to compare if as long as we have no dynamic input.

Christian
______________________________________________

On Mon, Feb 3, 2014 at 11:56 AM, Hermann Stamm-Wilbrandt
<STAMMW at de.ibm.com> wrote:
> Thanks for your XQuery 1-dimensional sample.
>
> There are 4 XQuery with JSONiq implemenations named on jsoniq.org:
> 28.io, Zorba, IBM Websphere DataPower Integration Appliance and Pascal
> XQuery engine
>
> It seems not to be that easy to measure runtime.
> Since http://try.zorba.io allows to share and run code I used that.
> The method I found was to place Zorba's datetime:current-time() in result
> sequence as first and last elements.
> And the matrix multiplications need to be executed often to result in
> measurable times (I did use 10.000.000).
>
> These are JSONiq (1) and your XQuery (2) implemenations:
> http://try.zorba.io/queries/xquery/vq+kL9tWK+jmntDZz0oxDcyrypA=
> http://try.zorba.io/queries/xquery/NIlfOIBmkdvt8+2zNmvM8Hf1+bo=
>
> The times reported are quite different although run on same processor:
> PT1.713634S (JSONiq) versus PT9.77805S (XQuery)
>
> Yes, that is only result for one processor. But I would assume even
(much)
> bigger differences in case the matrix dimensions become bigger and not
toy
> like as in the examples.
>
>
> (1)
> import module namespace datetime =
> "http://www.zorba-xquery.com/modules/datetime";
>
> declare variable $A := [
>   [1,2],
>   [3,4],
>   [5,6],
>   [7,8]
> ];
> declare variable $B := [
>   [1,2,3],
>   [4,5,6]
> ];
> declare variable $N := 10000000;
>
> let $R := ( datetime:current-time(),
>   for $h in 1 to $N return
>   [
>     for $i in 1 to count(jn:members($A)) return
>     [
>       for $k in 1 to count(jn:members($B(1))) return
>         fn:sum(
>           for $j in 1 to count(jn:members($B)) return
>             $A($i)($j) * $B($j)($k)
>         )
>     ]
>   ]
> , datetime:current-time() )
>
> return $R[count($R)] - $R[1]
>
> (2)
> import module namespace datetime =
> "http://www.zorba-xquery.com/modules/datetime";
>
> declare variable $a:=(2, (:2 columns :) 1,2, 3,4, 5,6, 7,8);
> declare variable $b:=(3, (:3 columns :) 1,2,3, 4,5,6);
> declare variable $N := 10000000;
>
> let $R := ( datetime:current-time(),
>   for $h in 1 to $N return
>     ( $b[1], for $i in 1 to xs:int((count($a) -1) div $a[1]), $j in 1 to
> xs:int($b[1]) return
>       sum( for $k in 1 to xs:int($a[1]) return ($a[($i -1)*$a[1]+$k+1] *
$b
> [($k -1)*$b[1]+$j+1]) ) )
> , datetime:current-time() )
>
> return $R[count($R)] - $R[1]
>
>
> Mit besten Gruessen / Best wishes,
>
> Hermann Stamm-Wilbrandt
> Level 3 support for XML Compiler team and Fixpack team lead
> WebSphere DataPower SOA Appliances
> https://www.ibm.com/developerworks/mydeveloperworks/blogs/HermannSW/
> https://twitter.com/HermannSW/
> http://stamm-wilbrandt.de/GraphvizFiddle/
> ----------------------------------------------------------------------
> IBM Deutschland Research & Development GmbH
> Vorsitzende des Aufsichtsrats: Martina Koederitz
> Geschaeftsfuehrung: Dirk Wittkopp
> Sitz der Gesellschaft: Boeblingen
> Registergericht: Amtsgericht Stuttgart, HRB 243294
>
>
>
>   From:       David Carlisle <davidc at nag.co.uk>
>
>   To:         Hermann Stamm-Wilbrandt/Germany/IBM at IBMDE,
talk at x-query.com,
>
>   Date:       02/02/2014 01:44 AM
>
>   Subject:    Re: [xquery-talk] Matrix Multiplication (JSONiq)
>
>
>
>
>
>
> On 01/02/2014 23:33, Hermann Stamm-Wilbrandt wrote:
>>
>> Last Sylvester there was a thread on Matrix Multiplication in
>> XQuery
>> http://markmail.org/message/7q7qnbbnjo7cljzv?q=list:com.x-query.talk
> +matrix+multiplication
>>
>>
>
>>
>> The biggest problem identified was that XQuery does not allow for
>> efficient representation of 2+dimensional arrays.
>>
>
> well it does, but as in other languages that only really have 1-D arrays
> (or languages such as C or Fortran where 2D arrays are a thin veneer
> over 1D arrays), you need to store a 2 D array as a 1D array with an
> additional integer giving the stride or leading dimension (in row or
> column order). To keep the arrays self contained I stored this as the
> first item in each sequence in the example below.
>
>
>
>
>> JSON does provide 2+dimensional arrays for free.
>>
>> I did not measure performance yet, but this JSONiq script looks very
>> similar to what would be done in C:
>> http://try.zorba.io/queries/xquery/jFd3Q8f82HuZGzcYDzQpdN4SdfY=
>>
>> declare variable $A := [ [1,2], [3,4], [5,6], [7,8] ]; declare
>> variable $B := [ [1,2,3], [4,5,6] ];
>>
>> [ for $i in 1 to count(jn:members($A)) return [ for $k in 1 to
>> count(jn:members($B(1))) return fn:sum( for $j in 1 to
>> count(jn:members($B)) return $A($i)($j) * $B($j)($k) ) ] ]
>>
>>
>
> In Xquery 1 you could do
>
>
> let $a:=(2, (:2 columns :)
> 1,2,
> 3,4,
> 5,6,
> 7,8),
>
> $b:=(3, (:3 columns :)
> 1,2,3,
> 4,5,6)
>
> return
>
> (
> $b[1],
> for $i in 1 to xs:int((count($a) -1) div $a[1]),
> $j in 1 to xs:int($b[1])
> return
> sum(
> for $k in 1 to xs:int($a[1]) return
> ($a[($i -1)*$a[1]+$k+1] * $b[($k -1)*$b[1]+$j+1])
> )
> )
>
>
> which produces
>
> 3 (:3 columns :)
>    9 12 15
>   19 26 33
>   29 40 51
>   39 54 69
>
>
>
>> And much simpler than in XSLT:
>> http://rosettacode.org/wiki/Matrix_multiplication#XSLT_1.0:
>>
>>
>
> As the above is in fact only Xpath 2, you could do the identical
> expression in XSLT 2
>
>
> David
>
>
>
>
> _______________________________________________
> talk at x-query.com
> http://x-query.com/mailman/listinfo/talk







More information about the talk mailing list