kk_oop said:
Remember that the standard implementation is almost always good enough,
given modern GC and modern JITCs. If your code uses a LOT of empty
lists, though, you can have a problem.
One program I worked with had hundreds of thousands of empty lists that
got iterated through. A first step towards fixing the performance
problems was a fix for that. A later step dropped the number of calls
dramatically, which is typical. Fix the algorithm, not the detail code,
for real performance gain. That said, a detail fix had a lot of
benefits.
The immutable EMPTY_LIST, in Collections.java, has the code:
private static class EmptyList extends AbstractList
implements RandomAccess, Serializable
{
private static final long serialVersionUID = 8842843931221139166L;
public int size() {return 0;}
public boolean contains(Object obj) {return false;}
public Object get(int index) {
throw new IndexOutOfBoundsException("Index: "+index);
}
private Object readResolve() {
return EMPTY_LIST;
}
}
We see, therefore, that whenever iterator() is called, you get the
standard one in AbstractList. Thus, there are several needless function
calls. If you know that you are going to have a LOT of these, you might
do better with an implementation like:
private static class MyEmptyList extends AbstractList
implements RandomAccess, Serializable
{
private static final long serialVersionUID = 8842843931221139166L;
public int size() {return 0;}
public boolean contains(Object obj) {return false;}
public Object get(int index) {
throw new IndexOutOfBoundsException("Index: "+index);
}
private Object readResolve() {
return MY_EMPTY_LIST;
}
public Iterator iterator() {
return new Iterator() {
public boolean hasNext() {
return false;
}
public Object next() {
throw new NoSuchElementException();
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
This does create a new iterator for every call, though, so it is not
ideal if you try to iterate through a lot of empty collections. The
following caches the iterator:
private static class MyEmptyList extends AbstractList
implements RandomAccess, Serializable
{
private static final long serialVersionUID = 8842843931221139166L;
public int size() {return 0;}
public boolean contains(Object obj) {return false;}
public Object get(int index) {
throw new IndexOutOfBoundsException("Index: "+index);
}
private Object readResolve() {
return MY_EMPTY_LIST;
}
private static empty_iterator;
public Iterator iterator() {
if (empty_iterator==null) empty_iterator=new Iterator() {
public boolean hasNext() {
return false;
}
public Object next() {
throw new NoSuchElementException();
}
public void remove() {
throw new UnsupportedOperationException();
}
};
return empty_iterator;
}
}
Again, do not do this until your profiler indicates it is a good idea.
Scott
).