[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