Performance issue (4x) with indexed sparse vectors and distanceSquared

[cnuernber]

Replacing:

(.distanceSquared sparse-indexed-left sparse-indexed-right)

with:

(defn distance-squared
  ^Double [^SparseIndexedVector lhs ^SparseIndexedVector rhs]
  (let [result (.clone lhs)]
    (.sub result rhs)
    (.magnitudeSquared result)))

Resulted around a 4X perf gain.

My guess is there is a bunch of work to be done around special casing operations between types (even higher order operations) so that when using specialized types the full benefits of the type are realized.

[mikera]

You are hitting reflection here.... If you use a Clojure type hint then it should solve the issue, e.g.

(.distanceSquared ^AVector sparse-indexed-left ^AVector sparse-indexed-right)

[cnuernber]

Definite possibility but I think that is not the case here.

I have:

(set! warn-on-reflection true)

At the top of the file and it compiles with no warnings.

I dove through the code to figure out what is going on and here are the results of the analysis:

First, we are dealing with very sparse vectors, basically 1 out of 100 elements are nonzero. Given that each vector is of len length with num-elems being (* .01 len) nonzero items on average.

The implementation of distance square for AVector is here:

public double distanceSquared(AVector v) {
int len=checkSameLength(v);
double total=0.0;
for (int i=0; i<len; i++) {
double d=unsafeGet(i)-v.unsafeGet(i);
total+=d*d;
}
return total;
}

This has a running time of O(len) where len is the total length of the indexed vectors.

The implementation I attached at the top of the file has a running time on the order of num-elems given that the sparse vector clone, sub, and magnitudeSquared operations are all on the order of O(num-elems).

[mikera]

OK thanks yes I see what is happening. this implementation should probably be in Vectorz itself rather than on the Clojure side, I'll take a look and insert it in the right place.

Thanks!

[mikera]

OK I think this is fixed in this commit:

82bc83a

[cnuernber]

Yep, verified from this end.