You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2020/07/09 19:33:08 UTC
[lucene-solr] branch branch_8x updated: LUCENE-8574: the
DoubleValues for dependent bindings for an expression are now cached and
reused and no longer inefficiently recomputed per hit
This is an automated email from the ASF dual-hosted git repository.
mikemccand pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/branch_8x by this push:
new 1791d7e LUCENE-8574: the DoubleValues for dependent bindings for an expression are now cached and reused and no longer inefficiently recomputed per hit
1791d7e is described below
commit 1791d7e44278e9d032f99822e82b25109f8952c0
Author: Mike McCandless <mi...@apache.org>
AuthorDate: Thu Jul 9 15:04:31 2020 -0400
LUCENE-8574: the DoubleValues for dependent bindings for an expression are now cached and reused and no longer inefficiently recomputed per hit
---
lucene/CHANGES.txt | 5 +-
.../expressions/CachingExpressionValueSource.java | 75 ++++++++++++++++++++++
.../expressions/ExpressionFunctionValues.java | 14 +++-
.../lucene/expressions/ExpressionValueSource.java | 7 +-
.../expressions/TestExpressionValueSource.java | 29 +++++++++
5 files changed, 125 insertions(+), 5 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index e20a788..c095422 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -24,7 +24,10 @@ Optimizations
Bug Fixes
---------------------
-(No changes)
+
+* LUCENE-8574: Add a new ExpressionValueSource which will enforce only one value per name
+ per hit in dependencies, ExpressionFunctionValues will no longer
+ recompute already computed values (Haoyu Zhai)
Other
---------------------
diff --git a/lucene/expressions/src/java/org/apache/lucene/expressions/CachingExpressionValueSource.java b/lucene/expressions/src/java/org/apache/lucene/expressions/CachingExpressionValueSource.java
new file mode 100644
index 0000000..e8499bb
--- /dev/null
+++ b/lucene/expressions/src/java/org/apache/lucene/expressions/CachingExpressionValueSource.java
@@ -0,0 +1,75 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.expressions;
+
+import java.io.IOException;
+import java.util.HashMap;
+import java.util.Map;
+
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.search.DoubleValues;
+import org.apache.lucene.search.DoubleValuesSource;
+
+/**
+ * This expression value source shares one value cache when generating {@link ExpressionFunctionValues}
+ * such that only one value along the whole generation tree is corresponding to one name
+ */
+final class CachingExpressionValueSource extends ExpressionValueSource {
+
+ CachingExpressionValueSource(Bindings bindings, Expression expression) {
+ super(bindings, expression);
+ }
+
+ CachingExpressionValueSource(DoubleValuesSource[] variables, Expression expression, boolean needsScores) {
+ super(variables, expression, needsScores);
+ }
+
+ public CachingExpressionValueSource(ExpressionValueSource expressionValueSource) {
+ super(expressionValueSource.variables, expressionValueSource.expression, expressionValueSource.needsScores);
+ }
+
+ @Override
+ public DoubleValues getValues(LeafReaderContext readerContext, DoubleValues scores) throws IOException {
+ return getValuesWithCache(readerContext, scores, new HashMap<>());
+ }
+
+ private DoubleValues getValuesWithCache(LeafReaderContext readerContext, DoubleValues scores,
+ Map<String, DoubleValues> valuesCache) throws IOException {
+ DoubleValues[] externalValues = new DoubleValues[expression.variables.length];
+
+ for (int i = 0; i < variables.length; ++i) {
+ String externalName = expression.variables[i];
+ DoubleValues values = valuesCache.get(externalName);
+ if (values == null) {
+ if (variables[i] instanceof CachingExpressionValueSource) {
+ values = ((CachingExpressionValueSource) variables[i]).getValuesWithCache(readerContext, scores, valuesCache);
+ } else {
+ values = variables[i].getValues(readerContext, scores);
+ }
+ if (values == null) {
+ throw new RuntimeException("Unrecognized variable (" + externalName + ") referenced in expression (" +
+ expression.sourceText + ").");
+ }
+ valuesCache.put(externalName, values);
+ }
+ externalValues[i] = zeroWhenUnpositioned(values);
+ }
+
+ return new ExpressionFunctionValues(expression, externalValues);
+ }
+}
diff --git a/lucene/expressions/src/java/org/apache/lucene/expressions/ExpressionFunctionValues.java b/lucene/expressions/src/java/org/apache/lucene/expressions/ExpressionFunctionValues.java
index 2e6f7c4..052fce7 100644
--- a/lucene/expressions/src/java/org/apache/lucene/expressions/ExpressionFunctionValues.java
+++ b/lucene/expressions/src/java/org/apache/lucene/expressions/ExpressionFunctionValues.java
@@ -24,6 +24,9 @@ import org.apache.lucene.search.DoubleValues;
class ExpressionFunctionValues extends DoubleValues {
final Expression expression;
final DoubleValues[] functionValues;
+ double currentValue;
+ int currentDoc = -1;
+ boolean computed;
ExpressionFunctionValues(Expression expression, DoubleValues[] functionValues) {
if (expression == null) {
@@ -38,14 +41,23 @@ class ExpressionFunctionValues extends DoubleValues {
@Override
public boolean advanceExact(int doc) throws IOException {
+ if (currentDoc == doc) {
+ return true;
+ }
for (DoubleValues v : functionValues) {
v.advanceExact(doc);
}
+ currentDoc = doc;
+ computed = false;
return true;
}
@Override
public double doubleValue() {
- return expression.evaluate(functionValues);
+ if (computed == false) {
+ currentValue = expression.evaluate(functionValues);
+ computed = true;
+ }
+ return currentValue;
}
}
diff --git a/lucene/expressions/src/java/org/apache/lucene/expressions/ExpressionValueSource.java b/lucene/expressions/src/java/org/apache/lucene/expressions/ExpressionValueSource.java
index 1f8713d..afd6570 100644
--- a/lucene/expressions/src/java/org/apache/lucene/expressions/ExpressionValueSource.java
+++ b/lucene/expressions/src/java/org/apache/lucene/expressions/ExpressionValueSource.java
@@ -31,7 +31,7 @@ import org.apache.lucene.search.IndexSearcher;
/**
* A {@link DoubleValuesSource} which evaluates a {@link Expression} given the context of an {@link Bindings}.
*/
-final class ExpressionValueSource extends DoubleValuesSource {
+class ExpressionValueSource extends DoubleValuesSource {
final DoubleValuesSource[] variables;
final Expression expression;
final boolean needsScores;
@@ -69,7 +69,8 @@ final class ExpressionValueSource extends DoubleValuesSource {
if (values == null) {
values = variables[i].getValues(readerContext, scores);
if (values == null) {
- throw new RuntimeException("Internal error. External (" + externalName + ") does not exist.");
+ throw new RuntimeException("Unrecognized variable (" + externalName + ") referenced in expression (" +
+ expression.sourceText + ").");
}
valuesCache.put(externalName, values);
}
@@ -79,7 +80,7 @@ final class ExpressionValueSource extends DoubleValuesSource {
return new ExpressionFunctionValues(expression, externalValues);
}
- private static DoubleValues zeroWhenUnpositioned(DoubleValues in) {
+ static DoubleValues zeroWhenUnpositioned(DoubleValues in) {
return new DoubleValues() {
boolean positioned = false;
diff --git a/lucene/expressions/src/test/org/apache/lucene/expressions/TestExpressionValueSource.java b/lucene/expressions/src/test/org/apache/lucene/expressions/TestExpressionValueSource.java
index 3b5589b..eb7d106 100644
--- a/lucene/expressions/src/test/org/apache/lucene/expressions/TestExpressionValueSource.java
+++ b/lucene/expressions/src/test/org/apache/lucene/expressions/TestExpressionValueSource.java
@@ -128,6 +128,35 @@ public class TestExpressionValueSource extends LuceneTestCase {
assertFalse(vs1.equals(vs4));
}
+ public void testFibonacciExpr() throws Exception {
+ int n = 40;
+ SimpleBindings bindings = new SimpleBindings();
+ bindings.add("f0", DoubleValuesSource.constant(0));
+ bindings.add("f1", DoubleValuesSource.constant(1));
+ for (int i = 2; i < n + 1; i++) {
+ // Without using CachingExpressionValueSource this test will fail after 1 min around because of out of heap space when n=40
+ bindings.add("f" + Integer.toString(i), new CachingExpressionValueSource(
+ (ExpressionValueSource) JavascriptCompiler.compile("f" + Integer.toString(i - 1)+" + f" + Integer.toString(i - 2)).getDoubleValuesSource(bindings)));
+ }
+ DoubleValues values = bindings.getDoubleValuesSource("f" + Integer.toString(n)).getValues(null, null);
+
+ assertTrue(values.advanceExact(0));
+ assertEquals(fib(n), (int)values.doubleValue());
+ }
+
+ private int fib(int n) {
+ if (n == 0) {
+ return 0;
+ }
+ int prev = 0, curr = 1, tmp;
+ for (int i = 1; i < n; i++) {
+ tmp = curr;
+ curr += prev;
+ prev = tmp;
+ }
+ return curr;
+ }
+
public void testRewrite() throws Exception {
Expression expr = JavascriptCompiler.compile("a");