ArrayList is faster than LinkedList for add() operation

I was always wondering if it is a good idea to use LinkedList if the number of elements in the list is unknown. So I decided to test it. Program is pretty short here:

https://github.com/artgo/TestLists/blob/master/src/TestLists.java

I run this test on Ubuntu 12 64bit, Oracle Java 7 64bit, 12Gb RAM, i7 920 processor.

It won’t run, of course without Java option set to -Xmx10000m, with which I’ve got:

ArrayList : 17_781_152_915
LinkedList: 85_340_498_650

It was slow and definitely it is not your server configuration, isn’t it?

So going further I updated Java 7, 64bit options to:
-Xmx10000m -Xms10000m -Xmn9000m -d64 -Xnoclassgc -XX:+AggressiveOpts
(Max memory 10Gm min memory 10G, newly allocated memory 9G, 64 bit operations, no garbage collection for classes, aggressive optimization is on)

And got:

ArrayList : 1_442_938_558
LinkedList: 2_105_144_104

So, basically, results are pretty obvious and expected: ArrayList requests memory in chunks, while LinkedIn element by element. Frankly speaking if you know number of elements in advance you better end up with arrays whenever possible if list-performance is critical.

When would you use LinkedList then? I think there could be use-cases where you can have pretty advanced algorithms where you would insert/remove elements somewhere in the middle of List. Queues might work pretty well. But those are pretty rare, aren’t they?

Addition: Testing insertion into the middle of the list showed that ArrayList is still faster!

I updated these lines:


linkedList.add(i>>1, ints[i]);

arrayList.add(i>>1, ints[i]);

And got the following results:

ArrayList : 76_381_256_439
LinkedList: 1075_967_955_689

Advertisements

Author: Artem's Blog

Working on software and more...

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s