GlenKPeterson
commented
8 years ago Excellent questions!
"What's the preferred way to create a PersistentVector with multiple elements?"
If you have a fixed number of elements, use vec(a, b, c)
To create a vector from a traditional Java collection and maybe transform them some how (like filter some of them):
xform(collection)
.filter(x -> x != 3)
.toImList()If you are stuck building a vector in a legacy loop, there's a MutableVector inside PersistentVector, but I tried to make it really hard to access. If you think you really need it, please post the code that justifies exposing this potentially confusing feature for performance reasons.
"Would you recommend to first create a list or array, then use concat to benefit from the mutable vector optimization?"
No. Creating lists or arrays will likely be more expensive than using the immutable concat (TODO: prove this one way or the other).
Your unspoken follow-up questions are:
- Why not use PersistentVector.MutableVector inside Transformable.toImList()?
This is an oversight. Thanks for pointing it out. I can fix this over the weekend and have a new version for you on Monday by adding the following static method to PersistentVector (to avoid exposing MutableVector):
public static <T> ImList<T> fromXform(Transformable<T> trans) {
return trans.foldLeft(emptyTransientVector(),
MutableVector<T>::append).persistent();
}And changing the body of Transformable.toImList() to:
return PersistentVector.fromXform(this);But I want to run JMH (the Java Microbenchmarking Harness) to prove that it makes a positive difference for vectors of various sizes before I commit the change.
- Why create an unnecessary list wrapper inside StaticImports.vec(T... items)?
// INTENDED USE
ImList<Integer> myVec = vec(1,2,3,4,5,6);
// ALSO POSSIBLE: PROTECT AGAINST MUTATION
int[] myInts = { 1,2,3,4,5,6 };
ImList<Integer> myVec = vec(myInts);
myInts[3] = 359;I didn't want to trust the array we are passed, so I copy it to make sure the situation above causes no mutation inside the vector. Lists are easier to work with. I timed it (without JMH) and it looked like the Arrays.asList() made less than a 10% difference (or no difference) vs iterating the array directly during the copy.
If I remember correctly, the real speed limit is on adding an element, we copy an array of N elements (the tail of the existing vector) into an array of N+1 elements (the new tail), then add the new element to the second array. Java writes a 0 into each element of the second array, then copies elements over every one of those zeros. If there was a way to get Java to provide an uninitialized array, the existing implementation might be 50% faster for it. Maybe when they get rid of Unsafe in Java 9 they'll expose something like this?
This copy-on-write strategy for the tail array is what makes it thread-safe. Other synchronization could cause deadlocks that are potentially more (or less) time consuming, but probably harder to reason about. I don't know. Without proving that I could make it better, I eventually moved on.
Would it make sense to have a builder for this? A builder could perhaps perform additional optimizations, such as using a different representation for vectors with a small number of elements.
I did several experiments along these lines and had real trouble improving on Rich Hickey's design. But your perspective may yield better results. I am interested in hearing more!
I think Google Guava uses builders to create unmodifiable collections. But then if you know you're going to add more, you're left passing a mutable builder around. If you ever have to add just one more element to an unmodifiable collection, it forces an expensive copy. Both situations encourage surprises. The Clojure collections are always immutable with fairly fast appends. They take less thought, less planning, and is always safe to add another element without a huge performance penalty.
If you need the kind of performance you can only get by mutating in place, you can rewrite that piece of code using the traditional Java collections. My experience so far with these transforms and the Clojure collections is that my first pass has fewer bugs and runs faster because I'm not worrying about the shortcomings I just mentioned, so I can focus instead on the Big O complexity of what I'm doing. I generally never need to do that rewrite. In fact, things often go faster when I rewrite traditional Java using these collections just because there is nothing to distract me from the Big O consequences of the transformations.
Still, if all transformations are done functionally, that might mean you never have to expose the builder. With enough forethought, you rarely need to add just one more item later. I need to think more on this.
Anyway, I guess timing the vector against Guava would be another good task. That might be the following weekend though.
Great questions. I hope this helped without getting too far off topic. I'm interested in hearing your follow-ups!
pniederw
What's the preferred way to create a PersistentVector with multiple elements? Would you recommend to first create a list or array, then use
concatto benefit from the mutable vector optimization? Would it make sense to have a builder for this? A builder could perhaps perform additional optimizations, such as using a different representation for vectors with a small number of elements.