Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (497)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 2 3 [4] 5
  ignore  |  Print  
  ArrayList vs LinkedList  (Read 13580 times)
0 Members and 1 Guest are viewing this topic.
Offline nsigma
« Reply #90 - Posted 2012-08-23 16:31:06 »

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 reallyWink

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline sproingie

JGO Kernel


Medals: 202



« Reply #91 - Posted 2012-08-23 16:59:28 »

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.



Offline Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #92 - Posted 2012-08-23 17:27:38 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #93 - Posted 2012-08-23 18:54:01 »

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

Cas Smiley

Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #94 - Posted 2012-08-23 19:59:58 »

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

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline princec

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #95 - Posted 2012-08-23 22:13:55 »

That's like saying oranges are faster than apples.

Cas Smiley

Offline ra4king

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #96 - Posted 2012-08-23 22:16:45 »

But don't appels always win? Wink

Offline Cero
« Reply #97 - Posted 2012-08-23 22:21:25 »

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 Grin

Offline princec

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #98 - Posted 2012-08-24 11:45:05 »

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 Smiley

Offline ra4king

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #99 - Posted 2012-08-24 12:06:00 »

Seems like no one got my joke Emo

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #100 - Posted 2012-08-24 12:06:27 »

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

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #101 - Posted 2012-08-24 12:09:32 »

Or maybe it was just terrible Wink

<tumbleweed> <tolling bell>

Cas Smiley

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #102 - Posted 2012-08-24 12:17:05 »

Gah!

</tolling bell>

</tumbleweed>

Phew. Better now.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #103 - Posted 2012-08-24 12:35:21 »

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 Smiley
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.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline princec

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #104 - Posted 2012-08-24 12:52:32 »

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 Smiley

Offline Roquen
« Reply #105 - Posted 2012-08-24 12:58:26 »

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).
Offline princec

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #106 - Posted 2012-08-24 13:00:31 »

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 Smiley

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #107 - Posted 2012-08-24 13:10:57 »

What's the Bag interface do then?

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

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline princec

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #108 - Posted 2012-08-24 13:26:16 »

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 Smiley

* well, similar code anyway

Offline Roquen
« Reply #109 - Posted 2012-08-24 14:28:33 »

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.
Offline DrewLols

Senior Member


Medals: 3
Projects: 1


Noob going through metamorphosis...


« Reply #110 - Posted 2012-08-24 20:20:13 »

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!   Grin

Did you know that 90% of statistics are wrong?
Offline DrewLols

Senior Member


Medals: 3
Projects: 1


Noob going through metamorphosis...


« Reply #111 - Posted 2012-08-24 20:29:03 »

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

Did you know that 90% of statistics are wrong?
Offline StumpyStrust
« Reply #112 - Posted 2012-08-24 22:15:10 »

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?

Offline princec

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #113 - Posted 2012-08-24 22:34:26 »

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 Smiley

Offline DrewLols

Senior Member


Medals: 3
Projects: 1


Noob going through metamorphosis...


« Reply #114 - Posted 2012-08-25 01:17:59 »

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...   Undecided  Yeah, I'm definitely going to use Bag in the future!

Did you know that 90% of statistics are wrong?
Offline princec

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #115 - Posted 2012-08-25 09:10:01 »

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 Smiley

Offline Best Username Ever

Junior Member





« Reply #116 - Posted 2012-08-25 16:32:31 »

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)
Offline sproingie

JGO Kernel


Medals: 202



« Reply #117 - Posted 2012-08-25 20:54:53 »

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.
Offline ra4king

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #118 - Posted 2012-08-25 20:57:11 »

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

Offline sproingie

JGO Kernel


Medals: 202



« Reply #119 - Posted 2012-08-25 21:04:57 »

Remove on iterable is a completely different interface.  But yeah I suppose that's how you could do it for Bag too.
Pages: 1 2 3 [4] 5
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (21 views)
2014-09-19 03:14:18

Dwinin (35 views)
2014-09-12 09:08:26

Norakomi (62 views)
2014-09-10 13:57:51

TehJavaDev (87 views)
2014-09-10 06:39:09

Tekkerue (42 views)
2014-09-09 02:24:56

mitcheeb (65 views)
2014-09-08 06:06:29

BurntPizza (47 views)
2014-09-07 01:13:42

Longarmx (35 views)
2014-09-07 01:12:14

Longarmx (40 views)
2014-09-07 01:11:22

Longarmx (36 views)
2014-09-07 01:10:19
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!