• Hey Guest! Ever feel like entering a Game Jam, but the time limit is always too much pressure? We get it... You lead a hectic life and dedicating 3 whole days to make a game just doesn't work for you! So, why not enter the GMC SLOW JAM? Take your time! Kick back and make your game over 4 months! Interested? Then just click here!

Why does everyone use ds lists/grids, and why are they better than arrays?

E

elsi11

Guest
Hey guys!

I like arrays. You got 2 types. one has 1 number in the brackets, the other has 2 numbers. They hold values and they look like a grid. Easy peasy. But I see high-level code almost always using ds_something. I understand you can shift values or something in them, and I suspect that in a ds grid, you can have variable length of rows and don't waste ram if one row has 100 entries and the others just 1.
But I still don't get it. Why? Are there special kind of situations where this is good? I know for sure that you will use ds_lists in a save/load system. What's wrong with a local array as an intermediary? I see how the ds_grid shuffle function would be useful for randomizing a result of a gamble where certain items have a lower/higher chance to get picked (the super rare item has only 1 space in the grid, while the basic ones occupy like 20 spaces), but I'm also sure you could do this with a small script for arrays.
I dunno.
I never used them because they look hard, and I'm 50% sure they are more intensive than arrays.
Explain this to me.
Tnx! :D
 

Hyomoto

Member
Data structures are not a magic bullet, and in many cases arrays are simpler and sometimes faster to use. There are a few reasons people prefer them:
1) They can be accessed easily by their "id" and shared between objects and rooms. Arrays can be tricky, if not outright unreliable, to reference from different locations. You can share the id of a data structure and be assured the contents are identical no matter where or how they are accessed, they are also preserved between rooms since all data structures are "persistent".
2) There are some built-in functions such as sorting, clearing and saving many people find useful. Also they'd dynamically resize, so deleting a value resized the whole structure where appropriate.
3) Arrays, lists and grids are very similar, but stacks, queues and maps have unique qualities that make them more useful than arrays.

In short, data structures are often overused in my opinon. Many people outright prefer them, however there are times when they are not just appropriate but outright better. But like any system, they are what you make of them. If arrays get it done for you, that's fine.
 
E

elsi11

Guest
"data structures cause memory leaks unless you destroy them"
ლ(ಠ_ಠლ)
Ain't nobody got time for that.
Array memory gets reallocated as soon as nothing is referring to it.
And I can't imagine myself being in need of such data gymnastics that I would take chances.
Thanks for reinforcing my prejudices :p
Arrays are the best
 
@elsi11

minor quible here: "Array memory gets reallocated as soon as nothing is referring to it."

I have found that is not always the case. Creating arrays and "destroying" them too quickly can cause gamemaker's garbage collector to fall behind eventually leading to degraded performance. I don't know whether the same thing can happen with data structures.

I don't end up using grids too often, so I wont comment on them. But for lists, there are certain kinds of tasks for which lists are bettter suited than arrays. For example, randomly adding unpredictable numbers of items into the structure, or inserting items somewhere in the middle of the structure.
 

Hyomoto

Member
@elsi11 - You shouldn't just write them off. If you don't need them, you don't need them. However, there is one aspect of arrays that make data structures almost vital:
Code:
this.array[ 0 ] = [ one, two, three ];
that.array[ 1 ] = this.array[ 0 ];
What does that.array[ 1 ] contain? A pointer to the array? A copy of the array? The actual array? Who knows? GM2 certainly doesn't, and neither do you. In a case where multiple objects might need to access or pass around the same data, a data structure is superior in all ways. As I said before, they also have some behaviors that make them useful. Stacks for example are much easier to use in hierarchical states than arrays, queues are superior when dealing with... queues, and lists and maps can be resized without having to rebuild the entire data structure, something arrays must do. This is a pretty massive benefit, making lists ideal when the contents of your list may change. Additionally grids are not ragged like 2d arrays, and also will not crash if you access outside their boundaries. These are all behaviors you could implement with arrays, but unless you just like reinventing things that already exist, there is a benefit in adding them to your toolbox.

You have to use what you are comfortable with, but while I'm not going to say they are vital they are damn useful when used in the right place. Just like arrays.
 
I

icuurd12b42

