search

rhelgeby / smprojectbase

Automatically exported from code.google.com/p/smprojectbase
0 stars 0 forks source link

Optimizing ADT arrays a bit #35

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
I've noticed that CreateArray has a startsize parameter.

The problem with dynamic arrays is that they really aren't dynamic. When 
we add an item and there's no space left it has to expand. That usually 
means copying the entire array into a new array with one extra element.

Then imagine adding elements one by one in some hot spots of the plugin. 
Once they get bigger there will be a huge performance hit. I don't know if 
the SourceMod version expand by 10 or 1 each time, but it's possible to 
make use of the startsize parameter.

If you can predict the array size in the long run (something like "I 
expect 40 elements") then set the start size. Directly reading and writing 
to elements doesn't have any performance hit, so that's no problem. I'm 
just worried when it needs to expand, but that problem is solved if a 
start size is set.

Original issue reported on code.google.com by richard.helgeby@gmail.com on 26 Feb 2010 at 7:54

GoogleCodeExporter commented 9 years ago 
However I don't know if GetArraySize will return the allocated size or the 
number of 
elements added. I bet the last one, but it should be easy to test.

Original comment by richard.helgeby@gmail.com on 26 Feb 2010 at 7:58

GoogleCodeExporter commented 9 years ago 
I think you misunderstand the startsize.  That controls the number of cells PER 
ELEMENT.  If you noticed it took a lot of work in modulemanager.inc to 
determine how 
much room I need per element.  Since I was storing arrays using an enum 
structure as 
elements, I have to know the max space that can be used storing data in the 
static 
enum array.

Ex:

enum ModuleData
{
    bool:ModuleData_Disabled = 0,
    bool:ModuleData_Hidden,
    String:ModuleData_FullName[CM_DATA_FULLNAME],
    String:ModuleData_ShortName[CM_DATA_SHORTNAME],
    String:ModuleData_Description[CM_DATA_DESCRIPTION],
}

#define MODULE_DATA_CELL_COUNT 1 + 1 + CM_DATA_FULLNAME + CM_DATA_SHORTNAME + 
CM_DATA_DESCRIPTION

That define just adds together all of cells used by each enum entry.  The issue 
with 
this in particular is in the project base, each manager is storing its own data 
in 
the same array.  So I have to keep track of how many cells are being stored in 
each 
one, and then using the biggest value for the startsize of the array.

Here's where I determine the startsize:

// Initialize the max block size to the number of cells needed for the module 
manager.
    g_iMMMaxBlockSize = MM_DATA_MAX_CELLS;

    // Now check each of the other base project files if they need more cells, and 
set the max to that if true.

    #if defined EVENT_MANAGER
        if (EM_DATA_MAX_CELLS > g_iMMMaxBlockSize)
            g_iMMMaxBlockSize = EM_DATA_MAX_CELLS;
    #endif

    #if defined CONFIG_MANAGER
        if (CM_DATA_MAX_CELLS > g_iMMMaxBlockSize)
            g_iMMMaxBlockSize = CM_DATA_MAX_CELLS;
    #endif

    #if defined LOG_MANAGER
        if (LM_DATA_MAX_CELLS > g_iMMMaxBlockSize)
            g_iMMMaxBlockSize = LM_DATA_MAX_CELLS;
    #endif

So the arrays should never have to expand, since I'm allocating enough memory 
for 
each element from the start.  If I don't allocate enough, weird things happen 
and 
garbage memory starts being read and bad things happen.  So it'll be evident if 
that 
happens.

GetArraySize returns the number of elements.

The only performance issue that could arise from them are natives like 
FindStringInArray and FindValueInArray.  But those are not used often, and the 
adt 
arrays should never become too big.  I use 1 adt array per-module and store 
their 
handles in a separate adt array.

Original comment by andrewbo...@gmail.com on 26 Feb 2010 at 11:19

GoogleCodeExporter commented 9 years ago 
Sorry I confused startsize and blocksize.

startsize just creates indexes on creation as opposed to using PushArray*()

I don't think I am ever pushing data unless stuff is being cached, or loaded.  
Optimizing load times isn't really necessary.  I'd rather shove as much 
processor use 
into loading stuff as we can.  ADT arrays are only read or written during the 
game, 
never expanded.

Original comment by andrewbo...@gmail.com on 26 Feb 2010 at 11:24

GoogleCodeExporter commented 9 years ago 
I found a better way to get the size of an array without needing defines;

stock array[enum];  // Dummy array to use sizeof() on.  'stock' stops the 
compiler 
warnings.
sizeof(array)

Original comment by andrewbo...@gmail.com on 27 Feb 2010 at 10:07

GoogleCodeExporter commented 9 years ago 
"Optimizing load times isn't really necessary."

If everyone thinks like that imagine how long time loading CS:S _really_ would 
have 
taken.

Here it actually IS possible to optimize a little bit by just giving the start 
size 
to CreateArray. In java the start size of a dynamic array is 10. In ZR I guess 
we 
need a start size of 30 (no. of modules).

It's the developer who have to predict the start size, not the plugin. Just 
make 
some defines for different array types with a start size. So setting the start 
size 
won't "steal" cpu resources during load time and other events.

Original comment by richard.helgeby@gmail.com on 27 Feb 2010 at 12:55

GoogleCodeExporter commented 9 years ago 
"When we add an item and there's no space left it has to expand. That usually 
means copying the entire array into a new array with one extra element."

Where did you get that info from?  I don't think the adt array API is just a 
wrapper 
around static arrays.

And about load times, this isn't a professionally made game, it's just a plugin 
for a 
game that has load times of under a second.  We'd be saving less than 100ths of 
a 
second by creating pre-made indexes.  I don't want to check when to use "Push" 
and 
when to use "Set", that's more checks the processor has to do.  Maybe not as 
much as 
if I allocated all the indexes on creation, but the opportunity cost (time) 
exceeds 
the benefit of changing it.

Original comment by andrewbo...@gmail.com on 27 Feb 2010 at 8:04

GoogleCodeExporter commented 9 years ago 
Static arrays are... static. They cannot change size. Dynamic arrays are static 
arrays too, but through its API it will expand the array when needed. By 
expanding I 
mean copying the entire array into a new bigger array.

I had a look at the source code for ADT arrays. In core/logic/CellArray.h 
there's a 
GrowIfNeeded function. According to this one the start size is 8, and allocated 
size 
is doubled each time more space is needed. So it won't copy the array as often 
as I 
thought.

I also looked at how it's done in Java (ArrayList class). There they expand it 
one 
by one. It appears that the SourceMod team did it in a smarter way by doubling 
the 
size instead so it doesn't have to expand that often.

Original comment by richard.helgeby@gmail.com on 28 Feb 2010 at 2:29

GoogleCodeExporter commented 9 years ago 
Yes I know what you mean by ADT arrays just being static but being re-copied, 
but I was 
just wondering why you thought that.  I didn't think ADT arrays were just 
normal arrays 
but just being recopied when adding an element.  I thought there may be some 
more 
elegant method that could be used in C++.

And that's good that it may not be as CPU intensive as initially believed.

Original comment by andrewbo...@gmail.com on 28 Feb 2010 at 4:31

GoogleCodeExporter commented 9 years ago 
The task finished here is changing the method of counting how many cells are 
needed for 
an enum-array.

Original comment by andrewbo...@gmail.com on 2 Mar 2010 at 1:36

GoogleCodeExporter commented 9 years ago 
lol I went over ADT arrays in C++ in class 3 days ago.  I'm surprised Java's 
default behavior is expanding by 1.  That's terribly inefficient.  We learned 
the doubling method and in C++'s STL you can even tell it the start-size and 
how much to grow by every time it hits the limit.

Original comment by andrewbo...@gmail.com on 27 Mar 2011 at 9:23

GoogleCodeExporter commented 9 years ago 
Java expand exponentially and start with an initial size of 10 elements. I 
don't remember where I got the expand by one from, but apparently I didn't read 
enough code.

It's an old discussion and no longer an issue because of mistakes. However, 
setting initial size to some arrays you know will be big will help a little bit.

Original comment by richard.helgeby@gmail.com on 27 Mar 2011 at 3:26