You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by jh...@apache.org on 2020/04/28 22:36:43 UTC
[calcite] branch master updated: [CALCITE-3827] Reduce the time
complexity of finding in-edges of a vertex in the graph (Liya Fan)
This is an automated email from the ASF dual-hosted git repository.
jhyde pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/calcite.git
The following commit(s) were added to refs/heads/master by this push:
new 0e00d65 [CALCITE-3827] Reduce the time complexity of finding in-edges of a vertex in the graph (Liya Fan)
0e00d65 is described below
commit 0e00d65532251aacc8fdcde703bc1d8ddf8dff16
Author: liyafan82 <fa...@foxmail.com>
AuthorDate: Wed Feb 26 16:06:04 2020 +0800
[CALCITE-3827] Reduce the time complexity of finding in-edges of a vertex in the graph (Liya Fan)
Add benchmark to measure performance difference;
Place inward & outward edges in VertexInfo;
Switch algorithms when removing vertices.
Based on benchmarking, change threshold to 35%, and convert
collection to HashSet; add benchmarking README. (Julian Hyde)
---
.../util/graph/AttributedDirectedGraph.java | 28 ++-
.../calcite/util/graph/DefaultDirectedGraph.java | 94 +++++--
.../apache/calcite/util/graph/DirectedGraph.java | 2 +
ubenchmark/README.md | 76 ++++++
.../benchmarks/DefaultDirectedGraphBenchmark.java | 280 +++++++++++++++++++++
5 files changed, 454 insertions(+), 26 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/util/graph/AttributedDirectedGraph.java b/core/src/main/java/org/apache/calcite/util/graph/AttributedDirectedGraph.java
index 7e3cc96..756d973 100644
--- a/core/src/main/java/org/apache/calcite/util/graph/AttributedDirectedGraph.java
+++ b/core/src/main/java/org/apache/calcite/util/graph/AttributedDirectedGraph.java
@@ -61,8 +61,8 @@ public class AttributedDirectedGraph<V, E extends DefaultEdge>
if (info == null) {
throw new IllegalArgumentException("no vertex " + vertex);
}
- final VertexInfo<V, E> info2 = vertexMap.get(targetVertex);
- if (info2 == null) {
+ final VertexInfo<V, E> targetInfo = vertexMap.get(targetVertex);
+ if (targetInfo == null) {
throw new IllegalArgumentException("no vertex " + targetVertex);
}
@SuppressWarnings("unchecked")
@@ -71,6 +71,7 @@ public class AttributedDirectedGraph<V, E extends DefaultEdge>
final E edge = f.createEdge(vertex, targetVertex, attributes);
if (edges.add(edge)) {
info.outEdges.add(edge);
+ targetInfo.inEdges.add(edge);
return edge;
} else {
return null;
@@ -86,18 +87,31 @@ public class AttributedDirectedGraph<V, E extends DefaultEdge>
/** Removes all edges from a given vertex to another.
* Returns whether any were removed. */
public boolean removeEdge(V source, V target) {
- final VertexInfo<V, E> info = vertexMap.get(source);
- List<E> outEdges = info.outEdges;
- int removeCount = 0;
+ // remove out edges
+ final List<E> outEdges = vertexMap.get(source).outEdges;
+ int removeOutCount = 0;
for (int i = 0, size = outEdges.size(); i < size; i++) {
E edge = outEdges.get(i);
if (edge.target.equals(target)) {
outEdges.remove(i);
edges.remove(edge);
- ++removeCount;
+ ++removeOutCount;
}
}
- return removeCount > 0;
+
+ // remove in edges
+ final List<E> inEdges = vertexMap.get(target).inEdges;
+ int removeInCount = 0;
+ for (int i = 0, size = inEdges.size(); i < size; i++) {
+ E edge = inEdges.get(i);
+ if (edge.source.equals(source)) {
+ inEdges.remove(i);
+ ++removeInCount;
+ }
+ }
+
+ assert removeOutCount == removeInCount;
+ return removeOutCount > 0;
}
/** Factory for edges that have attributes.
diff --git a/core/src/main/java/org/apache/calcite/util/graph/DefaultDirectedGraph.java b/core/src/main/java/org/apache/calcite/util/graph/DefaultDirectedGraph.java
index 0b2c67b..cae5b4b 100644
--- a/core/src/main/java/org/apache/calcite/util/graph/DefaultDirectedGraph.java
+++ b/core/src/main/java/org/apache/calcite/util/graph/DefaultDirectedGraph.java
@@ -21,6 +21,7 @@ import com.google.common.collect.Ordering;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
+import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
@@ -95,13 +96,14 @@ public class DefaultDirectedGraph<V, E extends DefaultEdge>
if (info == null) {
throw new IllegalArgumentException("no vertex " + vertex);
}
- final VertexInfo<V, E> info2 = vertexMap.get(targetVertex);
- if (info2 == null) {
+ final VertexInfo<V, E> targetInfo = vertexMap.get(targetVertex);
+ if (targetInfo == null) {
throw new IllegalArgumentException("no vertex " + targetVertex);
}
final E edge = edgeFactory.createEdge(vertex, targetVertex);
if (edges.add(edge)) {
info.outEdges.add(edge);
+ targetInfo.inEdges.add(edge);
return edge;
} else {
return null;
@@ -120,17 +122,32 @@ public class DefaultDirectedGraph<V, E extends DefaultEdge>
}
public boolean removeEdge(V source, V target) {
- final VertexInfo<V, E> info = vertexMap.get(source);
- List<E> outEdges = info.outEdges;
+ // remove out edges
+ final List<E> outEdges = vertexMap.get(source).outEdges;
+ boolean outRemoved = false;
for (int i = 0, size = outEdges.size(); i < size; i++) {
E edge = outEdges.get(i);
if (edge.target.equals(target)) {
outEdges.remove(i);
edges.remove(edge);
- return true;
+ outRemoved = true;
+ break;
+ }
+ }
+
+ // remove in edges
+ final List<E> inEdges = vertexMap.get(target).inEdges;
+ boolean inRemoved = false;
+ for (int i = 0, size = inEdges.size(); i < size; i++) {
+ E edge = inEdges.get(i);
+ if (edge.source.equals(source)) {
+ inEdges.remove(i);
+ inRemoved = true;
+ break;
}
}
- return false;
+ assert outRemoved == inRemoved;
+ return outRemoved;
}
public Set<V> vertexSet() {
@@ -138,10 +155,56 @@ public class DefaultDirectedGraph<V, E extends DefaultEdge>
}
public void removeAllVertices(Collection<V> collection) {
+ // The point at which collection is large enough to make the 'majority'
+ // algorithm more efficient.
+ final float threshold = 0.35f;
+ final int thresholdSize = (int) (vertexMap.size() * threshold);
+ if (collection.size() > thresholdSize && !(collection instanceof Set)) {
+ // Convert collection to a set, so that collection.contains() is
+ // faster. If there are duplicates, collection.size() will get smaller.
+ collection = new HashSet<>(collection);
+ }
+ if (collection.size() > thresholdSize) {
+ removeMajorityVertices((Set<V>) collection);
+ } else {
+ removeMinorityVertices(collection);
+ }
+ }
+
+ /** Implementation of {@link #removeAllVertices(Collection)} that is efficient
+ * if {@code collection} is a small fraction of the set of vertices. */
+ private void removeMinorityVertices(Collection<V> collection) {
+ for (V v : collection) {
+ final VertexInfo<V, E> info = vertexMap.get(v);
+ if (info == null) {
+ continue;
+ }
+
+ // remove all edges pointing to v
+ for (E edge : info.inEdges) {
+ final V source = (V) edge.source;
+ final VertexInfo<V, E> sourceInfo = vertexMap.get(source);
+ sourceInfo.outEdges.removeIf(e -> e.target.equals(v));
+ }
+
+ // remove all edges starting from v
+ for (E edge : info.outEdges) {
+ final V target = (V) edge.target;
+ final VertexInfo<V, E> targetInfo = vertexMap.get(target);
+ targetInfo.inEdges.removeIf(e -> e.source.equals(v));
+ }
+ }
vertexMap.keySet().removeAll(collection);
+ }
+
+ /** Implementation of {@link #removeAllVertices(Collection)} that is efficient
+ * if {@code vertexSet} is a large fraction of the set of vertices in the
+ * graph. */
+ private void removeMajorityVertices(Set<V> vertexSet) {
+ vertexMap.keySet().removeAll(vertexSet);
for (VertexInfo<V, E> info : vertexMap.values()) {
- //noinspection SuspiciousMethodCalls
- info.outEdges.removeIf(next -> collection.contains(next.target));
+ info.outEdges.removeIf(e -> vertexSet.contains((V) e.target));
+ info.inEdges.removeIf(e -> vertexSet.contains((V) e.source));
}
}
@@ -150,15 +213,7 @@ public class DefaultDirectedGraph<V, E extends DefaultEdge>
}
public List<E> getInwardEdges(V target) {
- final ArrayList<E> list = new ArrayList<>();
- for (VertexInfo<V, E> info : vertexMap.values()) {
- for (E edge : info.outEdges) {
- if (edge.target.equals(target)) {
- list.add(edge);
- }
- }
- }
- return list;
+ return vertexMap.get(target).inEdges;
}
final V source(E edge) {
@@ -172,12 +227,13 @@ public class DefaultDirectedGraph<V, E extends DefaultEdge>
}
/**
- * Information about an edge.
+ * Information about a vertex.
*
* @param <V> Vertex type
* @param <E> Edge type
*/
static class VertexInfo<V, E> {
- public List<E> outEdges = new ArrayList<>();
+ final List<E> outEdges = new ArrayList<>();
+ final List<E> inEdges = new ArrayList<>();
}
}
diff --git a/core/src/main/java/org/apache/calcite/util/graph/DirectedGraph.java b/core/src/main/java/org/apache/calcite/util/graph/DirectedGraph.java
index 24fb45a..24e3d30 100644
--- a/core/src/main/java/org/apache/calcite/util/graph/DirectedGraph.java
+++ b/core/src/main/java/org/apache/calcite/util/graph/DirectedGraph.java
@@ -49,6 +49,8 @@ public interface DirectedGraph<V, E> {
Set<V> vertexSet();
+ /** Removes from this graph all vertices that are in {@code collection},
+ * and the edges into and out of those vertices. */
void removeAllVertices(Collection<V> collection);
List<E> getOutwardEdges(V source);
diff --git a/ubenchmark/README.md b/ubenchmark/README.md
new file mode 100644
index 0000000..e7673ab
--- /dev/null
+++ b/ubenchmark/README.md
@@ -0,0 +1,76 @@
+<!--
+{% comment %}
+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.
+{% endcomment %}
+-->
+# Micro-benchmarks
+
+This directory, `ubenchmark`, contains micro-benchmarks written using
+the [jmh](https://openjdk.java.net/projects/code-tools/jmh/) framework.
+
+The benchmarks are tools for development and are not distributed as
+Calcite artifacts. (Besides, jmh's license does not allow that.)
+
+## Running all benchmark from the command line
+
+To run all benchmarks:
+
+{noformat}bash
+$ cd calcite
+$ ./gradlew :ubenchmark:jmh
+{noformat}
+
+## Running one benchmark from the command line
+
+To run just one benchmark, modify `ubenchmark/build.gradle.kts` and add the
+following task:
+
+{noformat}kotlin
+jmh {
+ include = listOf("removeAllVertices.*Benchmark")
+}
+{noformat}
+
+and run
+
+{noformat}bash
+$ ./gradlew :ubenchmark:jmh
+{noformat}
+
+as before. In this case, `removeAllVertices.*Benchmark` is a
+regular expression that matches a few methods -- benchmarks -- in
+`class DefaultDirectedGraphBenchmark`.
+
+The `jmd-gradle-plugin` has
+[many other options](https://github.com/melix/jmh-gradle-plugin#configuration-options)
+but you will need to translate them from Groovy syntax to our Kotlin syntax.
+
+## Recording results
+
+When you have run the benchmarks, please record them in the relevant JIRA
+case and link them here:
+
+* ParserBenchmark:
+ [459](https://issues.apache.org/jira/browse/CALCITE-459),
+ [1012](https://issues.apache.org/jira/browse/CALCITE-1012)
+* ArrayListTest:
+ [3878](https://issues.apache.org/jira/browse/CALCITE-3878)
+* DefaultDirectedGraphBenchmark:
+ [3827](https://issues.apache.org/jira/browse/CALCITE-3827)
+* RelNodeBenchmark:
+ [3836](https://issues.apache.org/jira/browse/CALCITE-3836)
+* ReflectVisitorDispatcherTest:
+ [3873](https://issues.apache.org/jira/browse/CALCITE-3873)
diff --git a/ubenchmark/src/jmh/java/org/apache/calcite/benchmarks/DefaultDirectedGraphBenchmark.java b/ubenchmark/src/jmh/java/org/apache/calcite/benchmarks/DefaultDirectedGraphBenchmark.java
new file mode 100644
index 0000000..fb9ad0d
--- /dev/null
+++ b/ubenchmark/src/jmh/java/org/apache/calcite/benchmarks/DefaultDirectedGraphBenchmark.java
@@ -0,0 +1,280 @@
+/*
+ * 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.calcite.benchmarks;
+
+import org.apache.calcite.util.graph.DefaultDirectedGraph;
+import org.apache.calcite.util.graph.DefaultEdge;
+import org.apache.calcite.util.graph.DirectedGraph;
+
+import com.google.common.collect.Lists;
+
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.runner.Runner;
+import org.openjdk.jmh.runner.RunnerException;
+import org.openjdk.jmh.runner.options.Options;
+import org.openjdk.jmh.runner.options.OptionsBuilder;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import java.util.concurrent.TimeUnit;
+
+/**
+ * Benchmarks for {@link org.apache.calcite.util.graph.DefaultDirectedGraph}
+ */
+public class DefaultDirectedGraphBenchmark {
+
+ private static class Node {
+ final int id;
+
+ private Node(int id) {
+ this.id = id;
+ }
+
+ @Override public boolean equals(Object o) {
+ return o == this
+ || o instanceof Node
+ && ((Node) o).id == id;
+ }
+
+ @Override public int hashCode() {
+ return Objects.hash(id);
+ }
+ }
+
+ /**
+ * State object for the benchmarks.
+ */
+ @State(Scope.Benchmark)
+ public static class GraphState {
+
+ static final int NUM_LAYERS = 8;
+
+ DirectedGraph<Node, DefaultEdge> graph;
+
+ List<Node> nodes;
+
+ List<Node> tenNodes;
+ List<Node> twentyNodes;
+ List<Node> thirtyNodes;
+ List<Node> fortyNodes;
+ List<Node> fiftyNodes;
+ List<Node> sixtyNodes;
+ List<Node> seventyNodes;
+ List<Node> eightyNodes;
+ List<Node> ninetyNodes;
+
+ @Setup(Level.Invocation)
+ public void setUp() {
+ nodes = new ArrayList<>();
+
+ // create a binary tree
+ graph = DefaultDirectedGraph.create();
+
+ // create nodes
+ int curId = 1;
+ Node root = new Node(curId++);
+ nodes.add(root);
+ graph.addVertex(root);
+ List<Node> prevLayerNodes = Lists.newArrayList(root);
+
+ for (int i = 1; i < NUM_LAYERS; i++) {
+ List<Node> curLayerNodes = new ArrayList<>();
+ for (Node node : prevLayerNodes) {
+ Node leftChild = new Node(curId++);
+ Node rightChild = new Node(curId++);
+
+ curLayerNodes.add(leftChild);
+ curLayerNodes.add(rightChild);
+
+ nodes.add(leftChild);
+ nodes.add(rightChild);
+
+ graph.addVertex(leftChild);
+ graph.addVertex(rightChild);
+
+ graph.addEdge(node, leftChild);
+ graph.addEdge(node, rightChild);
+ }
+ prevLayerNodes = curLayerNodes;
+ }
+
+ int tenNodeCount = (int) (nodes.size() * 0.1);
+ int twentyNodeCount = (int) (nodes.size() * 0.2);
+ int thirtyNodeCount = (int) (nodes.size() * 0.3);
+ int fortyNodeCount = (int) (nodes.size() * 0.4);
+ int fiftyNodeCount = (int) (nodes.size() * 0.5);
+ int sixtyNodeCount = (int) (nodes.size() * 0.6);
+ int seventyNodeCount = (int) (nodes.size() * 0.7);
+ int eightyNodeCount = (int) (nodes.size() * 0.8);
+ int ninetyNodeCount = (int) (nodes.size() * 0.9);
+ tenNodes = nodes.subList(0, tenNodeCount);
+ twentyNodes = nodes.subList(0, twentyNodeCount);
+ thirtyNodes = nodes.subList(0, thirtyNodeCount);
+ fortyNodes = nodes.subList(0, fortyNodeCount);
+ fiftyNodes = nodes.subList(0, fiftyNodeCount);
+ sixtyNodes = nodes.subList(0, sixtyNodeCount);
+ seventyNodes = nodes.subList(0, seventyNodeCount);
+ eightyNodes = nodes.subList(0, eightyNodeCount);
+ ninetyNodes = nodes.subList(0, ninetyNodeCount);
+ }
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public int getInwardEdgesBenchmark(GraphState state) {
+ int sum = 0;
+ int curId = 1;
+ for (int i = 0; i < GraphState.NUM_LAYERS; i++) {
+ // get the first node in each layer
+ Node curNode = state.nodes.get(curId - 1);
+ sum += state.graph.getInwardEdges(curNode).size();
+ curId *= 2;
+ }
+ return sum;
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public int getOutwardEdgesBenchmark(GraphState state) {
+ int sum = 0;
+ int curId = 1;
+ for (int i = 0; i < GraphState.NUM_LAYERS; i++) {
+ // get the first node in each layer
+ Node curNode = state.nodes.get(curId - 1);
+ sum += state.graph.getOutwardEdges(curNode).size();
+ curId *= 2;
+ }
+ return sum;
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public boolean addVertexBenchmark(GraphState state) {
+ return state.graph.addVertex(new Node(100));
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public DefaultEdge addEdgeBenchmark(GraphState state) {
+ return state.graph.addEdge(state.nodes.get(0), state.nodes.get(5));
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public DefaultEdge getEdgeBenchmark(GraphState state) {
+ return state.graph.getEdge(state.nodes.get(0), state.nodes.get(1));
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public boolean removeEdgeBenchmark(GraphState state) {
+ return state.graph.removeEdge(state.nodes.get(0), state.nodes.get(1));
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public void removeAllVertices10Benchmark(GraphState state) {
+ state.graph.removeAllVertices(state.tenNodes);
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public void removeAllVertices20Benchmark(GraphState state) {
+ state.graph.removeAllVertices(state.twentyNodes);
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public void removeAllVertices30Benchmark(GraphState state) {
+ state.graph.removeAllVertices(state.thirtyNodes);
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public void removeAllVertices40Benchmark(GraphState state) {
+ state.graph.removeAllVertices(state.fortyNodes);
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public void removeAllVertices50Benchmark(GraphState state) {
+ state.graph.removeAllVertices(state.fiftyNodes);
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public void removeAllVertices60Benchmark(GraphState state) {
+ state.graph.removeAllVertices(state.sixtyNodes);
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public void removeAllVertices70Benchmark(GraphState state) {
+ state.graph.removeAllVertices(state.seventyNodes);
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public void removeAllVertices80Benchmark(GraphState state) {
+ state.graph.removeAllVertices(state.eightyNodes);
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public void removeAllVertices90Benchmark(GraphState state) {
+ state.graph.removeAllVertices(state.ninetyNodes);
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public void removeAllVertices100Benchmark(GraphState state) {
+ state.graph.removeAllVertices(state.nodes);
+ }
+
+ public static void main(String[] args) throws RunnerException {
+ Options opt = new OptionsBuilder()
+ .include(DefaultDirectedGraphBenchmark.class.getName())
+ .forks(1)
+ .build();
+
+ new Runner(opt).run();
+ }
+}