Guest
>Array memory gets reallocated as soon as nothing is referring to it.
You mean as soon as you set every variable that references the array to to 0 otherwise it leaks.

That alone is why I stopped using them for anything complex
 
H

Homunculus

Guest
>Array memory gets reallocated as soon as nothing is referring to it.
You mean as soon as you set every variable that references the array to to 0 otherwise it leaks.

That alone is why I stopped using them for anything complex
Can you elaborate that? I assume that array memory gets cleaned when references are set to zero or all the variables are destroyed (in the case of a temporary array in a local variable or instance variable in a no longer existing instance). In which case does it leak?
 
I

icuurd12b42

Guest
Can you elaborate that? I assume that array memory gets cleaned when references are set to zero or all the variables are destroyed (in the case of a temporary array in a local variable or instance variable in a no longer existing instance). In which case does it leak?
In theory that how it should work. in reality you must set the variable to 0 after your are done using the array. even arrays in arrays! which becomes a hge pain...

Yoyo may have fixed the huge leakage issue, but as they say, once bitten...

that alone makes array way more trouble to manage than lists.
 

Niels

Member
Arrays are kinda limited in GM. Ds_lists and grids have a lot of extra functions that allow them to much more flexible.
 

Juju

Member
Thanks for reinforcing my prejudices
Might wanna have a watch of that talk to see why learning data structures is a path to more robust code - code that is suitable for commercial projects.

Who knows?
It's a pointer to the child array - the one inserted into the 0th element of the parent array.

GM2 certainly doesn't
Yes, it does. Open up the debugger and have a look. Variables defined as arrays are handled internally by GameMaker as pointers to arrays.

a data structure is superior in all ways.
No, they're not. I usually prefer to use data structures but arrays have their uses. Main example that I give is returning multiple values from a script. Doing that with a list is clumsy.

lists and maps can be resized without having to rebuild the entire data structure, something arrays must do.
I believe lists are implemented as arrays internally by GameMaker and, as such, when you resize a list you're reallocating memory in the same way as an array (I think that's what @Mike said, it'd be grand if he could confirm that). It's certainly true that you can't resize an array to be smaller, and that's a bit frustrating, but it rarely comes up.

also will not crash if you access outside their boundaries.
...which makes it annoying to find an out-of-bounds access for a grid deep in your code because GameMaker doesn't report where the warning has occurred. Hard stops are sometimes preferable to soft warnings when debugging code.

otherwise it leaks.
Not seen that, but I've not gone looking for it. I use arrays quite sparingly (and 90% of the time as local variables) so that's likely a factor. Ditto did have odd behaviour with a globally scoped array not clearing itself on PS4 recently, but I think that was a bug in YYC rather than a structural issue with GML as it worked as expected on Windows YYC and PS4 VM.
 

GMWolf

aka fel666
I think the main advantages with data structures are the fancy functions it offers.
Also the strict size makes it easier to catch errors.
Not being garbage collected is probably a performance benefit, but since they are reference counted I don't think it's a big deal.

Other than that, arrays are more convenient.
 
I

icuurd12b42

Guest
Not seen that, but I've not gone looking for it. I use arrays quite sparingly (and 90% of the time as local variables) so that's likely a factor. Ditto did have odd behaviour with a globally scoped array not clearing itself on PS4 recently, but I think that was a bug in YYC rather than a structural issue with GML as it worked as expected on Windows YYC and PS4 VM.
Looking at the video, I assumed you were aware of this, in the repeat a billion time, set array and finally set array to undefine... slide

I do agree it's more of a bug than a language issue. you should not require to set the array back to 0 or undefined when done.
 

Hyomoto

Member
Might wanna have a watch of that talk to see why learning data structures is a path to more robust code - code that is suitable for commercial projects.

It's a pointer to the child array - the one inserted into the 0th element of the parent array.

Yes, it does. Open up the debugger and have a look. Variables defined as arrays are handled internally by GameMaker as pointers to arrays.
Hey, try doing this:
Code:
this.array[ 0 ] = [ one, two, three ];
that.array[ 1 ] = this.array[ 0 ];

var _this = that.array[ 1 ];

_this[ 0 ] = four;

