MODULE : dynamic arrays with direct memory access

[Monsieur OUXX]

Module : Dynamic arrays
Author : Monsieur OUXX
AGS version : 2.72 (but should be compatible with following versions!)


IMPORTANT NOTE: What Vector Class do you need?
- if you use AGS 3.0, you don't need any. It's built-in! (unless you want to be able to "point" at your arrays, then use this one)
- if you use a version previous to AGS 3.0 and need some easy-to-use and error-proof dynamic arrays with real unlimited size, use Monkey_05_06&HeirOfNorton's Vector classes.
- if you use AGS 2.72 or 3.0 or upper, are familiarized with pointers, and need some really fast (allocation and memory read/write) dynamic arrays, use this one. The maximum total size of the data you will be able to store is around 5Mb

Download   http://ottl.free.fr/ouxx/agsh/DynamicArrays.zip

Abstract

This script module implements a way to dynamically allocate some arrays within a big static array called “the memory”. It also provides functions to handle these so-called "dynamic arrays" (getSize, etc.) When an array is no longer needed, one can "free" it by calling FreeArray

Allocation and disallocation are quite fast ( in O(log2) ), and memory read/write is as fast as possible ( in O(1) with no function call needed)

Why are dynamic arrays so usefull?

Sometimes, it is useful to be able to refer to a variable not by its name but by a numeral value (its address / its pointer).



Once you have created a dynamic array, use its pointer :

·        You can pass it to a function as a parameter

·        Don't bother about where you create your arrays, or if there is still room in each array or in the virtual memory: when there's no room left, the engine tells you. Then you just have to increase the size of your virtual memory for your game to be stable.

·        You can create arrays of arrays (therefore multidimensional arrays)

