JavaAPI/Collections

Right now this page is just a discussion about when to use your the Collections classes and when to roll your own list implementations.

In my experience, all of java built in list classes are slow as hell because of the casting needed in every read. I used to have linked lists for my gun's scan log, when I replaced them with custom made linked lists my execution speed increased 10x. Bottom line is, class casting in (big) inner loops should be avoided at all costs. -- ABC

ABC, is it possible you could package a focused example with your deep loop list problem? And also provide your custom list classes and we could make it a competition to try solve the speed problem with different approaches? Ideally a solution using the standard Collections classes will result with a speed penalty you could live with. -- PEZ

By not using the standard Collections classes I'm actually decreasing the probability of a future JVM surprise, imo. I just made a very simple linked list, here is an example: You need to save a history of every enemy scan:

public class ScanInfo {
	long time;
	double x, y, vel, heading;
	double distance;

	public ScanInfo(AdvancedRobot bot, ScannedRobotEvent e) {
	...
	}
}

Since you will always be traversing this list sequencially, I made a LinkedList of ScanInfos?. The problem is that if you use the listIterator classes, your code inside the loop looks like this:

info = (ScanInfo)it.previous();

That cast (ScanInfo?) is the problem, especially when you are traversing a list with thousands of elements. My solution, add a pointer field (or two, if you want a double linked list) to that class:

ScanInfo previous, next;

and you loop looks like this:

 info = info.previous;

This change made my gun 10x faster. If you want I'll make an example bot with working code and you can try making it run close to the speed of my solution with the standard Collection classes...

-- ABC

Yes, ABC, please make that example bot.

Here is my example: http://robocode.aclsi.pt/abc.ListTester_slow_1.0.jar, http://robocode.aclsi.pt/abc.ListTester_fast_1.0.jar. Run each one 10 rounds against SittingDuck. In my comp the fast version took 17 secs to run and the slow one 34. -- ABC

I'm not sure how your gun works and how much "sequenciality" you need in traversing that list. But somehow I don't think it's the cast that makes the Collections solution slow. It's the iterator. Using an ArrayList instead of a LinkedList and this idiom to traverse the list:

	    for (int i = scanLog.size() - 1; i >= 0; i--) {
		ScanInfo sci = (ScanInfo)scanLog.get(i);
	    }

your list tester reports it takes 11 secs on my machine. The custom linked list runs in 13 secs. I've run the list testers 10 times each and it's pretty stable in these figures.

-- PEZ

You are right, ArrayList is faster. That is strange, I remember making an array version of my gun and it being slower than with the linked list. But even so, the way I use my scanLog collection makes much more sense with a linked list structure. From the scans resulting from that search I trace the future position by iterating forward (info.next) until the bullet meets the enemy, much more elegant than fiddling with array indexes. And I don't depend on Sun to make a better/worse linked list implementation (or even breaking it) in the future. -- ABC

Yeah, but often one can abstract away the indexing and use the metaphore of choice. In this case though, instead of rolling your own list you migh roll your own iterator instead:

class ScanIterator implements ListIterator {
    List list;
    int size;
    int currentIndex;

    public ScanIterator(List list, int startIndex) {
	this.list = list;
	if (list != null) {
	    this.size = list.size();
	}
	currentIndex = Math.min(size - 1, startIndex);
    }

    public boolean hasNext() {
	return currentIndex < size - 1;
    }

    public boolean hasPrevious() {
	return currentIndex > 0;
    }

    public Object next() {
	if (currentIndex < size - 1) {
	    return list.get(++currentIndex);
	}
	else {
	    throw new NoSuchElementException();
	}
    }

    public int nextIndex() {
	return currentIndex + 1;
    }

    public Object previous(){
	if (currentIndex > 0) {
	    return list.get(--currentIndex);
	}
	else {
	    throw new NoSuchElementException();
	}
    }

    public int previousIndex() {
	return currentIndex - 1;
    }

    public void remove() {
	throw new UnsupportedOperationException();
    }

    public void add(Object o) {
	throw new UnsupportedOperationException();
    }

    public void set(Object o) {
	throw new UnsupportedOperationException();
    }
}

Which you then traverse like so:

	    if (scanLog.size() > 0) {
		ScanIterator it = new ScanIterator(scanLog, scanLog.size() - 1);
		while (it.hasPrevious()) {
		    ScanInfo sci = (ScanInfo)it.previous();
		}
	    }

