• 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!

Legacy GM [solved]What are the differences between data structures?

Hi.

I am using as ds_list to store instance ID's as part of my AI. The list is created at the 'create' event, cleared then repopulated during normal steps, and then destroyed in the 'Destroy' event.

THE SHORT VERSION OF MY QUESTION WOULD BE:
depending on the size of this structure which is most beneficial for just storing id's? a ds_list, array or a buffer? (could a buffer hold such data?)

THE LONG VERSION OF MY QUESTION WOULD BE:
An alternative of doing this with an array seemed slightly slower - but I would I be right in thinking it's better memory management specifying the exact length of the array, than having a permanently open ds_list that expands as necessary?

Then I read about buffers...and that confused things for me (I'm easily confused...) as it's yet another data structure. What are the benefits over using an array - speed? memory size?

If anyone has the time to give me a basic explanation it would be appreciated.

EDIT:
I thought I'd include the code to show what I'm doing. The number of entries into a buffer would be known, as it would be the size of the ds_priority after it has been filled. If an id can be stored in a buffer, would it be faster and more efficient than a ds_list?

(sorry if this looks messy - I don't usually do my code like this, and have tried to make it how people prefer to read it)

Code:
if (current_state==states.object_test)
{
state_is="object test";
   if path_position==1
   {
   if path_exists(get_path)
       {
       path_delete(get_path);
        }
        path_position=0;
    }
var num,bbox,cur_x,cur_y;
num=instance_number(object12);
ds_list_clear(object_list);
bbox=bbox_top;
cur_x=x;
cur_y=y;
if num > 1
{
var b,hit2,dist2;
      for (b=0;b < num;b+=1)
     {
     hit2=instance_find(object12,b);
     if hit2!=id
         {
         dist2=point_distance(cur_x,cur_y,hit2.x,hit2.y);
         if (dist2 < 200)
             {
              if ((hit2.bbox_bottom) >= (bbox))
                 {
                ds_priority_add(dist_list,hit2,dist2);
                 }
             }
          }
        }
var size,index,dist;
size=ds_priority_size(dist_list);
if size > 0
    {
    for (index=0; index < size; index+=1;)
       {
      dist=ds_priority_delete_min(dist_list);
       object_list[| index]=dist;
        }
     }
size2=ds_list_size(object_list);
current_state=states.path_test;
}
else
{
current_state=states.set_alarm;
}
}
 
Last edited:
A

ArendPeter

Guest
Hello,
First off I don't have much experience with buffers either so I can't really make a judgement there.
For arrays vs lists it depends how you manipulate object_list later on.
Since Game Maker's list supports an insert operator I'm guessing that it's implemented using a linked list. (arrays don't work well for that, and it would be strange to use arrays when they already have support for arrays on their own)
Insertion with lists is much faster than with arrays because arrays have to move a lot of memory around whenever you insert (possibly the entire thing if you insert in the front), lists don't require shifting memory regardless of how large the list is.
For searching items by their id, lists iterate from the beginning (or maybe also end) to find items in the list when you search them. So if you do ds_list_find(object_list,5) it iterates through the first 5 items to find the one you're looking for. Arrays on the other hand can directly search items by id. So this makes arrays much faster for this purpose.

TLDR

If you're doing more searches use arrays
If you're doing more insertions use lists
 
T

TimothyAllen

Guest
Hello,
First off I don't have much experience with buffers either so I can't really make a judgement there.
For arrays vs lists it depends how you manipulate object_list later on.
Since Game Maker's list supports an insert operator I'm guessing that it's implemented using a linked list. (arrays don't work well for that, and it would be strange to use arrays when they already have support for arrays on their own)
Insertion with lists is much faster than with arrays because arrays have to move a lot of memory around whenever you insert (possibly the entire thing if you insert in the front), lists don't require shifting memory regardless of how large the list is.
For searching items by their id, lists iterate from the beginning (or maybe also end) to find items in the list when you search them. So if you do ds_list_find(object_list,5) it iterates through the first 5 items to find the one you're looking for. Arrays on the other hand can directly search items by id. So this makes arrays much faster for this purpose.

TLDR

If you're doing more searches use arrays
If you're doing more insertions use lists
You're making a whole lot of assumptions here. In GMS1 lists are nearly identical to arrays in speed when iterating over the list. I do not think (though dont know) that a list is implemented via a linked list. Deleting index 0 is much slower than deleting the last index... Which it shouldn't be if it were a linked list. It actually would be slower to delete the last index unless the list maintained a tail pointer and was doubly linked. In GMS2 the speed difference between arrays and list are seems to be completely gone... In fact in a few tests I've run, list seems faster than arrays.

I would assume that lists must be contiguous in memory since iterating over them is as fast as arrays... Or possible arrays are not contiguous, but I would bet on them being contiguous.

On a side note, never use the accessor notation when adding to a list beyond its current capacity (I do not think that ds_list_clear / delete reduces capacity, nor do I think you can determine a list's capacity). Yes it does it and you do not get an error, but it is way way way slower than ds_list_add.

DISCLAIMER: My claims are based on tests I've personlly done and can't prove any of it. But you can do you own tests and see how it fares for you.
 
Last edited by a moderator:

TheouAegis

Member
Some tests have shown buffers to be slower. But all tests done around here should be taken with a grain of salt.

As Arend said, depending on what you're doing, it can go either way. If you're going to clear it every step, then you may as well just use lists for your ease anyway. You ain't gonna get ideal speed results using Game Maker most of the time anyway, so just worry about making your own life easier.
 
On a side note, never use the accessor notation when adding to a list. Yes it does it and you do not get an error, but it is way way way slower than ds_list_add.
Thanks! I will test to see if there is a difference with ds_list_add, as I was unaware of that. That may explain why the step event this is running in is fairly slow.

That just leaves the question of whether any of the data structures are more appropriate. I know now that a buffer can store an id.
Is it smaller than an array / ds_list with the same information?
 
T

TimothyAllen

Guest
Thanks! I will test to see if there is a difference with ds_list_add, as I was unaware of that. That may explain why the step event this is running in is fairly slow.

That just leaves the question of whether any of the data structures are more appropriate. I know now that a buffer can store an id.
Is it smaller than an array / ds_list with the same information?
Note that I said using the accessor is slower when adding to the list past its capacity. For example:
Code:
// This is slow
var list = ds_list_create();
for (var i = 0; i < whatever; ++i)
{
    list[| i] = somevalue;
}

// This is faster
var list = ds_list_create();
for (var i = 0; i < whatever; ++i)
{
    ds_list_add(list, somevalue);
}
But if the list is already created and had values in it and you simple use ds_list_clear and are adding back into it, the accessor will not necessarily be slower than ds_list_add. Also I am talking about GMS1 and can't speak for GMS2 since I don't really use it atm.

ps. if you are having lots of slow down, it can also be because of the priority list (If you have lots of object12). They are pretty sluggish and it might be better to just add directly into your list and keep it sorted as you go. (you would have to benchmark this yourself). Did a quick test and my implementation was much slower than using a priority list.
 
Last edited by a moderator:
Top