Performance variations

Added by Vladimir Nesterovsky almost 4 years ago

Hello,

while testing shortest path graph algorithm I've found performance variations depending on the way parameters are passed.

There are three tests based on map of Rome:

that use three implementations of algorithm that differ only in a way of how parameters are handled within recursion:

dijkstra-search.xslt uses following technique to pass parameters (note the first dummy parameter):

fold-left
(
  $neighbors,
  (0, $queue, $visited),
  function($state as item()*, $neighbor as map(*)) 
  {
    let $queue := $state[2] return
    let $visited := $state[3] return

dijkstra-search.v2.xslt uses:

fold-left
(
  $neighbors,
  ($queue, $visited),
  function($state as item()*, $neighbor as map(*)) 
  {
    let $queue := $state[1] return
    let $visited := $state[2] return

dijkstra-search.v3.xslt uses:

fold-left
(
  $neighbors,
  map { 'queue': $queue, 'visited': $visited },
  function($state as map(*), $neighbor as map(*)) 
  {
    let $queue := $state?queue return
    let $visited := $state?visited return

On my laptop:

dijkstra-search.xslt runs in 1598.9737ms
dijkstra-search.v2.xslt runs in 7572.8157ms
dijkstra-search.v3.xslt runs in 10436.5133ms

My observations show that the difference is a multiplication factor, as it scales with distance between points. Other than that all implementations produce same results.

Question:

Why do we see such a difference?
What is the best practice to deal with such situation?

Replies (5)

Please register to reply

RE: Performance variations - Added by Vladimir Nesterovsky almost 4 years ago

I've added one more test: dijkstra-search.v4.xslt that is based purely on xsl:iterate instruction that looks like this:

...
<xsl:variable name="next" as="item()*">
  <xsl:iterate select="$neighbors">
    <xsl:param name="queue" as="map(*)" select="$queue"/>
    <xsl:param name="visited" as="map(*)" select="$visited"/>

    <xsl:on-completion select="$queue, $visited"/>
...

takes only 688.554ms, and adds more to my non-understanding.

RE: Performance variations - Added by Michael Kay almost 4 years ago

Thanks for sharing the data, but as there's no suggestion of any product problems or unexpected anomalies here, I can't offer to do any investigation.

As far as I can see you're using Saxon-HE whose source code is available, so if you want to investigate the differences in more detail, you are very welcome to do so, and if you find any opportunities for improving the implementation, please let us know.

RE: Performance variations - Added by Vladimir Nesterovsky almost 4 years ago

I can observe at least one strange behavior related to performance: dijkstra-search.xslt that uses sequence of three items to represent fold-left's $zero, where the first item is dummy comparing to dijkstra-search.v2.xslt that uses sequence of two items to represent fold-left's $zero.

Performance difference is by factor ~4, where dijkstra-search.xslt is faster. Other than that I agree I did not report on any incorrect behavior.

RE: Performance variations - Added by Michael Kay almost 4 years ago

I'm mildly surprised at the size of the difference, but we do handle the subscript [1] differently from other subscripts. And optimizations sometimes behave in non-linear ways; a small optimization opens the door for a bigger one. Have you checked the -explain output?

RE: Performance variations - Added by Vladimir Nesterovsky almost 4 years ago

Have you checked the -explain output?

Yes, I've checked it, and see no differences except those related to difference of parameters.

I'm attaching those explain files here. Just in case.

Download all files

explain.rome-test.xml (121 KB) explain.rome-test.xml
explain.rome-test.v2.xml (121 KB) explain.rome-test.v2.xml

(1-5/5)

Please register to reply

Project

Profile

Help

Saxon