this.array[ 0 ] = _this;
Let me know how that turns out for you. The expected outcome would be this.array[ 0 ] and that.array[ 1 ] have the same pointer to _this and therefore should all be identical. It's my experience this is not the case. If it's been fixed, great. But I've posted bugs and talked to @Mike about this scenario, for someone who claims to barely use arrays you'll excuse me if I don't just take your word for it.
No, they're not. I usually prefer to use data structures but arrays have their uses. Main example that I give is returning multiple values from a script. Doing that with a list is clumsy.
Cool, and my comment was there are places where data structures are better than arrays. In this case situations where you needed to pass the same values between objects or scripts. As in a list of items that should be shared. You could use an array for this, but your response here has to do with returning multiple values from a script and nothing to do with what I was talking about. I'm just trying to bring you back from out in the weeds.
I believe lists are implemented as arrays internally by GameMaker and, as such, when you resize a list you're reallocating memory in the same way as an array (I think that's what @Mike said, it'd be grand if he could confirm that). It's certainly true that you can't resize an array to be smaller, and that's a bit frustrating, but it rarely comes up.
Me: "there's no simple way to delete values from an array, lists and maps are good ways to deal with that situation." You: "That barely comes up." That's good to know: hey while you are out there in the weeds again you want to pick me up some mushrooms? Because last I checked GM has no functional equivalent when it comes to arrays:
Code:
ds_list_delete( list, position )
Now, it's possible internally it's the same thing and by my wording I suppose that's fair. I don't know. But it also doesn't change the fact that there is no simple way to delete values from an array, ds_lists have a built-in function for it and you would have to manually rebuild an array. It's almost like that's what I said. But here's a hammer and some nails if you want to build a house since you apparently live out there now.
...which makes it annoying to find an out-of-bounds access for a grid deep in your code because GameMaker doesn't report where the warning has occurred. Hard stops are sometimes preferable to soft warnings when debugging code.
I never said anything about this, I simply said it was true. Which it is. Grids will allow you to access outside their boundaries without crashing. I see your house is coming along nicely. Hey, not to mention I've made this same argument before. The difference is I made it during discussions about error handling where it was appropriate, not when talking about the features of data structures.
 

DeScruff

Member
In theory that how it should work. in reality you must set the variable to 0 after your are done using the array. even arrays in arrays! which becomes a hge pain...

Yoyo may have fixed the huge leakage issue, but as they say, once bitten...

that alone makes array way more trouble to manage than lists.
Wait... Does that include local temporary arrays? Like if I made a
Code:
var tmpArray[4] = 5;
// End of script
Or will the fact they are local variables clear the thing without a problem?
 
I

icuurd12b42

Guest
Wait... Does that include local temporary arrays? Like if I made a
Code:
var tmpArray[4] = 5;
// End of script
Or will the fact they are local variables clear the thing without a problem?
I personally set the array to 0 when done, unless it's a function that returns it. simple use

Main issue is the moment you assign the array to multiple vaiables is usually where the leak happen. so without wanting the take ANY chance, I personally always set the array variable to nothing

Let me know how that turns out for you. The expected outcome would be this.array[ 0 ] and that.array[ 1 ] have the same pointer to _this and therefore should all be identical. It's my experience this is not the case. If it's been fixed, great. But I've posted bugs and talked to @Mike about this scenario, for someone who claims to barely use arrays you'll excuse me if I don't just take your word for it.
each variable that reference the array point to the same array instance. until you modify the array without using the @ assessor, which basically is what your example does... if you modify the array without the @ accessor, that array with a modified entry is new, and only that variable referencing it has that array.

It's TOTALLY messed up, I don't agree with this behaviour, it's silly and I personally have never encountered a language that acts like that with arrays.
 

DeScruff

Member
I personally set the array to 0 when done, unless it's a function that returns it. simple use
Main issue is the moment you assign the array to multiple vaiables is usually where the leak happen. so without wanting the take ANY chance, I personally always set the array variable to nothing
Welp. Sounds like I should start adding some array cleaning lines, I don't use temporary arrays that often, but I'd rather not have the possibility for a leak on something that runs every couple of steps... Thank You.
 

GMWolf

aka fel666
It's TOTALLY messed up, I don't agree with this behaviour, it's silly and I personally have never encountered a language that acts like that with arrays.
Yeah I'm not a fan either.
But it was done this way for backwards compatibility reasons.

I usually dont have many issues with arrays, but as soon as my algorithms get more complex than a couple scripts, I immediately have to drop the project ans use Java/C++ for it, simply because Keeping track of what array indices do what, what scripts created what data structure etc becomes a little too complex.
 

NightFrost

Member
One (another?) big problem with arrays is how we don't have something even so simple as in_array(needle, haystack) to operate them, you have to write everything yourself. Another handy thing missing is any iterative command like foreach(A in B){ ... } which would be very useful if made to work with one dimensional DSes too (consider the current clumsy implementation of iterating through a DS map).
 
E

elsi11

Guest
Ok, guys, I need backup. Tell the other guys how arrays are super good, and ds stuff is even more unreliable with the memory stuff and things :D
 

Nux

GameMaker Staff
GameMaker Dev.
I like to use 1D arrays as "structs" to store a group of similar values, e.g. a rect structure as [left,top,right,bottom] instead of objects or data structures because:
  1. Overhead from objects
  2. I've heard arrays are faster than lists and maps
However, if its a constantly changing data source then just use data structures because they're robust and are far more optimised if you use the built-in functions.

The only use for 2D arrays I can think of is to store additional data about an existing value, such as local and world coordinates. If you're thinking of using 2D arrays for collisions: I would just use ds_grids because they appear to be faster, and have a abundance of useful functions to make your life easier.
 
H

Homunculus

Guest
Ok, guys, I need backup. Tell the other guys how arrays are super good, and ds stuff is even more unreliable with the memory stuff and things :D
Are you serious? This is not a football match where you have to choose and cheer a team. Good developers know the pros and cons of both arrays and ds, and use them both according to the problem they need to solve. If you just stick with one approach because “stuff” you are just limiting yourself.
 

DesArts

Member
Neither are better. One is just simpler for simple things, and other is simpler for more complex things.

If I need a list of data which is collected from elsewhere and then read from, I'll use arrays, both temporary or local.
If I need a list of data which will be written to and read from more than once, and change in any significant way (like adding or removing entries, or it will have a changing length, etc) then the obvious choice is a list/grid.

For example - if you make an undo/redo system for an editor, and you keep a list of strings to read from (each string being a snapshot of the editor every time an action is completed). If you undo a few times, it goes down the list and retrieves the editor data from that row. If you are lower down in the list and perform a new action, you need to remove all the data that was above your list position so you're now at the top.

You can do these more complex things with arrays, but if you're after ease of use - ds_* is the way to go.
 

TheouAegis

Member
Grids are rectangular in shape, 2D arrays aren't. That's my argument in support of 2D arrays.

I don't like the extra crap I have to do in later versions of GM to get arrays to work right sometimes, but that's me.


And everyone's neglecting buffers here. Fastest maze generation codes I ever ran used buffers instead of ds_* sets and used less memory than arrays. And that was before I even understood how to use buffers.
 
ლ(ಠ_ಠლ)
Ain't nobody got time for that.
Array memory gets reallocated as soon as nothing is referring to it.
And I can't imagine myself being in need of such data gymnastics that I would take chances.
Thanks for reinforcing my prejudices :p
Arrays are the best
I like that I can reset an array just by array_name = 0;

I still use lists and grids for more complex things, but I'd have to say 99% of the time an array is all I need.
 

Joe Ellis

Member
I use arrays all the time, the only other thing I use is buffers when I need to save an array to a file.

I think it all depends on what you would rather use yourself, unless you're doing really intensive stuff like a 3d modelling program (like me) or constantly rebuilding\editing the ds\array every step, you could use whichever you find easiest, the speed difference won't be that much unless you're dealing with hundreds, maybe thousands of objects, for instance vertices & triangles (like me) I had to start using arrays cus data structures were way too slow for this.

An interesting thing I've found though from making my own functions that edit arrays is that there are alot of useful things that could be part of the ds functions that gm doesn't have yet, for instance, excluding a value from a list, merging 2 lists with none identical values, adding something to a list if it doesn't exist in it already, and deleting multiple indices of a list all at once, alot of these things are essential to what I'm doing.

An observation of mine is that all data structures are arrays, even ds_maps how they're 3d and gm can't handle 3d arrays, but really, every multidimensional array is a group of 1d arrays.. try making a 2d array with [0, 11] = 0, [1, 10] = 0... try reading [1, 11] and you'll get an out of bounds error, thats cus really, each first column is another 1d array, with the length being the furthest index in the second column.

