Dynamic Array Efficiency?

[Major Cooke]

SlotCount is not going to be kept. I'm just going to use Actor.Size().

[kb1]

SlotCount is not going to be kept. I'm just going to use Actor.Size().

It's up to you. The concern is the behind-the-scenes work that occurs when testing the element for NULL. The thread I posted earlier provides some more information.

But, we're talking about a few hundred elements being tested every couple seconds or so, so it probably will be pretty fast regardless. As long as your actor count is not too high, it should perform pretty well regardless. Personally, I don't really understand your insistence on tested proven unused space each time, but that's your prerogative. It would eat at me.

[Major Cooke]

Because I plan on making the array shrink if it's under 1/4 the size (except for a minimum of 256). At this point it's just micro-optimizations that aren't going to do anything better.

[kb1]

Because I plan on making the array shrink if it's under 1/4 the size (except for a minimum of 256). At this point it's just micro-optimizations that aren't going to do anything better.

Code: Select all

If (Actors.SlotCount >=256)
    Actors.Resize(SlotCount + 128);

My guess is that ZScript does not reallocate the array, it probably just changes Actors.Size on a shrink, leaving the extra memory intact - which is a good thing for you, because really shrinking an array involves reallocation which takes time.

In other words, shrinking the array probably does not reclaim any memory. The memory involved is very small (4, or possibly 8 bytes per actor: 10,000 actors = 40k or 80k). And, shrinking the array is in essence an attempt to get the same benefit of SlotCount with Size.

I can't keep going with this. I tried my best. I'm glad to have helped. I don't understand the motivations, but that's ok. I cannot understand your apprehension for using a very needed variable that will never slow it down, and will almost always speed it up considerably. I cannot understand reading unused memory over and over. But that's ok too.

I cannot convince you to, at least try it, and profile it with a few thousand missile throwing monsters? Maybe try it both ways, and see if there's a difference? It won't be much, but with that many monsters, I think it might be noticeable. I'm honestly trying to give you the best - that's my motivation.

Anyway, best of luck with your project.

[Graf Zahl]

Because I plan on making the array shrink if it's under 1/4 the size (except for a minimum of 256). At this point it's just micro-optimizations that aren't going to do anything better.

Code: Select all

If (Actors.SlotCount >=256)
    Actors.Resize(SlotCount + 128);

My guess is that ZScript does not reallocate the array, it probably just changes Actors.Size on a shrink, leaving the extra memory intact - which is a good thing for you, because really shrinking an array involves reallocation which takes time.

Correct. That's how nearly all dynamic array classes work. They always overallocate the buffer so that it isn't necessary for each added element to call malloc. The backing class (TArray) starts with an allocation of 16 and if it needs more doubles the storage size. But when removing elements it doesn't reallocate.

[Major Cooke]

Don't get the wrong idea. I'm still using your code, just using the Size() function instead, along with the Resize() function because, indeed, that's how dynamic arrays work in ZScript.

[kb1]

Don't get the wrong idea. I'm still using your code, just using the Size() function instead, along with the Resize() function because, indeed, that's how dynamic arrays work in ZScript.

I guess you didn't read Graf's response that really explains how dynamic arrays work...meaning that the resizing is doing nothing, and you're writing towards worst case performance. It's not my code if the unused space is not being divided by a variable - that's the whole point of the code - heh. After having coded as long as I have, I find it difficult to understand why some things are not just obvious. Sorry about that. Regardless, please don't credit me if you use such an implementation - it just doesn't make sense, and I don't want to be associated with it.

Best of luck.

@Graf: Not all languages do, but they should.

[Graf Zahl]

The Size() function doesn't return size of allocated space but size of USED space. No, using Size() as the delimiter is not going for worst performance, it is what should be used to traverse all parts of the array that MAY be in use.
With garbage collected objects that can obviously be a bit tricky because every used entry can be null, but it will never check the unused but allocated parts of the array.

[kb1]

