from GapList.java:get // A note about the inlining capabilities of the Java HotSpot Performance Engine // (http://java.sun.com/developer/technicalArticles/Networking/H...) // The JVM seems not able to inline the methods called within // this method, irrespective whether they are "private final" or not. // Also -XX:+AggressiveOpts seems not to help. // We therefore do inlining manually.

GapList.get inlines everything, including the rangechecks. ArrayList has two calls to functions.

I'm wondering why GapList is slower than LinkedList on random add. The LinkedList is constant time, the GapList has to copy data around.

It might be due to caching, but even so it's going to depend on how big the data is. When the data's bigger than cache and the GapList is copying large amounts of data for every random insert, the O(1) linked-list insert is going to beat it.

Or maybe he's inserting to an indexed location, and counting the time required for the LinkedList to traverse to that location.

Agreed. I can imagine a situation where GapList might perform better if you were alternating requests to the beginning and ending of the list and GapList happened to store them close enough in memory that they were both on the same cache line. But by their names, none of the benchmarks seem likely to test that case.