You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by GitBox <gi...@apache.org> on 2020/10/30 00:03:58 UTC
[GitHub] [lucene-solr] jtibshirani opened a new pull request #2047: LUCENE-9592: Use doubles in VectorUtil to maintain precision.
jtibshirani opened a new pull request #2047:
URL: https://github.com/apache/lucene-solr/pull/2047
Currently we use floats throughout the vector computations like dot product.
This PR switches to doubles to avoid a loss of precision.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] jtibshirani commented on a change in pull request #2047: LUCENE-9592: Use doubles in VectorUtil to maintain precision.
Posted by GitBox <gi...@apache.org>.
jtibshirani commented on a change in pull request #2047:
URL: https://github.com/apache/lucene-solr/pull/2047#discussion_r514636862
##########
File path: lucene/core/src/java/org/apache/lucene/util/VectorUtil.java
##########
@@ -25,47 +25,22 @@
private VectorUtil() {
}
- public static float dotProduct(float[] a, float[] b) {
- float res = 0f;
- /*
- * If length of vector is larger than 8, we use unrolled dot product to accelerate the
- * calculation.
- */
- int i;
- for (i = 0; i < a.length % 8; i++) {
- res += b[i] * a[i];
- }
- if (a.length < 8) {
- return res;
- }
- float s0 = 0f;
- float s1 = 0f;
- float s2 = 0f;
- float s3 = 0f;
- float s4 = 0f;
- float s5 = 0f;
- float s6 = 0f;
- float s7 = 0f;
- for (; i + 7 < a.length; i += 8) {
- s0 += b[i] * a[i];
- s1 += b[i + 1] * a[i + 1];
- s2 += b[i + 2] * a[i + 2];
- s3 += b[i + 3] * a[i + 3];
- s4 += b[i + 4] * a[i + 4];
- s5 += b[i + 5] * a[i + 5];
- s6 += b[i + 6] * a[i + 6];
- s7 += b[i + 7] * a[i + 7];
+ public static double dotProduct(float[] a, float[] b) {
Review comment:
I thought it could make sense to keep a simple approach for now before we have a vector search implementation and benchmarking set-up (in the spirit of not optimizing too early) ? There are a few options we may want to try, like decoding and taking the dot product at the same time.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] jtibshirani commented on a change in pull request #2047: LUCENE-9592: Use doubles in VectorUtil to maintain precision.
Posted by GitBox <gi...@apache.org>.
jtibshirani commented on a change in pull request #2047:
URL: https://github.com/apache/lucene-solr/pull/2047#discussion_r524826537
##########
File path: lucene/core/src/java/org/apache/lucene/util/VectorUtil.java
##########
@@ -25,47 +25,22 @@
private VectorUtil() {
}
- public static float dotProduct(float[] a, float[] b) {
- float res = 0f;
- /*
- * If length of vector is larger than 8, we use unrolled dot product to accelerate the
- * calculation.
- */
- int i;
- for (i = 0; i < a.length % 8; i++) {
- res += b[i] * a[i];
- }
- if (a.length < 8) {
- return res;
- }
- float s0 = 0f;
- float s1 = 0f;
- float s2 = 0f;
- float s3 = 0f;
- float s4 = 0f;
- float s5 = 0f;
- float s6 = 0f;
- float s7 = 0f;
- for (; i + 7 < a.length; i += 8) {
- s0 += b[i] * a[i];
- s1 += b[i + 1] * a[i + 1];
- s2 += b[i + 2] * a[i + 2];
- s3 += b[i + 3] * a[i + 3];
- s4 += b[i + 4] * a[i + 4];
- s5 += b[i + 5] * a[i + 5];
- s6 += b[i + 6] * a[i + 6];
- s7 += b[i + 7] * a[i + 7];
+ public static double dotProduct(float[] a, float[] b) {
Review comment:
Simply changing the test to use a larger epsilon sounds good to me. After thinking about this more, I'm not sure we want to optimize for the precision of these individual calculations. Many high-dimensional vectors are already an approximation to an original object, like a piece of text. And I've heard of practitioners choosing less precise representations (like bfloat16) for each vector element to save space, and still achieving acceptable results.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] jtibshirani commented on a change in pull request #2047: LUCENE-9592: Use doubles in VectorUtil to maintain precision.
Posted by GitBox <gi...@apache.org>.
jtibshirani commented on a change in pull request #2047:
URL: https://github.com/apache/lucene-solr/pull/2047#discussion_r524835397
##########
File path: lucene/core/src/java/org/apache/lucene/util/VectorUtil.java
##########
@@ -25,47 +25,22 @@
private VectorUtil() {
}
- public static float dotProduct(float[] a, float[] b) {
- float res = 0f;
- /*
- * If length of vector is larger than 8, we use unrolled dot product to accelerate the
- * calculation.
- */
- int i;
- for (i = 0; i < a.length % 8; i++) {
- res += b[i] * a[i];
- }
- if (a.length < 8) {
- return res;
- }
- float s0 = 0f;
- float s1 = 0f;
- float s2 = 0f;
- float s3 = 0f;
- float s4 = 0f;
- float s5 = 0f;
- float s6 = 0f;
- float s7 = 0f;
- for (; i + 7 < a.length; i += 8) {
- s0 += b[i] * a[i];
- s1 += b[i + 1] * a[i + 1];
- s2 += b[i + 2] * a[i + 2];
- s3 += b[i + 3] * a[i + 3];
- s4 += b[i + 4] * a[i + 4];
- s5 += b[i + 5] * a[i + 5];
- s6 += b[i + 6] * a[i + 6];
- s7 += b[i + 7] * a[i + 7];
+ public static double dotProduct(float[] a, float[] b) {
Review comment:
I opened https://github.com/apache/lucene-solr/pull/2047, it if it looks okay I can close out this PR.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] jtibshirani closed pull request #2047: LUCENE-9592: Use doubles in VectorUtil to maintain precision.
Posted by GitBox <gi...@apache.org>.
jtibshirani closed pull request #2047:
URL: https://github.com/apache/lucene-solr/pull/2047
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] msokolov commented on a change in pull request #2047: LUCENE-9592: Use doubles in VectorUtil to maintain precision.
Posted by GitBox <gi...@apache.org>.
msokolov commented on a change in pull request #2047:
URL: https://github.com/apache/lucene-solr/pull/2047#discussion_r523001646
##########
File path: lucene/core/src/java/org/apache/lucene/util/VectorUtil.java
##########
@@ -25,47 +25,22 @@
private VectorUtil() {
}
- public static float dotProduct(float[] a, float[] b) {
- float res = 0f;
- /*
- * If length of vector is larger than 8, we use unrolled dot product to accelerate the
- * calculation.
- */
- int i;
- for (i = 0; i < a.length % 8; i++) {
- res += b[i] * a[i];
- }
- if (a.length < 8) {
- return res;
- }
- float s0 = 0f;
- float s1 = 0f;
- float s2 = 0f;
- float s3 = 0f;
- float s4 = 0f;
- float s5 = 0f;
- float s6 = 0f;
- float s7 = 0f;
- for (; i + 7 < a.length; i += 8) {
- s0 += b[i] * a[i];
- s1 += b[i + 1] * a[i + 1];
- s2 += b[i + 2] * a[i + 2];
- s3 += b[i + 3] * a[i + 3];
- s4 += b[i + 4] * a[i + 4];
- s5 += b[i + 5] * a[i + 5];
- s6 += b[i + 6] * a[i + 6];
- s7 += b[i + 7] * a[i + 7];
+ public static double dotProduct(float[] a, float[] b) {
Review comment:
As an alternative, we could also consider changing the test to have a larger epsilon. I found that with the current 1e-5, I got one failure in 100 runs. Changing to 1e-4, I ran 1000 iterations with no failures.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] jtibshirani commented on a change in pull request #2047: LUCENE-9592: Use doubles in VectorUtil to maintain precision.
Posted by GitBox <gi...@apache.org>.
jtibshirani commented on a change in pull request #2047:
URL: https://github.com/apache/lucene-solr/pull/2047#discussion_r524835397
##########
File path: lucene/core/src/java/org/apache/lucene/util/VectorUtil.java
##########
@@ -25,47 +25,22 @@
private VectorUtil() {
}
- public static float dotProduct(float[] a, float[] b) {
- float res = 0f;
- /*
- * If length of vector is larger than 8, we use unrolled dot product to accelerate the
- * calculation.
- */
- int i;
- for (i = 0; i < a.length % 8; i++) {
- res += b[i] * a[i];
- }
- if (a.length < 8) {
- return res;
- }
- float s0 = 0f;
- float s1 = 0f;
- float s2 = 0f;
- float s3 = 0f;
- float s4 = 0f;
- float s5 = 0f;
- float s6 = 0f;
- float s7 = 0f;
- for (; i + 7 < a.length; i += 8) {
- s0 += b[i] * a[i];
- s1 += b[i + 1] * a[i + 1];
- s2 += b[i + 2] * a[i + 2];
- s3 += b[i + 3] * a[i + 3];
- s4 += b[i + 4] * a[i + 4];
- s5 += b[i + 5] * a[i + 5];
- s6 += b[i + 6] * a[i + 6];
- s7 += b[i + 7] * a[i + 7];
+ public static double dotProduct(float[] a, float[] b) {
Review comment:
I opened https://github.com/apache/lucene-solr/pull/2084, it if it looks okay I can close out this PR.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] msokolov commented on a change in pull request #2047: LUCENE-9592: Use doubles in VectorUtil to maintain precision.
Posted by GitBox <gi...@apache.org>.
msokolov commented on a change in pull request #2047:
URL: https://github.com/apache/lucene-solr/pull/2047#discussion_r518030964
##########
File path: lucene/core/src/java/org/apache/lucene/util/VectorUtil.java
##########
@@ -25,47 +25,22 @@
private VectorUtil() {
}
- public static float dotProduct(float[] a, float[] b) {
- float res = 0f;
- /*
- * If length of vector is larger than 8, we use unrolled dot product to accelerate the
- * calculation.
- */
- int i;
- for (i = 0; i < a.length % 8; i++) {
- res += b[i] * a[i];
- }
- if (a.length < 8) {
- return res;
- }
- float s0 = 0f;
- float s1 = 0f;
- float s2 = 0f;
- float s3 = 0f;
- float s4 = 0f;
- float s5 = 0f;
- float s6 = 0f;
- float s7 = 0f;
- for (; i + 7 < a.length; i += 8) {
- s0 += b[i] * a[i];
- s1 += b[i + 1] * a[i + 1];
- s2 += b[i + 2] * a[i + 2];
- s3 += b[i + 3] * a[i + 3];
- s4 += b[i + 4] * a[i + 4];
- s5 += b[i + 5] * a[i + 5];
- s6 += b[i + 6] * a[i + 6];
- s7 += b[i + 7] * a[i + 7];
+ public static double dotProduct(float[] a, float[] b) {
Review comment:
That's a fair comment. I put this in because we had someone do some extensive work on trying to optimize this code loop, and he found that unrolling like this made it more amenable to being expressed as AVX instructions, leading to some speedup, but it wasn't huge. Still - would you mind running some microbenchmark to see if there is any measurable change in performance with this?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org