Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (575) Games in Android Showcase (154) games submitted by our members Games in WIP (622) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 ArrayList vs LinkedList  (Read 15564 times) 0 Members and 1 Guest are viewing this topic.
Wiki Duke

?

 « Posted 2012-08-03 01:17:00 »

ArrayList and LinkedList are both very similar. They're used in the exact same way, but have very different performance characteristics. Even if you're using the right one for the job, you might still be using the list in a bad way leading to bad performance.

A very important thing to consider when choosing which one to use is how they scale for large lists. How lists (and algorithms in general) scale with their size can be described using Big O notation.

For example, ArrayList.get(int index) method always returns in O(1) time. The time it takes to find an object is always the same. It does not get slower as the list grows, since it's just simple array access in this case.

LinkedList.get(int index) however is O(n). Finding the i'th object requires it to follow the linked list to the i'th. As the list gets longer, get(int index) ON AVERAGE gets slower. Finding the first object is obviously fast, O(1), but finding the last object is O(n) where n is the length of the list. On average, finding an object is O(n/2). However, the /2 is irrelevant in big O notation since it only describes how the list SCALES. LinkedList.get(int index) on average scales linearly with the list's length, so it's therefore O(n).

ArrayList:
- Adding objects is O(1).
- Getting objects is O(1).
- Removing objects is O(n). Double the size and the (average) access time doubles too. Note that remove(0) is the worse case scenario as a remove forces a copy of all following objects to fill the first spot that was left empty.
- contains(object) is O(n) since the whole list has to be traversed to check if the object is in the list.

- Adding objects is O(1)
- Random access (getting using indices) is O(n). Getting objects in order using an iterator is O(1).
- Removing objects is O(n) when using indices or references to remove objects. Removing objects with an iterator is O(1).
- contains(object) is O(n) since the whole list has to be traversed to check if the object is in the list.

Which should I use for my game objects?

Looking at the above makes it's easy to conclude that LinkedList is the most flexible one. Adding objects is O(1), iterating over objects in order is O(1) and removing objects as we iterate over them is O(1). ArrayList is very similar, but is O(n) for removing. Game objects will die and be removed as the game progresses, so LinkedList scales the best.

Even though LinkedList scales better, it does not necessarily have to be the fastest option for a certain use case. The problem with LinkedList is that it creates an Entry object which it wraps in each object added to store the next and previous entries. This allocation (and later garbage collection) makes it a lot slower to add and remove stuff than ArrayList in most use cases. Big O notation says nothing about the actual performance of these two. Adding objects is O(1) for both lists, but is still a lot slower for LinkedLists. Basically, for "small" lists ArrayList will always be faster, but for "large" lists LinkedList is faster. The exact point where you should start using LinkedList also depends on how you use the list, so it's impossible to give an exact number.

ArrayList is most almost always the best choice for a game object list. Even when you have lots of stuff to remove, ArrayList can be a good choice. A good solution might be to use TWO ArrayLists and pingpong your objects between them. By doing that you can avoid all shifting while still getting fast (and random) access to all objects.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31 `ArrayList currentList, nextList;//Lists created at load time//Example game loop:while(true){    update(); //Updates all objects    render(); //Draws all objects}private void update(){    for(int i = 0; i < currentList.size(); i++){        GameObject go = currentList.get(i);        go.update();        if(go.isAlive()){            nextList.add(go);        }    }        //Alive objects are now in nextList. Clear currentList.    currentList.clear();        //Swap current and next list    ArrayList temp = nextList;    nextList = currentList;    currentList = temp;}`
This wiki entry has had 0 revisions with contributions from 1 members. (more info)
gimbal

JGO Knight

Medals: 25

 « Reply #1 - Posted 2012-08-03 11:51:01 »

Wasn't memory fragmentation another good reason to avoid LinkedList?
matheus23

JGO Kernel

Medals: 121
Projects: 3

You think about my Avatar right now!

 « Reply #2 - Posted 2012-08-03 11:52:01 »

