build.clojure.org test results were good for the committed fix. Resolving as fixed.

New automated test cases that fail with the existing core.rrb-vector code, plus a fix that in all testing before has been found to preserve the O(log N) run time of catvec, have been committed here:

I will close this issue as fixed if build.clojure.org gives good test results, as those changes already have on my machine.

The best fix for this issue is to make it so that the depth of the tree returned by catvec never gets too large, within the desired O(log N) run-time bounds. I don’t have such a fix yet.

In thinking about the problem, I realized that if one wanted a simpler fix to get going with, but would not be guaranteed O(log N) run-time bounds, one could, inside of catvec, check whether the result tree was “too tall and skinny” just before returning the result, and if it was, do an O(N) creation of a perfectly regular vector, i.e. the densest kind, as created by clojure.core/vector, and return that instead.

It is kind of like a “stop the world garbage collector” :-)

A likely culprit, and probably the only one where this could actually be caused, is in catvec returning data structures that add new levels to the tree when it should not.

This is an interesting one. From a bit of investigation, the internal tree data structure gets so “tall and skinny”, i.e. so far from an average branching factor of 32-way, that even a vector with only around 1,000 elements gets deeper than 12 levels. The ‘shift’ values go up to around 65, which causes the code to misbehave, since it is written assuming that the shift values will never go over 30.

Fixing this means finding the part of the code that is trying to keep the trees wide and shallow, and fixing it.