Adding to a large Java collection, performance bottleneck

Question

I am trying to add a million objects to the list. The time it takes is longer than I have the patience to wait. It seems that with each step a longer transition is also required.

int size = 1000000; Deque<DatastoreElement> content = new LinkedList<DatastoreElement>(); for (int i = 0; i < size; i++) { String k = Utils.getRandomStringOfLength(20); String v = Utils.getRandomStringOfLength(300); // goes faster with smaller number int metaHash = random.nextInt(10) + 1; KVPair kvp = new KVPair(k, v); DatastoreElement dse = new DatastoreElement(metaHash, kvp); content.addLast(dse); // confirmed problem is here if (i % 10000 == 0) { System.out.println(i); } } 

I tried adding content to a List , Set with very similar results. It starts quickly and suffocates after a certain amount.

What collection should I use to store a large number of similar items? Did I miss something simple here?

Answer 1

This issue is not related to collections, not to LinkedList , as shown (which has O(1) adding features).

The likely suspect thus deceives / swaps the memory. Make sure the JVM has enough memory and that the system has more.

Switching from LinkedList to ArrayList (or ArrayDeque ) will support O(1) performance amortization, but may have slightly less overhead. (The overhead, and if such a reduction will even matter, depends on the size of the added objects and the fill factors of the backup storage.)

Answer 2

• ArrayList has already been proposed (in a linked list, each element / node implies an additional object).
• Also (previously suggested), if you are using an array-based collection, try building / resizing to a sufficient length.
• Also, if memory is a problem, you can use the Flyweight template with String#intern() string elements, so you can collect redundant instances.