Wasn't memory fragmentation another good reason to avoid LinkedList?
This doesn't apply with a Mark 'n Sweep GC tough, right? Or does it?

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
 Games published by our own members! Check 'em out!
theagentd

« JGO Bitwise Duke »

Medals: 432
Projects: 2
Exp: 8 years

 « Reply #3 - Posted 2012-08-03 11:58:45 »

Wasn't memory fragmentation another good reason to avoid LinkedList?
I thought about that too. In my tests LinkedLists are slower to traverse. I believe this is because in an ArrayList it can predict all following references and load those from RAM, but in LinkedList only the next reference in the list is known.

Myomyomyo.
Roquen
 « Reply #4 - Posted 2012-08-03 12:08:32 »

Small allocations on a heap lead to fragmentation.  Linked lists will (statistically) walk random memory, arraylist will walk linear.
princec

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #5 - Posted 2012-08-03 12:35:30 »

I think I've said before that there is almost no actual utility whatsoever for a RAM-based linked list implementation. There is no software problem anyone will encounter that will not be better faster and more efficiently by ArrayList.

Cas

Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #6 - Posted 2012-08-03 12:39:52 »

The only usecase I can think of is an extremely long queue (millions of elements) where realtime behaviour is required (ruling out array based queues as they have to grow/shift/compact sooner or later).

It's very unlikely to have this requirement though.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Roquen
 « Reply #7 - Posted 2012-08-03 13:03:48 »

Free lists of pool allocated items comes to mind (edit: but that's in-place so linked lists vs. LinkedList).
sproingie

JGO Kernel

Medals: 202

 « Reply #8 - Posted 2012-08-03 15:46:33 »

Wasn't memory fragmentation another good reason to avoid LinkedList?
This doesn't apply with a Mark 'n Sweep GC tough, right? Or does it?

It does.  Mark and sweep is one of the slowest forms of GC, and the more pointers you have to chase, the more time it takes.  Java has to do M&S with the tenured generation, whereas it has fast copying collectors for the young generation.  The more fragmented your memory gets, the less it's able to take advantage of cache, and once your app starts paging to disk, the page thrashing can really kill your app (sometimes quite literally)

princec

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #9 - Posted 2012-08-03 15:50:36 »

That's one of the G1 GC's strengths apparently - it performs the mark/sweep operation concurrently, and in small chunks, compacting collected stuff into contiguous RAM, which should then in theory make it a bit more cache-friendly next time.

Cas

 Games published by our own members! Check 'em out!
 « Reply #10 - Posted 2012-08-03 17:54:13 »

I have to agree with the fact that we will probably never need something else than an ArrayList for game. I tried inserting integer into an arraylist, always in the middle of the list. And I didn't got any performance hit before 10000 elements... After that the performance degrade really fast but I don't think a lot of us are using more than 10000 elements.

<off topic>
Note : With Mark-sweep compact collector there is no fragmentation. I thought Java was using that one instead of Mark-sweep collector for the tenured generation.

@princec : The Concurrent collector is also supposed to do that, but when I tried it the performance were absolutely awful

The concurrent collector performs most of its work concurrently (i.e., while the application is still running) to keep garbage collection pauses short. It is designed for applications with medium- to large-sized data sets for which response time is more important than overall throughput, since the techniques used to minimize pauses can reduce application performance. The concurrent collector is enabled with the option -XX:+UseConcMarkSweepGC.
</off topic>
princec

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #11 - Posted 2012-08-03 23:50:10 »

Just for fun I did some raw microbenchmarks comparing the ways to manage a hypothetical particle or game entity system. Using the sweep-and-copy with ArrayList is approximately 4x faster than LinkedList on its own, and uses less memory. Using iterators slows things down by between 10% and 25%.

However... this was testing with 500,000 entities/particles, and I was getting times of under 1ms for ArrayList and only 4ms for LinkedList. A more realistic sort of scenario with the kinds of games we make round these parts, with maybe 1/100th the number of entities, would mean that the amount of time spent culling entities or particles in a frame would be probably unmeasurable.

Furthermore with just 5,000 entities, we were talking only 2ms using brute force on an ArrayList. And this is for the pathologically unlikely scenario that you're killing all 5,000 entities in a single frame.

I think this might go back to that fascinating talk given by Jon Blow on making computer games. Please watch it. It is massively significant to how good you will be at making games, or even just software.

Cas

gimbal

JGO Knight

Medals: 25

 « Reply #12 - Posted 2012-08-07 07:57:50 »

I think this might go back to that fascinating talk given by Jon Blow on making computer games. Please watch it. It is massively significant to how good you will be at making games, or even just software.

That is certainly going on the 'watch ASAP' list. Conversely if you have any more of those little treasures floating around in your bookmarks, don't hesitate to spam
princec

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #13 - Posted 2012-08-07 08:41:14 »

ONLY THIS. I ams as robots.

Cas

Roquen
 « Reply #14 - Posted 2012-08-07 10:12:17 »

This is worth a quick read IHMO: http://blogs.valvesoftware.com/abrash/valve-how-i-got-here-what-its-like-and-what-im-doing-2/
gene9

Senior Devvie

Medals: 10

 « Reply #15 - Posted 2012-09-18 23:13:57 »

Generally speaking:

If preserving element order is important and insert/remove before/after operations are common, linked list is much faster at those uses than arrays.
If you want a persistent data structure (in the sense of immutability, not persisting to storage which is another use of the same word), linked lists are ideal.
In most other cases, use arrays.

BTW, you can do O(1) removes on arrays if you can alter element order (swap element with last and remove last)

This is a very elementary, academic subject. I wouldn't think it is fully in line with this site.
Abuse

JGO Knight

Medals: 17

falling into the abyss of reality

 « Reply #16 - Posted 2012-09-19 00:24:28 »

I think this might go back to that fascinating talk given by Jon Blow on making computer games. Please watch it. It is massively significant to how good you will be at making games, or even just software.

Cas

I appreciate what he's talking about, and when you're hand-coding the data structures in question then it makes sense to keep it simple.
However, we have access to Java's wonderful Collections api; so using a HashXYZ is no more effort than using a less complex structure like an ArrayList.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
princec

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #17 - Posted 2012-09-19 13:21:03 »

It's not so much about effort as what's fastest in what circumstances. LinkedList is an academic curiosity. No-one in their right mind should be using it.

Cas

Junior Devvie

 « Reply #18 - Posted 2012-09-19 22:02:44 »

I tested the performance of several List implementations. I couldn't decide what to do with collection size vs add/remove frequency, but it was surprising. Frequent adds/removes on relatively small linked-lists-based Lists out performed the same frequency, but large lists were the opposite. I couldn't find a relationship between size and frequency and did not want to spend time testing and plotting all kinds of possibilities, so I decided it would be too hard to make a meaningful benchmark.

I would not make generalizations on linked lists vs arrays. I would just use Lists in the form List<Thing> someList = new ListType<Thing>(); and replace the implementation later if needed. In general, you will more likely than not see better performance from ArrayLists than LinkedLists for games on PCs, but that's not universally true for all hardware (although a real time system is not the usual platform for games) or all applications. I also think it's naive to use either LinkedList or ArrayLists as an automatic choice of data structure.
princec

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #19 - Posted 2012-09-19 22:43:46 »

Small aside: were you to implement a linked list in the traditional way - with forward and maybe back pointers actually inside the instances you were linking - you would alleviate some of the problems that LinkedList has, which revolve around the need to implement the List interface, and the creation of little bits of potentially long lived support garbage all over the place.

Cas

TheGDeveloper

Junior Devvie

Projects: 1

 « Reply #20 - Posted 2012-11-14 22:34:59 »

the add method on ArrayList is not O(1), if it needs memory reallocation is O(n).
In general you are using ArrayLists when you are not add and remove many times and LinkedList when you do not need random access onto the objects

TheGDeveloper

Junior Devvie

Projects: 1

 « Reply #21 - Posted 2012-11-14 22:39:37 »

Wasn't memory fragmentation another good reason to avoid LinkedList?
I thought about that too. In my tests LinkedLists are slower to traverse. I believe this is because in an ArrayList it can predict all following references and load those from RAM, but in LinkedList only the next reference in the list is known.
traverse is faster because there is the CPU cache. When you reference a memory location the architectures laods on the cache and some more memory that is near

divxdede
 « Reply #22 - Posted 2012-11-14 23:09:47 »

In fact

adding an item on an ArrayList can't be considered as O(1) cost since an array list may perform an array re-allocation if the current allocation becomes fullor unsufficient.
This method perform a full instanciation of a new array and a full copy that have a cost that depends of the size of the list.

So, this threads talk about the memory fragmentation of a LinkedList but not the wast space of an ArrayList and the re-allocation process that may be a real penalty in adding operations.

By example,
Create an ArrayList with the default constructor that mean an initial capacity of 10 and you will insert on your list 600 items.
@11th   insertion ==> array[10] copied on a new array[15]
@15th   insertion ==> array[15] copied on a new array[22]
@23th   insertion ==> array[22] copied on a new array[33]
@34th   insertion ==> array[33] copied on a new array[49]
@50th   insertion ==> array[49] copied on a new array[73]
@74th   insertion ==> array[73] copied on a new array[109]
@110th insertion ==> array[109] copied on a new array[163]
@164th insertion ==> array[163] copied on a new array[244]
@245th insertion ==> array[244] copied on a new array[366]
@367th insertion ==> array[366] copied on a new array[549]
@550th insertion ==> array[549] copied on a new array[823]
@600th insertion ==> you have an array of 823 that means a wast of 223 bullets and 11 arrays instanciations and copy.

Hopefully in often/some cases, we can estimate the final size of a list before filling it. When it's the case, we should consider to use the good one constructor in order to prevent theses reallocations. With a LinkedList you haven't this issue.
theagentd

« JGO Bitwise Duke »

Medals: 432
Projects: 2
Exp: 8 years

 « Reply #23 - Posted 2012-11-15 00:20:49 »

Create an ArrayList with the default constructor that mean an initial capacity of 10...
... because you can't possibly predict an approximate capacity and/or you can't stand a single 0.01ms spike to copy 100 objects from one array to another with a super-fast natively optimized Arrays.copyOf() called ONCE? Instead you rely on an linked list which is slower to add to, produces garbage when removed from and is slower to traverse? Just create a large enough ArrayList. It's gonna use a lot less memory than a LinkedList since that one creates a Node object for each entry, and
Quote
a normal object requires 8 bytes of "housekeeping" space
(http://www.javamex.com/tutorials/memory/object_memory_usage.shtml)
plus 3 references * 4 bytes each. That's 5 times as much data as an ArrayList stores per slot. Add cache inefficiency since the CPU can't predict which object we'll read, and it's seriously not worth it.

add(): O(1) as long as you have a large enough array, which you will eventually get and keep forever. Better than LinkedList's O(1) since it doesn't produce garbage
remove(): not needed, we'll never have to remove an object if we use the double ArrayList technique I've linked to over 9000 times by now.
get(index): O(1), much faster than LinkedList.
get in sequence: Faster due to cache coherency, doesn't need to create an iterator object every time you want to loop over in sequence.
memory usage: 1/5th as much per object.

Hopefully in often/some cases, we can estimate the final size of a list before filling it. When it's the case, we should consider to use the good one constructor in order to prevent theses reallocations. With a LinkedList you haven't this issue.
No, instead we have shitty performance all the time.

Myomyomyo.
princec

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #24 - Posted 2012-11-15 09:54:43 »