The Size() function doesn't return size of allocated space but size of USED space. No, using Size() as the delimiter is not going for worst performance, it is what should be used to traverse all parts of the array that MAY be in use.
With garbage collected objects that can obviously be a bit tricky because every used entry can be null, but it will never check the unused but allocated parts of the array.

I'm not sure I'm with you there.

When you say "USED", do you mean "the size the ZScript writer asked for with Resize()", or do you mean that "Size() tracks the highest element within the ZScript writer's Resized() space that was assigned a value at some time"?
And when you say "unused but allocated", do you mean "the extra space internally allocated by the ZScript engine beyond what was asked for via Resize()", or do you mean that "you actively track which elements have been initialized"?

In both cases, I think you mean the first definition, not the second.
There are quite a few variables and I'm not 100% sure about the names of them, but I'll try to make my point with clarification:

Say the ZScript writer initially allocates 10 elements for the Actors() array. Then, they add 3 imps, each which fire a missile. You stated previously that you start at 16. So, internally, I'm thinking that the array and Size() look like this:

Code: Select all

+----------------------------------------------------------------------------------------------------------+
|                            SlotCount-1              Size-1                          Internal_Size-1      |
|                                v                       v                                    v            |
|  0     1     2     3     4     5     6     7     8     9     10    11    12    13    14    15            |
| Imp1  Imp2  Imp3  Misl1 Misl2 Misl3 NULL  NULL  NULL  NULL   ?     ?     ?     ?     ?     ?             |
+----------------------------------------------------------------------------------------------------------+

Now, the missile from Imp1 and Imp2 explode and are destroyed. I think the array and Size() now look like this:

Code: Select all

+----------------------------------------------------------------------------------------------------------+
|                            SlotCount-1              Size-1                          Internal_Size-1      |
|                                v                       v                                    v            |
|  0     1     2     3     4     5     6     7     8     9     10    11    12    13    14    15            |
| Imp1  Imp2  Imp3  NULL  NULL  Misl3 NULL  NULL  NULL  NULL   ?     ?     ?     ?     ?     ?             |
+----------------------------------------------------------------------------------------------------------+

Finally, the Clean function is run, which packs all non-null actors towards the start of the array, and adjusts SlotCount accordingly:

Code: Select all

+----------------------------------------------------------------------------------------------------------+
|                SlotCount-1                          Size-1                          Internal_Size-1      |
|                    v                                   v                                    v            |
|  0     1     2     3     4     5     6     7     8     9     10    11    12    13    14    15            |
| Imp1  Imp2  Imp3  Misl3 NULL  NULL  NULL  NULL  NULL  NULL   ?     ?     ?     ?     ?     ?             |
+----------------------------------------------------------------------------------------------------------+

SlotCount has been decremented twice, in preparation for 2 functions: Loops that parse active actors, and new actor Adds. SlotCount is now 4, while Size is still at 10, and Internal_Size is still at 16.

The whole purpose of this class is to provide an array the coder can use to add new actors, and to parse active actors quickly. In this case, SlotCount is ready to add a new actor by simply assigning Actors[SlotCount++] = new_actor;. SlotCount is also ready to parse active actors with

Code: Select all

for (i = 0; i < SlotCount; i++)
{
  if (Actors[i] != NULL)
  {
    ; do stuff with actors[i];
  }
}

Since SlotCount = 4, that's a lot less parsing than if using Size which = 10. The CleanUp is also faster, having to parse 4 elements vs. 10.

All of this assumes that Size() = "the number of elements allocated in ZScript using Resize" (not the actual internal number of elements allocated).
If you tell me that Size() means something different, like "the highest non-NULL element in the array", then, yes, that maybe approaches the same performance of using a simple integer like SlotCount, but internally calculating Size() would require more logic than I would expect a function like Size() to perform, and if so, I would expect there to be another function that would simply return the size allocated by the script writer, because that's important for the script writer to know.

Please tell me if Size() is more complicated than "the number of elements allocated in ZScript using Resize".

SlotCount works, regardless of the internal implementation, and it guarantees to:
1. be the correct position to do ActorAdds
2. be the most elements that need to be parsed, by the Clean function, and by anyone using the class to parse active actors.

