Dynamic Array Efficiency?

[Major Cooke]

I've been contemplating for a while now on how best to handle dynamic array management to make it as efficient as possible.

It seems there is a way to do so, but I wanted to ask more of the broader audience to see if this method can work, with the idea inspired by phantombeta.

The typical way of doing things is to insert/push actors into an array and delete/clear them out afterwards. But this leads to constantly creating a new temporary array, copying it over, adding/removing the entry and replacing the old array.

From what I've been lead to believe, the pros for manual management are:

• More efficient injections
• Less reallocating/array copying

While the cons are:

• Not optimized by default VM (if it even is done so by JIT)
• Requires manual maintenance
  • Searching for nulls to insert into array (unsure if Find() function can be used to locate nulls or if a for loop is needed)
  • Allocating new sizes whenever full

This is an example of manual management I made from my dynamic random spawner class.

Code: Select all

//==========================================================================
// AddActor functions
//==========================================================================
// ReserveArrays
//
// Grows the array by the specific amount if > 0. Then initializes those
// arrays by defaulting them because otherwise the game will crash upon
// attempting to check them.
//==========================================================================
private void ReserveArrays(int amt)
{
	if (amt < 1)	
		return;
	
	int oldSize = Mobj.Size();
	Mobj.Reserve(amt);
	Chance.Reserve(amt);
	for (int i = oldSize; i < Mobj.Size(); i++)
	{
		Mobj[i] = null;
		Chance[i] = 0;
	}
}
//==========================================================================
// Internal array management. Finds a null uses that position to store the
// added class type and its spawn chance (weight). If there isn't any space,
// make room for it.
//==========================================================================
private void _AddActor(Class<Actor> cls, int weight)
{
	if (Mobj.Size() < 1)
	{
		ReserveArrays(ReserveAmt);
	}
	for (int i = 0; i < Mobj.Size(); i++)
	{
		if (Mobj[i] == null)
		{
			Mobj[i] = cls;
			Chance[i] = weight;
			return;
		}
		int size = Mobj.Size();
		if (i >= size - 1)
		{
			ReserveArrays(ReserveAmt);
			i = size - 1;
		}
	}
}

//==========================================================================
// The main function that handles everything, making sure it exists and has
// weight > 0.
//==========================================================================
void AddActor(String cls, int weight)
{
	if (cls == '' || cls == 'None')
		return;
		
	Class<Actor> mon = cls;
	if (!mon)	
	{
		Console.Printf("%s - bad actor", cls);	
		return;
	}
	
	if (weight < 1)
	{
		Console.Printf("%s - weight must be above zero", cls);
		return;
	}
	
	_AddActor(cls, weight);
}

TL:DR of the code, it manually expands the array by an amount whenever there's no room and initializes them to default values (null/0). It always assigns the values to the slot where a null is found.

Pretending the non-jit slowdown via the regular VM is a non-issue and eliminating that con (since it can call up to 3 functions in total), is this more efficient?

[Graf Zahl]

You are overestimating the reallocations. The array grows in blocks, i.e. if it is too small the allocated size gets doubled which then gets gradually filled in.
If you remove elements no reallocation takes place. This type of dynamic array gets used everywhere these days, and it hardly causes performance issues, unless you use it wrong, e.g. constantly removing elements at the start instead of the end.

[Major Cooke]

Huh! Okay! Well, I certainly know where I can improve some of my arrays for certain then! I do have a series that, every 10 seconds, is cleared of nulls. Naturally monsters in mods like AEoD and D4D can be blasted into oblivion and stop existing.

Since these arrays record them and special actors, this will certainly help. I can make a temporary array, find all non-nulls, push them to the temporary, and then move the temporary one onto the original. That'll be far more efficient for such a time scale.

But when Move() is used, should we err on the side of caution and use Clear() afterwards or does it do that automatically?

[Graf Zahl]

Move moves, it doesn't copy. The source will be empty afterward.
In fact it frees the old destination buffer and then just moves over the pointer from the source to the destination, there is no copy involved.

[Major Cooke]