·        You can use it to implement arrays of Vectors, Hashmap, Trees, etc. These could also be passed to functions as parameters (which can't be done with a normal “struct”)


How to use dynamic arrays

Code: ags

 //allocate the array
 ADDR myArray = AGSH_DynArrays.AllocArray(100); //arbitrary size

 //example of use : fill in the array with an arbitrary value
 int i=0;
 while (i < AGSH_DynArrays.GetArraySize(myArray) {
     memory[myArray+i] = 66;
     i++;
 } 

 //show what's inside the array
 AGSH_DynArrays.DisplayMemoryRaw(myArray, AGSH_DynArrays.GetArraySize(myArray));

 //free the array
 AGSH_DynArrays.FreeArray(myArray);

[Akatosh]

Sounds quite useful. It would have been cool to get more of a documentation, but I should be able to chew my way through 

[monkey0506]

Looking through the script I don't see any obvious advantage to using this over one of the existing dynamically-sized integer array modules. Seeing as that's all you've provided is integers.

I'm not saying that there's necessarily anything wrong with the module...and without actually testing it there's no way I could honestly say whether this would be faster than storing the data in a String and having to look it up; but the difference would likely be fractions of a second.

For my own purposes I have implemented a vector type that can store virtually any data type, ints, floats, Strings, and even Character*s, GUI*s, Object*s, etc. It uses the String-allocation method, but there isn't any kind of noticeable hit to the speed when I've used it.

The only real benefits of the String-allocation method over yours is perhaps that it saves memory by actually allocating the memory dynamically and it also allows storage of multiple types using a single method.

Interesting idea though.

[Monsieur OUXX]

For my own purposes I have implemented a vector type that can store virtually any data type, ints, floats, Strings, and even Character*s, GUI*s, Object*s, etc.

I know, these modules are VERY good and I was using them at the beginning, but I had to change the way I handle dynamic structures, and i'll try to explain why.

There is something missing there, and it seems that I haven't been able to explain clearly what it is yet : indeed, people keep asking me what is better in my module than in other Vector modules.

There is nothing "better", your modules are very elegant. But there is something missing, that is missing to the whole AGS script. It's not even really a feature, it's a concept.

the concept of dereferencing.

Explanation for nerds :

By using one of the objects you provided, I get a dereferencing level of 0. If i declare an object, i MUST call it by its name. This means I can manipulate what's inside the object, but not the object itself.

If i create an array of your objects, I get a dereferencing level of 1, because I can manipulate them by their index, without giving a name to every one of them. I just name the array. But then I still have to handle manually what cells of this array are free or used, what's its size, etc.

I need to be able to reach an unlimited level of dereferencing. Pointers of pointers of pointers of etc.

In C, you could write "int******* insanePointer;"

With my module, you can reach this level of derefencing.

Explanation for normal people :

Let's give a pragmatic example : with dereferencing, you can create some multi-dimensional arrays (int[][][]). 2-D arrays can be useful to create a table; 3D arrays can be useful if you do some 3-D (points in a 3-D space); 5-D arrays are useful if you create a 2-D table of 3-D points, etc. As you can see, a 5-levels dereferencing can be reached quite fast!



Note : I just added support for as many types as one wants.

[Rui 'Trovatore' Pires]

I'm a normal person, and I didn't get anything in this thread except for the 3D arrays. That I like.

But could you include some documentation as to how we can quickly set up a 3D array, please? Especially since I thought a 3D array would look like int[X,X,X], rather than int [X] [X] [X].

[Monsieur OUXX]

I thought a 3D array would look like int[X,X,X], rather than int [X] [X] [X].

It depends on your notation. Don't confuse int{1,2,3} (pseudo C-like notation), which is a 1-D array with 3 cells, and int[10][10][10] (C-like notation) which is a 3-D array with 10 cells in each dimension. You were probably thinking of the mathematical notation : int [][][] would be a matrix of 1 dimension with 3 scalars?

I like 3D arrays. Could you include some documentation as to how we can quickly set up a 3D array?

the code below would have to be gathered in a function, so that you'd reuse it every time you create a 3D array :

Code: ags

//creating a 2D array (widthxheight)
ADDR array2d= AGSH_DynArrays.AllocArray(width);
int i=0;
while (i < width) {
  memory[array2d+i] = AGSH_DynArrays.AllocArray(height);
  i++;
}

Then :

Code: ags

//calculating the address of cell at (x, y) :
ADDR cell = memory[memory[array2d+x]+y];

//then, set or get !
memory[cell] = ...;
return memory[cell];

[strazer]

Just a quick note to clarify that you can also do simulated 2D or 3D arrays without this module, as described here and here.

[Monsieur OUXX]

you can also do simulated 2D or 3D arrays without this module

Code: ags

array[x*width + y] = value;

My module works exactly the same way (it's always a story of y*width+x), but with no need of having a fixed width or height, nor a fixed total size.
Imagine you want to represent tables; you can insert a row or enlarge it with an extra column easily.

[Monsieur OUXX]

without actually testing it there's no way I could honestly say whether this would be faster than storing the data in a String

I was worried about that, so I tested it.

Once again, the point is not to show that my method is "better" - Monkey's "String vectors" should be used as often as possible because they are more elegant, more powerful, more error-proof - but in some cases speed and dereferencing are needed.

Here is the test code :

Code: ags

	int testSize = 10000; // the vector will store this number of values
	bool testWithVectorObject = true; // test with direct-memory-access vector or with String-based vector?
	bool testWithPush = false; //try expanding the vector by successive Pushs or set an initial size?
	int i=0;
	
	if (!testWithVectorObject) { // test with direct-memory-access vector
	
		ADDR vector = INVALID_ADDR;
		
		if (testWithPush) {  //try expanding the vector by successive Push
		  
			vector = AGSH_Vector0.NewInt(1,  5);
		
			i=0;
			while (i<testSize) {
				vector = AGSH_Vector0.PushInt(vector,  6666);
				i++;
			}
	
		} else {	//set an initial size to the vector to save some allocation time
		  
			vector = AGSH_Vector0.NewInt(testSize,  5);
			
		}
		
		//now, change the contents of the vector
		i=0;
		while (i<AGSH_Vector0.GetSize(vector, MEMSEG_INT)) {
			memory[vector+i] = 7777;
			i++;
		}
	
	} else { //test with complex iVector object
	  
		iVector testV;
		
		if (testWithPush) { //try expanding the vector by successive Push
			i=0;
			while (i<testSize) {
				testV.Push(6666);
				i++; 
			}
		} else {
			testV.SetSize(testSize); //set an initial size to the vector to save some allocation time
		}

		//now, try to change the contents of the vector
		i=0;
		while (i<testV.Size) {
			testV.Set(i, 7777);
			i++;
		}
	}

Results on a 3GHz computer : (wether testWithPush is true or false) :


METHOD               |    String allocation      |     direct memory acces

allocation time       |              10s                 |                <0.5s
time to set values |              6s                   |                  <0.5s


Note 1 : this test is made with an non-fragmented memory (in the "direct memory access case"), this speeds up the process a lot, but I doubt fragmentation causes a 17-times rate slowdown.

Note 2 : this test may contain an obvious error (I hope not). If so, don't think I'm not honest with you; just tell me and I'll test again.

[Scorpiorus]

Great work here, having fast dynamic arrays may surely come in handy

[monkey0506]

Just to be clear, I never meant to contest your module. I was simply stating that from my POV the only advantage would be increased speed, yet there would be a higher file size.

So the real question for the end-user then becomes whether they need faster-access or smaller file size/more flexible memory allocation.

I think this module is definitely a good thing. The String-access method is clearly slower, so it's nice to have a faster alternative for those who may need it.

[Monsieur OUXX]

the only advantage would be increased speed...

...and infinite dereferencing! Increased speed is only a cool side-effect. I won't give up with the dereferencing issue, since it's why I decided to code this module. 



Concerning the file size, since there are only zeros, here is the compression rate i got :
7MB --> 500kB

This is why I finally considered that this unpleasant side-effect wasn't really relevant.

[monkey0506]

And Chris just went and implemented dynamic arrays into 2.8 beta 5. Hahahah...gotta love when he does that to ya. 8)

I mean...for 2.7 - 2.72 it'll be good...but that's as far as you get. We get. I wrote modules for this too...BLAST!

[Monsieur OUXX]

And Chris just went and implemented dynamic arrays into 2.8 beta 5.

Blast it! Haha, never mind, in fact it's cool, because as you may have noticed, I'm writing all these strange modules to use them as lower layers in my big AGSH module. And when I write them, I keep in mind that they should be replaced by native features as soon as they get implemented.

--> I was pretty sure that dynamic arrays would appear one day (but no so soon ), and I'm also absolutely sure that true OOP will be implemented in the future. When it'll happen, i'll adapt my code to englobe this new feature.

I'm looking forward to see how these new built-in dynamic arrays work!

Dynamic arrays don't change anything to the dereferencing problematic. They only remove the "fixed-size virtual memory" limitation. Now, my dynamic arrays can be used within an "unlimited virtual memory", that's all.

I don't mean to be rude, but even if this new feature is absolutely essential (thanks to Chris!), an int[] still cannot be used as in out parameter which is what i'm trying to do fo all the reasons I gave previously.

[monkey0506]

Well I suppose that you would still have to use some sort of custom function (i.e., the module's functions) to get the dereferencing feature. But as for the actual issue with dynamically-size arrays, at least you'll be able to get that small filesize.

[Scorpiorus]

Built-in dynamic arrays are now really necessary to have, since AGS moves towards removing the limits on the total count of its entities and it is not now feasible to use AGS_MAX-style #defines to set array size.

[Monsieur OUXX]

at least you'll be able to get that small filesize.

Yes, this is neat.

[realet]

First off, THANK YOU for supporting the concept of dynamic hashes in memory with AGS. This is exactly what I need.

I'm having a little trouble compiling the script with AGS 2.72. I'm getting an invalid operator error on:

  AGSH_Memory.SetAt(array+ARRAY_SIZE_INDEX, size);

Looks like mixing a signed integer with type ADDR isn't working.

Have I:

a.) used the wrong version of AGS with this script?
b.) used the wrong version of your script?
c.) or do I just need to cast between data types for this call and for the GetAt call immediately following in order to fix? Is type casting supported in AGS scripting?

