[xquery-talk] Matrix Multiplication (JSONiq)

[Hermann Stamm-Wilbrandt]

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