search

nicolasstucki / scala-rrb-vector

Implementation and benchmarking of Scala Vectors with relaxed radix balanced trees for more efficient concatenations
Apache License 2.0
54 stars 4 forks source link

Concatenation yields two single element leafs #11

Open konsumlamm opened 3 years ago

konsumlamm commented 3 years ago

Code to reproduce (I cloned the repo to have access to the private methods):

val vec1 = RRBVector.range(0, 1025)
val vec2 = RRBVector.range(0, 1025).map(x => -x) // to distinguish between vec1 and vec2
val vec = vec1 ++ vec2
vec.focusOn(2048)
println(vec.debugToString) // display0 = [Ljava.lang.Object;@63e2203c [-1023]
vec.focusOn(2049)
println(vec.debugToString) // display0 = [Ljava.lang.Object;@76707e36 [-1024]

As you can see, the resulting vector has two (consecutive) single element leafs.

Now I'm not sure if this is the correct behaviour. The concatenation algorithm seems to work as described, but the generated tree doesn't seem right, shouldn't every "inner" node have a length of 32 or 31? As I am currently implementing my own RRB Vector library (and I'm getting the same result there), I wanna make sure that this behaviour is intended.

nicolasstucki commented 3 years ago

Not sure is this precise instance might be a bug. But in some instances, when we know that we are not going to use the end of the array we trim it to save a bit of space. Maybe it is simpler to start by always creating arrays of 32 and once the implementation works, add the optimization.