scalaz/scalaz — pull request #860 by djspiewak (2014-12-04 18:53:04+00:00)
Title: IVector

@puffnfresh encouraged me to "go for it" and just implement `IVector`. So here it is. Huzzah!

There are a couple of things to call out here. First, I have included the BSD license header in the source code. I did this because, *originally* (as in, about six years ago) this code was a straight port of the Clojure vector implementation. That was a long, long time ago, and I've now rewritten the code three times. The second, and most significant rewrite was a loose collaboration with @richhickey, who was toying with an idea of polymorphically specializing the seven vector cases to enable better HotSpot optimization. To my knowledge, this idea never made it into Clojure itself, since the gains that I measured from my implementation were somewhat marginal (extant, but not significant enough to care). History lesson aside, we may in fact be far enough removed from the original Clojure implementation to call this freshly copywritten work. I would really like it if Rich could weigh in on this point.

Second, you'll notice that this is basically implemented in terms of `Array[AnyRef]`. That is not a necessary state of affairs! I plan on specializing this data structure (using actual `@specialized` and some implicitly resolved path dependent types), which would give us the insanely exciting property of having a `Vector[Int]` that is basically as fast as one *primitive* array lookup, one megamorphic and one monomorphic dispatch. All while being immutable and pure and working within the existing Scalaz abstraction framework. That makes me pretty excited! But I decided to PR this first just so we could get the ball rolling. Slow, generic case now, specialization later.

Third, in case it isn't clear, this is a different data structure from what is in the Scala standard library. It has very, *very* fast append (`:+`). Very fast. Lookups are also extremely fast (and I do include an unsafe `apply` method to avoid extra boxing if desired). In fact, in my benchmarks (which unfortunately date back to 2.9), this data structure is between 2 and 4 times faster than the Scala standard library at appends, and about 2 times faster at random reads. The tradeoff is that *prepend* (`+:`) is O(n), whereas the Scala standard library `Vector` promises `O(log_32 n)` for prepending. The Scala standard library vector also provides slightly better locality of reference for usage patterns which "randomly" read and write repeatedly from the same range of indices (up to width 32). In practice, I tend to think that optimizing random reads and appends is better, but I understand other people may have a difference of opinion.

Fourth, many of the function implementations here are less efficient than they could be. In some cases, *much* less efficient. Comment and complain and I'll make it better, but for a first cut, I really didn't care. :-D I didn't go out of my way to make it slow, but there are a lot of functions and I just wanted to get them out.

Fifth (bonus point!), some of the tests for both `IVector` and `IList` are done using ScalaCheck and fail to generate values which actually test anything reasonable. A fun exercise for the whole family is taking the `drop` implementation for `IList` and adding a `reverse` to the final output. The test will *not* detect this aberration. Part of this is the 33 case limit, but most of it is just somewhat naive property design. For *one* idea on how to improve this, see the test I added for `IVector#get`. Discussion welcome on this point, since my `get` property is certainly not without flaws.

Anyway, enjoy! More work is coming here, but this *should* be ready for merge.