Another observation is that pretty much everything that involves memory is an array, a texture is an array of colors, a byte is an array of 8 bits,
this makes me think, "array" is just a word, so whatever way gamemaker lets you deal with memory, its up to you how you use it.
 
E

elsi11

Guest
Are you serious? This is not a football match where you have to choose and cheer a team. Good developers know the pros and cons of both arrays and ds, and use them both according to the problem they need to solve. If you just stick with one approach because “stuff” you are just limiting yourself.
I get what you are saying, but literally every post between my last post and the one before that was an array hating match, going even so far as implying that you need to destroy arrays and set them to 0, or some magical memory leak will happen somewhere. I mean, cmon. If I ever needed to set the array to 0, it would have been a local variable anyway, at which point, the variable and the pointer would be automatically destroyed, no?

The only use for 2D arrays I can think of is to store additional data about an existing value, such as local and world coordinates.
I just recently used them for a menu, but I'm thinking about just making several 1D arrays. (I did research where I saw that accessing a 2d array value is 27% slower than 1D) (inb4 people telling me that ds stuff is god-given for menus because of how easy it is to implement and maintain :p)

Grids are rectangular in shape, 2D arrays aren't. That's my argument in support of 2D arrays.
I'd hate to question this statement that supports arrays, but I was under the impression that ds_stuff has the freedom to make any row as long or short as it will. And also, I thought that any 2D array is by definition rectangular, and if you put 100 values in the first row, and 1 in the second, you just wasted 99 spots of reserved memory because 2x100 were reserved. What do you say to that? Sounds pretty rectangular to me.
 
I

icuurd12b42

Guest
You can NOT believe the arrays leak if you want :)

Hre' my take....
I Like arrays as a replacement for GM's lack of data structures... confusing statement..

but say in c
typedef struct (
int x;
int y;
int z;
} VECTOR;

VECTOR t = {10,10,10};

in javascript
t = {10,10,10};
or
t = [10,10,10];

in gml
t = [10,10,10];

and compound structures
typedef struct {
VECTOR pos;
COLOR col;
} VOXEL;

VOXEL t = {{10,10,10},{255,255,255}};

in gml
t = [[10,10,10],[255,255,255]];

in 1.4 you need a function that creates an array from argument
t = MakeArray(MakeArray(10,10,10),MakeArray(255,255,255));

As far are 1d array, I do prefer ds_lists. they are about as efficient as array and almost identical in use with the list[|i] accessor. and they don't effing leak unless you forget to destroy them PERIOD
 
I thought that any 2D array is by definition rectangular, and if you put 100 values in the first row, and 1 in the second, you just wasted 99 spots of reserved memory because 2x100 were reserved. What do you say to that? Sounds pretty rectangular to me.
Interestingly enough, 2D arrays in GML are not necessarily rectangular/square.

Documentation to the rescue:

It is also worth noting that the length of each 2D array can be different, so you can have an array with a height of 2, but entry 0 could be 2 in length, entry 1 could be 4 in length and entry 2 could be 3 in length:
 
I

icuurd12b42

Guest
2d arrays are basically 1d arrays in a 1d array, so that allows varying sizes per row
 
H

Homunculus

Guest
2d arrays are basically 1d arrays in a 1d array, so that allows varying sizes per row
That is in fact an advantage in terms of memory with respect to ds_grid. Although I can’t really imagine a situation where you want this to happen...
 
I

icuurd12b42

Guest
That is in fact an advantage in terms of memory with respect to ds_grid. Although I can’t really imagine a situation where you want this to happen...
Yeah, in 30 years of programming I rarely actually encountered a situation that required the use of a 2d array of common fixes rows and columns. The fact that 2d arrays are not even in Javascript makes me suspect that the concept is going the way of the GOTO....
 
E

elsi11

Guest
You can NOT believe the arrays leak if you want :)
I believe that may have been true in the olden days. I'm willing to test it out if you tell me how. Also, maybe someone can summon some yoyo guy who is "in the know" so he can tell us: "oh, yea, we fixed that in 1.2".. or smt..
In one of my posts, some official guy came and assured us that arrays are super good any easy and you can't have problems with them.. Though, I'm having trouble navigating those things..
Here, I found it.
When arrays fall out of scope (ie. nothing references them anymore) their memory gets freed and becomes available to the program again - meaning you don't need to worry about freeing arrays like you would with data structures
 
