4 ms·
I find it odd that "get" is faster on a GapList than an ArrayList. Surely "get" on an ArrayList should be unbeatable.
by Leszek 14y ago
I find it odd that "get" is faster on a GapList than an ArrayList. Surely "get" on an ArrayList should be unbeatable.
- colomon 14y agoAgreed. 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.
- Tuna-Fish 14y agofrom GapList.java:get // A note about the inlining capabilities of the Java HotSpot Performance Engine // (http://java.sun.com/developer/technicalArticles/Networking/HotSpot/inlining.html 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.
- _casperc 14y agoOut of curiosity, how do you go about finding out if your code is inlined or not?
- DennisP 14y agoI'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.