Performance of splitAt function on a vector

Question

Most operations on a vector are effectively constant because of its trie representation. However, I cannot figure out what the performance profile is of the splitAt implementation.

It is defined in the library as:

override /*IterableLike*/ def splitAt(n: Int): (Vector[A], Vector[A]) = (take(n), drop(n))

The take function has the following definition:

  override def take(n: Int): Vector[A] = {
    if (n <= 0)
      Vector.empty
    else if (startIndex + n < endIndex)
      dropBack0(startIndex + n)
    else
      this
  }

And the dropBack0 has the following definition:

  private def dropBack0(cutIndex: Int): Vector[A] = {
    val blockIndex = (cutIndex - 1) & ~31
    val xor = startIndex ^ (cutIndex - 1)
    val d = requiredDepth(xor)
    val shift = (startIndex & ~((1 << (5*d))-1))    
    val s = new Vector(startIndex-shift, cutIndex-shift, blockIndex-shift)
    s.initFrom(this)
    s.dirty = dirty
    s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex)
    s.preClean(d)
    s.cleanRightEdge(cutIndex-shift)
    s
  }

As you can see dropBack0 is doing some pretty complicated surgery.

Does splitAt have effectively constant performance or is it worse? It seems to be effectively constant.

Answer 1

It is effectively constant. Vector is a tree with branching factor 32. take and drop operations are performed in o(log₃₂N * 32). As the height of the tree can't be more than 5, number of operations for take, drop or update in worst case will be 5 * 32 = 160.

Answer 2

Yes, if you follow each method called in dropBack0, all of them require constant or effectively constant (maximum array size 32) time.