You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by sd...@apache.org on 2022/05/30 11:46:13 UTC
[ignite] branch master updated: IGNITE-17043 Shrink GridHandleTable on clear (#10045)
This is an automated email from the ASF dual-hosted git repository.
sdanilov pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/ignite.git
The following commit(s) were added to refs/heads/master by this push:
new 14ea49d197a IGNITE-17043 Shrink GridHandleTable on clear (#10045)
14ea49d197a is described below
commit 14ea49d197a7e77533ee1db69653630adb587353
Author: Semyon Danilov <sa...@yandex.ru>
AuthorDate: Mon May 30 15:46:07 2022 +0400
IGNITE-17043 Shrink GridHandleTable on clear (#10045)
---
.../optimized/OptimizedObjectOutputStream.java | 2 +-
.../ignite/internal/util/GridHandleTable.java | 94 ++++++++++++++--------
.../internal/util/GridHandleTableSelfTest.java | 35 ++++++--
3 files changed, 91 insertions(+), 40 deletions(-)
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/marshaller/optimized/OptimizedObjectOutputStream.java b/modules/core/src/main/java/org/apache/ignite/internal/marshaller/optimized/OptimizedObjectOutputStream.java
index 2deddec8b03..f422246e329 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/marshaller/optimized/OptimizedObjectOutputStream.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/marshaller/optimized/OptimizedObjectOutputStream.java
@@ -223,7 +223,7 @@ public class OptimizedObjectOutputStream extends ObjectOutputStream {
int handle = -1;
if (!desc.isPrimitive() && !desc.isEnum() && !desc.isClass() && !desc.isProxy())
- handle = handles.lookup(obj);
+ handle = handles.putIfAbsent(obj);
if (obj0 != obj) {
obj = obj0;
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/util/GridHandleTable.java b/modules/core/src/main/java/org/apache/ignite/internal/util/GridHandleTable.java
index aace1ed0ba3..695e91db928 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/util/GridHandleTable.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/util/GridHandleTable.java
@@ -24,15 +24,18 @@ import java.util.Arrays;
* assigned in ascending order.
*/
public class GridHandleTable {
+ /** Initial size. */
+ private final int initCap;
+
+ /** Factor for computing size threshold. */
+ private final float loadFactor;
+
/** Number of mappings in table/next available handle. */
private int size;
/** Size threshold determining when to expand hash spine. */
private int threshold;
- /** Factor for computing size threshold. */
- private final float loadFactor;
-
/** Maps hash value -> candidate handle value. */
private int[] spine;
@@ -42,12 +45,6 @@ public class GridHandleTable {
/** Maps handle value -> associated object. */
private Object[] objs;
- /** */
- private int[] spineEmpty;
-
- /** */
- private int[] nextEmpty;
-
/**
* Creates new HandleTable with given capacity and load factor.
*
@@ -55,30 +52,36 @@ public class GridHandleTable {
* @param loadFactor Load factor.
*/
public GridHandleTable(int initCap, float loadFactor) {
+ this.initCap = initCap;
this.loadFactor = loadFactor;
- spine = new int[initCap];
- next = new int[initCap];
- objs = new Object[initCap];
- spineEmpty = new int[initCap];
- nextEmpty = new int[initCap];
+ init(initCap, initCap);
+ }
- Arrays.fill(spineEmpty, -1);
- Arrays.fill(nextEmpty, -1);
+ /**
+ * Initialize hash table.
+ *
+ * @param spineLen Spine array length.
+ * @param size Hash table length.
+ */
+ private void init(int spineLen, int size) {
+ spine = new int[spineLen];
+ next = new int[size];
+ objs = new Object[size];
- threshold = (int)(initCap * loadFactor);
+ Arrays.fill(spine, -1);
- clear();
+ threshold = (int)(spineLen * loadFactor);
}
/**
- * Looks up and returns handle associated with given object, or -1 if
- * no mapping found.
+ * Looks up and returns handle associated with the given object. If the given object was not found,
+ * puts it into the table and returns {@code -1}.
*
* @param obj Object.
- * @return Handle.
+ * @return Object's handle or {@code -1} if it was not in the table.
*/
- public int lookup(Object obj) {
+ public int putIfAbsent(Object obj) {
int idx = hash(obj) % spine.length;
if (size > 0) {
@@ -107,10 +110,16 @@ public class GridHandleTable {
* Resets table to its initial (empty) state.
*/
public void clear() {
- System.arraycopy(spineEmpty, 0, spine, 0, spineEmpty.length);
- System.arraycopy(nextEmpty, 0, next, 0, nextEmpty.length);
+ if (size < objs.length) {
+ if (shrink()) {
+ size = 0;
+
+ return;
+ }
+ }
- Arrays.fill(objs, null);
+ Arrays.fill(spine, -1);
+ Arrays.fill(objs, 0, size, null);
size = 0;
}
@@ -144,12 +153,9 @@ public class GridHandleTable {
int size = (spine.length << 1) + 1;
spine = new int[size];
- spineEmpty = new int[size];
threshold = (int)(spine.length * loadFactor);
- Arrays.fill(spineEmpty, -1);
-
- System.arraycopy(spineEmpty, 0, spine, 0, spineEmpty.length);
+ Arrays.fill(spine, -1);
for (int i = 0; i < this.size; i++) {
Object obj = objs[i];
@@ -170,9 +176,6 @@ public class GridHandleTable {
System.arraycopy(next, 0, newNext, 0, size);
next = newNext;
- nextEmpty = new int[newLen];
-
- Arrays.fill(nextEmpty, -1);
Object[] newObjs = new Object[newLen];
@@ -181,6 +184,33 @@ public class GridHandleTable {
objs = newObjs;
}
+ /**
+ * Tries to gradually shrink hash table by factor of two when it's cleared.
+ *
+ * @return {@code true} if shrinked the table, {@code false} otherwise.
+ */
+ private boolean shrink() {
+ int newSize = Math.max((objs.length - 1) / 2, initCap);
+
+ if (newSize >= size && newSize < objs.length) {
+ int newSpine = spine.length;
+
+ if (spine.length > initCap) {
+ int prevSpine = (spine.length - 1) / 2;
+ int prevThreshold = (int)(prevSpine * loadFactor);
+
+ if (newSize < prevThreshold)
+ newSpine = prevSpine;
+ }
+
+ init(newSpine, newSize);
+
+ return true;
+ }
+
+ return false;
+ }
+
/**
* Returns hash value for given object.
*
diff --git a/modules/core/src/test/java/org/apache/ignite/internal/util/GridHandleTableSelfTest.java b/modules/core/src/test/java/org/apache/ignite/internal/util/GridHandleTableSelfTest.java
index 6b3d9d43a3d..d7d2d6b4794 100644
--- a/modules/core/src/test/java/org/apache/ignite/internal/util/GridHandleTableSelfTest.java
+++ b/modules/core/src/test/java/org/apache/ignite/internal/util/GridHandleTableSelfTest.java
@@ -24,21 +24,19 @@ import org.junit.Test;
* Test for {@link GridHandleTable}.
*/
public class GridHandleTableSelfTest extends GridCommonAbstractTest {
- /**
- * @throws Exception If failed.
- */
+ /** */
@Test
- public void testGrow() throws Exception {
+ public void testGrow() {
GridHandleTable table = new GridHandleTable(8, 2);
for (int i = 0; i < 16; i++)
- assertEquals(-1, table.lookup(i));
+ assertEquals(-1, table.putIfAbsent(i));
Object testObj = new Object();
- assertEquals(-1, table.lookup(testObj));
+ assertEquals(-1, table.putIfAbsent(testObj));
- assertEquals(16, table.lookup(testObj));
+ assertEquals(16, table.putIfAbsent(testObj));
int cnt = 0;
@@ -49,4 +47,27 @@ public class GridHandleTableSelfTest extends GridCommonAbstractTest {
assertEquals(1, cnt);
}
+
+ /** */
+ @Test
+ public void testShrink() {
+ GridHandleTable table = new GridHandleTable(8, 3);
+
+ assertEquals(8, table.objects().length);
+
+ for (int i = 0; i < 32; i++)
+ assertEquals(-1, table.putIfAbsent(i));
+
+ assertEquals(35, table.objects().length);
+
+ table.clear();
+
+ table.clear();
+
+ assertEquals(17, table.objects().length);
+
+ table.clear();
+
+ assertEquals(8, table.objects().length);
+ }
}