RFR: jsr166 jdk9 integration wave 12
Martin Buchholz
martinrb at google.com
Fri Nov 18 03:17:33 UTC 2016
Here's an update that adds some explanations, addresses some of Paul's
comments, and improves handling of capacities near 2**31.
Coincidentally, today I got access to a machine with enough memory to run
testHugeCapacity without dying, so that test gets fixed. Previous
iterations tried to get rid of the spare slot, and there may be some other
lingering vestige of that, as with this test.
Index: src/main/java/util/ArrayDeque.java
===================================================================
RCS file:
/export/home/jsr166/jsr166/jsr166/src/main/java/util/ArrayDeque.java,v
retrieving revision 1.113
diff -u -r1.113 ArrayDeque.java
--- src/main/java/util/ArrayDeque.java 13 Nov 2016 02:10:09 -0000 1.113
+++ src/main/java/util/ArrayDeque.java 18 Nov 2016 03:09:50 -0000
@@ -68,13 +68,15 @@
*
* Because in a circular array, elements are in general stored in
* two disjoint such slices, we help the VM by writing unusual
- * nested loops for all traversals over the elements.
+ * nested loops for all traversals over the elements. Having only
+ * one hot inner loop body instead of two or three eases human
+ * maintenance and encourages VM loop inlining into the caller.
*/
/**
* The array in which the elements of the deque are stored.
- * We guarantee that all array cells not holding deque elements
- * are always null.
+ * All array cells not holding deque elements are always null.
+ * The array always has at least one null slot (at tail).
*/
transient Object[] elements;
@@ -88,7 +90,8 @@
/**
* The index at which the next element would be added to the tail
- * of the deque (via addLast(E), add(E), or push(E)).
+ * of the deque (via addLast(E), add(E), or push(E));
+ * elements[tail] is always null.
*/
transient int tail;
@@ -187,7 +190,10 @@
* @param numElements lower bound on initial capacity of the deque
*/
public ArrayDeque(int numElements) {
- elements = new Object[Math.max(1, numElements + 1)];
+ elements =
+ new Object[(numElements < 1) ? 1 :
+ (numElements == Integer.MAX_VALUE) ?
Integer.MAX_VALUE :
+ numElements + 1];
}
/**
@@ -201,7 +207,7 @@
* @throws NullPointerException if the specified collection is null
*/
public ArrayDeque(Collection<? extends E> c) {
- elements = new Object[c.size() + 1];
+ this(c.size());
addAll(c);
}
@@ -224,19 +230,21 @@
}
/**
- * Adds i and j, mod modulus.
- * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
+ * Circularly adds the given distance to index i, mod modulus.
+ * Precondition: 0 <= i < modulus, 0 <= distance <= modulus.
+ * @return index 0 <= i < modulus
*/
- static final int add(int i, int j, int modulus) {
- if ((i += j) - modulus >= 0) i -= modulus;
+ static final int add(int i, int distance, int modulus) {
+ if ((i += distance) - modulus >= 0) distance -= modulus;
return i;
}
/**
* Subtracts j from i, mod modulus.
- * Index i must be logically ahead of j.
- * Returns the "circular distance" from j to i.
- * Precondition and postcondition: 0 <= i < modulus, 0 <= j < modulus.
+ * Index i must be logically ahead of index j.
+ * Precondition: 0 <= i < modulus, 0 <= j < modulus.
+ * @return the "circular distance" from j to i; corner case i == j
+ * is diambiguated to "empty", returning 0.
*/
static final int sub(int i, int j, int modulus) {
if ((i -= j) < 0) i += modulus;
@@ -862,9 +870,9 @@
if ((t = fence) < 0) t = getFence();
if (t == (i = cursor))
return false;
- final Object[] es;
- action.accept(nonNullElementAt(es = elements, i));
+ final Object[] es = elements;
cursor = inc(i, es.length);
+ action.accept(nonNullElementAt(es, i));
return true;
}
@@ -1232,6 +1240,8 @@
/** debugging */
void checkInvariants() {
+ // Use head and tail fields with empty slot at tail strategy.
+ // head == tail disambiguates to "empty".
try {
int capacity = elements.length;
// assert head >= 0 && head < capacity;
Index: src/main/java/util/concurrent/ArrayBlockingQueue.java
===================================================================
RCS file:
/export/home/jsr166/jsr166/jsr166/src/main/java/util/concurrent/ArrayBlockingQueue.java,v
retrieving revision 1.137
diff -u -r1.137 ArrayBlockingQueue.java
--- src/main/java/util/concurrent/ArrayBlockingQueue.java 13 Nov 2016
02:10:09 -0000 1.137
+++ src/main/java/util/concurrent/ArrayBlockingQueue.java 18 Nov 2016
03:09:50 -0000
@@ -58,6 +58,11 @@
public class ArrayBlockingQueue<E> extends AbstractQueue<E>
implements BlockingQueue<E>, java.io.Serializable {
+ /*
+ * Much of the implementation mechanics, especially the unusual
+ * nested loops, are shared and co-maintained with ArrayDeque.
+ */
+
/**
* Serialization ID. This class relies on default serialization
* even for the items array, which is default-serialized, even if
@@ -1555,6 +1560,10 @@
// meta-assertions
// assert lock.isHeldByCurrentThread();
try {
+ // Unlike ArrayDeque, we have a count field but no spare slot.
+ // We prefer ArrayDeque's strategy, but our field layout is
+ // baked into the serial form, and so is annoying to change.
+ // putIndex == takeIndex must be disambiguated by checking
count.
int capacity = items.length;
// assert capacity > 0;
// assert takeIndex >= 0 && takeIndex < capacity;
Index: src/test/tck/ArrayDeque8Test.java
===================================================================
RCS file:
/export/home/jsr166/jsr166/jsr166/src/test/tck/ArrayDeque8Test.java,v
retrieving revision 1.1
diff -u -r1.1 ArrayDeque8Test.java
--- src/test/tck/ArrayDeque8Test.java 25 Oct 2016 01:32:55 -0000 1.1
+++ src/test/tck/ArrayDeque8Test.java 18 Nov 2016 03:09:51 -0000
@@ -51,43 +51,42 @@
/**
* Handle capacities near Integer.MAX_VALUE.
- * ant -Dvmoptions='-Xms28g -Xmx28g'
-Djsr166.testImplementationDetails=true -Djsr166.expensiveTests=true
-Djsr166.tckTestClass=ArrayDequeTest -Djsr166.methodFilter=testHuge tck
+ * ant -Dvmoptions='-Xms28g -Xmx28g' -Djsr166.expensiveTests=true
-Djsr166.tckTestClass=ArrayDeque8Test
-Djsr166.methodFilter=testHugeCapacity tck
*/
- public void testHuge() {
+ public void testHugeCapacity() {
if (! (testImplementationDetails
&& expensiveTests
&& Runtime.getRuntime().maxMemory() > 24L * (1 << 30)))
return;
- ArrayDeque q;
- Integer e = 42;
- final int maxSize = Integer.MAX_VALUE - 8;
+ final Integer e = 42;
+ final int maxArraySize = Integer.MAX_VALUE - 8;
assertThrows(OutOfMemoryError.class,
- () -> new ArrayDeque<>(Integer.MAX_VALUE));
+ () -> new ArrayDeque(Integer.MAX_VALUE));
{
- q = new ArrayDeque<>(maxSize);
+ ArrayDeque q = new ArrayDeque(maxArraySize - 1);
assertEquals(0, q.size());
assertTrue(q.isEmpty());
q = null;
}
{
- q = new ArrayDeque();
- assertTrue(q.addAll(Collections.nCopies(maxSize - 2, e)));
+ ArrayDeque q = new ArrayDeque();
+ assertTrue(q.addAll(Collections.nCopies(maxArraySize - 3, e)));
assertEquals(e, q.peekFirst());
assertEquals(e, q.peekLast());
- assertEquals(maxSize - 2, q.size());
+ assertEquals(maxArraySize - 3, q.size());
q.addFirst((Integer) 0);
q.addLast((Integer) 1);
assertEquals((Integer) 0, q.peekFirst());
assertEquals((Integer) 1, q.peekLast());
- assertEquals(maxSize, q.size());
+ assertEquals(maxArraySize - 1, q.size());
ArrayDeque qq = q;
ArrayDeque smallish = new ArrayDeque(
- Collections.nCopies(Integer.MAX_VALUE - maxSize + 1, e));
+ Collections.nCopies(Integer.MAX_VALUE - q.size() + 1, e));
assertThrows(
IllegalStateException.class,
() -> qq.addAll(qq),
More information about the core-libs-dev
mailing list