From a42b44c9a6680929cb1f260571526ac101ccdba8 Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Wed, 21 Sep 2022 06:56:26 +0200 Subject: Revert "Revert "Short circuit boolean expressions"" --- .../BooleanExpressionTransformer.java | 105 +++++++++++++++++++++ .../expressiontransforms/ExpressionTransforms.java | 3 +- .../schema/RankingExpressionInliningTestCase.java | 4 +- .../BooleanExpressionTransformerTestCase.java | 57 +++++++++++ 4 files changed, 166 insertions(+), 3 deletions(-) create mode 100644 config-model/src/main/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformer.java create mode 100644 config-model/src/test/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformerTestCase.java (limited to 'config-model') diff --git a/config-model/src/main/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformer.java b/config-model/src/main/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformer.java new file mode 100644 index 00000000000..e1affaf2aac --- /dev/null +++ b/config-model/src/main/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformer.java @@ -0,0 +1,105 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.schema.expressiontransforms; + +import com.yahoo.searchlib.rankingexpression.evaluation.BooleanValue; +import com.yahoo.searchlib.rankingexpression.rule.ArithmeticNode; +import com.yahoo.searchlib.rankingexpression.rule.ArithmeticOperator; +import com.yahoo.searchlib.rankingexpression.rule.CompositeNode; +import com.yahoo.searchlib.rankingexpression.rule.ConstantNode; +import com.yahoo.searchlib.rankingexpression.rule.ExpressionNode; +import com.yahoo.searchlib.rankingexpression.rule.IfNode; +import com.yahoo.searchlib.rankingexpression.transform.ExpressionTransformer; +import com.yahoo.searchlib.rankingexpression.transform.TransformContext; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Deque; +import java.util.Iterator; +import java.util.List; + +/** + * Transforms + * a && b into if(a, b, false) + * and + * a || b into if(a, true, b) + * to avoid computing b if a is false and true respectively. + * + * This may increase performance since boolean expressions are short-circuited. + * + * @author bratseth + */ +public class BooleanExpressionTransformer extends ExpressionTransformer { + + @Override + public ExpressionNode transform(ExpressionNode node, TransformContext context) { + if (node instanceof CompositeNode composite) + node = transformChildren(composite, context); + + if (node instanceof ArithmeticNode arithmetic) + node = transformBooleanArithmetics(arithmetic); + + return node; + } + + private ExpressionNode transformBooleanArithmetics(ArithmeticNode node) { + Iterator child = node.children().iterator(); + + // Transform in precedence order: + Deque stack = new ArrayDeque<>(); + stack.push(new ChildNode(ArithmeticOperator.OR, child.next())); + for (Iterator it = node.operators().iterator(); it.hasNext() && child.hasNext();) { + ArithmeticOperator op = it.next(); + if ( ! stack.isEmpty()) { + while (stack.size() > 1 && ! op.hasPrecedenceOver(stack.peek().op)) { + popStack(stack); + } + } + stack.push(new ChildNode(op, child.next())); + } + while (stack.size() > 1) + popStack(stack); + return stack.getFirst().child; + } + + private void popStack(Deque stack) { + ChildNode rhs = stack.pop(); + ChildNode lhs = stack.peek(); + + ExpressionNode combination; + if (rhs.op == ArithmeticOperator.AND) + combination = andByIfNode(lhs.child, rhs.child); + else if (rhs.op == ArithmeticOperator.OR) + combination = orByIfNode(lhs.child, rhs.child); + else + combination = new ArithmeticNode(List.of(lhs.child, rhs.child), List.of(rhs.op)); + lhs.child = combination; + } + + + private IfNode andByIfNode(ExpressionNode a, ExpressionNode b) { + return new IfNode(a, b, new ConstantNode(new BooleanValue(false))); + } + + private IfNode orByIfNode(ExpressionNode a, ExpressionNode b) { + return new IfNode(a, new ConstantNode(new BooleanValue(true)), b); + } + + /** A child with the operator to be applied to it when combining it with the previous child. */ + private static class ChildNode { + + final ArithmeticOperator op; + ExpressionNode child; + + public ChildNode(ArithmeticOperator op, ExpressionNode child) { + this.op = op; + this.child = child; + } + + @Override + public String toString() { + return child.toString(); + } + + } + +} diff --git a/config-model/src/main/java/com/yahoo/schema/expressiontransforms/ExpressionTransforms.java b/config-model/src/main/java/com/yahoo/schema/expressiontransforms/ExpressionTransforms.java index 86aedd4332a..132597ee75e 100644 --- a/config-model/src/main/java/com/yahoo/schema/expressiontransforms/ExpressionTransforms.java +++ b/config-model/src/main/java/com/yahoo/schema/expressiontransforms/ExpressionTransforms.java @@ -35,7 +35,8 @@ public class ExpressionTransforms { new FunctionInliner(), new FunctionShadower(), new TensorMaxMinTransformer(), - new Simplifier()); + new Simplifier(), + new BooleanExpressionTransformer()); } public RankingExpression transform(RankingExpression expression, RankProfileTransformContext context) { diff --git a/config-model/src/test/java/com/yahoo/schema/RankingExpressionInliningTestCase.java b/config-model/src/test/java/com/yahoo/schema/RankingExpressionInliningTestCase.java index 789c4ac5577..5eecee516ec 100644 --- a/config-model/src/test/java/com/yahoo/schema/RankingExpressionInliningTestCase.java +++ b/config-model/src/test/java/com/yahoo/schema/RankingExpressionInliningTestCase.java @@ -163,7 +163,7 @@ public class RankingExpressionInliningTestCase extends AbstractSchemaTestCase { " \n" + " rank-profile test {\n" + " first-phase {\n" + - " expression: A + C + D\n" + + " expression: A + C - D\n" + " }\n" + " function inline D() {\n" + " expression: B + 1\n" + @@ -184,7 +184,7 @@ public class RankingExpressionInliningTestCase extends AbstractSchemaTestCase { Schema s = builder.getSchema(); RankProfile test = rankProfileRegistry.get(s, "test").compile(new QueryProfileRegistry(), new ImportedMlModels()); - assertEquals("attribute(a) + C + (attribute(b) + 1)", test.getFirstPhaseRanking().getRoot().toString()); + assertEquals("attribute(a) + C - (attribute(b) + 1)", test.getFirstPhaseRanking().getRoot().toString()); assertEquals("attribute(a) + attribute(b)", getRankingExpression("C", test, s)); assertEquals("attribute(b) + 1", getRankingExpression("D", test, s)); } diff --git a/config-model/src/test/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformerTestCase.java b/config-model/src/test/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformerTestCase.java new file mode 100644 index 00000000000..71d0657c701 --- /dev/null +++ b/config-model/src/test/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformerTestCase.java @@ -0,0 +1,57 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.schema.expressiontransforms; + +import com.yahoo.searchlib.rankingexpression.RankingExpression; +import com.yahoo.searchlib.rankingexpression.evaluation.MapContext; +import com.yahoo.searchlib.rankingexpression.evaluation.MapTypeContext; +import com.yahoo.searchlib.rankingexpression.transform.TransformContext; +import org.junit.jupiter.api.Test; +import static org.junit.jupiter.api.Assertions.assertEquals; + +import java.util.Map; + +/** + * @author bratseth + */ +public class BooleanExpressionTransformerTestCase { + + @Test + public void testTransformer() throws Exception { + assertTransformed("if (a, b, false)", "a && b"); + assertTransformed("if (a, true, b)", "a || b"); + assertTransformed("if (a, true, b + c)", "a || b + c"); + assertTransformed("if (c + a, true, b)", "c + a || b"); + assertTransformed("if (c + a, true, b + c)", "c + a || b + c"); + assertTransformed("if (a + b, true, if (c - d * e, f, false))", "a + b || c - d * e && f"); + assertTransformed("if (a, true, if (b, c, false))", "a || b && c"); + assertTransformed("if (a + b, true, if (if (c, d, false), e * f - g, false))", "a + b || c && d && e * f - g"); + assertTransformed("if(1 - 1, true, 1 - 1)", "1 - 1 || 1 - 1"); + } + + @Test + public void testIt() throws Exception { + assertTransformed("if(1 - 1, true, 1 - 1)", "1 - 1 || 1 - 1"); + } + + private void assertTransformed(String expected, String input) throws Exception { + var transformedExpression = new BooleanExpressionTransformer() + .transform(new RankingExpression(input), + new TransformContext(Map.of(), new MapTypeContext())); + + assertEquals(new RankingExpression(expected), transformedExpression, "Transformed as expected"); + + MapContext context = contextWithSingleLetterVariables(); + var inputExpression = new RankingExpression(input); + assertEquals(inputExpression.evaluate(new MapContext()).asBoolean(), + transformedExpression.evaluate(new MapContext()).asBoolean(), + "Transform and original input are equivalent"); + } + + private MapContext contextWithSingleLetterVariables() { + var context = new MapContext(); + for (int i = 0; i < 26; i++) + context.put(Character.toString(i + 97), Math.floorMod(i, 2)); + return context; + } + +} -- cgit v1.2.3