Java-Gaming.org    
Featured games (78)
games approved by the League of Dukes
Games in Showcase (429)
Games in Android Showcase (89)
games submitted by our members
Games in WIP (467)
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
  ignore  |  Print  
  retainAll() vs. costum code thingy  (Read 2569 times)
0 Members and 1 Guest are viewing this topic.
Offline Regenuluz
« Posted 2012-11-06 18:59:46 »

Right, so at some point I found this piece of code, in here, to maintain an active list of elements (I currently use this code):

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
for(Entity e : this.entities) {
   if(e.isActive()) {
      e.update();
     
      if(e.isActive()) {
         this.stillActive.add(e);
      }
   }
}
   
ArrayList<Entity> tmp = this.entities;
this.entities = this.stillActive;
this.stillActive = tmp;
this.stillActive.clear();


The stuff that happens in the for loop is pretty straight forward, however I'm not sure I get the last bit, with swapping pointers and what not(At least, that's what I assume it does, as to switch the elements from stillActive over into entities).

Today, however, I ran into the retainAll() function, that's defined in the Set interface, which does exactly the same.

So instead of the above code, I could write:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
for(Entity e : this.entities) {
   if(e.isActive()) {
      e.update();
     
      if(e.isActive()) {
         this.stillActive.add(e);
      }
   }
}
     
this.entities.retainAll(this.stillActive);
this.stillActive.clear();

which imo is a lot more readable and understandable. My question is, which method is better?

Cheers! Smiley
Offline Regenuluz
« Reply #1 - Posted 2012-11-06 19:17:44 »

Actually, it just hit me that retainAll must be a lot slower. Since it compares all elements in A to all elements in B. And B can contain elements that's not in A to begin with.

However, I'd still like someone to explain how the whole pointer swapping actually works in the first code. Because I'm not quite sure of that. Tongue (Though I know what pointers are and what they do, I've meddled with them in C and C++)

Here's how I guess it works:
 - First the pointer for entities is copied over into tmp
 - Next the pointer for entities is overwritten with the pointer for stillActive
 - Then the pointer for stillActive is overwritten with the one from tmp (Or the original pointer to entities)
 - Then stillActive is cleared (Along with tmp, I suppose)

.... And writing this out, I think I just understood how exactly it works.. Assuming it works as I just wrote.

Any confirmations on that? Smiley
Offline Danny02
« Reply #2 - Posted 2012-11-06 21:31:13 »

It would make things easier when you just drop the global stillActive Collection.
-create a new Collection
-put all active entitys in this new collection
-set the entity collection reference to the new collection
-finish

Some always try to reuse objects, but I think this premature optimization is just evil Smiley
reusing objects is just so error prone, especially if there is a lot of state which needs to get reset.

The garbage collector on Android is not that fast, because of that object reuse can be a valid optimization on this platform.
But remember we are talking about one single object here, so I would argue that this optimization is even on Android useless.

ps: In Java Pointers are called References
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline RobinB

JGO Knight


Medals: 37
Projects: 1
Exp: 3 years


Spacegame in progress


« Reply #3 - Posted 2012-11-06 21:31:48 »

just use an for(int i... loop an delete stuff on the fly?
I dont know what stuff you are doing, but its alot faster then your function.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
Entity e;
for(int i = this.entities.size() - 1; i >= 0; i-- ) {
   e = this.entities.get(i);
   if(e.isActive()) {
      e.update();
     
      if(!e.isActive()) {
          this.entities.removeat(i);
      }
   }
}
Offline princec

JGO Kernel


Medals: 285
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #4 - Posted 2012-11-06 21:56:07 »

Great if you can iterate backwards through your entities, and don't have too many of them.
The OP has the optimal solution right there, for all platforms and architectures.

Cas Smiley

Offline Regenuluz
« Reply #5 - Posted 2012-11-06 22:44:06 »

Awesome! Smiley And my understanding of how it works is right too, right? Tongue
Offline RobinB

JGO Knight


Medals: 37
Projects: 1
Exp: 3 years


Spacegame in progress


« Reply #6 - Posted 2012-11-06 22:56:21 »

Great if you can iterate backwards through your entities, and don't have too many of them.
The OP has the optimal solution right there, for all platforms and architectures.

Cas Smiley

Could you explain please?
I thought using an iterator was really slow + filling an list with each active element is extra slow.
Why would that solution be optimal?
Offline princec

JGO Kernel


Medals: 285
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #7 - Posted 2012-11-06 23:04:20 »

Ok here goes...

Firstly the absolute fastest thing to do is not use an iterator, this is true: use an ArrayList and scan through with a for loop, it's about 10% faster even on the server VM on the desktop. So why not? Smiley

Secondly, the way CPUs and memory buses work means that memory that is accessed sequentially takes advantage of the CPU pre-cacheing data that it thinks it will need next. By scanning linearly through memory, as you will be doing like this, you are using memory incredibly efficiently, and you're only gonna look at it once. Likewise writes.

So what you're doing is:
- scan through your list of things sequentially. As absolutely efficient as can possibly be on any architecture.
- perform whatever operation you normally do on the thing
- check to see if it's dead. If it's not dead, copy it sequentially into a second list. As super efficient as it is possible to be, again.
- When you're done, clear the original list, and then swap the references to the lists around, so next time, you're running against that list you built up. Rinse, repeat. The swap is virtually instantaneous, consisting of swapping 4 bytes with another 4 bytes.

This algorithm a) makes the absolute best use of cache as possible on any architecture b) is as fast at removing every single element in the list in one go as it is removing only one element c) does everything in one pass and d) retains the order of the things in the list (often important). Its only disadvantage is using 2x the memory for the list. Which for a list containing 1 million elements will be a pathetic extra 4mb.