Using an ArrayList for the list this takes 14 secs according to your list tester. 1 sec more than using your custom list and 3 secs more than just iterating the list using the pure "for loop" idiom. This approach retains some of the advantages of using a Collections list while still allowing you to walk the list backwards or forwards at will. With only a slight speed penalty. I assume their are purer ways of implementing your own iterators. I have never done this sort of thing before, but I imagine making your own Collections compatible List would come closer to the ideal. The above is just to show that working with the Collections library needn't be too much slower than rolling your own custom lists.

-- PEZ

Duh! I just noticed that ArrayList already provides a listIterator() method!! I'll try that one and see what performance we get. -- PEZ

Well, using the default listIterator(), like so:

	    if (scanLog.size() > 0) {
		ListIterator it = scanLog.listIterator(scanLog.size() - 1);
		while (it.hasPrevious()) {
		    ScanInfo sci = (ScanInfo)it.previous();
		}
	    }

is a bit slower than my home brewed one. 16 secs. Using a for loop with the iterator, like you did in your example above results in 18 secs execution time. I don't understand why, but a while() is clearer anyway.

-- PEZ

Use Java 1.5 and then there is no need for those casts :) -- Pulsar

Not that the casts are the problem though. =) And, if they were, wouldn't the casts happen implicitly even using Java 1.5? -- PEZ

True and true, it was mostly a joke, hence the smiley ;-) -- Pulsar

So, in conclusion, java's LinkedList is much slower than should be expected even if you use it like a simple linked list (never by index, always iterating). The best (fastest) solution is simply replacing it with an ArrayList and you can use the same List interface. But you have to keep in mind that Iterators are slow and the general execution speed depends on the java version used, so you better access it by index anyway. I still like the "make it yourself, it's just a linked list!" solution better, though. ;) -- ABC

I'm not sure LinkedList is slower than should be expected. The contract of AbstractSequentialList? seems to demand that things are done in a special way that I think penalizes the kind of access you tried to use it for. And are Iterators really that slow? I still think rolling your own linked list still is a bit drastic. But if you know for sure you're not going to want to do anything else with the list so sure, "it's just a linked list" then. The Collections classes tend to be speedier with each Java version though, not the other way around. -- PEZ

About Iterators, when you used the index access it took 11s, with the iterator it took 16s, 45% slower. That's a very big difference. I would expect the LinkedList solution to be (almost) as fast as my own linked list implementation, it is 100% slower. How hard can it be to extend Object with some .next and .previous pointers? -- ABC

16 secs was with the built in iterator. It provides all sorts of protections and also allows you to delete elements as you traverse the list and such. I got 14 secs by using a less decorated iterator. Random access is faster yes, but that's to be expected I think. It's faster than your own linked list implementation too, remember? LinkedList is more than the name implies. -- PEZ

But my implementation is a linked list! I want a linked list not an array! ;) How can you not be sure LinkedList is slower than expected? All your faster implementations are array based. What if I want to add/remove big blocks in the middle of my list? I'm sure a (proper) linked list will always be faster in that case... -- ABC

I think you want the interface of a linked list. =) I'm not sure what I expect from LinkedList is what I'm saying. Obviously it's not the tool for your task, that's agreed. -- PEZ

Nope, I want the characteristics of a linked list, not the interface. If it is the tool for the task or not is debatable. For my simplified example it is not, but only in an execution speed perspective, and not by much. From the LinkedList description in the java API: "All of the operations perform as could be expected for a doubly-linked list". Now, my implementation is a doubly-linked list, shouldn't I expect a performance close to mine if I replace it with a LinkedList? -- ABC

They are most likely referring to the complexity ( O(n), O(1) etc ). -- Pulsar

Good question. =) What characteristics of a linked list is it that you want? I thought the primary reason to using a linked list was to be able to insert and delete elements anywhere in the list at will without the speed penalty you get when doing this with array-type lists. So far I've only seen you ask for a speedy and intuitive traversal. If you get that from an ArrayList, isn't that to your satisfaction? -- PEZ

I think linked lists are cool :). I don't like indexes when all I want is to sequentially traverse my list. I like to get the next element of my list without knowing the indexOf(currentElement). I like speedy and intuitive traversal. I think a linked list is the best representation for the abstract structure I see in my mind when I think of a scan log for PM targeting. Call me stubborn, but I want to use a linked list in my code. Elegant and slow solution: use LinkedList, elegant and fast solution: make your own linked list implementation, fastest (but not elegant, imo) solution: use an array based list and be prepared to pay the price if you reach the point where you realise a linked list was best afterall and an array solution gets slow as hell. -- ABC