Therefore, SlotCount kills 2 birds with 1 stone, all of which is completely deliberate and intentional. It simply does not work efficiently without it - that's why I wrote it that way.

Unless Size() is doing something special, using it is going to cause you to parse more elements than necessary. That's all I'm saying. Please correct me if I'm wrong. Please show me where the above code steps through one more element than necessary.

Now, based on what you've told me about how you allocate internally, the class array grow code could be simplified to Actors.Resize(Actors.Size()+1) vs. doing the doubling in ZScript. Since ZScript is smart about providing extra space internally in anticipation of Resize, this should perform very well.

Please check out the class, and see what I'm babbling about. I think a programmer of your stature will immediately identify the algorithms for their efficiency. Or, if not, let me know.

Sorry this post is so long...I really want to understand how things are done in ZScript, and, to really understand, I need to know just a bit about what's happening internally, as it affects performance, as it would in any language. Thanks in advance.

[Graf Zahl]

If you need the SlotCount variable, you are doing something wrong.
In this case Size() should be the value SlotCount is, and if you have to append anything to the array, use the Push function, if you remove entries that reduce the size, call Resize or Pop. Arrays are designed around such a workflow.
The only case where calling Resize to enlarge an array makes sense is if you want to append a known quantity of elements that's larger than 1, but due to optimization issues, even in this case, Push may be faster.

[kb1]

If you need the SlotCount variable, you are doing something wrong.
In this case Size() should be the value SlotCount is, and if you have to append anything to the array, use the Push function, if you remove entries that reduce the size, call Resize or Pop. Arrays are designed around such a workflow.
The only case where calling Resize to enlarge an array makes sense is if you want to append a known quantity of elements that's larger than 1, but due to optimization issues, even in this case, Push may be faster.

You didn't read the code, huh? Oh well, that's all right - I've spent way too long on this anyway. Thanks.

EDIT:
I thought about this some more to try to understand your answer, despite the fact that you didn't answer my 2 questions which were critical for understanding your last post, which kinda sucks, man. If you had, things just might be clear. Instead, I need to speculate to get answers, which is ok - I'm pretty good at it.

You describe Push and Pop as being the answer. Maybe, behind the scenes, you're essentially doing something very similar to my class, pruning NULLs out, which is kinda cool, if you want a LIFO buffer.
But the goal was to have a random access array of current actors, not a LIFO buffer. How do you use the array more than once, if you've popped off all the actors?

Maybe I should seek some documentation - maybe I'll get my answers there. I have no problem admitting when I'm wrong, but, so far, I'm just not seeing it.

EDIT 2:
Ok, I checked the wiki, and I saw nothing there to indicate that my code would not do the advertised job as optimally as possible, following all of ZScript's rules. Sure, I might be missing something, but I haven't read it yet.

@Major Cooke:
Do what you want with it - I have no more time to spend on it. Just know that I tried.

[Major Cooke]

If you need the SlotCount variable, you are doing something wrong.
In this case Size() should be the value SlotCount is, and if you have to append anything to the array, use the Push function, if you remove entries that reduce the size, call Resize or Pop. Arrays are designed around such a workflow.
The only case where calling Resize to enlarge an array makes sense is if you want to append a known quantity of elements that's larger than 1, but due to optimization issues, even in this case, Push may be faster.

This just reaffirms I'm going to continue using Size() and I'll now consider using Push() over Resize instead when making the array bigger. Thanks!

@kb1 I think it's safe to say that dynamic arrays in GZDoom work differently than how you're used to them. The fewer the iterations the better. That's why I go for sizing it down and just iterating through the whole thing. However, I do thank you for giving me the code for reorganizing the data, that most certainly has come to fruition. Coupled with sizing it down afterwards (which does affect the Size() function), this reduces iterations greatly.

The biggest thing I want to minimize is iterations. Those can be more costly than resizing the array by far.

[kb1]