Cas Smiley

Offline RobinB

JGO Knight


Medals: 37
Projects: 1
Exp: 3 years


Spacegame in progress


« Reply #8 - Posted 2012-11-06 23:23:11 »

So at first you say the function
1  
for(int i = this.entities.size() - 1; i >= 0; i-- ) {
is faster and efficienter.
So, the iterater loop could be replaced by this loop for maximum performance?

If i understood it well, the Arraylist uses an array to store its data.
I understand removing can use loads of resources, because the array needs to be rebuild on every delete.
But with adding values the array, the array needs to be resised on every addition or will this be cashed to?
Offline princec

JGO Kernel


Medals: 285
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #9 - Posted 2012-11-07 00:03:57 »

Don't count backwards, do it like this:
1  
2  
for (int i = 0; i < entites.size(); i ++) {
}

You need to check entities.size() every iteration in case a new entity is added by one of the entities already in the list. Eg. a player fires a bullet. And going backwards is likely to be wrong for just that sort of thing too. Using an Iterator furthermore will actually crash with a ConcurrentModificationException when you try and spawn the bullet. Bad! Slow! Avoid!

Removal in ArrayLists can get very slow for large arraylists, especially if there are quite a few near the start of the list. Conversely, increasing the size of an ArrayList happens very infrequently and is only about the same cost as a single removal might be. After just a few iterations of your game loop your ArrayLists are likely to be the biggest they will ever need to be, and will remain that size. Or just size them properly ahead of time in the constructor.

Cas Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline RobinB

JGO Knight


Medals: 37
Projects: 1
Exp: 3 years


Spacegame in progress


« Reply #10 - Posted 2012-11-07 00:14:02 »

Thanks, very handy to know.
I didnt really think about the inner structure, but its really clear now.
Offline Regenuluz
« Reply #11 - Posted 2012-11-07 07:01:20 »

I'm *glad* I asked this question, it cleared up a lot of things for me too and it's always good to know how and why stuff works as it does!

Thanks a bunch for the clear answers, Cas! Smiley (And of course thanks to all you other guys that bothered answering in here! Smiley )

Offline StumpyStrust
« Reply #12 - Posted 2012-11-07 07:26:20 »

Sweet I am doing it this way and was wondering the same kinda of thing.

Actually...I was doing it almost work for work the way princec described... persecutioncomplex

Edit:
I don't know how much a method call is but couldn't you have update return whether or not the object/entity is active instead of calling a method? That way it could be

1  
2  
3  
4  
5  
for(Entity e : this.entities) {
   if(e.update())
         this.stillActive.add(e);
   }
}


then clear the old list and set the old list to point at the new one and clear the temp one.


Offline princec

JGO Kernel


Medals: 285
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #13 - Posted 2012-11-07 10:45:44 »

You could do that yes, though it sort of pollutes the purpose of your update() method, and you'll still need isAlive() or isDead() so that entities can check that references they may hold be alive still during their update.

Cas Smiley

Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #14 - Posted 2012-11-08 03:42:37 »

Here's my code, I handle an array myself... this as optimal as it gets I think

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
Entity[] entities;
int size;

public void update() {
  int alive = 0;
  for ( int i = 0; i < size; i++ ) {
    Entity e = entities[i];
    e.update();
    if ( e.isActive() ) {
      entities[ alive++ ] = e;
    }
  }
  // if you want to clear the references..
 while ( alive < size ) {
      entities[ alive++ ] = null;
  }
}

Offline princec

JGO Kernel


Medals: 285
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #15 - Posted 2012-11-08 10:02:03 »

That's pretty nifty. I suspect most people including myself would get away with doing something like that if mutation of the entities array wasn't a problem during iteration (I suspect it isn't but I've always played it safe).

Cas Smiley

Offline Regenuluz
« Reply #16 - Posted 2012-11-08 10:08:56 »

Only problem as I see it, is that you need to know exactly how many entities you'll have at max, at any given time. Or else you'll need to add code for changing the length of the array. Smiley But that code is a lot easier to comprehend than the other code is. Smiley

And I think I might just implement something like that in my particle emitter, as it has a max number of particles defined. ^^
Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #17 - Posted 2012-11-08 12:35:31 »

