Java-Gaming.org    
Featured games (78)
games approved by the League of Dukes
Games in Showcase (426)
Games in Android Showcase (89)
games submitted by our members
Games in WIP (466)
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  
  ReadWriteCollection for entities  (Read 4224 times)
0 Members and 1 Guest are viewing this topic.
Offline Riven
Showcase Moderator

JGO Overlord


Medals: 611
Projects: 4
Exp: 16 years


Hand over your head.


« Posted 2013-02-06 06:04:07 »

The problem
We often see people asking question about entity management, involving removing items from a list, during iteration, or adding new items to them.


Naive attempts
A naive attempt usually results in a rather confusing ConcurrentModificationException, thrown by some of Java's provided collections. When getting rid of this exception, more often than not, there is an hard to discover off-by-one bug lingering in there, leading to silent errors.
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
// attempt 1
for(Entity current: entities) {
   if(current.isDead()) {
      entities.remove(current); // exception
  }
   else if(current.isShooting()) {
      entities.add(new BulletEntity()); // exception
  }
}

// attempt 2
for(int i=0; i<entities.size(); i++) {
   Entity current = entities.get(i);
   if(current.isDead()) {
      entities.remove(i); // silent error, skips the next element!
  }
   else if(current.isShooting()) {
      entities.add(new BulletEntity()); // OK
  }
}


Solution A
Normally helpful people are suggesting to 'correct i', after a removal of an element and all is well, except performance.
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
for(int i=0; i<list.size(); i++) {
   Entity current = list.get(i);
   if(current.isDead()) {
      list.remove(i); // extremely slow
     i--; // correct i
  }
   else if(current.isShooting()) {
      list.add(new BulletEntity());
   }
}


Solution B
Iterating the collection in the opposite order. This has a few downsides: first, you force yourself to visit entities in opposite order, which might alter logic. Second, it prevents you from visiting elements you add to the collection while iterating over it. Last but not least, when removing an element from a List, you trigger an array-shift, which is time consuming, especially as it is performed for every removed element.
1  
2  
3  
4  
5  
6  
7  
8  
9  
for(int i=list.size()-1; i>=0; i--) {
   Entity current = list.get(i);
   if(current.isDead()) {
      list.remove(i); // extremely slow
  }
   else if(current.isShooting()) {
      list.add(new BulletEntity()); // will not be visited this iteration
  }
}


Solution C (fast and correct, but deemed a hassle)
A fast solution is to create two lists, where you iterate over the first, while also adding new entities to the first, while copying enities that 'survive' to the second list. When all entities are visited, you clear the list that was just iterated, and swap both lists. This allows you to remove while iterating without any overhead, and adding items as you go, while processing those immediately during iteration. It however brings some bookkeeping, and requires twice the amount of memory. Clearing the list that was just iterated over is also less than optimal, as all array elements have to be nulled behind the scenes.
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
for(int i=0; i<curr.size(); i++) {
   Entity current = curr.get(i);
   if(!current.isDead()) {
      next.add(current);
   }
   else if(current.isShooting()) {
      curr.add(new BulletEntity()); // will be visited this iteration
  }
}
curr.clear();
// swap lists
temp = curr;
curr = next;
next = temp;


Proposed Solution (fast and convenient)
We can use the strategy of Solution C and merge the two lists into one. We keep the support for the feature of iterating over new entities in the current loop, and removing entities without the overhead that is imposed by the typical List implementation. Then we use the Iterator/Iterable interfaces to support convenient syntax, while also retaining support for methods like remove() and add(...).
1  
2  
3  
4  
5  
6  
7  
8  
9  
ReadWriteCollection<Entity> entities = ...;
for(Entity entity: entities) {
   if(current.isDead()) {
      entities.remove(); // very fast
  }
   else if(current.isShooting()) {
      entities.add(new BulletEntity()); // will be visited this iteration
  }
}

You can see that the 'entities' instance is stateful, so that while iterating, 'entities.remove()' knows which element to discard.

The following demo code will show how to use the class:
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  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
ReadWriteCollection<String> data = new ReadWriteCollection<>();

data.add("a");
data.add("b");
data.add("c");
data.add("d");
data.add("e");
data.add("f");
data.add("g");

for (String str : data) {
   System.out.println("found: " + str);
}

System.out.println(data); // "[a, b, c, d, e, f, g]"

for (String str : data) {
   // print the element
  System.out.println("found: " + str);

   if (str.equals("e")) {
      // remove while iterating
     data.remove();

      // add while iterating
     data.add("ee");
   } else if (str.equals("ee")) {
      System.out.println("encountered added item!");
   }
}

System.out.println(data); // "[a, b, c, d, f, g, ee]"

// fast clearing of the collection while iterating over it
for (String str : data) {
   data.remove();
}
// or use the clear method: both versions are O ( n )
data.clear();

System.out.println(data); // "[]"



Implementation
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  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
import java.util.*;

public class ReadWriteCollection<E> implements Iterator<E>, Iterable<E> {
   private int iterateIndex, retainIndex, endIndex;
   private E[] items;
   private boolean doRetain;

   @SuppressWarnings("unchecked")
   public ReadWriteCollection() {
      items = (E[]) new Object[4];
   }

   public void add(E item) {
      if (endIndex == items.length) {
         items = Arrays.copyOf(items, Math.max(4, items.length << 1));
      }
      items[endIndex++] = item;
   }

   @Override
   public Iterator<E> iterator() {
      this.prepareForAccess();
      return this;
   }

   @Override
   public boolean hasNext() {
      if (doRetain) {
         items[retainIndex++] = items[iterateIndex - 1];
         doRetain = false;
      }

      if (iterateIndex == endIndex) {
         flip();
         return false;
      }

      return endIndex > 0;
   }

   @Override
   public E next() {
      if (iterateIndex == endIndex) {
         throw new NoSuchElementException();
      }
      doRetain = true;
      return items[iterateIndex++];
   }

   @Override
   public void remove() {
      if (iterateIndex == 0) {
         throw new NoSuchElementException();
      }
      if (!doRetain) {
         throw new IllegalStateException("already removed");
      }
      doRetain = false;
   }

   public void clear() {
      retainIndex = 0;
      flip();
   }

   public void trimToSize() {
      this.prepareForAccess();
      this.items = Arrays.copyOf(items, endIndex);
   }

   private void prepareForAccess() {
      if ((iterateIndex | retainIndex) == 0) {
         // no need to init
        return;
      }

      // process any unprocessed value from the previous iteration
     int off = iterateIndex + (doRetain ? 0 : 1);
      int len = endIndex - off;
      if (off != retainIndex) {
         System.arraycopy(items, off, items, retainIndex, len);
      }
      retainIndex += len;

      this.flip();
   }

   private void flip() {
      Arrays.fill(items, retainIndex, endIndex, null);
      endIndex = retainIndex;
      retainIndex = 0;
      iterateIndex = 0;
      doRetain = false;
   }

