Contribution: Immutable Persistent Vector

[scabug]

I have created a full port of the Clojure PersistentVector data structure to Scala. This data structure differs significantly from other ordered structures currently in the standard library in that it makes nearly-constant time performance guarantees. More precisely, reads and writes are both O(log_32(n)) (where n is the length of the Vector), with writes having ~\theta(32). Since n < 2^32^, the absolute worst-case read/write performance is O(7x), where x is some constant factor representing overhead.

The data structure is random access both in reads and in writes. Appending and removal are done at the tail, "updates" are possible at arbitrary indexes. The data structure is highly-persistent, and the implementation is internally immutable. Thus, Vector is suitable for asynchronous access and supports immutable revisions without performance degradation.

Performance benchmarks can be provided if necessary. In general, Vector is 2-3x slower than the mutable ArrayBuffer, but several orders of magnitude faster than the next-closest immutable counterpart (IntMap).

This Vector class fully implements the standard collection methods, providing specific overrides for Vector[T] where applicable (e.g. #map(...):Vector[B]). It also provides implementations of several Array-like methods, such as #zipWithIndex. Projection and reversal are both constant-time operations, though the first update operation on the result will have linear complexity (because of copying).

I have performed extensive testing of this data structure using ScalaCheck, achieving 98% line coverage and 82% branch coverage (according to Cobertura). The sources for both the data structure and its test suite are currently hosted on GitHub:

• http://github.com/djspiewak/scala-collections/tree/master/src/main/scala/com/codecommit/collection/Vector.scala
• http://github.com/djspiewak/scala-collections/tree/master/src/test/scala/VectorSpecs.scala

Some stress-test usage can be seen here: http://github.com/djspiewak/scala-collections/tree/master/src/test/scala/VectorPerf.scala

This data structure does not wholly constitute my own work. It is literally a straight port of Rich Hickey's PersistentVector Java class from the Clojure language. As of today, the Java source of this class (specifically) has been placed under the BSD license.

I would like to submit the Vector class for inclusion into the Scala immutable collections library.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-1509?orig=1 Reporter: @djspiewak Attachments:

• vector-011009.patch (created on Jan 10, 2009 8:08:28 PM UTC, 13354 bytes)

[scabug]

Anders Bach Nielsen [X] (nielsen) said: After the collections redesign by Martin, this should be added to the library. Assigning to Martin, because he will proberly have to supervise this.

[scabug]

@djspiewak said: Patch against current trunk/

[scabug]

@odersky said: Thanks for reminding me of this. We certainly want immutable persistent vectors to be in the library! In fact Phil Bagwell, who was the original inventor of some of the datastructures in Clojure, has been working with Tiark Rompf on implementations which are improved further. I am reassigning to Tiark, so he can judge what to take over from the patch.

[scabug]

@TiarkRompf said: immutable.Vector added in r19369