Performance of Vector.slice and Vector.concat

Question
1

I am making another attempt to get the in and outs of the new Vector, in particular slicing and concatenation. It seems like slicing is O(logn) (well, O(1) because Int.MaxValue is small enough), but appending a new Vector is O(n)? I am confused as there is a size check made using a constant Log2ConcatFaster, which would imply O(logn) I would expect from a finger tree, but the only optimization I actually see is appending whole arrays on the lowest level only? Is it the price of having a packed structure and better random indexing performance than in a BTree-based finger tree?

2

re: concat, have you seen https://github.com/scala/scala/pull/10159 ?

3

I haven’t. This seems to settle the issue that it’s O(n). A bit surprising for me, considering it’s advertised as a finger tree, although I guess that faster apply and lesser overhead due to tight packing is worth it. Do you know what’s the complexity of slice?

4

This seems to settle the issue that it’s O(n) . A bit surprising for me, considering it’s advertised as a finger tree

I’m confused what you’re referring to. What is “it”? Are there two different 'it"s here?

Vector append was O(n), but the PR (10159) fixes that. The PR will be included in the upcoming Scala 2.13.11 release.

I don’t know about slice, but have you looked at Rewrite Vector (now "radix-balanced finger tree vectors"), for performance by szeiger · Pull Request #8534 · scala/scala · GitHub ? That’s the first place I’d look. You could also look at the source code.