That's exactly where I pulled this code from, from my ParticleEffect class =P

Offline princec

JGO Kernel


Medals: 285
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #18 - Posted 2012-11-08 13:11:34 »

Well it wouldn't hurt to replace the array with an ArrayList but use the same technique.

Cas Smiley

Offline nsigma
« Reply #19 - Posted 2012-11-08 14:04:16 »

Well it wouldn't hurt to replace the array with an ArrayList but use the same technique.

Probably not (given extra method calls will probably get inlined) but it's also easy enough to expand the array on demand in the way ArrayList does in only a couple of lines!

@ClickerMonkey - nice example.  Was initially trying to understand the size field, then realized I think you're missing setting the size to the number of live objects prior to nulling the dead ones.  Won't this cause a NPE on the next run otherwise?

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Damocles
« Reply #20 - Posted 2012-11-08 14:22:21 »

I think for performance reasons, just using a normal Array fits better

add  -> in the ArrayList Class
 
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
public boolean add(E e) {
   ensureCapacity(size + 1);  // Increments modCount!!
  elementData[size++] = e;
   return true;
    }
   
public void ensureCapacity(int minCapacity) {
   modCount++;
   int oldCapacity = elementData.length;
   if (minCapacity > oldCapacity) {
       Object oldData[] = elementData;
       int newCapacity = (oldCapacity * 3)/2 + 1;
           if (newCapacity < minCapacity)
      newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
           elementData = Arrays.copyOf(elementData, newCapacity);
   }
 }  
 



 that one might be quicker
 
1  
  entities[ alive++ ] = e;

Offline Danny02
« Reply #21 - Posted 2012-11-08 14:28:52 »

premature optimization guys^^

I would bet that the update method of the entities is much heavier than the loop + the deleting. Besides, how many entities will u have? one, two thousand?
Offline nsigma
« Reply #22 - Posted 2012-11-08 14:31:34 »

I think for performance reasons, just using a normal Array fits better

add  -> in the ArrayList Class

You're looking at the wrong method - try set(..).  Still has some extra overhead though, as it returns the old value.

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Damocles
« Reply #23 - Posted 2012-11-08 14:32:12 »

Well, any "repeated in a large loop every frame" processing is
a prime candidate for optimization.

Especially when it comes to things like particles or other graphical gimmics.


Offline Damocles
« Reply #24 - Posted 2012-11-08 14:34:34 »

"add" would take over increasing the index counter.
Thats why I assumed it would have been chosen.

Offline princec

JGO Kernel


Medals: 285
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #25 - Posted 2012-11-08 14:34:38 »

premature optimization guys^^

I would bet that the update method of the entities is much heavier than the loop + the deleting. Besides, how many entities will u have? one, two thousand?
Not premature really, this is just a trivial way of doing things that is no more complicated than any other way but just happens to be really easy to understand and use and is the fastest possible way to do it. And let's not forget when you're on a 700MHz ARM chip with a 16 bit bus running a crappy Dalvik VM that every cycle is important.

<edit>Should probably be noted that if you are dealing with particles in this way you might well have a few thousand of them as well.

Cas Smiley

Offline nsigma
« Reply #26 - Posted 2012-11-08 14:37:17 »

"add" would take over increasing the index counter.

It isn't the index counter!

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Damocles
« Reply #27 - Posted 2012-11-08 14:38:35 »

ok size counter.
...whatever is used to determine the next entry

Offline Danny02
« Reply #28 - Posted 2012-11-08 14:50:38 »

this is just a trivial way of doing things that is no more complicated than any other way
Cas Smiley

I agree with you, when you handling particles this quite a different story.
What I think a big problem with premature optimization is, is that so much time gets wasted thinking about better ways of doing a simple thing.
And this thread is still going on, even a good enough solution was found^^
Offline nsigma
« Reply #29 - Posted 2012-11-08 14:57:07 »

ok size counter.
...whatever is used to determine the next entry

You're still not getting it!  Tongue

This moves live objects earlier in the list over dead ones - it doesn't append at the end of the list.  Obviously, read array for list in the original code.

You'd then clean up at the end by calling (ideally) removeRange() - which for some reason requires subclassing ArrayList  Huh

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Pages: [1] 2
  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.

xsi3rr4x (81 views)
2014-04-15 18:08:23

BurntPizza (73 views)
2014-04-15 03:46:01

UprightPath (84 views)
2014-04-14 17:39:50

UprightPath (67 views)
2014-04-14 17:35:47

Porlus (84 views)
2014-04-14 15:48:38

tom_mai78101 (107 views)
2014-04-10 04:04:31

BurntPizza (167 views)
2014-04-08 23:06:04

tom_mai78101 (263 views)
2014-04-05 13:34:39

trollwarrior1 (214 views)
2014-04-04 12:06:45

CJLetsGame (223 views)
2014-04-01 02:16:10
List of Learning Resources
by SHC
2014-04-18 03:17:39

List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30
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!