The conclusion on this comparison is that most of the data accessed during list iteration is located into L2 for LinkedList but into 元 for ArrayList. Mechanically, LLC hits are very important for ArrayList.For L2 cache accesses we have a clear difference: ArrayList has significant more L2 misses compared to LinkedList.Instructions is little higher for LinkedList.Clearly LinkedList spent much more cycles than ArrayList. Number of cycles is the number of CPU cycle spent on executing our code.:overseer.jar .ListIteration linked 0įirst run is on the ArrayList implementation, second with LinkedList. Let’s run our program with no buffer allocation on Linux with 2 Xeon X5680: java -cp. if 0, no buffer is allocated.īench method performs a search of a constant string which is not contained into the list, so we fully traverse the list.įinally, main method, perform initialization of the list, warmups the bench method and measure 1000 runs of this method. We may also allocate a buffer based on our second parameter of the program. Each string is newly created just before add it to the list. This method fills a list implementation with 50K strings. The program take 2 parameters: the first one to choose between ArrayList implementation or LinkedList one, the second one to take a buffer size used in initializeList method.
#Java array vs arraylist reddit code
You can find the code of this class here. To measure, I am using a class called HWCounters based on overseer library to get Hardware Performance Counters. List benchList = "array".equals(args) ? arrayList : linkedList Public static void main(String args) throws Exception Public static void initializeList(List list, int bufferSize) Private static List linkedList = new LinkedList() Private static List arrayList = new ArrayList() Here my code for measuring list iteration for LinkedList & ArrayList: And also because the memory access pattern for a list is a good example of CPU cache interaction.
I am focusing my study on list iteration because, beside adding an element, this is the most common task for a list. No need to present those data structures, everybody knows what they are using for and how they are implemented. I will not time using System.nanoTime(), but rather using HPCs like cache hits/misses.
I will not perform a micro-benchmark, well not directly. I have recently read this blog post and this is a good summary of discussions & debates about this subject.īut this time I would like to try a different approach to compare those 2 well known data structures: using Hardware Performance Counters. I must confess the title of this post is a little bit catchy.
0 kommentar(er)
