You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@geode.apache.org by je...@apache.org on 2022/04/06 14:13:44 UTC
[geode] branch develop updated: GEODE-10160: fixes SizeableByteArrayList sizing (#7519)
This is an automated email from the ASF dual-hosted git repository.
jensdeppe pushed a commit to branch develop
in repository https://gitbox.apache.org/repos/asf/geode.git
The following commit(s) were added to refs/heads/develop by this push:
new 4cae7ac076 GEODE-10160: fixes SizeableByteArrayList sizing (#7519)
4cae7ac076 is described below
commit 4cae7ac07641780663f648ef533cdb9a4b978aac
Author: Steve Sienkowski <30...@users.noreply.github.com>
AuthorDate: Wed Apr 6 10:13:38 2022 -0400
GEODE-10160: fixes SizeableByteArrayList sizing (#7519)
* Update SizeableByteArrayList with overrides for LinkedList's set() and add()
methods to ensure memory overhead is updated appropriately. This helps to
correct sizing issues in other RedisList methods such as LINSERT and LTRM.
Co-authored-by: Jens Deppe <jd...@vmware.com>
---
.../geode/redis/internal/data/RedisList.java | 19 +--
.../data/collections/SizeableByteArrayList.java | 58 ++++++-
.../collections/SizeableByteArrayListTest.java | 190 ++++++++++++++++++++-
3 files changed, 234 insertions(+), 33 deletions(-)
diff --git a/geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java b/geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
index 1c48f384ef..4dc66335ad 100644
--- a/geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
+++ b/geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
@@ -456,24 +456,7 @@ public class RedisList extends AbstractRedisData {
public synchronized int elementInsert(byte[] elementToInsert, byte[] referenceElement,
boolean before) {
- int i = 0;
- ListIterator<byte[]> iterator = elementList.listIterator();
-
- while (iterator.hasNext()) {
- if (Arrays.equals(iterator.next(), referenceElement)) {
- if (before) {
- iterator.previous();
- iterator.add(elementToInsert);
- return i;
- } else {
- iterator.add(elementToInsert);
- return i + 1;
- }
- }
- i++;
- }
-
- return -1;
+ return elementList.insert(elementToInsert, referenceElement, before);
}
public synchronized void elementInsert(byte[] toInsert, int index) {
diff --git a/geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/collections/SizeableByteArrayList.java b/geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/collections/SizeableByteArrayList.java
index fedc73470b..2e74a61889 100644
--- a/geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/collections/SizeableByteArrayList.java
+++ b/geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/collections/SizeableByteArrayList.java
@@ -136,20 +136,22 @@ public class SizeableByteArrayList extends LinkedList<byte[]> implements Sizeabl
}
/**
- * @param remove in order (smallest to largest) list of indexes to remove
+ * @param removalList in order (smallest to largest) list of indexes to remove
*/
- public void removeIndexes(List<Integer> remove) {
- int removeIndex = 0;
- int firstIndexToRemove = remove.get(0);
+ public void removeIndexes(List<Integer> removalList) {
+ int removalListIndex = 0;
+ int firstIndexToRemove = removalList.get(0);
+ int lastIndexToRemove = removalList.get(removalList.size() - 1);
+
ListIterator<byte[]> iterator = listIterator(firstIndexToRemove);
// Iterates only through the indexes to remove
- for (int i = firstIndexToRemove; i <= remove.get(remove.size() - 1); i++) {
+ for (int index = firstIndexToRemove; index <= lastIndexToRemove; index++) {
byte[] element = iterator.next();
- if (i == remove.get(removeIndex)) {
+ if (index == removalList.get(removalListIndex)) {
iterator.remove();
memberOverhead -= calculateByteArrayOverhead(element);
- removeIndex++;
+ removalListIndex++;
}
}
}
@@ -175,6 +177,25 @@ public class SizeableByteArrayList extends LinkedList<byte[]> implements Sizeabl
return element;
}
+ @Override
+ public boolean removeLastOccurrence(Object o) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public byte[] set(int index, byte[] newElement) {
+ byte[] replacedElement = super.set(index, newElement);
+ memberOverhead -= calculateByteArrayOverhead(replacedElement);
+ memberOverhead += calculateByteArrayOverhead(newElement);
+ return replacedElement;
+ }
+
+ @Override
+ public void add(int index, byte[] element) {
+ memberOverhead += calculateByteArrayOverhead(element);
+ super.add(index, element);
+ }
+
@Override
public void addFirst(byte[] element) {
memberOverhead += calculateByteArrayOverhead(element);
@@ -187,8 +208,27 @@ public class SizeableByteArrayList extends LinkedList<byte[]> implements Sizeabl
super.addLast(element);
}
- public boolean removeLastOccurrence(Object o) {
- throw new UnsupportedOperationException();
+ public int insert(byte[] elementToInsert, byte[] referenceElement, boolean before) {
+ int i = 0;
+ ListIterator<byte[]> iterator = listIterator();
+
+ while (iterator.hasNext()) {
+ if (Arrays.equals(iterator.next(), referenceElement)) {
+ if (before) {
+ iterator.previous();
+ iterator.add(elementToInsert);
+ memberOverhead += calculateByteArrayOverhead(elementToInsert);
+ return i;
+ } else {
+ iterator.add(elementToInsert);
+ memberOverhead += calculateByteArrayOverhead(elementToInsert);
+ return i + 1;
+ }
+ }
+ i++;
+ }
+
+ return -1;
}
private int calculateByteArrayOverhead(byte[] element) {
diff --git a/geode-for-redis/src/test/java/org/apache/geode/redis/internal/data/collections/SizeableByteArrayListTest.java b/geode-for-redis/src/test/java/org/apache/geode/redis/internal/data/collections/SizeableByteArrayListTest.java
index 5fb6015724..b2a1fcdcbe 100644
--- a/geode-for-redis/src/test/java/org/apache/geode/redis/internal/data/collections/SizeableByteArrayListTest.java
+++ b/geode-for-redis/src/test/java/org/apache/geode/redis/internal/data/collections/SizeableByteArrayListTest.java
@@ -18,7 +18,6 @@ import static org.assertj.core.api.Assertions.assertThat;
import java.util.ArrayList;
import java.util.List;
-import java.util.Random;
import org.junit.Test;
@@ -74,14 +73,40 @@ public class SizeableByteArrayListTest {
@Test
public void removeObjects_getSizeInBytesIsAccurate() {
+ // Create a list with only duplicate elements and confirm that it correctly reports its size
+ SizeableByteArrayList list = new SizeableByteArrayList();
+ byte[] bytes = "anElement".getBytes();
+ for (int i = 0; i < INITIAL_NUMBER_OF_ELEMENTS; ++i) {
+ // Clone the byte array because otherwise we end up with the list containing multiple
+ // references to the same object in memory rather than references to multiple different
+ // objects
+ list.addFirst(bytes.clone());
+ }
+ assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
+
+ // Remove elements from the head
+ list.remove(bytes, INITIAL_NUMBER_OF_ELEMENTS / 4);
+ assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
+
+ // Remove elements from the tail
+ list.remove(bytes, INITIAL_NUMBER_OF_ELEMENTS / 4);
+ assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
+
+ // Remove all of the remaining elements
+ list.remove(bytes, 0);
+ assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
+ assertThat(list).isEmpty();
+ }
+
+ @Test
+ public void removeObject_getSizeInBytesIsAccurate() {
// Create a list with an initial size and confirm that it correctly reports its size
SizeableByteArrayList list = createList();
assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
// Remove all the elements and assert that the size is correct after each remove
- Random rand = new Random();
for (int i = 0; i < INITIAL_NUMBER_OF_ELEMENTS; ++i) {
- list.remove(makeByteArrayOfSpecifiedLength(i + 1), rand.nextInt(3) - 1);
+ list.remove(makeByteArrayOfSpecifiedLength(i + 1));
assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
}
assertThat(list.size()).isEqualTo(0);
@@ -93,16 +118,169 @@ public class SizeableByteArrayListTest {
SizeableByteArrayList list = createList();
assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
+ // Remove all the elements and assert that the size is correct after each remove
+ for (int i = INITIAL_NUMBER_OF_ELEMENTS - 1; 0 <= i;) {
+ // Remove in batches of 5
+ List<Integer> indexesToRemove = new ArrayList<>(5);
+ for (int j = 0; j < 5 && i >= 0; j++) {
+ indexesToRemove.add(0, i--);
+ }
+ list.removeIndexes(indexesToRemove);
+ assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
+ }
+ assertThat(list.size()).isEqualTo(0);
+ }
+
+ @Test
+ public void removeIndex_getSizeInBytesIsAccurate() {
+ // Create a list with an initial size and confirm that it correctly reports its size
+ SizeableByteArrayList list = createList();
+ assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
+
// Remove all the elements and assert that the size is correct after each remove
for (int i = INITIAL_NUMBER_OF_ELEMENTS - 1; 0 <= i; --i) {
- List<Integer> indexToRemove = new ArrayList<>(1);
- indexToRemove.add(i);
- list.removeIndexes(indexToRemove);
+ list.remove(i);
assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
}
assertThat(list.size()).isEqualTo(0);
}
+ @Test
+ public void set_getSizeInBytesIsAccurate() {
+ // Create a list with one initial element and confirm that it correctly reports its size
+ SizeableByteArrayList list = new SizeableByteArrayList();
+ byte[] element = "element name".getBytes();
+ list.addFirst(element);
+ long initialSize = list.getSizeInBytes();
+ assertThat(initialSize).isEqualTo(sizer.sizeof(list));
+
+ // Set the list's element to a larger element and ensure the size is correct
+ byte[] largerElement = "a larger updated element name".getBytes();
+ list.set(0, largerElement);
+ assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
+
+ // Revert the list's element to the original value and ensure size is consistent
+ list.set(0, element);
+ assertThat(list.getSizeInBytes()).isEqualTo(initialSize);
+ }
+
+ @Test
+ public void addElementAtIndex_getSizeInBytesIsAccurate() {
+ // Create a new list and confirm that it correctly reports its size
+ SizeableByteArrayList list = createList();
+ assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
+
+ // Add an element by index and assert size is updated
+ byte[] element = "element name".getBytes();
+ list.add(1, element);
+ long sizeAfterAddingElement = list.getSizeInBytes();
+ assertThat(sizeAfterAddingElement).isEqualTo(sizer.sizeof(list));
+ }
+
+ @Test
+ public void addFirst_getSizeInBytesIsAccurate() {
+ // Create a new list and confirm that it correctly reports its size
+ SizeableByteArrayList list = createList();
+ assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
+
+ // Add an element and assert size is updated
+ byte[] element = "element name".getBytes();
+ list.addFirst(element);
+ long sizeAfterAddingElement = list.getSizeInBytes();
+ assertThat(sizeAfterAddingElement).isEqualTo(sizer.sizeof(list));
+ }
+
+ @Test
+ public void addLast_getSizeInBytesIsAccurate() {
+ // Create a new list and confirm that it correctly reports its size
+ SizeableByteArrayList list = createList();
+ assertThat(list.getSizeInBytes()).isEqualTo(sizer.sizeof(list));
+
+ // Add an element and assert size is updated
+ byte[] element = "element name".getBytes();
+ list.addLast(element);
+ long sizeAfterAddingElement = list.getSizeInBytes();
+ assertThat(sizeAfterAddingElement).isEqualTo(sizer.sizeof(list));
+ }
+
+ @Test
+ public void insertElementBeforeReferenceElement_getSizeInBytesIsAccurate() {
+ // Create a new list and confirm that it correctly reports its size
+ SizeableByteArrayList list = new SizeableByteArrayList();
+ byte[] referenceElement = "element".getBytes();
+ list.addFirst(referenceElement);
+ long initialSize = list.getSizeInBytes();
+ assertThat(initialSize).isEqualTo(sizer.sizeof(list));
+
+ // Insert an element by reference and assert size is updated
+ byte[] beforeElement = "before".getBytes();
+ list.insert(beforeElement, referenceElement, true);
+
+ long sizeAfterAddingElement = list.getSizeInBytes();
+ assertThat(sizeAfterAddingElement).isEqualTo(sizer.sizeof(list));
+ }
+
+ @Test
+ public void insertElementAfterReferenceElement_getSizeInBytesIsAccurate() {
+ // Create a new list and confirm that it correctly reports its size
+ SizeableByteArrayList list = new SizeableByteArrayList();
+ byte[] referenceElement = "element".getBytes();
+ list.addFirst(referenceElement);
+ long initialSize = list.getSizeInBytes();
+ assertThat(initialSize).isEqualTo(sizer.sizeof(list));
+
+ // Insert an element by reference and assert size is updated
+ byte[] beforeElement = "after".getBytes();
+ list.insert(beforeElement, referenceElement, false);
+
+ long sizeAfterAddingElement = list.getSizeInBytes();
+ assertThat(sizeAfterAddingElement).isEqualTo(sizer.sizeof(list));
+ }
+
+ @Test
+ public void insertElementBeforeReferenceElement_placesElementCorrectly() {
+ // Create a new list with a single element
+ SizeableByteArrayList list = new SizeableByteArrayList();
+ byte[] referenceElement = "element".getBytes();
+ list.addFirst(referenceElement);
+
+ // Insert new element before reference element
+ byte[] beforeElement = "before".getBytes();
+ list.insert(beforeElement, referenceElement, true);
+
+ // Assert list contains exactly the elements in the expected order
+ assertThat(list).containsExactly(beforeElement, referenceElement);
+ }
+
+ @Test
+ public void insertElementAfterReferenceElement_placesElementCorrectly() {
+ // Create a new list with a single element
+ SizeableByteArrayList list = new SizeableByteArrayList();
+ byte[] referenceElement = "element".getBytes();
+ list.addFirst(referenceElement);
+
+ // Insert new element after reference element
+ byte[] afterElement = "after".getBytes();
+ list.insert(afterElement, referenceElement, false);
+
+ // Assert list contains exactly the elements in the expected order
+ assertThat(list).containsExactly(referenceElement, afterElement);
+ }
+
+ @Test
+ public void insertElementAfterNonexistentReferenceElement_doesNotPlaceElement() {
+ // Create a new list with a single element
+ SizeableByteArrayList list = new SizeableByteArrayList();
+ byte[] nonExistentElement = "non-existent-element".getBytes();
+
+ // Attempt to insert an element after a non-existent reference element
+ byte[] afterElement = "after".getBytes();
+ list.insert(afterElement, nonExistentElement, false);
+
+ // Assert that no elements were added to the list
+ assertThat(list).isEmpty();
+ }
+
private SizeableByteArrayList createList() {
SizeableByteArrayList list = new SizeableByteArrayList();
for (int i = 0; i < INITIAL_NUMBER_OF_ELEMENTS; ++i) {