ArrayList vs LinkedList

Newbie & Debugging Questions
#81

Because the point IS code quality, and because I haven’t run on speed problems by now ?
If you really have to optimize speed, you should do your own test and check where the bottlenecks are. Because the data structure for your updatable list is probably not the cause: nobody gain 20 FPS by switching his LinkedList with two ArrayList.
But sure, it probably help if you want to run your game on a lower end PC.

As a matter of fact I did my own benchmark on this matter. Most of the time, the gain between using an ArrayList and a LinkedList is negligible. Even with a simple iteration (296 ArrayList / 315 LinkedList), which I just tested right now.
And by negligible I mean negligible on a modern PC, don’t get me wrong.

What I haven’t benchmarked yet is the potential speed gain of using a LinkedList to remove objects during the iteration.
I think the gain is so negligible I should’nt bother with it at all. Athough that’s just a theory, as I said I should write a benchmark to be REALLY sure about it.

#82

Another tangent! Code quality doesn’t mean diddly squat. Shipping games is what’s important. The qualities I admire most in code is that it works and I can move on to the next thing to get the game out the door.

Not everyone’s using a modern PC btw. There’s a lot of people monkeying around in Android and let me tell it to you in no uncertain terms, you do not want to use LinkedLists. Or HashSets. Or even, really, iterators, I suspect.

Cas :slight_smile:

#83

[quote=“Klems,post:81,topic:39437”]
Just to reiterate, not every place Java is running is a powerful desktop computer. Also raw throughput is not always the only goal. One reason I developed various techniques in games was because I was doing realtime television graphics and we couldn’t allow a single frame drop. This of course means absolutely minimising garbage and LinkedLists make rather a lot of it. I still use these techniques today because I want rock solid framerates in my games. The number of people I see posting in Java game related threads about stuttering and juddering animation…

Cas :slight_smile:

#84

[quote=“princec,post:82,topic:39437”]
I agree with you. I try to write the simplest code possible without sacrificing speed.
But writing a new List implementation for an Updatable List require time, and I’m probably not going to get it perfectly at the first try. You may be able to do it on the fly, but that’s not my case. That’s extra work I could put on something with a higher priority.

I write simple code. Simple code is easy. Why should I want to make it more complex ? Dumb code = good code.
As long as dumb doesn’t mean slow.

#85

Well well well… Did I mention well? This thread seems to have taken on a life of its own. Yeah, so I’ll be using a plain ol’ ArrayList unless I find that the cpu is being murderd. Haven’t really seen cpu usage go above 17%. I can always just assume I’ll be using SOME sort of list and will be able to easily change it in the future.


List<Zippittydooda> zippittydoodas = new ArrayList<Zippittydooda>();
for(Zippitydooda day : zippittydoodas)
{
    day.lolwut();
}

Yeah… That’ll work out just fine!

#86

I just want to stop in and say that this thread is freaking AWESOME.

And for the rest of the people new to the thread that don’t want to read all the awesomeness, the answer to the original question is ArrayList.

#87

It works… but if using ArrayList for whatever reason, take the consequential step and don’t use enhanced loops with its implicit iterator crap.

#88

Actually lately I try to use Libgdx’ Array Class, they claim its like ArrayList but with less garbage.

#89

Iterator garbage is miniscule to be honest, not something you should worry about on the desktop. It does come with a 10% performance penalty though.

Cas :slight_smile:

#90

Oh noez, a SINGLE garbage item. Better crap up the entire program with clunky inflexible syntax and off-by-one errors to save a few bytes!

And on Android at least, they give the opposite advice: http://developer.android.com/guide/practices/performance.html (search down for “enhanced for loop”)

#91

hmm … do they really? :wink:

#92

Ah, it’s the advice they give for everything but ArrayList, and then they skip over that entirely and use raw Arrays instead. Oh well that’s Android for you; for a real JIT, I still put the burden of proof on the claimant.

#93

It also reveals that array.length is not stored in a local variable before entering the for-loop. You’d say that checking whether the array localvar is assigned in the loop would be a trivial check, after which the length field can be cached. Seems like the JIT has a long way to go.

#94

The JIT is basically JamVM, and JamVM is very, very, very simple as JITs go.

Cas :slight_smile:

#95

I use the Bag, it’s just silly faster than ArrayList or LinkedList. Maintaining order doesn’t matter for a lot of games.

#96

That’s like saying oranges are faster than apples.

Cas :slight_smile:

#97

But don’t appels always win? :wink:

#98

well tbh I use ArrayLists and most of the time I dont need to an order

if I’m ever really desperate for a little performance gain I might use something else ;D

#99

There’s only one thing faster and that’s arrays but as you almost always need them to expand and you almost always need to know how many entries are in them, you just can’t beat ArrayList. Period.

Cas :slight_smile:

#100

Seems like no one got my joke :emo: