You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@bookkeeper.apache.org by eo...@apache.org on 2022/02/27 21:14:53 UTC
[bookkeeper] branch master updated: reduce unnecessary expansions for ConcurrentLong map and set (#3072)
This is an automated email from the ASF dual-hosted git repository.
eolivelli pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/bookkeeper.git
The following commit(s) were added to refs/heads/master by this push:
new 9a932c5 reduce unnecessary expansions for ConcurrentLong map and set (#3072)
9a932c5 is described below
commit 9a932c5822eb8ef47c1954ea31acfd47f8f6f440
Author: lin chen <15...@qq.com>
AuthorDate: Mon Feb 28 05:14:48 2022 +0800
reduce unnecessary expansions for ConcurrentLong map and set (#3072)
---
.../util/collections/ConcurrentLongHashMap.java | 16 ++++++++++++++++
.../util/collections/ConcurrentLongHashSet.java | 10 ++++++++++
.../util/collections/ConcurrentLongLongHashMap.java | 10 ++++++++++
.../util/collections/ConcurrentLongLongPairHashMap.java | 3 ++-
.../util/collections/ConcurrentOpenHashMap.java | 11 +++++++++++
.../util/collections/ConcurrentOpenHashSet.java | 10 ++++++++++
6 files changed, 59 insertions(+), 1 deletion(-)
diff --git a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongHashMap.java b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongHashMap.java
index d98d3a7..8993b57 100644
--- a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongHashMap.java
+++ b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongHashMap.java
@@ -355,6 +355,18 @@ public class ConcurrentLongHashMap<V> {
}
}
+ private void cleanDeletedStatus(int startBucket) {
+ // Cleanup all the buckets that were in `DeletedValue` state,
+ // so that we can reduce unnecessary expansions
+ int lastBucket = signSafeMod(startBucket - 1, capacity);
+ while (values[lastBucket] == DeletedValue) {
+ values[lastBucket] = (V) EmptyValue;
+ --usedBuckets;
+
+ lastBucket = signSafeMod(--lastBucket, capacity);
+ }
+ }
+
private V remove(long key, Object value, int keyHash) {
int bucket = keyHash;
long stamp = writeLock();
@@ -377,6 +389,8 @@ public class ConcurrentLongHashMap<V> {
if (nextValueInArray == EmptyValue) {
values[bucket] = (V) EmptyValue;
--usedBuckets;
+
+ cleanDeletedStatus(bucket);
} else {
values[bucket] = (V) DeletedValue;
}
@@ -419,6 +433,8 @@ public class ConcurrentLongHashMap<V> {
if (nextValueInArray == EmptyValue) {
values[bucket] = (V) EmptyValue;
--usedBuckets;
+
+ cleanDeletedStatus(bucket);
} else {
values[bucket] = (V) DeletedValue;
}
diff --git a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongHashSet.java b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongHashSet.java
index b0edaad..acb5573 100644
--- a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongHashSet.java
+++ b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongHashSet.java
@@ -305,6 +305,16 @@ public class ConcurrentLongHashSet {
if (table[nextInArray] == EmptyItem) {
table[bucket] = EmptyItem;
--usedBuckets;
+
+ // Cleanup all the buckets that were in `DeletedKey` state,
+ // so that we can reduce unnecessary expansions
+ bucket = (bucket - 1) & (table.length - 1);
+ while (table[bucket] == DeletedItem) {
+ table[bucket] = EmptyItem;
+ --usedBuckets;
+
+ bucket = (bucket - 1) & (table.length - 1);
+ }
} else {
table[bucket] = DeletedItem;
}
diff --git a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongLongHashMap.java b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongLongHashMap.java
index f3e3d56..c5d1c7b 100644
--- a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongLongHashMap.java
+++ b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongLongHashMap.java
@@ -608,6 +608,16 @@ public class ConcurrentLongLongHashMap {
table[bucket] = EmptyKey;
table[bucket + 1] = ValueNotFound;
--usedBuckets;
+
+ // Cleanup all the buckets that were in `DeletedKey` state, so that we can reduce unnecessary expansions
+ bucket = (bucket - 2) & (table.length - 1);
+ while (table[bucket] == DeletedKey) {
+ table[bucket] = EmptyKey;
+ table[bucket + 1] = ValueNotFound;
+ --usedBuckets;
+
+ bucket = (bucket - 2) & (table.length - 1);
+ }
} else {
table[bucket] = DeletedKey;
table[bucket + 1] = ValueNotFound;
diff --git a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongLongPairHashMap.java b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongLongPairHashMap.java
index 6775610..2aee488 100644
--- a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongLongPairHashMap.java
+++ b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentLongLongPairHashMap.java
@@ -499,7 +499,8 @@ public class ConcurrentLongLongPairHashMap {
table[bucket + 3] = ValueNotFound;
--usedBuckets;
- // Cleanup all the buckets that were in `DeletedKey` state, so that we can reduce unnecessary expansions
+ // Cleanup all the buckets that were in `DeletedKey` state,
+ // so that we can reduce unnecessary expansions
bucket = (bucket - 4) & (table.length - 1);
while (table[bucket] == DeletedKey) {
table[bucket] = EmptyKey;
diff --git a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentOpenHashMap.java b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentOpenHashMap.java
index 475b70e..8610833 100644
--- a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentOpenHashMap.java
+++ b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentOpenHashMap.java
@@ -429,6 +429,17 @@ public class ConcurrentOpenHashMap<K, V> {
table[bucket] = EmptyKey;
table[bucket + 1] = null;
--usedBuckets;
+
+ // Cleanup all the buckets that were in `DeletedKey` state,
+ // so that we can reduce unnecessary expansions
+ bucket = (bucket - 2) & (table.length - 1);
+ while (table[bucket] == DeletedKey) {
+ table[bucket] = EmptyKey;
+ table[bucket + 1] = null;
+ --usedBuckets;
+
+ bucket = (bucket - 2) & (table.length - 1);
+ }
} else {
table[bucket] = DeletedKey;
table[bucket + 1] = null;
diff --git a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentOpenHashSet.java b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentOpenHashSet.java
index 19482e4..83a953d 100644
--- a/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentOpenHashSet.java
+++ b/bookkeeper-server/src/main/java/org/apache/bookkeeper/util/collections/ConcurrentOpenHashSet.java
@@ -285,6 +285,16 @@ public class ConcurrentOpenHashSet<V> {
if (values[nextInArray] == EmptyValue) {
values[bucket] = (V) EmptyValue;
--usedBuckets;
+
+ // Cleanup all the buckets that were in `DeletedValue` state,
+ // so that we can reduce unnecessary expansions
+ int lastBucket = signSafeMod(bucket - 1, capacity);
+ while (values[bucket] == DeletedValue) {
+ values[bucket] = (V) EmptyValue;
+ --usedBuckets;
+
+ lastBucket = signSafeMod(--lastBucket, capacity);
+ }
} else {
values[bucket] = (V) DeletedValue;
}