CODEWITHSUNDEEP
javaperformancecollections
James Raitsev
James Raitsev

Reputation: 96391

Adding to a large Java collection, performance bottleneck

I am trying to add a million objects into a list. The time it takes to do it, is longer than i have patience to wait for. It also seems to take progressively longer to carry on with each step.

    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 the List, Set with very similar results. It starts up fast and chokes after some number.

What collection should i be using to store a large number of like elements? Am i missing something simple here?

Upvotes: 7

Views: 492

Answers (2)

Javier
Javier

Reputation: 678

  • ArrayList has already been suggested (in a linked list, each item/node implies an additional object).
  • Also (previously suggested as well), if you use an array-based collection, try to construct/resize into an adequate length.
  • Also, if memory is an issue, you might want to use the Flyweight pattern with the string elements String#intern(), so redundant instances can be collected.

Upvotes: 1

user166390
user166390

Reputation:

This issue is not with collections in general, and not with the LinkedList as shown (which has O(1) adding characteristics).

The likely suspect is thus thrashing/swap of memory. Make sure the JVM has enough memory, and the system has more ..

Switching from LinkedList to ArrayList (or ArrayDeque) will keep O(1) amortized performance, but may have slightly less overhead per-item. (The overhead, and if such a reduction would even matter, depends upon the size of the objects added and the fill ratios of the backing stores.)

Upvotes: 11

Related Questions