This is an automated email from the ASF dual-hosted git repository. asf-gitbox-commits pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/commons-jcs.git
commit 39b55b388109baf5d2b2c63e3fa66ff9a4940d97 Author: Thomas Vandahl <[email protected]> AuthorDate: Wed Sep 30 16:05:29 2026 +0200 Remove unnecessary operations, use random for shard selection --- .../jcs4/utils/struct/DoubleLinkedList.java | 97 ++++++++++--------- .../utils/struct/DoubleLinkedListUnitTest.java | 105 +++++++++++---------- 2 files changed, 110 insertions(+), 92 deletions(-) diff --git a/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedList.java b/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedList.java index 7631a3d4..ea23f8c1 100644 --- a/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedList.java +++ b/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedList.java @@ -1,7 +1,8 @@ package org.apache.commons.jcs4.utils.struct; +import java.util.Arrays; import java.util.Iterator; -import java.util.concurrent.atomic.AtomicInteger; +import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; @@ -39,12 +40,12 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> /** The logger */ private static final Log log = Log.getLog( DoubleLinkedList.class ); - /** Record size to avoid having to iterate */ - private AtomicInteger size; - /** Number of shards */ private final int shards; + /** Record sizes to avoid having to iterate */ + private int[] size; + /** The locks */ private final Lock[] lock; @@ -54,26 +55,6 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> /** LRU double linked list tail node */ private DoubleLinkedListNode[] last; - private static class AtomicCyclicCounter - { - private final int max; - private final AtomicInteger counter; - - private AtomicCyclicCounter(int max) - { - this.max = max; - counter = new AtomicInteger(-1); - } - - private int incrementAndGet() - { - return counter.accumulateAndGet(1, (index, inc) -> (++index >= max ? 0 : index)); - } - } - - /** shard to spool */ - private final AtomicCyclicCounter spoolShard; - /** * Construct DoubleLinkedList * @@ -81,12 +62,11 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> */ public DoubleLinkedList(int shards) { - this.size = new AtomicInteger(); this.shards = shards; + this.size = new int[shards]; this.lock = new Lock[shards]; this.first = new DoubleLinkedListNode[shards]; this.last = new DoubleLinkedListNode[shards]; - this.spoolShard = new AtomicCyclicCounter(shards); for (int i = 0; i < shards; i++) { @@ -95,6 +75,7 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> first[i].next = this.last[i]; last[i].prev = this.first[i]; lock[i] = new ReentrantLock(); + size[i] = 0; } } @@ -131,11 +112,16 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> lock[shard].lock(); try { + if (me.prev == first[shard] && first[shard].next == me) + { + // already first + return; + } me.prev = first[shard]; me.next = first[shard].next; first[shard].next.prev = me; first[shard].next = me; - size.incrementAndGet(); + size[shard]++; } finally { @@ -154,11 +140,16 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> lock[shard].lock(); try { + if (me.next == last[shard] && last[shard].prev == me) + { + // already last + return; + } me.next = last[shard]; me.prev = last[shard].prev; last[shard].prev.next = me; last[shard].prev = me; - size.incrementAndGet(); + size[shard]++; } finally { @@ -190,9 +181,9 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> public T getFirst() { log.debug("returning first node"); + int shard = ThreadLocalRandom.current().nextInt(shards); for (int i = 0; i < shards; i++) { - int shard = this.spoolShard.incrementAndGet(); lock[shard].lock(); try { @@ -207,6 +198,8 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> { lock[shard].unlock(); } + + shard = ++shard % shards; } return null; @@ -220,9 +213,9 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> public T getLast() { log.debug("returning last node"); + int shard = ThreadLocalRandom.current().nextInt(shards); for (int i = 0; i < shards; i++) { - int shard = this.spoolShard.incrementAndGet(); lock[shard].lock(); try { @@ -237,6 +230,8 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> { lock[shard].unlock(); } + + shard = ++shard % shards; } return null; @@ -253,17 +248,24 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> lock[shard].lock(); try { - if (ln.prev != null && ln.next != null) + if (ln.prev == first[shard] && first[shard].next == ln) + { + // already first + return; + } + if (ln.prev == null || ln.next == null) + { + size[shard]++; + } + else { ln.prev.next = ln.next; ln.next.prev = ln.prev; - size.decrementAndGet(); } ln.prev = first[shard]; ln.next = first[shard].next; first[shard].next.prev = ln; first[shard].next = ln; - size.incrementAndGet(); } finally { @@ -282,17 +284,24 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> lock[shard].lock(); try { - if (ln.prev != null && ln.next != null) + if (ln.next == last[shard] && last[shard].prev == ln) + { + // already last + return; + } + if (ln.prev == null || ln.next == null) + { + size[shard]++; + } + else { ln.prev.next = ln.next; ln.next.prev = ln.prev; - size.decrementAndGet(); } ln.next = last[shard]; ln.prev = last[shard].prev; last[shard].prev.next = ln; last[shard].prev = ln; - size.incrementAndGet(); } finally { @@ -313,19 +322,21 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> lock[shard].lock(); try { - if (me.prev != null && me.next != null) + if (me.prev == null || me.next == null) { - me.prev.next = me.next; - me.next.prev = me.prev; - me.prev = me.next = null; - size.decrementAndGet(); + return false; } + + me.prev.next = me.next; + me.next.prev = me.prev; + size[shard]--; } finally { lock[shard].unlock(); } + me.prev = me.next = null; return true; } @@ -346,10 +357,10 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> me = me.next; toRemove.prev = null; toRemove.next = null; - size.decrementAndGet(); } first[i].next = last[i]; last[i].prev = first[i]; + size[i] = 0; } finally { @@ -382,7 +393,7 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> */ public int size() { - return size.get(); + return Arrays.stream(size).sum(); } /** diff --git a/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListUnitTest.java b/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListUnitTest.java index 648b5fd6..bc6cf419 100644 --- a/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListUnitTest.java +++ b/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListUnitTest.java @@ -21,6 +21,7 @@ package org.apache.commons.jcs4.utils.struct; import static org.junit.jupiter.api.Assertions.assertEquals; import static org.junit.jupiter.api.Assertions.assertNull; +import static org.junit.jupiter.api.Assertions.assertTrue; import org.junit.jupiter.api.Test; @@ -37,10 +38,10 @@ class DoubleLinkedListUnitTest final DoubleLinkedListNode node1 = new DoubleLinkedListNode(); // WO WORK - list.addLast( node1 ); + list.addLast(node1); // VERIFY - assertEquals( node1, list.getLast(), "Wrong last" ); + assertEquals(node1, list.getLast(), "Wrong last"); } /** Verify that the last is added when the list is empty. */ @@ -54,11 +55,11 @@ class DoubleLinkedListUnitTest final DoubleLinkedListNode node2 = new DoubleLinkedListNode(); // WO WORK - list.addLast( node1 ); - list.addLast( node2 ); + list.addLast(node1); + list.addLast(node2); // VERIFY - assertEquals( node2, list.getLast(), "Wrong last" ); + assertEquals(node2, list.getLast(), "Wrong last"); } /** Verify that it's added last. */ @@ -70,15 +71,15 @@ class DoubleLinkedListUnitTest final DoubleLinkedListNode node1 = new DoubleLinkedListNode(); - list.addFirst( node1 ); + list.addFirst(node1); // DO WORK - list.makeLast( node1 ); + list.makeLast(node1); // VERIFY - assertEquals( 1, list.size(), "Wrong size" ); - assertEquals( node1, list.getLast(), "Wrong last" ); - assertEquals( node1, list.getFirst(), "Wrong first" ); + assertEquals(1, list.size(), "Wrong size"); + assertEquals(node1, list.getLast(), "Wrong last"); + assertEquals(node1, list.getFirst(), "Wrong first"); } /** Verify that it's added last. */ @@ -91,16 +92,16 @@ class DoubleLinkedListUnitTest final DoubleLinkedListNode node1 = new DoubleLinkedListNode(); final DoubleLinkedListNode node2 = new DoubleLinkedListNode(); - list.addFirst( node2 ); - list.addFirst( node1 ); + list.addFirst(node2); + list.addFirst(node1); // DO WORK - list.makeLast( node1 ); + list.makeLast(node1); // VERIFY - assertEquals( 2, list.size(), "Wrong size" ); - assertEquals( node1, list.getLast(), "Wrong last" ); - assertEquals( node2, list.getFirst(), "Wrong first" ); + assertEquals(2, list.size(), "Wrong size"); + assertEquals(node1, list.getLast(), "Wrong last"); + assertEquals(node2, list.getFirst(), "Wrong first"); } /** Verify that it's added last. */ @@ -114,17 +115,17 @@ class DoubleLinkedListUnitTest final DoubleLinkedListNode node2 = new DoubleLinkedListNode(); final DoubleLinkedListNode node3 = new DoubleLinkedListNode(); - list.addFirst( node2 ); - list.addFirst( node1 ); - list.addFirst( node3 ); + list.addFirst(node2); + list.addFirst(node1); + list.addFirst(node3); // DO WORK - list.makeLast( node1 ); + list.makeLast(node1); // VERIFY - assertEquals( 3, list.size(), "Wrong size" ); - assertEquals( node1, list.getLast(), "Wrong last" ); - assertEquals( node3, list.getFirst(), "Wrong first" ); + assertEquals(3, list.size(), "Wrong size"); + assertEquals(node1, list.getLast(), "Wrong last"); + assertEquals(node3, list.getFirst(), "Wrong first"); } /** Verify that it's added last. */ @@ -137,16 +138,16 @@ class DoubleLinkedListUnitTest final DoubleLinkedListNode node1 = new DoubleLinkedListNode(); final DoubleLinkedListNode node2 = new DoubleLinkedListNode(); - list.addFirst( node1 ); - list.addFirst( node2 ); + list.addFirst(node1); + list.addFirst(node2); // DO WORK - list.makeLast( node1 ); + list.makeLast(node1); // VERIFY - assertEquals( 2, list.size(), "Wrong size" ); - assertEquals( node1, list.getLast(), "Wrong last" ); - assertEquals( node2, list.getFirst(), "Wrong first" ); + assertEquals(2, list.size(), "Wrong size"); + assertEquals(node1, list.getLast(), "Wrong last"); + assertEquals(node2, list.getFirst(), "Wrong first"); } /** Verify shard cleanup */ @@ -176,12 +177,18 @@ class DoubleLinkedListUnitTest // VERIFY assertEquals(4, list.size(), "Wrong size"); - assertEquals(node10, list.getLast(), "Wrong last"); - assertEquals(node02, list.getLast(), "Wrong last"); - assertEquals(node10, list.getLast(), "Wrong last"); - assertEquals(node12, list.getFirst(), "Wrong first"); - assertEquals(node00, list.getFirst(), "Wrong first"); - assertEquals(node12, list.getFirst(), "Wrong first"); + + // selected shard is random + DoubleLinkedListNode lastNode = list.getLast(); + assertTrue(node10 == lastNode || node02 == lastNode, "Wrong last"); + lastNode = list.getLast(); + assertTrue(node10 == lastNode || node02 == lastNode, "Wrong last"); + + // selected shard is random + DoubleLinkedListNode firstNode = list.getFirst(); + assertTrue(node12 == firstNode || node00 == firstNode, "Wrong first"); + firstNode = list.getFirst(); + assertTrue(node12 == firstNode || node00 == firstNode, "Wrong first"); } /** Verify that remove and removeAll work. */ @@ -194,30 +201,30 @@ class DoubleLinkedListUnitTest final DoubleLinkedListNode node1 = new DoubleLinkedListNode(); final DoubleLinkedListNode node2 = new DoubleLinkedListNode(); - list.addFirst( node1 ); - list.addFirst( node2 ); - assertEquals( 2, list.size(), "Wrong size" ); + list.addFirst(node1); + list.addFirst(node2); + assertEquals(2, list.size(), "Wrong size"); // DO WORK - list.remove( node1 ); + list.remove(node1); // VERIFY - assertEquals( 1, list.size(), "Wrong size" ); - assertEquals( node2, list.getLast(), "Wrong last" ); - assertEquals( node2, list.getFirst(), "Wrong first" ); + assertEquals(1, list.size(), "Wrong size"); + assertEquals(node2, list.getLast(), "Wrong last"); + assertEquals(node2, list.getFirst(), "Wrong first"); - list.addFirst( node1 ); - assertEquals( 2, list.size(), "Wrong size" ); - assertEquals( node1, list.getFirst(), "Wrong first" ); - assertEquals( node2, list.getLast(), "Wrong last" ); + list.addFirst(node1); + assertEquals(2, list.size(), "Wrong size"); + assertEquals(node1, list.getFirst(), "Wrong first"); + assertEquals(node2, list.getLast(), "Wrong last"); // DO WORK list.removeAll(); // VERIFY - assertEquals( 0, list.size(), "Wrong size" ); - assertNull( list.getLast(), "Wrong last" ); - assertNull( list.getFirst(), "Wrong first" ); + assertEquals(0, list.size(), "Wrong size"); + assertNull(list.getLast(), "Wrong last"); + assertNull(list.getFirst(), "Wrong first"); assertNull(node1.next, "node1.next should be null"); assertNull(node1.prev, "node1.prev should be null"); assertNull(node2.next, "node2.next should be null");
