Saxon

Which processor did you use in oXygen, only Saxon EE? Or HE as well?

The symptoms suggest that the array is being created as an unbalanced tree, leading to stack overflow when subsequently scanning the tree in a recursive tree walk.

Interesting, I tried the code with SaxonCS and SaxonJS from the command line and it works to output e.g.

<?xml version="1.0" encoding="UTF-8"?>
<output xmlns:array="http://www.w3.org/2005/xpath-functions/array"
         xmlns:tan="tag:textalign.net,2015:ns"
         xmlns:xs="http://www.w3.org/2001/XMLSchema">12288</output>

but both Saxon HE 11.3 J and EE 11.3 J from the command line just crash out with lots of at net.sf.saxon.ma.parray.ImmList2.iterator(ImmList2.java:120) lines.

But oXygen 24.1 also gives me a StackOverflow when using Saxon 10.6 EE.

The failure is going to be sensitive to the amount of stack space available.

array:join() is being called to join 12288 arrays each apparently containing one member which is a sequence of length 3.

array:join() is implemented by repeated application of array:concat().

It looks to me as if the ImmList2 binary tree is never rebalanced when adding a singleton array using concat(). This is clearly a bug.

There is in fact an attempt at rebalancing, but it's not effective. After 13 or so additions, the tree looks like this:

((1,1),1)
(((1,1),1),1)
(((1,1),1),(1,1))
(((1,1),1),((1,1),1))
(((1,1),1),(((1,1),1),1))
(((1,1),1),((((1,1),1),1),1))
(((1,1),1),(((((1,1),1),1),1),1))
(((1,1),1),((((((1,1),1),1),1),1),1))
(((1,1),1),(((((((1,1),1),1),1),1),1),1))
(((1,1),1),((((((((1,1),1),1),1),1),1),1),1))
(((1,1),1),(((((((((1,1),1),1),1),1),1),1),1),1))

I think it's rebalacing at the top level, but isn't recursively rebalancing below the top level.

The code isn't recursively rebalancing the trees created during the rebalancing operation. When we add this, we get

((1,1),1)
(((1,1),1),1)
(((1,1),1),(1,1))
(((1,1),1),((1,1),1))
(((1,1),1),(((1,1),1),1))
(((1,1),1),(((1,1),1),(1,1)))
(((1,1),1),(((1,1),1),((1,1),1)))
(((1,1),1),(((1,1),1),(((1,1),1),1)))
(((1,1),1),(((1,1),1),(((1,1),1),(1,1))))
(((1,1),1),(((1,1),1),(((1,1),1),((1,1),1))))
(((1,1),1),(((1,1),1),(((1,1),1),(((1,1),1),1))))
(((1,1),1),(((1,1),1),(((1,1),1),(((1,1),1),(1,1)))))
(((1,1),1),(((1,1),1),(((1,1),1),(((1,1),1),((1,1),1)))))
(((1,1),1),(((1,1),1),(((1,1),1),(((1,1),1),(((1,1),1),1)))))
(((1,1),1),(((1,1),1),(((1,1),1),(((1,1),1),(((1,1),1),(1,1))))))
(((1,1),1),(((1,1),1),(((1,1),1),(((1,1),1),(((1,1),1),((1,1),1))))))

which looks much healthier. But it's still not quite right.

Add another call on rebalance() and we get

((1,1),1)
(((1,1),1),1)
(((1,1),1),(1,1))
(((1,1),1),((1,1),1))
(((1,1),1),(((1,1),1),1))
(((1,1),1),(((1,1),1),(1,1)))
(((1,1),1),(((1,1),1),((1,1),1)))
(((1,1),1),(((1,1),1),(((1,1),1),1)))
(((1,1),1),(((1,1),1),(((1,1),1),(1,1))))
(((1,1),1),(((1,1),1),(((1,1),1),((1,1),1))))
((((1,1),1),((1,1),1)),(((1,1),1),(((1,1),1),1)))
((((1,1),1),((1,1),1)),(((1,1),1),(((1,1),1),(1,1))))
((((1,1),1),((1,1),1)),(((1,1),1),(((1,1),1),((1,1),1))))
((((1,1),1),((1,1),1)),(((1,1),1),(((1,1),1),(((1,1),1),1))))
((((1,1),1),((1,1),1)),(((1,1),1),(((1,1),1),(((1,1),1),(1,1)))))
((((1,1),1),((1,1),1)),(((1,1),1),(((1,1),1),(((1,1),1),((1,1),1)))))

which is now looking properly balanced. I'm just slightly concerned (a) that we're doing more work than is needed to keep it balanced, and (b) that I'm not 100% confident the process is guaranteed to terminate.

A couple of thoughts on this:

(a) I'm sure there must be a better way of creating an iterator that walks a binary tree, rather than using the stack of iterators we currently employ.

(b) It would be nice to use the "ZenoChain" machinery that we now use for incrementally-constructed sequences, rather than having a completely separate mechanism. The ZenoChain consolidates chunks of the sequence away from its ends, meaning there are fewer objects to traverse and less work keeping the structure balanced. If it's good enough for sequences it should be good enough for arrays...

Added this as XSLT3 test case arrays-306.

Another litte thought: instead of array:join() working sequentially through the supplied arrays doing an incremental array:concat() on each one, it could do a divide-and-conquer approach (split the sequence in two, do array-join on each, then array-concat the results) which would mean much less incremental rebalancing is needed on the constructed tree.

Not sure if this helps. I revised the function, replacing array:join() with an incremental application of array:append(). The revised function worked fine with large sets in Oxygen, but I encountered the same error conditions in Java.

Have you tried increasing the stack size in Java? It's clear from the evidence that a little more stack space will give you breathing room.

I just tried doubling and tripling memory allowances, but no success--still the same error. My copy of VisualVM didn't show any unusual roofing of the memory during execution. But I may not know what to look for. I tried to remove IntelliJ from the equation by building and running from the CLI, but build dependencies were the customary thorn in my side, and I couldn't get it off the ground.

I wrote another revised permutation function, this time depending not upon arrays but upon an element tree, and the Java environment had no problem with the 12K+ permutations. Performance was only slightly longer, 136 ms extra for an operation that took on average 6,018 ms, averaged across 16 tests.

We currently hold the size (aka weight) of a tree in each node, so perhaps we should look for an algorithm that balances trees by weight rather than height:

https://en.wikipedia.org/wiki/Weight-balanced_tree

(But note, for some reason we only hold keys in leaf nodes. No idea why that decision was made, but let's try to avoid reinventing the whole thing...)

The balancing operations (rotations) for a weight-balanced tree are identical to those for a height-balanced tree; the difference is the criterion for deciding whether the tree is balanced. This is given in Wikipedia as size(left) <= α * size(right) && size(right) <= α * size(left), where the optimum value of α is 0.29289 (= 1 - √2/2).

With this change, the DocBook test passes. But I now get a StackOverflow in XSLT3 test arrays-306, creating an iterator over an array, which clearly shows that the tree is not balanced. I've made changes to fix that, and now arrays-305 gives infinite recursion while rebalancing. It looks as if the threshold level of imbalance is too low, allowing oscillation. Perhaps this is because I took the threshold value from a binary tree used as a search tree rather than a list, where the size of a new parent node is M+N+1 rather than M+N.