Today we will look at whether its worth developer time to pre-size ArrayList objects in Java application code. We will take a similar approach to the one taken in a prior post on how long it takes to handle an exception in Java.
Java has two convenient generic Listimplementations, LinkedListand ArrayList. As the name implies, ArrayList is an array backed implementation of a generic list which meansthatindexed based access to the list is quick,iterative read back is quick, and at any given point in time the objecthas areference to a backing array of a fixed size. LinkedList in Java are actually implemented using a doubly linked list data structure and are convenient because adding one additional element to them is a constant time operation [exceptfor exceptional circumstances like the JVM running out of heap space, but that has nothing to do with the list implementation.]
ArrayLists dont support guaranteed constant time element insertion because of the following situation:
Insert uh oh from Kid Pix here
Attempting to insert a pointer into an array like this in C would cause a segfault [or at least that is what you hope for as opposed to itsilently failing and then crashingat some later date in time.] This is a post about Java though so we have objects, object references, and clever code in the library ArrayList implementation. Prior to eachadd operationthe ArrayList will ensure that there is sufficient capacity in its backing array for one more element. If there is not sufficient capacity a new array is allocated, the contents of the original backing array are replicated into the new array, and then the insert continues. Alternatively, an application can specify the required backing array size when the ArrayList object is instantiated. Pre-sizing the ArrayList avoids unnecessarily object allocations and time spent copying array contents from one array to another on each sizing expansion.
As the post title and summary hints at, today we have some sample test code and numbers showing whether its actually worth spending time worrying about pre-sizing array lists. As usual measurements are done with a somewhat contrived testing harness, YMMV, and all commentary is made from the perspective of building reliable, maintainable enterprise applications, not HPC applications, etc.
[Spoiler alert:The optimization isnot worth it for run of the mill business applications.]
The test method is to prefill an array with 100000 random strings and then iterate over that array first filling an ArrayList without size initialization, then with size initialization, and then a LinkedList just for comparison.The code that ran the test is located here on GitHub
The numbers are only valid for relative comparison because they include time spent reading data out of the source array. The salient number here is the time difference between pre-sizing and not pre-sizing which came in at 279032 ns. This sounds like a lot, its notits slightly less than .00028 seconds. In other words I would have to execute this piece of code ~3500 times in order to have wasted 1 second resizing the ArrayList. Let usassume that were returning 100000 items at a time from a web service for some reason and are actually populating 5 ArrayList per request [1 for every tier in a classic 3-tier design plus 2 more for fun]. 5 ArrayLists mean that we have wasted 1 second for every 700 requests, or ~1.4 ms per request.
At this point I should point out that I am not against optimization. I dont think applications should be written without regard for hardware resources. Nor do I believe that performance does not matter in business applications. What is important though is a rational approach to optimization that balances cost against benefit. Put another way, if a developer writes his or her code with ArrayList pre-sizing to start with then by all means keep it in there, it is faster. If the code is not originally written that way, however,spending even a moment to refactor it forArrayList pre-sizing should be at the very bottom of the bucket when it comes to optimization.
Thats all for today. In short, use pre-sized ArrayListsif it is convenient and/or it happens to be a very performance sensitive application. Otherwise,in terms of performance it is probably more important to make sure that the applications data layer interactions [SQL queries??] are well written than worrying about pre-sized lists.