Why are vectors so shallow?

Question

What is the rationale behind Scala's vectors having a branching factor of 32, and not some other number? Wouldn't smaller branching factors enable more structural sharing? Clojure seems to use the same branching factor. Is there anything magic about the branching factor 32 that I am missing?

Answer 1

It would help if you explained what a branching factor is:

The branching factor of a tree or a graph is the number of children at each node.

So, the answer appears to be largely here:

http://www.scala-lang.org/docu/files/collections-api/collections_15.html

Vectors are represented as trees with a high branching factor. Every tree node contains up to 32 elements of the vector or contains up to 32 other tree nodes. Vectors with up to 32 elements can be represented in a single node. Vectors with up to 32 * 32 = 1024 elements can be represented with a single indirection. Two hops from the root of the tree to the final element node are sufficient for vectors with up to 2¹⁵ elements, three hops for vectors with 2²⁰, four hops for vectors with 2²⁵ elements and five hops for vectors with up to 2³⁰ elements. So for all vectors of reasonable size, an element selection involves up to 5 primitive array selections. This is what we meant when we wrote that element access is "effectively constant time".

So, basically, they had to make a design decision as to how many children to have at each node. As they explained, 32 seemed reasonable, but, if you find that it is too restrictive for you, then you could always write your own class.

For more information on why it may have been 32, you can look at this paper, as in the introduction they make the same statement as above, about it being nearly constant time, but this paper deals with Clojure it seems, more than Scala.

http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf