Strategy: Stop Using Linked-Lists

While using java.util.LinkedHashMap every now and then, when I feel that the insertion order is relevant to subsequent entrySet iterations, I do not recall having used a LinkedList any time, recently. Of course, I understand its purpose and since Java 6, I apreciate the notion of a Deque type. But the LinkedList implementation of the List type hasn’t occurred to be useful to me very often.

Now, here’s an interesting summary about why linked lists can be very bad for your performance:
http://highscalability.com/blog/2013/5/22/strategy-stop-using-linked-lists.html

This summary is referring another, original article:
http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html#more-818

While the “academic” advantage of a linked list is obvious to everyone (big-O advantage of insertion, removal operations), “real life” disadvantages related to hardware, memory, heap, quickly turn against you when using linked lists. What holds true in the C universe is probably not so wrong in the Java universe as well…

2 thoughts on “Strategy: Stop Using Linked-Lists

  1. True and not true. The topic is interesting and if there is smoke, then there is fire. The only question is if this is just a candle burning or the refinement oil factory blows up. I believe this is the first case: candle light that can be good to feel romantic and have a friendly discussion with friends and a glass of vine about optimization and program performance (if you are a nerdy geek or a geeky nerd), but this is nothing to worry about.

    First of all: premature optimization is root of all evil. I can not recall how many times I wrote this sentence during the last years. Worry about the performance if you have a problem with it. Saying something like “never ever use linked lists” is simply … to say politely … mentally challenged. Never say never. Linked list is a data structure that you can use if the environment fits and is good for the purpose.

    In case of modern CPU structures this may not be the case. There is a fast cache and “slow” memory and a CPU that can pre-fecth and do some calculation in case it needs it and not caring the result and the dissipated energy in case the calculation turns out to be useless.

    If you are old enough, this may remind you something similar. Just replace cache to memory, and memory to disk and CPU to data batch processor. These are techniques that are well known and widely used in database engines. On disk we do not use linked lists. Or do we? Do file systems use linked lists? Yes, they do. Aren’t they optimized? Doh. They are! How come then? They use it for the purpose it fits. When it is cheaper, faster to use linked lists to chain blocks and when needing the next block wait for the disk to rotate than moving the block of data and rearranging the block for a single write to speed up a possible later read. Rearrangement can be done in batch when the disk i/o is low. The same may hold for cache and memory for the future. Linked lists are still there and by the dawn of SSD in disk technology linked list is revitalized no need to wait for rotation. Still cache misses are there.

    Also: binary trees versus B-trees. In memory we usually use the first, DB technology on disk uses the second. Perhaps we also have to think about it again.

    Last but not least: Java is radically differs from C especially in this area: memory handling. (As for this aspect there is no much difference between C and C++.) In Java there are no pointers. There are references to objects. The major difference is that memory referenced by pointer can not be freely moved by any run time system. Objects can. And Java memory management does that. This way, sometimes amazingly, Java is faster than C. (At other times not.)

    And note that since there are only object references in Java and an array of object is essentially an array of references that refer to objects, array of objects are not much better than linked lists of objects. Your benefit is reading the references stored in an array faster, but you may still have the cache misses for the objects themselves.

    Without actual measurement, examples and sample codes the above in the referenced articles are speculations only and by no means should drive to the conclusion never use linked lists.

    • Thanks for the great insight. Yes, indeed, never was a bad choice of wording – or maybe just trying to get some attention. Nonetheless, often when you think you should use a LinkedList, you might still be better off just using an array, because using a LinkedList might just be – as you put it – premature optimisation.

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