If you need the SlotCount variable, you are doing something wrong.
In this case Size() should be the value SlotCount is, and if you have to append anything to the array, use the Push function, if you remove entries that reduce the size, call Resize or Pop. Arrays are designed around such a workflow.
The only case where calling Resize to enlarge an array makes sense is if you want to append a known quantity of elements that's larger than 1, but due to optimization issues, even in this case, Push may be faster.

This just reaffirms I'm going to continue using Size() and I'll now consider using Push() over Resize instead when making the array bigger. Thanks!

@kb1 I think it's safe to say that dynamic arrays in GZDoom work differently than how you're used to them. The fewer the iterations the better. That's why I go for sizing it down and just iterating through the whole thing. However, I do thank you for giving me the code for reorganizing the data, that most certainly has come to fruition. Coupled with sizing it down afterwards (which does affect the Size() function), this reduces iterations greatly.

The biggest thing I want to minimize is iterations. Those can be more costly than resizing the array by far.

You are most welcome. But I must reply to your comments.

First, I don't think Graf studied my code at all, which is disappointing. I say this because his comments really didn't seem to come from an understanding of what you wanted to accomplish. Graf must read a huge number of posts, so I don't blame him for not having the time to study the code - he's just too busy.

This does not affirm using Size(). What I learned is that ZScript is smart about its array resizing. It essentially does the exact same work that I was doing in the Add function. What that means is that you may simplify the Add function as follows: (I modified it to use Push instead of Resize, as Graf says that Push is typically faster.)

Code: Select all

   //--------------------------------------------------------------------------
   // Add - Add an actor to the array
   //--------------------------------------------------------------------------
   void Add(Actor mo)
   {
      // Make sure it exists and isn't restricted from insertion.
      if (!mo || (ClassType != null && !(mo is ClassType)))   return;
     
      // grow the array as needed
      if (SlotCount >= Actors.Size())
      {
         Actors.Push(mo);
         SlotCount++
      }
      else
      {
        Actors[SlotCount++] = mo;
      }
   }

ZScript internally does the 'requested size*2' stuff automatically, so it's not necessary to do it in the Add function.

NOTE: This does not mean that users of your class can use Push - that still must not be allowed. As you can see above, Push can only be used when the array is completely full, and you don't want your class users to have to determine that. It's best to just disallow Push externally.

Also, not to brag, but I must say that I've been programming for nearly 40 years, and I'm quite familiar with how every possible type of array works, directly, or via script, or in every other system I've ever encountered, and, believe me, I've encountered plenty. There's not much to it, really...it's not rocket science. I know how arrays are used in programming languages, and I know how the various languages actually store them in memory behind the scenes, and how they present them to the programmer, down to the machine language instructions that handle the input, output, resizing, etc. Please get that I absolutely do know how it works.

ZScript is doing a pretty standard array model, and it's doing it pretty well. ZScript arrays are fast, and they run on bare metal. Use them wrong, and it'll crash. Use them right, and they are quite fast. It's an implementation that I can appreciate.

You say "The fewer the iterations the better", but by not tracking the packed array size with a variable like SlotCount, you are doing way more iterations than necessary. Please understand this - I cannot draw any more ASCII diagrams to explain this - I did explain it more than once. Please, please study this until you understand. I have been trying to impress upon you how important it is to track the actual packed size (with SlotCount), which is going to be smaller than Size most of the time. And, if you Push when the packed array size is less then Size, you're adding Actors after the unused portion, causing many more iterations then needed. The Clean function will fix this, after doing maximum iterations, but you don't have to do maximum iterations.

I carefully wrote the code I gave you to perform the minimum iterations necessary, and it does that. This is not easy to accomplish - it requires careful stepping and tracking to run at top speed, and it requires a way to track the packed size (SlotCount). You simply don't get minimum iterations otherwise.

* Clean packs the array in a single pass, doing minimum iterations (if you use SlotCount).
* The Add function adds at SlotCount, which is super fast, and it keeps the array packed.
* Any custom function that wants to parse thru the actors will do (nearly) minimum iterations, if it uses SlotCount. (nearly, because there might be some NULLs until you Clean).

None of this is true if you use Size.

I am now devoted to helping you see exactly why tracking the packed size is so much faster. So, please, tell me how I can explain this so that you may understand. It's really neat code if you see how it accomplishes minimum iterations.

