Bug ID: JDK-6359979 (coll) Speed up collection iteration

Type: Enhancement
Component: core-libs
Sub-Component: java.util:collections
Affected Version: 6

Priority: P3
Status: Closed
Resolution: Fixed
OS: generic
CPU: generic

Submitted: 2005-12-07
Updated: 2016-05-30
Resolved: 2011-05-18

JDK 7
7 b15Fixed

Academics like to compare the performance of Java against other
language frameworks.  Due to a lack of creativity, they often pick
collection iteration as a particularly interesting number.  E.g. here
is one article where ArrayList iteration makes a particulary poor showing.

http://www.cs.cornell.edu/andru/papers/jmatch2.pdf

By specializing the Vector and ArrayList iterators, we can achieve up to
a factor of two performance improvement with -client; somewhat less with -server.
The Vector iterator only needs to synchronize in next(), not in hasNext().
The ArrayList iterator suffers due to the polymorphic virtual call to get() in next()
that hotspot is known to have troubles with. 

This performance improvement is quite important.

EVALUATION Yes.

07-12-2005

SUGGESTED FIX --- /u/martin/ws/mustang/src/share/classes/java/util/AbstractList.java 2005-12-04 14:54:45.962374000 -0800 +++ /u/martin/ws/Iter/src/share/classes/java/util/AbstractList.java 2005-12-05 15:12:34.281484000 -0800 @@ -342,22 +342,25 @@ } public E next() { - checkForComodification(); try { - E next = get(cursor); - lastRet = cursor++; + int i = cursor; + E next = get(i); + lastRet = i; + cursor = i + 1; return next; - } catch (IndexOutOfBoundsException e) { - checkForComodification(); + } catch (IndexOutOfBoundsException ex) { throw new NoSuchElementException(); + } finally { + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); } } public void remove() { if (lastRet == -1) throw new IllegalStateException(); - checkForComodification(); - + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); try { AbstractList.this.remove(lastRet); if (lastRet < cursor) @@ -368,11 +371,6 @@ throw new ConcurrentModificationException(); } } - - final void checkForComodification() { - if (modCount != expectedModCount) - throw new ConcurrentModificationException(); - } } private class ListItr extends Itr implements ListIterator<E> { @@ -384,19 +382,6 @@ return cursor != 0; } - public E previous() { - checkForComodification(); - try { - int i = cursor - 1; - E previous = get(i); - lastRet = cursor = i; - return previous; - } catch (IndexOutOfBoundsException e) { - checkForComodification(); - throw new NoSuchElementException(); - } - } - public int nextIndex() { return cursor; } @@ -405,11 +390,26 @@ return cursor-1; } + public E previous() { + try { + int i = cursor - 1; + E prev = get(i); + lastRet = i; + cursor = i; + return prev; + } catch (IndexOutOfBoundsException ex) { + throw new NoSuchElementException(); + } finally { + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + } + } + public void set(E e) { if (lastRet == -1) throw new IllegalStateException(); - checkForComodification(); - + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); try { AbstractList.this.set(lastRet, e); expectedModCount = modCount; @@ -419,10 +419,12 @@ } public void add(E e) { - checkForComodification(); - + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); try { - AbstractList.this.add(cursor++, e); + int i = cursor; + AbstractList.this.add(i, e); + cursor = i + 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { --- /u/martin/ws/mustang/src/share/classes/java/util/ArrayList.java 2005-12-04 14:54:46.971299000 -0800 +++ /u/martin/ws/Iter/src/share/classes/java/util/ArrayList.java 2005-12-05 15:13:01.941141000 -0800 @@ -570,7 +570,7 @@ for (int i=0; i<size; i++) s.writeObject(elementData[i]); - if (modCount != expectedModCount) { + if (expectedModCount != modCount) { throw new ConcurrentModificationException(); } @@ -593,4 +593,148 @@ for (int i=0; i<size; i++) a[i] = s.readObject(); } + + /** + * Returns a list-iterator of the elements in this list (in proper + * sequence), starting at the specified position in the list. + * Obeys the general contract of {@link List#listIterator(int)}. + * + * The list-iterator is fail-fast: if the list is structurally + * modified at any time after the Iterator is created, in any way except + * through the list-iterator's own <tt>remove</tt> or <tt>add</tt> + * methods, the list-iterator will throw a + * <tt>ConcurrentModificationException</tt>. Thus, in the face of + * concurrent modification, the iterator fails quickly and cleanly, rather + * than risking arbitrary, non-deterministic behavior at an undetermined + * time in the future. + * + * @param index index of the first element to be returned from the + * list-iterator (by a call to {@link ListIterator#next}) + * @return a list-iterator of the elements in this list (in proper + * sequence), starting at the specified position in the list + * @throws IndexOutOfBoundsException {@inheritDoc} + */ + public ListIterator<E> listIterator(int index) { + if (index < 0 || index > size) + throw new IndexOutOfBoundsException("Index: "+index); + return new ArrayListIterator(index); + } + + /** + * {@inheritDoc} + */ + public ListIterator<E> listIterator() { + return new ArrayListIterator(0); + } + + /** + * Returns an iterator over the elements in this list in proper sequence. + * + * @return an iterator over the elements in this list in proper sequence + */ + public Iterator<E> iterator() { + return new ArrayListIterator(0); + } + + /** + * A streamlined version of AbstractList.ListItr + */ + final class ArrayListIterator implements ListIterator<E> { + int cursor; // index of next element to return + int lastRet; // index of last element returned; -1 if no such + int expectedModCount; // to check for ConcurrentModificationException + + ArrayListIterator(int index) { + cursor = index; + lastRet = -1; + expectedModCount = modCount; + } + + public boolean hasNext() { + return cursor != size; + } + + public boolean hasPrevious() { + return cursor != 0; + } + + public int nextIndex() { + return cursor; + } + + public int previousIndex() { + return cursor - 1; + } + + public E next() { + try { + int i = cursor; + E next = get(i); + lastRet = i; + cursor = i + 1; + return next; + } catch (IndexOutOfBoundsException ex) { + throw new NoSuchElementException(); + } finally { + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + } + } + + public E previous() { + try { + int i = cursor - 1; + E prev = get(i); + lastRet = i; + cursor = i; + return prev; + } catch (IndexOutOfBoundsException ex) { + throw new NoSuchElementException(); + } finally { + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + } + } + + public void remove() { + if (lastRet < 0) + throw new IllegalStateException(); + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + try { + ArrayList.this.remove(lastRet); + if (lastRet < cursor) + cursor--; + lastRet = -1; + expectedModCount = modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + + public void set(E e) { + if (lastRet < 0) + throw new IllegalStateException(); + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + try { + ArrayList.this.set(lastRet, e); + expectedModCount = modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + + public void add(E e) { + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + try { + ArrayList.this.add(cursor++, e); + lastRet = -1; + expectedModCount = modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + } } --- /u/martin/ws/mustang/src/share/classes/java/util/Vector.java 2005-12-04 14:55:02.899644000 -0800 +++ /u/martin/ws/Iter/src/share/classes/java/util/Vector.java 2005-12-05 15:13:16.995085000 -0800 @@ -1025,4 +1025,152 @@ { s.defaultWriteObject(); } + + /** + * Returns a list-iterator of the elements in this list (in proper + * sequence), starting at the specified position in the list. + * Obeys the general contract of {@link List#listIterator(int)}. + * + * The list-iterator is fail-fast: if the list is structurally + * modified at any time after the Iterator is created, in any way except + * through the list-iterator's own {@code remove} or {@code add} + * methods, the list-iterator will throw a + * {@code ConcurrentModificationException}. Thus, in the face of + * concurrent modification, the iterator fails quickly and cleanly, rather + * than risking arbitrary, non-deterministic behavior at an undetermined + * time in the future. + * + * @param index index of the first element to be returned from the + * list-iterator (by a call to {@link ListIterator#next}) + * @return a list-iterator of the elements in this list (in proper + * sequence), starting at the specified position in the list + * @throws IndexOutOfBoundsException {@inheritDoc} + */ + public synchronized ListIterator<E> listIterator(int index) { + if (index < 0 || index > elementCount) + throw new IndexOutOfBoundsException("Index: "+index); + return new VectorIterator(index); + } + + /** + * {@inheritDoc} + */ + public synchronized ListIterator<E> listIterator() { + return new VectorIterator(0); + } + + /** + * Returns an iterator over the elements in this list in proper sequence. + * + * @return an iterator over the elements in this list in proper sequence + */ + public synchronized Iterator<E> iterator() { + return new VectorIterator(0); + } + + /** + * A streamlined version of AbstractList.ListItr. + */ + final class VectorIterator implements ListIterator<E> { + int cursor; // index of next element to return + int lastRet; // index of last element returned; -1 if no such + int expectedModCount; // to check for ConcurrentModificationException + + VectorIterator(int index) { + cursor = index; + expectedModCount = modCount; + lastRet = -1; + } + + public boolean hasNext() { + // Racy but within spec, since modifications are checked + // within or after synchronization in next/previous + return cursor != elementCount; + } + + public boolean hasPrevious() { + return cursor != 0; + } + + public int nextIndex() { + return cursor; + } + + public int previousIndex() { + return cursor - 1; + } + + public E next() { + try { + int i = cursor; + E next = get(i); + lastRet = i; + cursor = i + 1; + return next; + } catch (IndexOutOfBoundsException ex) { + throw new NoSuchElementException(); + } finally { + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + } + } + + public E previous() { + try { + int i = cursor - 1; + E prev = get(i); + lastRet = i; + cursor = i; + return prev; + } catch (IndexOutOfBoundsException ex) { + throw new NoSuchElementException(); + } finally { + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + } + } + + public void remove() { + if (lastRet == -1) + throw new IllegalStateException(); + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + try { + Vector.this.remove(lastRet); + if (lastRet < cursor) + cursor--; + lastRet = -1; + expectedModCount = modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + + public void set(E e) { + if (lastRet == -1) + throw new IllegalStateException(); + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + try { + Vector.this.set(lastRet, e); + expectedModCount = modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + + public void add(E e) { + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + try { + int i = cursor; + Vector.this.add(i, e); + cursor = i + 1; + lastRet = -1; + expectedModCount = modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + } }

07-12-2005

Relates :	JDK-8158160 - Change in behaviour of ArrayList iterator between JDK 6 and JDK 7
Relates :	JDK-5103956 - (coll) Suggested improvement to speed up ArrayList get and set calls