Changing AbstractList's iterator to track elements remaining rather than elements already returned.
On DRLVM, this results in a modest 10% runtime improvement in iteration. When I used -Xbootclasspath to run the current and new code on hotspot, the improvement was more pronounced. Runtimes are below; the benchmark results are below.
http://code.google.com/p/caliper/source/browse/trunk/test/com/google/caliper/examples/ListIterationBenchmarkSuite.java?spec=svn17&r=17
length vm ns logarithmic runtime
0 RI 20 |||||||||||
0 current 16 ||||||||||
0 new 14 ||||||||||
10 RI 63 ||||||||||||||||
10 current 82 |||||||||||||||||
10 new 45 ||||||||||||||
100 RI 393 |||||||||||||||||||||||
100 current 672 |||||||||||||||||||||||||
100 new 243 |||||||||||||||||||||
1000 RI 1191 |||||||||||||||||||||||||||
1000 current 2153 ||||||||||||||||||||||||||||||
1000 new 1294 ||||||||||||||||||||||||||||
git-svn-id: https://svn.apache.org/repos/asf/harmony/enhanced/classlib/trunk@889145 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/modules/luni/src/main/java/java/util/AbstractList.java b/modules/luni/src/main/java/java/util/AbstractList.java
index a032106..94fe49d 100644
--- a/modules/luni/src/main/java/java/util/AbstractList.java
+++ b/modules/luni/src/main/java/java/util/AbstractList.java
@@ -36,53 +36,48 @@
protected transient int modCount;
private class SimpleListIterator implements Iterator<E> {
- int pos = -1;
-
- int expectedModCount;
-
+ int numLeft = size();
+ int expectedModCount = modCount;
int lastPosition = -1;
- SimpleListIterator() {
- super();
- expectedModCount = modCount;
- }
-
public boolean hasNext() {
- return pos + 1 < size();
+ return numLeft > 0;
}
public E next() {
- if (expectedModCount == modCount) {
- try {
- E result = get(pos + 1);
- lastPosition = ++pos;
- return result;
- } catch (IndexOutOfBoundsException e) {
- throw new NoSuchElementException();
- }
- }
- throw new ConcurrentModificationException();
- }
-
- public void remove() {
- if (this.lastPosition == -1) {
- throw new IllegalStateException();
- }
-
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
try {
+ int index = size() - numLeft;
+ E result = get(index);
+ lastPosition = index;
+ numLeft--;
+ return result;
+ } catch (IndexOutOfBoundsException e) {
+ throw new NoSuchElementException();
+ }
+ }
+
+ public void remove() {
+ if (lastPosition == -1) {
+ throw new IllegalStateException();
+ }
+ if (expectedModCount != modCount) {
+ throw new ConcurrentModificationException();
+ }
+
+ try {
+ if (lastPosition == size() - numLeft) {
+ numLeft--; // we're removing after a call to previous()
+ }
AbstractList.this.remove(lastPosition);
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
expectedModCount = modCount;
- if (pos == lastPosition) {
- pos--;
- }
lastPosition = -1;
}
}
@@ -90,67 +85,64 @@
private final class FullListIterator extends SimpleListIterator implements
ListIterator<E> {
FullListIterator(int start) {
- super();
- if (0 <= start && start <= size()) {
- pos = start - 1;
- } else {
+ if (start < 0 || start > numLeft) {
throw new IndexOutOfBoundsException();
}
+ numLeft -= start;
}
public void add(E object) {
- if (expectedModCount == modCount) {
- try {
- AbstractList.this.add(pos + 1, object);
- } catch (IndexOutOfBoundsException e) {
- throw new NoSuchElementException();
- }
- pos++;
- lastPosition = -1;
- if (modCount != expectedModCount) {
- expectedModCount = modCount;
- }
- } else {
+ if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
+
+ try {
+ AbstractList.this.add(size() - numLeft, object);
+ expectedModCount = modCount;
+ lastPosition = -1;
+ } catch (IndexOutOfBoundsException e) {
+ throw new NoSuchElementException();
+ }
}
public boolean hasPrevious() {
- return pos >= 0;
+ return numLeft < size();
}
public int nextIndex() {
- return pos + 1;
+ return size() - numLeft;
}
public E previous() {
- if (expectedModCount == modCount) {
- try {
- E result = get(pos);
- lastPosition = pos;
- pos--;
- return result;
- } catch (IndexOutOfBoundsException e) {
- throw new NoSuchElementException();
- }
+ if (expectedModCount != modCount) {
+ throw new ConcurrentModificationException();
}
- throw new ConcurrentModificationException();
+
+ try {
+ int index = size() - numLeft - 1;
+ E result = get(index);
+ numLeft++;
+ lastPosition = index;
+ return result;
+ } catch (IndexOutOfBoundsException e) {
+ throw new NoSuchElementException();
+ }
}
public int previousIndex() {
- return pos;
+ return size() - numLeft - 1;
}
public void set(E object) {
- if (expectedModCount == modCount) {
- try {
- AbstractList.this.set(lastPosition, object);
- } catch (IndexOutOfBoundsException e) {
- throw new IllegalStateException();
- }
- } else {
+ if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
+
+ try {
+ AbstractList.this.set(lastPosition, object);
+ } catch (IndexOutOfBoundsException e) {
+ throw new IllegalStateException();
+ }
}
}