I

icuurd12b42

Guest
I believe that may have been true in the olden days. I'm willing to test it out if you tell me how. Also, maybe someone can summon some yoyo guy who is "in the know" so he can tell us: "oh, yea, we fixed that in 1.2".. or smt..
In one of my posts, some official guy came and assured us that arrays are super good any easy and you can't have problems with them.. Though, I'm having trouble navigating those things..
Here, I found it.
You can ask Russel, he's the one who told me how to fix my array leakage setting it to 0... I did mention it's possible the array leaks are fixed. and I did imply I don't trust yoyo on this even with Jobo's quote, given that's post simply states how it was supposed to work in the first place!!! does not mean they fixed the issue
 
E

elsi11

Guest
You can ask Russel, he's the one who told me how to fix my array leakage setting it to 0
Ok, so how does this work? Is 0 a special number or is it only about breaking the pointer from the variable? Can I use -1 or 2, or "banana" ?
Do I have to do it even with local variables? Even if the object is destroyed?
How does that even happen? Dead variable magically still holds pointer and keeps the memory space alive?
How to test it? Create 100 local arrays each step, let it run for 5 mins, and watch "RAM used"?
 

Bentley

Member
What's the scare about data structures though? You just destroy them when you're done with them. But maybe I'm missing something.
 
I

icuurd12b42

Guest
Ok, so how does this work? Is 0 a special number or is it only about breaking the pointer from the variable? Can I use -1 or 2, or "banana" ?
YES! setting a variable that was referencing an array to anything forces the garbage collector to react. Basically this whole mess started because the garbage collector was failing to detect it could free up the array.
Do I have to do it even with local variables? Even if the object is destroyed?
I do it everywhere, I implied I do not trust the garbage collector so I do what russel told me to do when I hit the problem. You may not do this if you wish and everything works fine for you. Then if things go south you can spend hours fixing it... I'd rather add the darn extra line right off the bat and be done with it.
How does that even happen? Dead variable magically still holds pointer and keeps the memory space alive?
Basically, the garbage collector is supposed to detect the reference count has dropped to 0 and free the memory that was allocated. The problem is the garbage collector seems to fail doing its job, either the reference count never gets back to 0 or the actual routine that frees memory is not executed (in every possible scenario) do you are left with memory that is never freed. setting the array reference to 0 (or anything) forces the garbage collector to react
How to test it? Create 100 local arrays each step, let it run for 5 mins, and watch "RAM used"?
[/quote]
Basically you will find post where people complain about the memory growing over time to the point where you get a memory error and the game quits and they come here for a solution... usually the error is because they are using arrays... or ds_lists without calling ds_destroy(). these are the 2 main reasons for the error.

ALRIGHT, so I'm done with repeating myself
1) I stated there was issues with leakage
2) I stated russel showed me how to fix it
3) I stated Yoyo May have fixed it
4) I Stated I don't know and don't trust if they did
5) I stated I do it, it's my choice, because I prefer to be safe

Now leave me the eff alone
 
S

seorin

Guest
And everyone's neglecting buffers here. Fastest maze generation codes I ever ran used buffers instead of ds_* sets and used less memory than arrays. And that was before I even understood how to use buffers.
I'm curious about this. I believe what you're saying, but my own testing showed arrays to be faster, and I'm wondering what the difference is in our results.

I was storing tile height data in an array and decided to try a buffer to see the speed difference. The fast buffer type was barely faster than fixed, fixed was faster in practice because rarely one of the values would be -1 and it was far slower to check for 255 and change it back when pulling the data out, and arrays were notably faster than either. I kept it as a buffer since it's better on memory usage and I can always change it again later if I need to when optimizing, but I was a bit disappointed to find it slower when I was expecting a speed increase.
 

TheouAegis

Member
Buffers are usually slower, but I was requiring so many reads and writes each step that the buffer ended up winning out in the end for one of my projects. I dunno why, it just did. Like, it went from 1 second to proc gen a room down to nearly instant for a room twice as large.
 
Top