Again, thanks!!

realet (Tom)

[Monsieur OUXX]

  AGSH_Memory.SetAt(array+ARRAY_SIZE_INDEX, size);

Looks like mixing a signed integer with type ADDR isn't working.

Have I:

a.) used the wrong version of AGS with this script?
b.) used the wrong version of your script?
c.) or do I just need to cast between data types for this call and for the GetAt call immediately following in order to fix? Is type casting supported in AGS scripting?

Quick answer (I'll look more precisely into it soon) :
- If you only need a dynamic array, use AGS 3.0, since they are built-in, and if you use AGS 2.72, use monkey's Dynamic Arrays module. Use my module only if you really need to "point" to an array, to handle it for special features.

- It's the only version of my script that I released, so there should be no version issue. But the source code and the FAQ/how-to may differ since I'm not serious. See below for clues of WHERE it could differ

- ADDR is int. It's the same type. ADDR is just a macro --> no cast issue

The compilation error is IN the module? Or in some custom code of yours? Is it possible that I posted a non-compiling version?

As I know me, I could have done such mistake... 

If the error is in your custom script, don't use SetAt, direct-access the memory by using memory[array+offset] = value, it will be more efficient.

[Monsieur OUXX]

Is it possible that I posted a non-compiling version?
As I know me, I could have done such mistake... 

Shame on me, when I exported my module I ripped off all macros definitions related to Arrays, including ARRAY_SIZE_INDEX,etc.
So, the operator error comes from the fact that one of the operands (the macro) hasn't been declared!  :

--> You won't be able to use the module, unless I re-export this version correctly, which I doubt I do, since the module changed A LOT since.   

But I'm almost done releasing the new version (the arrays and Vectors seem to work, I just have to debug the Hashmap)