## Performance variations

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)

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 Kayabout 2 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.

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 Kayabout 2 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?