Performance issue (4x) with indexed sparse vectors and distanceSquared about vectorz HOT 5 CLOSED

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)

from vectorz.

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).

from vectorz.

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!

from vectorz.

OK I think this is fixed in this commit:

82bc83a

from vectorz.

Yep, verified from this end.

from vectorz.