xsl-list
[Top] [All Lists]

Re: [xsl] A super-efficient way to compute the sum of A[i] * B[i] for i=1 to n?

2020-05-13 03:48:39
The cost of creating a thread (and handling its completion) here is far greater 
than the cost of the computation you are doing inside the thread (a single 
multiplication) so this result is no surprise. Multithreading only pays off 
when the amount of work done in each thread is quite substantial (which is why 
it's a feature that's only used if explicitly requested).

If you really want to get a speed-up from multithreading here, then it might be 
worth trying something along the lines

<xsl:variable name="batchSize" select="count($v1) idiv $THREADS"/>
<xsl:variable name="subtotals">
  <xsl:for-each select="1 to $THREADS" saxon:threads="{$THREADS}">
    <xsl:sequence select="sum(((. - 1) * $batchSize) + 1) to (. * $batchSize)) 
! $v1[current()] * $v2[current()]"/>
  </xsl:for-each
</xsl:variable>
<xsl:sequence select="sum($subtotals)"/>

(But there's probably a couple of off-by-one bugs there...)

To examine the difference between PE and EE we would need to study the detail 
(with performance, the devil is always in the detail). It may be due to 
bytecode generation; although hotspot bytecode generation was introduced in 
9.8, it's still sometimes the case that the cost of generating bytecode exceeds 
the benefit. The -TB command line option helps when studying this effect.

Michael Kay
Saxonica

On 13 May 2020, at 04:28, Dimitre Novatchev dnovatchev(_at_)gmail(_dot_)com 
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:

I played a little bit using saxon:threads:  
https://www.saxonica.com/html/documentation/extensions/attributes/threads.html
 
<https://www.saxonica.com/html/documentation/extensions/attributes/threads.html>
 , with the hope that this could lead to faster execution. The results are 
below, and they can be useful as a reference.
With a source XML document of 1M elements, each of which has a single text 
node with a numeric value, on my PC (6 cores, Intel i7-8700 CPU @3.20GHz, 
32.0GB RAM, x64-based processor and 64-bit Operating System (Windows 10)) I 
got these results:

Saxon Ver./Edition
saxon:threads
Time in seconds
Remarks
Saxon-EE 9.8.0.12
 1
1.8
 
Saxon-EE 9.8.0.12
 2
15.7
???????????????
----  “ -------“ ----------
 4
5.7
 
----  “ -------“ ----------
 6
4.3
 
----  “ -------“ ----------
 8
3.7
 
----  “ -------“ ----------
12
3.0
 
----  “ -------“ ----------
16
2.9
 
----  “ -------“ ----------
20
2.7
 
----  “ -------“ ----------
24
2.7
 
----  “ -------“ ----------
28
2.6
 
----  “ -------“ ----------
32
2.6
 
Saxon-PE 9.8.0.12
N/A
1.0
???????????????
 
Notice that the best result was reached when running Saxon-PE, in which the 
saxon:threads attribute is ignored and no threading takes place.



Also note that the best result with threading is when the number of threads 
is just 1.



Here is a fragment of the source XML document, just to give you an idea of 
the input:

<vectors>
<seq1>
 <n>0.1</n>
 <n>0.2</n>
 <n>0.3</n>
 <n>0.4</n>
 <n>0.5</n>
 <n>0.6</n>
 <n>0.7</n>
 <n>0.8</n>
 <n>0.9</n>
 <n>1</n>
 <n>0.1</n>
 <n>0.2</n>
 <n>0.3</n>
 <n>0.4</n>
 <n>0.5</n>
 <n>0.6</n>
 <n>0.7</n>
 <n>0.8</n>
 <n>0.9</n>
 <n>1</n>
 <n>0.1</n>

.  .  .  .  .  .  .  .

The <seq1> element has 1 000 000 (1M) child elements named "n".



Then it has an immediate sibling element <seq2> with contents that was copied 
from <seq1>.



Here is the transformation that uses saxon:threads:

<xsl:stylesheet version="3.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform 
<http://www.w3.org/1999/XSL/Transform>"
 xmlns:xs="http://www.w3.org/2001/XMLSchema 
<http://www.w3.org/2001/XMLSchema>" xmlns:saxon="http://saxon.sf.net/ 
<http://saxon.sf.net/>">
 <xsl:output method="text"/>
 <xsl:variable name="v1" select="/*/seq1/*/text()/number()"/>
 <xsl:variable name="v2" select="/*/seq2/*/text()/number()"/>
 <xsl:variable name="vLength" select="1000000"/>

  <xsl:template match="/">
    <xsl:variable name="vProds" as="xs:double*">
   <xsl:for-each select="1 to $vLength" saxon:threads="6">
     <xsl:sequence select="$v1[current()] * $v2[current()]"/>
   </xsl:for-each>
    </xsl:variable>
    
    <xsl:value-of select="sum($vProds)"/>
  </xsl:template>
</xsl:stylesheet>





Cheers,

Dimitre


On Sun, May 10, 2020 at 11:53 AM Dimitre Novatchev 
<dnovatchev(_at_)gmail(_dot_)com <mailto:dnovatchev(_at_)gmail(_dot_)com>> 
wrote:
For reference on fast sequential algorithms for computing the dot product, 
see this:

https://lemire.me/blog/2018/07/05/how-quickly-can-you-compute-the-dot-product-between-two-large-vectors/
 
<https://lemire.me/blog/2018/07/05/how-quickly-can-you-compute-the-dot-product-between-two-large-vectors/>
  

On Sat, May 9, 2020 at 10:52 AM Dimitre Novatchev 
<dnovatchev(_at_)gmail(_dot_)com <mailto:dnovatchev(_at_)gmail(_dot_)com>> 
wrote:
Hi Roger,

  > I need a super-efficient way to compute the sum of A[i] * B[i] for i=1 to 
n.  

In case you have n cores / processors, and the compiler knows to optimize 
functions like map(), zipWith() (for-each-pair() in XPath 3.0), then all 
processors can each do a corresponding multiplication in parallel in a single 
moment (computing cycle).

Then what remains is the summing of the results of these multiplications. 
This essentially is the map-reduce technique.

Interestingly enough, while not all reduce operations can be parallelized, in 
the case of sum() one can add together n numbers in Log2(n) summing steps -- 
very similar to the DVC (DiVide and Conquer) technique, but doing it parallel 
-- not sequentially. So, first there would be n/2 additions, then n/4 
additions (of the results of the first step), then n/8 additions, and so on 
-- in a total of ceiling(Log2(n)) steps. If for each steps we have sufficient 
number of processors (n/2 for the first step, less for the following steps), 
then the summing could be performed in Log2(n) computing cycles.

So, it seems that the whole computation could be performed in something like 
~ ceiling(Log2(n)) + 1 computing cycles.

Or maybe I am being wrong here? :)  Please, correct me.

Cheers,
Dimitre


On Sat, May 9, 2020 at 4:59 AM Costello, Roger L. 
costello(_at_)mitre(_dot_)org <mailto:costello(_at_)mitre(_dot_)org> 
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com 
<mailto:xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com>> wrote:
Hi Folks,

I need a super-efficient way to compute the sum of A[i] * B[i] for i=1 to n.

For example, suppose A is this:

<row>
    <col>0.9</col>
    <col>0.3</col>
</row>

and B is this:

<row>
    <col>0.2</col>
    <col>0.8</col>
</row>

I want to compute:

(0.9 * 0.2) + (0.3 * 0.8)

Here's one way to do it:

sum(for $i in 1 to count($A/col) return number($A/col[$i]) * 
number($B/col[$i]))

I suspect that is not the most efficient approach.

What is the most efficient approach? I will be doing hundreds of thousands of 
these computations, so I want to use the most efficient approach.

/Roger



XSL-List info and archive <http://www.mulberrytech.com/xsl/xsl-list>
EasyUnsubscribe <http://lists.mulberrytech.com/unsub/xsl-list/293509> (by 
email <>)
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--
<Prev in Thread] Current Thread [Next in Thread>