ArrayList vs LinkedList

[nsigma]

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

hmm ... do they really? 

[sproingie]

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.

[Riven]

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.

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.

Games published by our own members! Check 'em out!

[princec]

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

Cas

[appel]

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

[princec]

That's like saying oranges are faster than apples.

Cas

[ra4king]

But don't appels always win?

[Cero]

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

[princec]

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

[ra4king]

Seems like no one got my joke

Games published by our own members! Check 'em out!

[Roquen]

Oh but we did. (edit: but maybe some people are assuming you can't spell)

[princec]

Or maybe it was just terrible

<tumbleweed> <tolling bell>

Cas

[Orangy Tang]

Gah!

</tolling bell>

</tumbleweed>

Phew. Better now.

[appel]

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

Well, a (gapless) Bag simply encapsulates array. I've run plenty of tests using ArrayList vs. Bag, and the performance difference is crazy, I won't go back to using ArrayList, that's just "code smell" in my mind.
But yes, for 99,99% of the games we're doing here then ArrayList won't drag your game down to 5 fps, unless you're doing something crazy like thousands of particles per second.

[princec]

An ArrayList should be able to cope with millions of particles per second, though. In fact the ArrayList won't even be your bottleneck; it'll be the random location of your Particles in RAM anyway.
What's the Bag interface do then?

Cas

[Roquen]

As an aside:  If you're talking about a very large number of particle-like things, then the CPU should be taken out of the picture (yuck, yuck).

[princec]

That would depend on how the particles actually interact with whatever else is going on. Where it might be fine for trivial particle systems it's not fine when particles have to do clever stuff like bounce off walls or fill corridors etc.

Cas

[Orangy Tang]

What's the Bag interface do then?

http://www.java-gaming.org/topics/the-bag-fast-object-collection/24203/view.html

[princec]

Oh, that old trick! Yeah, I use it* in the SpriteEngine in SPGL because it's one of the few places where the order is irrelevant.

I used to use it in game code too for things like entities until I came across a series of extraordinarily difficult to trace bugs. It turns out it is nearly always important to preserve the order of those sorts of things or odd stuff happens. Worth knowing about.

Cas

* well, similar code anyway

[Roquen]

WRT: particles.  Well doing collisions on the GPU is totally doable.  But, of course, the real question here is wouldn't one be better off with each being more interesting rather than attempt to pump out of ton of them.

But really my attempted point was if any of these collections are getting large then the high level might need some rethinking.

[DrewLols]

It turns out it is nearly always important to preserve the order of those sorts of things or odd stuff happens. Worth knowing about.

Yeah, I've found that order can be important, which is why I've decided to split collision checks to multiple lists.  The order of a list is not important, but the list that an object is allocated to is.  I gave each collision object a priority enum which determines which list it gets added to.  Objects like terrain that keep the player from falling out of the field have the highest priority meaning that they are considered last.  Objects that I add later like moving crates and floor spikes have a low priority meaning they get called first.  By this logic, objects with a high priority get the last say when considering the position of the collision objects.

My only regret is that I have to make 3 array lists per quadrant because there are 3 types of priority enums...  Oh well, maybe I'll look into that bag class!  Maybe it has less fluff!  

[DrewLols]

Looked into Bag.  Looks nice, but it isn't a generic class.  Weird...   

[StumpyStrust]

Most games only do about 50-150k particles which is fairly low. I think skyrim does even less, like 1-3k. In my particle system I use arrays for emitters and effects because it is important that their locations in the array do not change. But for particles, order really does not matter much unless you have some serious physics going on.

What is the big advantage of a Bag?

[princec]

Very fast removal but it can only be safely done during iteration and it will change the order of elements as items are removed.

Cas

[DrewLols]

I finally looked at the source of Bag intensively!  Of course it's significantly faster at removing elements than ArrayList!  When you remove an element, it doesn't shift each down.  It places the final element in the gap that's created from the removal process, and decrements the size.  Yeeah...  It makes the whole concept of a LinkedList seem stupid...    Yeah, I'm definitely going to use Bag in the future!

[princec]

Don't forget that a Bag is not a List. The fundamental feature of a List is that elements remain in the order in which they are added, and this is often critically important design.

Cas

[Best Username Ever]

When is order important? I can only think of a few situations where it's desirable and can't be worked around.
1. Specialized data structures (ArrayList would basically be a useless layer of abstraction)
2. Queues (Circular buffers should be used instead)
3. User interface related things presented to the user in list format (Then a list makes sense, but at worst they will only store tens of items)

[sproingie]

4. Everything else that's ordered.  Which I suspect is a few more use cases than you can count on one hand.  Hm, seems it's important when it's important.

Collections doesn't define a Bag interface, which seems an odd oversight, but it could only solidly have Iterable<T> and add(T); once you add "remove", you end up needing List or Set semantics in the bargain anyway.

[ra4king]

Nope, remove works fine for Iterable: http://www.java-gaming.org/topics/implementing-and-using-an-array-backed-bag/27172/view.html

[sproingie]

Remove on iterable is a completely different interface.  But yeah I suppose that's how you could do it for Bag too.