Remove BTree.Builder Recycler to reduce memory usage patch by Jay Zhuang; reviewed by jasobrown for CASSANDRA-13929
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/ed5f8347 Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/ed5f8347 Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/ed5f8347 Branch: refs/heads/trunk Commit: ed5f8347ef0c7175cd96e59bc8bfaf3ed1f4697a Parents: b174819 Author: Jay Zhuang <jay.zhu...@yahoo.com> Authored: Mon Jan 29 18:17:56 2018 -0800 Committer: Jay Zhuang <jay.zhu...@yahoo.com> Committed: Fri Jun 8 10:40:06 2018 -0700 ---------------------------------------------------------------------- CHANGES.txt | 1 + build.xml | 4 +- .../columniterator/SSTableReversedIterator.java | 2 +- .../org/apache/cassandra/db/rows/BTreeRow.java | 2 +- .../cassandra/db/rows/ComplexColumnData.java | 5 +- .../org/apache/cassandra/utils/btree/BTree.java | 69 +++++--------- .../test/microbench/BTreeBuildBench.java | 96 ++++++++++++++++++++ .../org/apache/cassandra/utils/BTreeTest.java | 33 ++++++- 8 files changed, 161 insertions(+), 51 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/ed5f8347/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index 2e77d2e..7f4b655 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -1,4 +1,5 @@ 3.11.3 + * Remove BTree.Builder Recycler to reduce memory usage (CASSANDRA-13929) * Reduce nodetool GC thread count (CASSANDRA-14475) * Fix New SASI view creation during Index Redistribution (CASSANDRA-14055) * Remove string formatting lines from BufferPool hot path (CASSANDRA-14416) http://git-wip-us.apache.org/repos/asf/cassandra/blob/ed5f8347/build.xml ---------------------------------------------------------------------- diff --git a/build.xml b/build.xml index 4edfbb1..54c5372 100644 --- a/build.xml +++ b/build.xml @@ -422,8 +422,8 @@ <dependency groupId="org.jboss.byteman" artifactId="byteman-bmunit" version="${byteman.version}"/> - <dependency groupId="org.openjdk.jmh" artifactId="jmh-core" version="1.13"/> - <dependency groupId="org.openjdk.jmh" artifactId="jmh-generator-annprocess" version="1.13"/> + <dependency groupId="org.openjdk.jmh" artifactId="jmh-core" version="1.21"/> + <dependency groupId="org.openjdk.jmh" artifactId="jmh-generator-annprocess" version="1.21"/> <dependency groupId="org.apache.cassandra" artifactId="cassandra-all" version="${version}" /> <dependency groupId="org.apache.cassandra" artifactId="cassandra-thrift" version="${version}" /> http://git-wip-us.apache.org/repos/asf/cassandra/blob/ed5f8347/src/java/org/apache/cassandra/db/columniterator/SSTableReversedIterator.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/columniterator/SSTableReversedIterator.java b/src/java/org/apache/cassandra/db/columniterator/SSTableReversedIterator.java index cf8798d..6a0b7be 100644 --- a/src/java/org/apache/cassandra/db/columniterator/SSTableReversedIterator.java +++ b/src/java/org/apache/cassandra/db/columniterator/SSTableReversedIterator.java @@ -426,7 +426,7 @@ public class SSTableReversedIterator extends AbstractSSTableIterator public void reset() { built = null; - rowBuilder = BTree.builder(metadata.comparator); + rowBuilder.reuse(); deletionBuilder = MutableDeletionInfo.builder(partitionLevelDeletion, metadata().comparator, false); } http://git-wip-us.apache.org/repos/asf/cassandra/blob/ed5f8347/src/java/org/apache/cassandra/db/rows/BTreeRow.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/rows/BTreeRow.java b/src/java/org/apache/cassandra/db/rows/BTreeRow.java index 15ac30a..c70e0e2 100644 --- a/src/java/org/apache/cassandra/db/rows/BTreeRow.java +++ b/src/java/org/apache/cassandra/db/rows/BTreeRow.java @@ -738,7 +738,7 @@ public class BTreeRow extends AbstractRow this.clustering = null; this.primaryKeyLivenessInfo = LivenessInfo.EMPTY; this.deletion = Deletion.LIVE; - this.cells_ = null; + this.cells_.reuse(); this.hasComplex = false; } http://git-wip-us.apache.org/repos/asf/cassandra/blob/ed5f8347/src/java/org/apache/cassandra/db/rows/ComplexColumnData.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/rows/ComplexColumnData.java b/src/java/org/apache/cassandra/db/rows/ComplexColumnData.java index 380af7a..1395782 100644 --- a/src/java/org/apache/cassandra/db/rows/ComplexColumnData.java +++ b/src/java/org/apache/cassandra/db/rows/ComplexColumnData.java @@ -242,7 +242,10 @@ public class ComplexColumnData extends ColumnData implements Iterable<Cell> { this.column = column; this.complexDeletion = DeletionTime.LIVE; // default if writeComplexDeletion is not called - this.builder = BTree.builder(column.cellComparator()); + if (builder == null) + builder = BTree.builder(column.cellComparator()); + else + builder.reuse(column.cellComparator()); } public void addComplexDeletion(DeletionTime complexDeletion) http://git-wip-us.apache.org/repos/asf/cassandra/blob/ed5f8347/src/java/org/apache/cassandra/utils/btree/BTree.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/BTree.java b/src/java/org/apache/cassandra/utils/btree/BTree.java index a4519b9..a6c9826 100644 --- a/src/java/org/apache/cassandra/utils/btree/BTree.java +++ b/src/java/org/apache/cassandra/utils/btree/BTree.java @@ -21,12 +21,12 @@ package org.apache.cassandra.utils.btree; import java.util.*; import java.util.function.Consumer; +import com.google.common.annotations.VisibleForTesting; import com.google.common.base.Function; import com.google.common.base.Predicate; import com.google.common.collect.Iterators; import com.google.common.collect.Ordering; -import io.netty.util.Recycler; import org.apache.cassandra.utils.ObjectSizes; import static com.google.common.collect.Iterables.concat; @@ -769,25 +769,14 @@ public class BTree return 1 + lookupSizeMap(root, childIndex - 1); } - final static Recycler<Builder> builderRecycler = new Recycler<Builder>() - { - protected Builder newObject(Handle handle) - { - return new Builder(handle); - } - }; - public static <V> Builder<V> builder(Comparator<? super V> comparator) { - Builder<V> builder = builderRecycler.get(); - builder.reuse(comparator); - - return builder; + return new Builder<>(comparator); } public static <V> Builder<V> builder(Comparator<? super V> comparator, int initialCapacity) { - return builder(comparator); + return new Builder<>(comparator, initialCapacity); } public static class Builder<V> @@ -816,12 +805,23 @@ public class BTree boolean detected = true; // true if we have managed to cheaply ensure sorted (+ filtered, if resolver == null) as we have added boolean auto = true; // false if the user has promised to enforce the sort order and resolve any duplicates QuickResolver<V> quickResolver; - final Recycler.Handle recycleHandle; + protected Builder(Comparator<? super V> comparator) + { + this(comparator, 16); + } + + protected Builder(Comparator<? super V> comparator, int initialCapacity) + { + if (initialCapacity == 0) + initialCapacity = 16; + this.comparator = comparator; + this.values = new Object[initialCapacity]; + } - private Builder(Recycler.Handle handle) + @VisibleForTesting + public Builder() { - this.recycleHandle = handle; this.values = new Object[16]; } @@ -833,7 +833,6 @@ public class BTree this.detected = builder.detected; this.auto = builder.auto; this.quickResolver = builder.quickResolver; - this.recycleHandle = null; } /** @@ -851,30 +850,17 @@ public class BTree return this; } - public void recycle() + public void reuse() { - if (recycleHandle != null) - { - this.cleanup(); - builderRecycler.recycle(this, recycleHandle); - } + reuse(comparator); } - /** - * Cleans up the Builder instance before recycling it. - */ - private void cleanup() + public void reuse(Comparator<? super V> comparator) { - quickResolver = null; + this.comparator = comparator; Arrays.fill(values, null); count = 0; detected = true; - auto = true; - } - - private void reuse(Comparator<? super V> comparator) - { - this.comparator = comparator; } public Builder<V> auto(boolean auto) @@ -1101,16 +1087,9 @@ public class BTree public Object[] build() { - try - { - if (auto) - autoEnforce(); - return BTree.build(Arrays.asList(values).subList(0, count), UpdateFunction.noOp()); - } - finally - { - this.recycle(); - } + if (auto) + autoEnforce(); + return BTree.build(Arrays.asList(values).subList(0, count), UpdateFunction.noOp()); } } http://git-wip-us.apache.org/repos/asf/cassandra/blob/ed5f8347/test/microbench/org/apache/cassandra/test/microbench/BTreeBuildBench.java ---------------------------------------------------------------------- diff --git a/test/microbench/org/apache/cassandra/test/microbench/BTreeBuildBench.java b/test/microbench/org/apache/cassandra/test/microbench/BTreeBuildBench.java new file mode 100644 index 0000000..0d89ebb --- /dev/null +++ b/test/microbench/org/apache/cassandra/test/microbench/BTreeBuildBench.java @@ -0,0 +1,96 @@ +/* + * 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.cassandra.test.microbench; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.List; +import java.util.concurrent.TimeUnit; + +import org.apache.cassandra.utils.btree.BTree; +import org.apache.cassandra.utils.btree.UpdateFunction; +import org.openjdk.jmh.annotations.Benchmark; +import org.openjdk.jmh.annotations.BenchmarkMode; +import org.openjdk.jmh.annotations.Fork; +import org.openjdk.jmh.annotations.Level; +import org.openjdk.jmh.annotations.Measurement; +import org.openjdk.jmh.annotations.Mode; +import org.openjdk.jmh.annotations.OutputTimeUnit; +import org.openjdk.jmh.annotations.Param; +import org.openjdk.jmh.annotations.Scope; +import org.openjdk.jmh.annotations.Setup; +import org.openjdk.jmh.annotations.State; +import org.openjdk.jmh.annotations.Threads; +import org.openjdk.jmh.annotations.Warmup; + +@BenchmarkMode(Mode.Throughput) +@OutputTimeUnit(TimeUnit.MILLISECONDS) +@Warmup(iterations = 4, time = 1, timeUnit = TimeUnit.SECONDS) +@Measurement(iterations = 8, time = 2, timeUnit = TimeUnit.SECONDS) +@Fork(value = 2) +@Threads(4) +@State(Scope.Benchmark) +public class BTreeBuildBench +{ + private List<Integer> data; + + @Param({"1", "2", "5", "10", "20", "40", "100", "1000", "10000", "100000"}) + int dataSize; + + private static final Comparator<Integer> CMP = new Comparator<Integer>() + { + public int compare(Integer o1, Integer o2) + { + return Integer.compare(o1, o2); + } + }; + + @Setup(Level.Trial) + public void setup() + { + data = new ArrayList<>(dataSize); + for (int i = 0 ; i < dataSize; i++) + data.add(i); + } + + private int buildTree(List<Integer> data) + { + Object[] btree = BTree.build(data, UpdateFunction.noOp()); + // access the btree to avoid java optimized out this code + return BTree.size(btree); + } + + private int treeBuilderAddAll(List<Integer> data) + { + BTree.Builder<Integer> builder = BTree.builder(Comparator.naturalOrder()); + Object[] btree = builder.addAll(data).build(); + return BTree.size(btree); + } + + @Benchmark + public int treeBuilderRecycleAdd() + { + BTree.Builder<Integer> builder = BTree.builder(Comparator.naturalOrder()); + builder.auto(false); + for (Integer v : data) + builder.add(v); + Object[] btree = builder.build(); + return BTree.size(btree); + } +} http://git-wip-us.apache.org/repos/asf/cassandra/blob/ed5f8347/test/unit/org/apache/cassandra/utils/BTreeTest.java ---------------------------------------------------------------------- diff --git a/test/unit/org/apache/cassandra/utils/BTreeTest.java b/test/unit/org/apache/cassandra/utils/BTreeTest.java index ec4cdb8..9a59e3a 100644 --- a/test/unit/org/apache/cassandra/utils/BTreeTest.java +++ b/test/unit/org/apache/cassandra/utils/BTreeTest.java @@ -261,6 +261,32 @@ public class BTreeTest } } + @Test + public void testBuilderReuse() + { + List<Integer> sorted = seq(20); + BTree.Builder<Integer> builder = BTree.builder(Comparator.naturalOrder()); + builder.auto(false); + for (int i : sorted) + builder.add(i); + checkResult(20, builder.build()); + + builder.reuse(); + assertTrue(builder.build() == BTree.empty()); + for (int i = 0; i < 12; i++) + builder.add(sorted.get(i)); + checkResult(12, builder.build()); + + builder.auto(true); + builder.reuse(Comparator.reverseOrder()); + for (int i = 0; i < 12; i++) + builder.add(sorted.get(i)); + checkResult(12, builder.build(), BTree.Dir.DESC); + + builder.reuse(); + assertTrue(builder.build() == BTree.empty()); + } + private static class Accumulator extends Number implements Comparable<Accumulator> { final int base; @@ -385,7 +411,12 @@ public class BTreeTest private static void checkResult(int count, Object[] btree) { - Iterator<Integer> iter = BTree.slice(btree, CMP, BTree.Dir.ASC); + checkResult(count, btree, BTree.Dir.ASC); + } + + private static void checkResult(int count, Object[] btree, BTree.Dir dir) + { + Iterator<Integer> iter = BTree.slice(btree, CMP, dir); int i = 0; while (iter.hasNext()) assertEquals(iter.next(), ints[i++]); --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org