You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@activemq.apache.org by cl...@apache.org on 2020/03/17 14:49:07 UTC
[activemq-artemis] branch master updated: NO-JIRA Let
SparseArrayLinkedList to reuse the last empty array
This is an automated email from the ASF dual-hosted git repository.
clebertsuconic pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/activemq-artemis.git
The following commit(s) were added to refs/heads/master by this push:
new 0ae8c63 NO-JIRA Let SparseArrayLinkedList to reuse the last empty array
new fa4b579 This closes #2971
0ae8c63 is described below
commit 0ae8c63d415d318bdff878c4ba68cb0a302d36fe
Author: Francesco Nigro <ni...@gmail.com>
AuthorDate: Tue Feb 4 21:20:37 2020 +0100
NO-JIRA Let SparseArrayLinkedList to reuse the last empty array
---
.../utils/collections/SparseArrayLinkedList.java | 20 ++++++++++++++-----
.../collections/SparseArrayLinkedListTest.java | 23 +++++++++++++++++++---
2 files changed, 35 insertions(+), 8 deletions(-)
diff --git a/artemis-commons/src/main/java/org/apache/activemq/artemis/utils/collections/SparseArrayLinkedList.java b/artemis-commons/src/main/java/org/apache/activemq/artemis/utils/collections/SparseArrayLinkedList.java
index b797220..f6b2a51 100644
--- a/artemis-commons/src/main/java/org/apache/activemq/artemis/utils/collections/SparseArrayLinkedList.java
+++ b/artemis-commons/src/main/java/org/apache/activemq/artemis/utils/collections/SparseArrayLinkedList.java
@@ -29,7 +29,10 @@ import java.util.function.Predicate;
* Differently from an {@code UnrolledLinkedList} this list doesn't optimize addition and removal to achieve a balanced
* utilization among chunks ie a chunk is removed only if empty and chunks can't be merged.
* This list has been optimized for small-sized chunks (ideally <= 32 elements): this allow search/removal to
- * be performed with a greedy approach despite a sparse chunk utilization (ie chunks contains few sparse elements)
+ * be performed with a greedy approach despite a sparse chunk utilization (ie chunks contains few sparse elements).<br>
+ *
+ * From the memory footprint's point of view, this list won't remove the last remaining array although empty to optimize
+ * the case where its capacity would be enough to hold incoming elements, hence saving a new array allocation.
*/
public final class SparseArrayLinkedList<T> {
@@ -89,6 +92,11 @@ public final class SparseArrayLinkedList<T> {
}
}
size -= removed;
+ // reset the tail in case of no elements left:
+ // tail is set to be the next of the last
+ if (size == 0) {
+ tail = 0;
+ }
return removed;
}
@@ -134,10 +142,10 @@ public final class SparseArrayLinkedList<T> {
final int justRemoved = sparseArray.remove(filter);
removed += justRemoved;
if (justRemoved > 0) {
- // remove RecordInfo only if empty:
+ // remove the array only if empty and not the last one:
// it means that there is a chance of fragmentation
- // proportional with the capacity of chunk
- if (sparseArray.size() == 0) {
+ // proportional with the array capacity
+ if (sparseArrayList.size() > 1 && sparseArray.size() == 0) {
iter.remove();
}
}
@@ -159,11 +167,13 @@ public final class SparseArrayLinkedList<T> {
final int size = sparseArrayList.size();
long count = 0;
if (size > 0) {
- for (int i = 0; i < size; i++) {
+ for (int i = 0; i < size - 1; i++) {
// LinkedList::remove(0) is fast as LinkedList::getFirst
final SparseArray<T> removed = sparseArrayList.remove(0);
count += removed.clear(consumer);
}
+ // LinkedList::get(0) is fast as LinkedList::getFirst
+ count += sparseArrayList.get(0).clear(consumer);
}
return count;
}
diff --git a/artemis-commons/src/test/java/org/apache/activemq/artemis/utils/collections/SparseArrayLinkedListTest.java b/artemis-commons/src/test/java/org/apache/activemq/artemis/utils/collections/SparseArrayLinkedListTest.java
index 3ff5805..113929f 100644
--- a/artemis-commons/src/test/java/org/apache/activemq/artemis/utils/collections/SparseArrayLinkedListTest.java
+++ b/artemis-commons/src/test/java/org/apache/activemq/artemis/utils/collections/SparseArrayLinkedListTest.java
@@ -76,7 +76,7 @@ public class SparseArrayLinkedListTest {
}
final List<Integer> removed = new ArrayList<>(elements);
Assert.assertEquals(elements, list.clear(removed::add));
- Assert.assertEquals(0, list.sparseArraysCount());
+ Assert.assertEquals(1, list.sparseArraysCount());
Assert.assertEquals(0, list.size());
Assert.assertThat(removed, is(expected));
}
@@ -93,8 +93,9 @@ public class SparseArrayLinkedListTest {
Assert.assertEquals(elements - 1, list.size());
Assert.assertEquals(elements - 1, list.remove(e -> true));
Assert.assertEquals(0, list.size());
+ Assert.assertEquals(1, list.sparseArraysCount());
Assert.assertEquals(0, list.remove(e -> true));
- Assert.assertEquals(0, list.sparseArraysCount());
+ Assert.assertEquals(1, list.sparseArraysCount());
}
@Test
@@ -120,7 +121,7 @@ public class SparseArrayLinkedListTest {
final int endNotInclusiveLast = elements;
Assert.assertEquals(list.sparseArrayCapacity(),
list.remove(e -> e.intValue() >= startInclusiveLast && e.intValue() < endNotInclusiveLast));
- Assert.assertEquals(0, list.sparseArraysCount());
+ Assert.assertEquals(1, list.sparseArraysCount());
}
@Test
@@ -140,6 +141,22 @@ public class SparseArrayLinkedListTest {
}
@Test
+ public void shouldReuseAllTheAvailableSpaceInTheSameArray() {
+ final int elements = list.sparseArrayCapacity();
+ for (int i = 0; i < elements; i++) {
+ list.add(i);
+ }
+ Assert.assertEquals(1, list.sparseArraysCount());
+ // removing all elements
+ Assert.assertEquals(elements, list.remove(e -> true));
+ Assert.assertEquals(1, list.sparseArraysCount());
+ for (int i = 0; i < elements; i++) {
+ list.add(i);
+ }
+ Assert.assertEquals(1, list.sparseArraysCount());
+ }
+
+ @Test
public void shouldClearConsumeRemainingElementsInOrder() {
final int elements = ELEMENTS;
final Integer zero = 0;