By the way, here's a version of Clean that conditionally purges dead monsters from the array:

Code: Select all

   //--------------------------------------------------------------------------
   // Clean - Packs the array by shifting destroyed actors out of the iteration
   //         range as quickly as possible.
   //  If RemoveDeadMonsters is != 0, dead monsters will be purged from the
   //   array as well.
   //--------------------------------------------------------------------------
   // Reorganizes the array so all nulls are moved out of the normal
   //   iteration range, leaving the used portion of the array tightly packed.
   void Clean(int RemoveDeadMonsters)
   {
      int OverwriteHead;

      int tail = SlotCount - 1;
      for (int head = 0; head < tail; head++)
      {
         if (Actors[head] != NULL)
         {
            OverwriteHead = (RemoveDeadActors && Actors[head].health <= 0);
         }
         else
         {
            OverwriteHead = 1;
         }

         if (OverwriteHead)
         {
            // got a slot to fill, now find something to put there
            while (tail > head)
            {
               if (Actors[tail] != NULL)
               {
                  if (!RemoveDeadActors || Actors[tail].health > 0)
                  {
                     Actors[head] = Actors[tail];
                  }

                  Actors[tail] = NULL;
                  --tail;
                  --SlotCount;
                  break;
               }
               --tail;
            }
         }
      }
   }

If you don't want dead monsters in your array, this will really reduce iterations. Note: You may have to modify it to check more than "health <= 0". I don't know what is required in ZScript to distinguish a dead monster from, say, a light post. But this version of Clean will remove dead monsters, and still do it with minimum iterations, and still completely pack the array, and adjust SlotCount.

I suggest that you create a global variable that you print to the screen, named TotalIterations. Add this line in every place where iterations are occurring: TotalIterations++.
Do this in your code that uses Size, and then do the same thing with my code.
Then, make a map with 5000 imps. Let it play for one minute, then kill all the imps. Notice how high TotalIterations gets with my code using SlotCount vs. your code using Size. I'm sure that will convince you.

Please tell me what I can do to explain why my code always does the minimum iterations. It doesn't get any faster than that. Please know that I'm not trying to be arrogant, but it's just doesn't get any better than that. You must track the packed array size if you want to do minimum iterations. That's what you said you wanted. That's what I'm giving you. I'm proud of the code - it's pretty darn tight. But it has to be used in it's entirety, or it simply breaks down. You cannot pull out the most important variable SlotCount, that seriously breaks everything. Why are you apprehensive of the variable that makes everything work?

Please tell me how to better explain it - I want to show you what makes it work - it's pretty slick. If you want, rename SlotCount to PackedSize - that's probably a better name, and it helps explain its purpose a bit better.

Honestly, I can't really spend more time on this, but I do want to help. Let me know: Are you still open to the possibility of believing me and trying my method, or am I just wasting my time?
The biggest joy of writing this code, and giving it to you, is for you to see how it accomplishes and maintains minimum iterations at all times, and how it does this as fast as possible. To pass this on to you and have you appreciate it would be the greatest joy possible for me. Let me show you how it works, so you can appreciate it too.

[kb1]

@kb1 I think it's safe to say that dynamic arrays in GZDoom work differently than how you're used to them. The fewer the iterations the better. That's why I go for sizing it down and just iterating through the whole thing. However, I do thank you for giving me the code for reorganizing the data, that most certainly has come to fruition. Coupled with sizing it down afterwards (which does affect the Size() function), this reduces iterations greatly.

The biggest thing I want to minimize is iterations. Those can be more costly than resizing the array by far.

Heh, alright, you got me. Took me long enough to figure it out. Here' I'm thinking you're being serious... you were just going to let me keep explaining forever, right? Man, that's not very cool - I spent a long time typing up those replies, making sure they added up and were factual and as accurate as possible. I can be pretty naive at times, especially when discussing coding.

Oh, well, joke's on me - probably funnier from everyone else's perspective Heh - take care.

[Kinsie]

release your source port kb1