Prepend complexity of scala vector

Question

I am referring to official documentation

which shows prepend complexity of Vector as "effectively constant" (eC). But my understanding is that for a vector, prepend would mean that all other indexes need to be adjusted as well which will make the operation O(n) or L (linear). Could anyone please explain how is prepend in vector eC (effectively constant).

Answer 1

Found following visual explanation of the prepend operation where one character is getting prepended in each step. Picture only shows 2 slots per block for easy explanation but in case of vector it would be 32 slots per block. Vector maintains an start index (or offset in the picture) to keep track of empty places as well.

Following is the source code from the Vector.scala. Since it does not move all the elements it is not O(n).

override def prepended[B >: A](value: B): Vector[B] = {
    if (endIndex != startIndex) {
      val blockIndex = (startIndex - 1) & ~31
      val lo = (startIndex - 1) & 31

      if (startIndex != blockIndex + 32) {
        val s = new Vector(startIndex - 1, endIndex, blockIndex)
        s.initFrom(this)
        s.dirty = dirty
        s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex)
        s.display0(lo) = value.asInstanceOf[AnyRef]
        s
      } else {

        val freeSpace = (1 << (5 * depth)) - endIndex           // free space at the right given the current tree-structure depth
        val shift = freeSpace & ~((1 << (5 * (depth - 1))) - 1) // number of elements by which we'll shift right (only move at top level)
        val shiftBlocks = freeSpace >>> (5 * (depth - 1))       // number of top-level blocks

        if (shift != 0) {
          // case A: we can shift right on the top level
          if (depth > 1) {
            val newBlockIndex = blockIndex + shift
            val newFocus = focus + shift

            val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex)
            s.initFrom(this)
            s.dirty = dirty
            s.shiftTopLevel(0, shiftBlocks) // shift right by n blocks
            s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // maybe create pos; prepare for writing
            s.display0(lo) = value.asInstanceOf[AnyRef]
            s
          } else {
            val newBlockIndex = blockIndex + 32
            val newFocus = focus

            val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex)
            s.initFrom(this)
            s.dirty = dirty
            s.shiftTopLevel(0, shiftBlocks) // shift right by n elements
            s.gotoPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // prepare for writing
            s.display0(shift - 1) = value.asInstanceOf[AnyRef]
            s
          }
        } else if (blockIndex < 0) {
          // case B: we need to move the whole structure
          val move = (1 << (5 * (depth + 1))) - (1 << (5 * depth))
          val newBlockIndex = blockIndex + move
          val newFocus = focus + move

          val s = new Vector(startIndex - 1 + move, endIndex + move, newBlockIndex)
          s.initFrom(this)
          s.dirty = dirty
          s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // could optimize: we know it will create a whole branch
          s.display0(lo) = value.asInstanceOf[AnyRef]
          s
        } else {
          val newBlockIndex = blockIndex
          val newFocus = focus

          val s = new Vector(startIndex - 1, endIndex, newBlockIndex)
          s.initFrom(this)
          s.dirty = dirty
          s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex)
          s.display0(lo) = value.asInstanceOf[AnyRef]
          s
        }
      }
    } else {
      // empty vector, just insert single element at the back
      val elems = new Array[AnyRef](32)
      elems(31) = value.asInstanceOf[AnyRef]
      val s = new Vector(31, 32, 0)
      s.depth = 1
      s.display0 = elems
      s
    }
  }

Answer 2

No indexes need to be adjusted, because Scala's Vector is implemented as a tree. More specifically, a 32-way tree, meaning that each parent has 32 children.

http://www.scala-lang.org/api/2.12.0/scala/collection/immutable/Vector.html

It is backed by a little endian bit-mapped vector trie with a branching factor of 32.

This means that all operations take O(log32(n)) time to be performed. If this is not immediately obvious to you, just follow the logic from the more familiar binary trees, which have O(log2(n)) complexity on all operations.

However, there is a slight controversy on whether this complexity should be considered logarithmic or effectively constant. Theoretically speaking, it's a good old O(log n), but the fact that the base of the logarithm is 32, combined with some other implementation details (e.g. cacheing) makes it seem almost constant in practice (or, as they call it, "effectively constant").

Li Haoyi has a great article on this subject.