My First Encounter With Collection Performance
The first time I started wondering about collection performance was when I started working with over 100,000 elements collections. At that time, I heard some bad jokes such as I just understood why the Java logo is a cup of coffee because Java collections are so slow that when manipulating them, you have the time to go and grab some coffee before they do the job Just kidding!
At that time, I wanted to use an implementation ofjava.util.Listthat would have great performance on all the common methods provided by the interface [lets say get[index], add[Object], remove[Object], remove[index], contains[Object], iterator[], add other methods that you like], without wondering about memory usage [I mean, even this List would take 4 times the size of a LinkedList it wouldnt be a big deal].
In other words, some List that would not be instantiated a million times in my application, but a couple of times, and each instance will have great performances. For example, the model of a GUI Table, or some other GUI component, which data will evolve frequently, and which performances will sometimes be critical.
First of all, what do I mean by good performance? Usually, good performance is equivalent to an average complexity in O[1]. But this one is impossible to get all the time, so first, lets study current JDK List/Collection implementations and see what we have.
Current JDK List/Collection Implementations
Well, we already know basic information about collection methods and their complexity, such as the fact that aHashSethas an average O[1] complexity for its contains[o] method, or thatArrayListis also in O[1] for its method get[int index], etc.
But it will take some time to study the entire JDK Collection API to have an idea of the complexity of each implementation [sometimes, the complexity is not really explicit], so instead of that, lets conduct a basic benchmark to see what they are capable of:
private void execute[BenchRunnable run, int loop, String taskName] { System.out.print[taskName + " ... "]; // set default context collection.clear[]; collection.addAll[defaultCtx]; // warmup warmUp[]; isTimeout = false; // timeout timer Timer timer = new Timer[[int] timeout, new ActionListener[] { @Override public void actionPerformed[ActionEvent e] { isTimeout = true; // to raise a ConcurrentModificationException or a // NoSuchElementException to interrupt internal work in the List collection.clear[]; } }]; timer.setRepeats[false]; timer.start[]; long startTime = System.nanoTime[]; int i; for [i = 0; i < loop && !isTimeout; i++] { try { run.run[i]; } catch [Exception e] { // on purpose so ignore it } } timer.stop[]; long time = isTimeout ? timeout * 1000000 : System.nanoTime[] - startTime; System.out.println[[isTimeout ? "Timeout [>" + time + "ns] after " + i + " loop[s]" : time + "ns"]]; // restore default context // the collection instance might have been corrupted by the timeout, // create a new instance try { Constructor