But that can happen whichever path you choose. As long as you don't expect to start inserting and deleting in the beginning or middle of the list chances are you'll never find an array-based solution getting slower than a linked list one. And of course I call you stubborn. =) And if you use the List and Iterator interfaces all the time you can plug in and out different List implementations. And even if you end up rolling your own tailored linked list the change in implementation shouldn't be too hard anyway. Here's a few more experiments. First:

	    if (scanLog.size() > 0) {
		ListIterator it = scanLog.listIterator(scanLog.size() - 1);
		//ScanIterator it = new ScanIterator(scanLog, scanLog.size() - 1);
		for (int i = scanLog.size() - 1; i > 0; i--) {
		    ScanInfo sci = (ScanInfo)it.previous();
		}
	    }

This gives a performance of 15 secs for the standard iterator and 13 secs for my own one. But if you don't want to bother even that much with indexes:

		try {
		    while (true) {
			ScanInfo sci = (ScanInfo)it.previous();
		    }
		}
		catch (NoSuchElementException e) {};

gives 12 secs using the built-in listIterator() and 10 secs using my home cooked iterator. I would say this last one is both speedy and intuitive traversal.

-- PEZ

I now tried that last traversal with a LinkedList and it gives the same performance as with an ArrayList. In fact I know now what's so terribly wrong with your own first attempt using a LinkedList. It's that indexOf() in ListIterator it = scanLog.listIterator(scanLog.indexOf(((LinkedList)scanLog).getLast())). It forces a traversal of the entire list I think. Using ListIterator it = scanLog.listIterator(scanLog.size() - 1) instead avoids this. -- PEZ

That explains a lot! Thanks for restoring my faith in the List classes. But I still don't like the whole Iterator stuff, how do you store a reference to the current object without losing the Iterator context (next() and previous())? -- ABC

Btw, it should be ListIterator it = scanLog.listIterator(scanLog.size()), so that the next call to previous() returns the last element. It's just a bit too abstract for me, anything related to indexes (like listIterator(index)) makes no sense in a linked list context, imho. -- ABC

I agree. But since the lists are implemented as containers and not as decorations on existing objects I think there's only indexes available to initialize the iterator. I don't understand what you're asking there about storing references. Can you develop it a bit? -- PEZ

While I traversed the list I found 10 scans that match the criteria I was looking for, and I want to iterate the list forward from each of their positions. In my linked list I just store the scans in an array and use .next, how do you do the same with a LinkedList without storing the indexes? You .clone() the Iterator? -- ABC

Cool question. The API docs doesn't give any details on the actual iterator implementations (only the interfaces) which means we can't know from that documentation if clone() would work. You'll have to test it I guess. And I'm CuriousGeorge about if it works! -- PEZ

Here's the actual implementation, CuriousGeorge:

    private class ListItr implements ListIterator {
	private Entry lastReturned = header;
	private Entry next;
	private int nextIndex;
	private int expectedModCount = modCount;

	ListItr(int index) {
	    if (index < 0 || index > size)
		throw new IndexOutOfBoundsException("Index: "+index+
						    ", Size: "+size);
	    if (index < (size >> 1)) {
		next = header.next;
		for (nextIndex=0; nextIndex<index; nextIndex++)
		    next = next.next;
	    } else {
		next = header;
		for (nextIndex=size; nextIndex>index; nextIndex--)
		    next = next.previous;
	    }
	}

	public boolean hasNext() {
	    return nextIndex != size;
	}

	public Object next() {
	    checkForComodification();
	    if (nextIndex == size)
		throw new NoSuchElementException();

	    lastReturned = next;
	    next = next.next;
	    nextIndex++;
	    return lastReturned.element;
	}

	public boolean hasPrevious() {
	    return nextIndex != 0;
	}

	public Object previous() {
	    if (nextIndex == 0)
		throw new NoSuchElementException();

	    lastReturned = next = next.previous;
	    nextIndex--;
	    checkForComodification();
	    return lastReturned.element;
	}

	public int nextIndex() {
	    return nextIndex;
	}

	public int previousIndex() {
	    return nextIndex-1;
	}

	public void remove() {
            checkForComodification();
            try {
                LinkedList.this.remove(lastReturned);
            } catch (NoSuchElementException e) {
                throw new IllegalStateException();
            }
	    if (next==lastReturned)
                next = lastReturned.next;
            else
		nextIndex--;
	    lastReturned = header;
	    expectedModCount++;
	}

	public void set(Object o) {
	    if (lastReturned == header)
		throw new IllegalStateException();
	    checkForComodification();
	    lastReturned.element = o;
	}

	public void add(Object o) {
	    checkForComodification();
	    lastReturned = header;
	    addBefore(o, next);
	    nextIndex++;
	    expectedModCount++;
	}

	final void checkForComodification() {
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	}
    }

-- David Alves