Replaces the array's contents with contents of the specified other array, but leaves that other array in unspecified state. If you constructed some data in another array and you will only need it in its new location, this should be faster than Copy.

Right. Just checking. The wiki says it leaves it in an unspecified state, so I wasn't sure if that's equivalent to being uninitialized.

[Graf Zahl]

This is internally a C++ move assignment which absolutely must NOT leave anything in an unspecified state ever.

[kb1]

You are overestimating the reallocations. The array grows in blocks, i.e. if it is too small the allocated size gets doubled which then gets gradually filled in.
If you remove elements no reallocation takes place. This type of dynamic array gets used everywhere these days, and it hardly causes performance issues, unless you use it wrong, e.g. constantly removing elements at the start instead of the end.

Yes, this is extremely fast, it scales well, and tends to keep elements together in memory. Nice!

Major Cooke wrote:
I've been contemplating for a while now on how best to handle dynamic array management to make it as efficient as possible.

Does the order of the elements in the array matter to you? If not, try this (Note: I'm using pseudo-code below...please translate as needed):

Let's assume you have an array of animal types:
Dog, Cat, Bird, Mouse, and Rat.

First, maintain a separate count of the number of items:
So far, we could say that AnimalCount = 5.

To add an animal, first grow the array, if necessary, then add the new animal at element AnimalCount, and increment the count:

Code: Select all

Animals[AnimalCount++] = "Squirrel";

No search for NULLs needed here.

To delete an animal, move the last element of the array into the slot to be deleted, NULL the last element, and decrement the count:

Code: Select all

Animals[EntryToDelete] = Animals[AnimalCount - 1]; Animals[AnimalCount - 1] = NULL; AnimalCount--;

No search for NULLs needed here either. Also, no temporary array, no FOR loop either!
For example, after adding Squirrel, our array currently looks like this:
Dog, Cat, Bird, Mouse, Rat, Squirrel. AnimalCount = 6.

Now, let's delete Bird, which is element 2: (AnimalCount is still 6)

Code: Select all

Animals[2] = Animals[5]; Animals[5] = NULL; AnimalCount--;

Now, our array looks like this:
Dog, Cat, Squirrel, Mouse, Rat, NULL, with AnimalCount = 5.

Basically, the Add code always adds to the end of the list, and the Delete always frees up the element at the end of the list.

Simple, fast, and efficient in every way. Obviously, if deleting the last element, you skip the first step. Also, you might want to do some sanity checks on your array indices. I am assuming that the order of items in the array is unimportant, since your code was adding new items in the first NULL spot you could find. So, if you don't mind the elements moving around in the array, this method is very fast, and remains fast, regardless of the size of the array. Try it.

Another method is to maintain another array that holds a list of the slots that have been deleted in the first array. You use the deleted_slots array to know where to add new entries, until you've exhausted the list. But that's more complicated, and not really needed in this case.

If you do try one of these methods, please post your results - I'd love to check out your implementation. Enjoy, and good luck!

[Major Cooke]

Are you certain you didn't mean that for when order IS necessary? Because bear in mind, actors in an array become null the moment they're destroyed. In the event I'm tracking projectiles spawning and destroying for example, finding a null is actually needed. And order is not needed in my case.

On the bright side, Find(null) does seem to work. I still need to do more testing though, just to make certain.

If it actually is working as intended, then it's a lot easier just to do this:

Code: Select all

int i = Missiles.Find(null);
if (i >= Missiles.Size())
	Missiles.Push(mo);
else Missiles[i] = mo;

Of course the alternative is using just a for loop directly.

As for maintaining the arrays, I feel like this does its job a LOT better than when it used to have Delete. I simply make a temporary array, copy all non-null elements to it and then shove it over the original, then clearing it out for the next array every 5-10 seconds.

Code: Select all

override void WorldTick()
{
	// Clear the lists every TimeTrigger seconds of null pointers.
	Timer++;
	if (Timer >= TimeTrigger)
	{
		Timer = 0;
		int i = 0;
		Array<Actor> Temp; Temp.Clear();
		
		for (i = 0; i < DeadMonsters.Size(); i++)
		{
			Actor mo = DeadMonsters[i];
			if (mo)
			{	
				if (mo.health > 0)
				{
					Monsters.Push(mo);
					DeadMonsters[i] = null;
				}
				else	Temp.Push(mo);
			}
		}
		DeadMonsters.Move(Temp);		Temp.Clear();
		
		for (i = 0; i < Monsters.Size(); i++)		
		{
			Actor mo = Monsters[i];
			if (mo)
			{
				if (mo.health < 1)
				{
					DeadMonsters.Push(mo);
					Monsters[i] = null;
				}
				else	Temp.Push(mo);
			}
		}
		Monsters.Move(Temp);			Temp.Clear();
		
		for (i = 0; i < Carrion.Size(); i++)	
		{	
			let ca = D4PinataCarrion(Carrion[i]);
			if (ca && !ca.Owner)	Temp.Push(ca);
		}	
		Carrion.Move(Temp);		Temp.Clear();
		
		for (i = 0; i < Missiles.Size(); i++)	{	let mo = Missiles[i];	if (mo)	Temp.Push(mo);	}	Missiles.Move(Temp);	Temp.Clear();
		for (i = 0; i < Tracker.Size(); i++)	{	let mo = Tracker[i];	if (mo)	Temp.Push(mo);	}	Tracker.Move(Temp);		Temp.Clear();		
	}
}

[kb1]

Sorry for such a late response. I forgot about the thread for a bit

Yes, if the data you're storing in the array are objects that can become NULL outside of your control, my method above won't work as-is, unless the object can call a custom _Delete function before destroying itself.

There is another way, however, and you've touched upon it. I've read your code a bit more carefully this time, and noticed that you have similar ideas! I think it can be improved a bit, and made to run very fast.

Note that the speed increase is gained by avoiding having to iterate through your array for adds and deletes. Your code seems to be almost accomplishing this.

First, some observations:
* Functions like Find(NULL) are essentially internal for loops as well, and if you have to do it for each NULL, that could be a lot of iterations.
* Allocating arrays can be a slow process.
* Using temporary arrays to reorganize data can be a slow process.
* Usually clearing an array and reallocating it is a slow process.
* Most possible speedups will involve avoiding iterations, avoiding creating and destroying arrays, and avoiding moving data around.

Suggestions:
1. Use my method above for _Adding to your array. That code does no NULL searching - it just adds to the unfilled portion of your array and increments ActorCount, after growing the array, if necessary. I suggest growing it by (Size + 1) * 2 which effectively doubles it, and handles the case where Size = 0. The doubling technique minimizes the number of times you have to grow the array, while avoiding it becoming too big too fast. As you mentioned, these actors may become destroyed later, so the array will get holes, but we fix that below:

2. Periodically clear out the NULLs, like your WorldTick code (garbage collection). But your code is doing a lot of internal maintenance, as it requires dynamically-resizing arrays, and lots of iterations. Instead, the following code does, at most, a single pass. Basically, we modify the Delete algorithm I listed above that pulls an active element from the end of the array, and places it into a NULL slot. But, we extend this method to fill ALL the NULLs in one pass, without any reallocation, and with minimal data moving. We move forward to find NULL slots that need to be filled, and we move backwards to find non-NULL actors to fill the empty slots with. When these 2 pointers meet, we're done, and end up with a tightly-packed array.

Something like this:

Code: Select all

// pseudo code as before
// assumes you're using the Add code I posted above
// must still maintain a ActorCount var, containing the count of active mos we're tracking with our array. ActorCount is always <= array size-1

tail = ActorCount - 1;
for (head = 0; head < tail; head++)      
{
  if (ArrayOfMOs[head].mo == NULL)
  {
     // found an empty slot to fill
    while (tail > head)
    {
      if (ArrayOfMOs[tail].mo != NULL)
      {
        // found something to fill the empty slot with
        ArrayOfMOs[head].mo = ArrayOfMOs[tail].mo;

        // clear tail (not strictly necessary)
        ArrayOfMOs[tail].mo = NULL;

        --tail;
        --ActorCount;
        break;
      }
      --tail;
    }
  }
}

This should be very fast. Please be careful to only store pointers, and not the actor objects themselves. I'm not sure what the required syntax is to do this, or to check for destroyed actors, so replace my NULL stuff with the proper syntax.

Why the Find method is bad
Let's assume that you have 50 actors in your array, and the last 5 actors have been destroyed. During garbage collection, you'd want to do "Find(NULL)" repeatedly, until all of them were found. That means the Find function would have to look through 45 + 45 + 45 + 45 + 45 entries, plus an additional 45 at the end, adding up to 270 element comparisons. Plus, each time you're CLEARing, reallocating and populating (PUSH) an entire temporary array. The above code packs all actors at the beginning of the original array in one pass, meaning no clearing, no reallocations, and no sub-iterations. And, it can be run relatively infrequently (the array will grow a bit if you wait too long, up to a point where it will stop growing).

What might be a dumb question
Is there no built-in way to just iterate through the actual GZDoom internal Actors array? (Seriously, I don't know the answer to this, and I'm curious). I guess this array is a way to give your scripts a bunch of actors to manipulate, right? What is a good use case for this custom array?

By the way, if you get some use out of this, please let me know. I really hope you find it helpful

[Graf Zahl]

What might be a dumb question
Is there no built-in way to just iterate through the actual GZDoom internal Actors array? (Seriously, I don't know the answer to this, and I'm curious). I guess this array is a way to give your scripts a bunch of actors to manipulate, right? What is a good use case for this custom array?

By the way, if you get some use out of this, please let me know. I really hope you find it helpful

There is no such array. Doom never had one. Actors are stored in the list of thinkers, which in ZDoom gets complicated by having the list split into 128 slots by priority.
The ThinkerIterator class can be used to iterate over this but it's obviously a rather costly iteration.

[kb1]

That makes complete sense. I thought maybe ZScript might hide those complications and expose them as if they were a standard array. Considering the performance implications, it's probably best that it doesn't, because something like that would surely get misused - for example as a quick and dirty way to, say, find all imp fireballs at run-time and make them spawn sparks - ugh!

By the way, ZScript is a great achievement and accomplishment! You should be proud

[Graf Zahl]

because something like that would surely get misused - for example as a quick and dirty way to, say, find all imp fireballs at run-time and make them spawn sparks - ugh!

Some modders have abused the thinker iterators for such things - and then wondered why their mod ran like shit...

[Kruno]

because something like that would surely get misused - for example as a quick and dirty way to, say, find all imp fireballs at run-time and make them spawn sparks - ugh!

Some modders have abused the thinker iterators for such things - and then wondered why their mod ran like shit...

I will go and search for a better way to do this. This is exactly what I am doing in ZScript. Oops!

Thanks for the info.

[kb1]

because something like that would surely get misused - for example as a quick and dirty way to, say, find all imp fireballs at run-time and make them spawn sparks - ugh!

Some modders have abused the thinker iterators for such things - and then wondered why their mod ran like shit...

I will go and search for a better way to do this. This is exactly what I am doing in ZScript. Oops!

Thanks for the info.

The technique above may be exactly what you need. Basically, for the imp fireball sparkles, make a custom imp fireball that calls the _Add method above upon spawn. This provides you a very efficient array of active imp fireballs that you can directly iterate through as you see fit. Make sure you occasionally call the garbage collector (maybe every couple seconds or so) to purge spend fireballs, and you're there! All that's left is to use the array to do your custom stuff (spawning sparkles, or whatever). Use a for loop from 0 to ActorCount - 1, check for NULL, and if not NULL, do your custom work with the actor.

What's nice is that you only add actors to the array that you want to manipulate, so you're only parsing through the actors you care about. The above code should be just about as fast as a custom script can get.

Please post some progress, if you use this method - I'd love to hear about it!

[Kruno]

I would like to know if there is a nice way to profile my code.

I will create my own data structures based on measuring the performance of my code.