   @Override
   public String toString() {
      StringBuilder sb = new StringBuilder("[");
      for (int i = 0; i < retainIndex; i++) {
         sb.append(items[i]).append(",");
      }
      for (int i = iterateIndex - (doRetain ? 1 : 0); i < endIndex; i++) {
         sb.append(items[i]).append(",");
      }
      if (sb.length() > 1) {
         sb.setLength(sb.length() - 1);
      }
      return sb.append("]").toString();
   }
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #1 - Posted 2013-02-06 08:09:02 »

Good stuff! I use the same copy-back-during-iteration method in my entity collections as well.

Offline Riven
Showcase Moderator

JGO Overlord


Medals: 611
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2013-02-06 08:45:26 »

@ClickerMonkey: thanks for the feedback. You mean you used 'solution c', or something similar to my proposed solution? If so, please show your code, so we can compare Smiley


The core of the argorithm is that collection.remove() is lazy, as the algorithm is basically deciding whether to retain elements. Therefore removing is just setting a flag, and upon the next read access, that flag is used to decide whether to add the entity to the 'second list', which happens to use the same array as the 'first list'.

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 actual

JGO Coder


Medals: 24



« Reply #3 - Posted 2013-02-06 12:22:54 »

Interesting. I have been working on a similar data structure that has a couple of differences. The first is that when elements are added, they aren't visible during iteration until they are committed. This is to prevent cases where iterating through the list may produce more elements added to the list (which in turn may produce even more elements, etc).

1  
2  
3  
4  
5  
6  
BufferedIterator<String> iter = new BufferedIterator<String>();

iter.add("a");
iter.add("b");

iter.commitBuffer();  // Now "a" and "b" are available for iteration.

Think of an Event system where you loop through all of the Events and pass them to their receiving Entity to process. In handling that Event that Entity may generate more Events, which in turn may generate more.

The second is difference is that I also have an autoRemove(E element) method where the programmer can extend the data structure to automatically remove elements as it iterates.

1  
2  
3  
4  
5  
BufferedIterator<Event> eventList = new BufferedIterator<Event>() {
   
    @Override public boolean autoRemove(Event event) {
       return event.isExpired();
    }


(You can also remove via a remove() method like a regular iterator). I have mostly finished implementations of both an insertion ordered and no-order-guaranteed versions but I have niggling little bugs I haven't worked out yet.

I'll have to clean the code up, get it working, and share it to see what folks think.
Offline matheus23

JGO Kernel


Medals: 98
Projects: 3


You think about my Avatar right now!


« Reply #4 - Posted 2013-02-06 19:48:15 »

The core of the argorithm is that collection.remove() is lazy, as the algorithm is basically deciding whether to retain elements. Therefore removing is just setting a flag, and upon the next read access, that flag is used to decide whether to add the entity to the 'second list', which happens to use the same array as the 'first list'.

continuations, lazyness. I see you moving in the functional direction. What languages did you try out in the last couple of months? If you didn't already, try out guile scheme and haskell probably.

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline ctomni231

JGO Ninja


Medals: 71
Projects: 1
Exp: 7 years


Not a glitch. Just have a lil' pixelexia...


« Reply #5 - Posted 2013-02-06 20:45:54 »

Usually, for games, I find option A very efficient unless you are concurrently adding and deleting elements.

In that tiny 4K game I made, all the entities are in fact in one straight array. My solution for dealing with concurrency is just splitting the process into two parts. (Which is essentially what you did with Option C & D[Yours])

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
//creation sequence
for(int i = 0; i < array.length; i++){
        //creation of objects here              
}  

//deletion sequence
for(int i = 0; i < array.length; i++){
        //deletion of objects here
       i--;//for each deletion
}


I was unsuccessful in finding a way to do this in one iteration. It gets very close, but there is always lingering bugs when you try to do additions and deletions in the same loop. I've always used just one array to handle entities.

Usually, for particles, I like to have a max particle pool and stop rendering when particles get too much on the screen (in which human eyes won't tell the difference anyway.) For entities that keep expanding, then I just split the array into two parts.

Works fast and efficiently for me. I've been using this method since I've been coding in C++... so it just stuck around.

Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #6 - Posted 2013-02-06 21:25:40 »

@ClickerMonkey: thanks for the feedback. You mean you used 'solution c', or something similar to my proposed solution? If so, please show your code, so we can compare Smiley

The core of the argorithm is that collection.remove() is lazy, as the algorithm is basically deciding whether to retain elements. Therefore removing is just setting a flag, and upon the next read access, that flag is used to decide whether to add the entity to the 'second list', which happens to use the same array as the 'first list'.

I'm talking about your proposed solution, your remove() algorithm marks the current item to be copied over, so when hasNext is called it is "back-copied" as I like to say it (you overwrite previous entries overtop of dead ones). This is exactly what I do. I also like that you made the class implement Iterable and Iterator, I do this as well. It makes using for-each statements in games acceptable.

Offline Roquen
« Reply #7 - Posted 2013-02-06 21:28:21 »

continuations, lazyness. I see you moving in the functional direction.
This is a trap.  These are not functional notions.
Offline Grunnt

JGO Wizard


Medals: 59
Projects: 8
Exp: 5 years


Complex != complicated


« Reply #8 - Posted 2013-03-05 14:35:04 »

Thanks a lot for sharing this code, it was precisely what I was looking for and more elegant than anything I could have concocted myself..

Online StrideColossus
« Reply #9 - Posted 2013-03-05 15:40:41 »

Unless I'm missing the point you can remove entries from any collection while iterating using standard iterators:

final Iterator<T> itr = list.iterator();
while( itr.hasNext() ) {
    final T t = itr.next();
    final boolean dead = ....
    if( dead ) {
        itr.remove();
    }
}

Obviously not as concise as the for-each syntactic sugar but simple nevertheless.

Removing entries from any array-based collection (e.g. ArrayList) is going to perform poorly whatever removal strategy you use (due to the array resizing under the hood) unless the collection is a queue or linked list.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline actual

JGO Coder


Medals: 24



« Reply #10 - Posted 2013-03-05 15:48:22 »

If order is not important, than you can simply replace the element you want to delete with the last element in the list and then null the last element. Array backed bags take this approach.
Offline Riven
Showcase Moderator

JGO Overlord


Medals: 611
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2013-03-05 19:04:03 »

Unless I'm missing the point you can remove entries from any collection while iterating using standard iterators
How about reading the first post? It clearly explains all concepts that are discussed and how standard element removal is horribly slow.

Removing entries from any array-based collection (e.g. ArrayList) is going to perform poorly whatever removal strategy you use (due to the array resizing under the hood) unless the collection is a queue or linked list.
1. if you paid any attention to the code and the text, you'd have seen that my code solved the performance problem of removing many elements from an array backed collection.
2. when removing elements there is no array resizing in collection classes.
3. you seem to think a 'queue' is neither a linked list nor an array backed collection. what is it?



If order is not important, than you can simply replace the element you want to delete with the last element in the list and then null the last element. Array backed bags take this approach.
This collection (and text) explicitly states it solves the problem for cases where order is important.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Regenuluz
« Reply #12 - Posted 2013-03-05 22:54:32 »

I've been using method C, and didn't find it too much of a hassle. But I'll try out this collection, because it gives better looking code. (And doesn't use double the amount of memory.)
Offline Riven
Showcase Moderator

JGO Overlord


Medals: 611
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #13 - Posted 2013-03-05 23:20:03 »

Keep in mind this class is basically a wrapper over this simple algorithm:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
int entityRetainCount=0;
for(int i=0; i<entityCount; i++) {
   Entity entity = entities[i];
   if(entity.isDead()) {
      continue;
   }

  entities[entityRetainCount++] = entity; // compact
  if(entity.isShooting()) {
      entities[entityCount++].add(new BulletEntity()); // append
  }
}
Arrays.fill(entities, entityRetainCount, entityCount, null); // cleanup freed slots
entityCount = entityRetainCount;

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Grunnt

JGO Wizard


Medals: 59
Projects: 8
Exp: 5 years


Complex != complicated


« Reply #14 - Posted 2013-03-06 07:19:38 »

I just wondered: does using break when iterating over this collection cause issues? I don't see a way of handling this case nicely (other than not calling break of course).

Offline Riven
Showcase Moderator

JGO Overlord


Medals: 611
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #15 - Posted 2013-03-06 07:51:05 »

Just like the algorithm it wraps, it can't be interrupted halfway.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Online StrideColossus
« Reply #16 - Posted 2013-03-06 11:03:07 »

Sorry if I came across as challenging, I was actually attempting to be constructive lol.

Quote
1. if you paid any attention to the code and the text, you'd have seen that my code solved the performance problem of removing many elements from an array backed collection.

Running the test you posted (and a couple of others to compare add() and clear() ) to compare an ArrayList using Iterator.remove() against ReadWriteCollection shows no difference on the three machines/JVMs I tried it on, execution times were roughly the same irrespective of the size of the data, number of iterations, random or specific data, etc.  In fact ArrayList was slightly faster overall.

OK hardly a scientific analysis but what I was trying (unsuccessfully) to point out is I couldn't see how the ReadWriteCollection implementation solved the performance problem - see below.

Of course the main point of the ReadWriteCollection was the advantage of being able to concurrently add and remove whilst iterating rather than performance per se.

Quote
2. when removing elements there is no array resizing in collection classes.

Resizing was a poor choice of word, I was referring to array-copies: using the simple ArrayList as an example, most remove() operations will result in the right-hand part of the underlying array being copied one step to the left (unless one happens to remove the last element).  An analysis tool such as JProbe highlights the array copy as the highest-cost part of the test.  So the remove() operation is linear in both implementations, but the actual bottle-neck is the same.  That was what I was trying to point out.

Quote
3. you seem to think a 'queue' is neither a linked list nor an array backed collection. what is it?

Again poor terminology, forget queues, what I meant was linked lists (which by definition are not backed by an array) do not have the array-copy issue.

One question: ReadWriteCollection isn't in fact a Java Collection (realised that when I tried to write a parameterized test!) - any reason for that?
Offline Roquen
« Reply #17 - Posted 2013-03-06 12:03:04 »

The trouble with "linked lists" is two fold.  The first is what do you mean?  If you have an external container 'node', then they're virtually useless for large scale problems (if performance is a concern).  Random memory reads skyrocket.  Bad.  Linked lists where the chain is embedded is better (and can be a good to best choice in certain situations), but you're still adding memory bloat which needs to be offset by how you're walking data (again assuming performance is one of the large concerns).
Offline relminator
« Reply #18 - Posted 2013-03-06 12:23:02 »

The trouble with "linked lists" is two fold.  The first is what do you mean?  If you have an external container 'node', then they're virtually useless for large scale problems (if performance is a concern).  Random memory reads skyrocket.  Bad.  Linked lists where the chain is embedded is better (and can be a good to best choice in certain situations), but you're still adding memory bloat which needs to be offset by how you're walking data (again assuming performance is one of the large concerns).

I agree.  Ram latency makes games stutter. That's why I use linked/hashed arrays for constant time insertion and deletion O(2). Maintains 2 arrays (1 size of object and 1 size of integer for the hash-like ID system).  But considering that a linked list would need pointers for next and prev, the memory it needs is quite smaller.

The caveat is that you can't resize on the fly without a nasty overhead but with games, we usually know the maximum amount of entities we need beforehand.

http://www.java-gaming.org/topics/hi-i-need-someone-to-critique-my-bullet-hell-test-engine/28910/view.html

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  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
/**
 *
 * @author Richard Eric M. Lope (Relminator)
 * @version 1.00 2013/3/04
 */


import java.awt.Graphics2D;


public class BulletManager
{
   private Bullet[] bullets;
   private int size;
   
   private int numFreeBullets = 0;
   private int numActiveBullets = 0;
   
   private int[] freeBulletIndex;  
   
   
   public BulletManager( int size )
   {
      this.size = size;
      bullets = new Bullet[size];
      for( int i = 0; i < size; i++ )
      {
         bullets[i] = new Bullet();
      }
     
      numActiveBullets = 0;
      numFreeBullets = size;
      freeBulletIndex = new int[size];
     
      for( int i = 0; i < size; i++ )
      {
         freeBulletIndex[i] = i;
      }
     
   }
   
   public int getSize()
   {
      return size;
   }
   
   public int getActiveBullets()
   {
      return numActiveBullets;
   }
   
   public void addBullet( Bullet bullet )
   {
     
      if( numFreeBullets == 0 )
      {
         return;
      }
     
      numFreeBullets--;
     
      int index = freeBulletIndex[numFreeBullets];
      bullets[index] = bullet;
     
     
      numActiveBullets++;
     
   }
   
   void removeBullet( int index )
   {
     
      freeBulletIndex[numFreeBullets] = index;
         numFreeBullets++;
      numActiveBullets--;
         
   }
   
   public void updateBullets()
   {
      for( int i = 0; i < size; i++ )
      {
         if( bullets[i].isActive() )
         {
            bullets[i].update();
            if( (bullets[i].position.x < 0) || (bullets[i].position.x > Globals.SCREEN_WIDTH) ||
               (bullets[i].position.y < 0) || (bullets[i].position.y > Globals.SCREEN_HEIGHT) )
            {
               bullets[i].setActive(false) ;
               removeBullet(i);
            }
         }
      }
     
   }
   
   public void renderBullets( Screen screen, Graphics2D g, ImageAtlas imageAtlas )
   {
     
      for( int i = 0; i < size; i++ )
      {
         if( bullets[i].isActive() )
         {
            int frame = bullets[i].getFrame();
            g.drawImage( imageAtlas.getSprite(frame),
                      (int)bullets[i].position.x - imageAtlas.getSprite(frame).getWidth()/2,
                      (int)bullets[i].position.y - imageAtlas.getSprite(frame).getHeight()/2,
                      screen );
         }
      }
     
   }
   
}
Offline princec

JGO Kernel


Medals: 284
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #19 - Posted 2013-03-06 12:28:45 »

That's what you think...

Cas Smiley

Offline Riven
Showcase Moderator

JGO Overlord


Medals: 611
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #20 - Posted 2013-03-06 22:44:16 »

I agree.  Ram latency makes games stutter.
You're misinformed, unless you actually notice a 'stutter' of a couple of nanoseconds. Clueless


Running the test you posted (and a couple of others to compare add() and clear() ) to compare an ArrayList using Iterator.remove() against ReadWriteCollection shows no difference on the three machines/JVMs I tried it on, execution times were roughly the same irrespective of the size of the data, number of iterations, random or specific data, etc.  In fact ArrayList was slightly faster overall.

OK hardly a scientific analysis but what I was trying (unsuccessfully) to point out is I couldn't see how the ReadWriteCollection implementation solved the performance problem.


Data size ~1,000 entities
1  
2  
3  
4  
5  
6  
7  
testIterator[1321]: 37 micros
testIterator[1319]: 37 micros
testIterator[1314]: 31 micros

testCompactSweep[1321]: 11 micros
testCompactSweep[1319]: 12 micros
testCompactSweep[1314]: 11 micros


Data size ~10,000 entities
1  
2  
3  
4  
5  
6  
7  
testIterator[13461]: 464 micros
testIterator[13476]: 418 micros
testIterator[13456]: 421 micros

testCompactSweep[13461]: 119 micros
testCompactSweep[13476]: 117 micros
testCompactSweep[13456]: 114 micros


Data size ~100,000 entities
1  
2  
3  
4  
5  
6  
7  
testIterator[133683]: 24475 micros
testIterator[133671]: 23982 micros
testIterator[133729]: 22777 micros

testCompactSweep[133683]: 909 micros
testCompactSweep[133671]: 919 micros
testCompactSweep[133729]: 914 micros


Data size ~1,000,000 entities
1  
2  
3  
4  
5  
6  
7  
testIterator[1337267]: 2,744,038 micros
testIterator[1337171]: 2,979,241 micros
testIterator[1337389]: 3,012,128 micros

testCompactSweep[1337267]: 12,898 micros
testCompactSweep[1337171]: 13,587 micros
testCompactSweep[1337389]: 12,240 micros

We can conclude that for these data-sizes, we have a 3x, 4x, 25x and 246x performance increase, which is obviously significant and shows the compact-sweep algorithm scales exceptionally well (linearly).

Here is the benchmark:
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  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

public class EntityCollectionBenchmark {

   static class Entity {
      private int countdown;
      private final int offspring;

      public Entity(int maxAge, int offspring) {
         this.countdown = maxAge;
         this.offspring = offspring;
      }

      public boolean isDying() {
         return countdown <= 0;
      }

      public void tick() {
         countdown--;
      }
   }

   public static void main(String[] args) {
      testIterator(100 * 1337);
      System.out.println();
      testCompactSweep(100 * 1337);
   }

   private static void testIterator(int num) {
      List<Entity> entities = new ArrayList<>();

      final Random rndm = new Random(1234567890L);
      for (int i = 0; i < num; i++) {
         entities.add(new Entity(rndm.nextInt(256), rndm.nextInt(3)));
      }

      for (int i = 0; i < 100; i++) {
         long t0 = System.nanoTime();

         int spawnCount = 0;
         for (Iterator<Entity> it = entities.iterator(); it.hasNext();) {
            Entity entity = it.next();
            if (entity.isDying()) {
               spawnCount += entity.offspring;
               it.remove();
            } else {
               entity.tick();
            }
         }
         for (int q = 0; q < spawnCount; q++) {
            entities.add(new Entity(rndm.nextInt(256), rndm.nextInt(3)));
         }

         long t1 = System.nanoTime();

         if (i % 10 == 0) {
            System.out.println("testIterator[" + entities.size() + "]: " + (t1 - t0) / 1000 + " micros");
         }
      }
   }

   private static void testCompactSweep(int num) {
      Entity[] entities = new Entity[num * 2];
      int entityCount = 0;

      final Random rndm = new Random(1234567890L);
      for (int i = 0; i < num; i++) {
         entities[entityCount++] = new Entity(rndm.nextInt(256), rndm.nextInt(3));
      }

      for (int i = 0; i < 100; i++) {
         long t0 = System.nanoTime();

         int spawnCount = 0;
         int entityRetainCount = 0;
         for (int p = 0; p < entityCount; p++) {
            Entity entity = entities[p];
            if (entity.isDying()) {
               spawnCount += entity.offspring;
            } else {
               entity.tick();
               entities[entityRetainCount++] = entity;
            }
         }
         for (int q = 0; q < spawnCount; q++) {
            entities[entityRetainCount++] = new Entity(rndm.nextInt(256), rndm.nextInt(3));
         }

         if (entityRetainCount < entityCount) {
            Arrays.fill(entities, entityRetainCount, entityCount, null);
         }
         entityCount = entityRetainCount;

         long t1 = System.nanoTime();

         if (i % 10 == 0) {
            System.out.println("testCompactSweep[" + entityCount + "]: " + (t1 - t0) / 1000 + " micros");
         }
      }
   }
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline relminator
« Reply #21 - Posted 2013-03-07 01:33:01 »

I agree.  Ram latency makes games stutter.
You're misinformed, unless you actually notice a 'stutter' of a couple of nanoseconds. Clueless

I actually notice those things because I have a dinosaur of a netbook.  And also because I also code games on a 66mhz console.  Ram latency is also the reason why I went with simple boxed grid spatial partitioning in lieu of an octree for a 3D renderer on the said console.

But this is java so these things might not matter (JVM stuff I have no idea about).
 
Offline Riven
Showcase Moderator

JGO Overlord


Medals: 611
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #22 - Posted 2013-03-07 01:41:47 »

RAM latency (cache misses) drag down your performance, but stuttering is something else entirely.

It's like acusing a whale of triggering the earthquake that caused the tsunami, by reasoning: 'the whale can do that, because it's bloody big' - while it's 6-7 orders of magnitude off of being relevant.

And yes, boxed grids are much, much cache-friendlier than quad-trees and oct-trees. But even a tree (with continuous cache misses while traversing nodes) won't cause stuttering, it will just be slower, consistently.

I have no experience with 66MHz hardware, but even with the crappiest 1GHz Atom cache misses won't cause stuttering.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline relminator
« Reply #23 - Posted 2013-03-07 01:58:24 »

Our definition of stutter my have been different. ;*)

I  consider lag a stutter.
Offline Riven
Showcase Moderator

JGO Overlord


Medals: 611
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #24 - Posted 2013-03-07 02:01:15 »

lag = latency, so yeah, ram latency causes lag latency

My definition of stuttering is: (humanly) noticable irratic performance (like seeing a 10% drop in performance, for 1 frame, for no apparent reason, causing you to miss a frame or two)

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Agro
« Reply #25 - Posted 2013-03-07 02:31:22 »

Question, if all of the entities have a "depth", is there some simple way to sort all the entities with this class?

Offline Riven
Showcase Moderator

JGO Overlord


Medals: 611
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #26 - Posted 2013-03-07 02:12:17 »

We're moving, sorting (and rendering) 150,000 constantly moving entities at 60fps, using a non-square grid of buckets, which are sorted by gnome-sort. Don't let the 'performance characteristics' of O(n^2) fool you, I found it to be the best algorithm for this specific use case (sorting on Y, then X, to implement the painters algorithm).

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline matheus23

JGO Kernel


Medals: 98
Projects: 3


You think about my Avatar right now!


« Reply #27 - Posted 2013-03-07 17:32:03 »

We're moving, sorting (and rendering) 150,000 constantly moving entities at 60fps, using a non-square grid of buckets, which are sorted by gnome-sort. Don't let the 'performance characteristics' of O(n^2) fool you, I found it to be the best algorithm for this specific use case (sorting on Y, then X, to implement the painters algorithm).

Yeah but how do I actually do sorting with that collection? Or am I asking something plain stupid here? It doesn't look like this is possible with your code yet...

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline princec

JGO Kernel


Medals: 284
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #28 - Posted 2013-03-07 18:04:09 »

It's not a sortable collection; the whole point of it is that you need the order in which things are placed in it maintained. The example Riven gave there was not related to this collection; it's just an example of how misleading big-O notation is when one doesn't know the actual cost of the algorithm on its expected workload parameters.

Cas Smiley

Offline theagentd
« Reply #29 - Posted 2013-03-07 18:30:04 »

Yeah but how do I actually do sorting with that collection? Or am I asking something plain stupid here? It doesn't look like this is possible with your code yet...
You have a
1  
private E[] items;

It's dead simple to just use
Arrays.sort(items);
, right?

Myomyomyo.
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 (73 views)
2014-04-15 18:08:23

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

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

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

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

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

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

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

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

CJLetsGame (220 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!