ReadWriteCollection for entities

Shared Code
#21

You’re misinformed, unless you actually notice a ‘stutter’ of a couple of nanoseconds. :clue:

Data size ~1,000 entities


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


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


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


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:

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");
			}
		}
	}
}
#22

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

#23

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.

#24

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

I consider lag a stutter.

#25

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)

#26

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

#27

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

#28

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…

#29

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 :slight_smile:

#30

You have a

private E[] items;

It’s dead simple to just use [icode]Arrays.sort(items);[/icode], right?

#31

Nope, because the Collection seems to save some more data, which could be invalidated:

	private int iterateIndex, retainIndex, endIndex;
#32

That shouldn’t matter. The sort shouldn’t move anything around enough to break the whole list. Besides, I never said that you should throw it directly into Arrays.sort(). I just meant that it should be extremely easy to implement it.

#33

… again still missing the point of this collection, it’s for where the natural ordering of the elements is the order in which they were added. If you’re sorting it you’re using the wrong collection in the first place.

Cas :slight_smile:

#34

Ah, Arrays.sort helped me. Thanks

#35

I did read the replies to this question :P, but maybe an example will be better.

In the game I made, I used an array for the rings. Each ring has a lifetime where it gets created and deleted. Riven’s collection code helps with organizing this type of array. The rings don’t need to be sorted… they just need to destroy and create themselves without causing an error. Creating and deleting the elements at the same time during an array is really bad news :stuck_out_tongue:

#36

I must say Riven since you started working for Cas you have been making some pretty cool stuff. This coupled with that continuations lib is giving me all sorts of ideas about simulating massive populations of all sorts of things.

#37

Not for but with I should emphasise.

Cas :slight_smile: