GML Fastest way to read / write using data structures

Simon Gust

Member
I have some questions regarding data structures.
I know that they are altered arrays with various features in them making them suitable for different situations.

In my situation, I want to read and write a lot of data in a single draw.
My idea was to use a ds_stack to push and pop data super fast.
But I was disappointed, ds_list is somehow faster than a ds_stack? How come, when I have to feed an offset that reading is still faster in a ds_list. Am I doing something wrong?
Code:
repeat (120000) {
    //ds_queue_enqueue(queue, random(100));
    ds_stack_push(stack, random(100));
    // vs
    ds_list_add(list, random(100));
    //array[i++] = random(100);
}

buffer_seek(buffer, 0, 0);
// reading
var i = 0;
repeat (120000) {
    //var r = ds_queue_dequeue(queue);
    var r = ds_stack_pop(stack);
    // vs
    var r = ds_list_find_value(list, i++);
    //var r = array[i++];
}
queue: infinity ms
stack 330 ms
list: 255 ms
array 30 ms

This led me to believe that arrays must then be even faster than lists (which is true). But to me it doesn't feel like that is the task an array or list should take.

My plight: Is there a faster way to push and pop data than an array?
 

NicoFIDI

Member
Data structures are not arrays modified (Not necesarely), yet they are to convey information by the type, and to give behaviour.
A list and a array are almost the same every chance (they even acces in the same way) yet you wont find holes in a list.
A stack it's when you play a chain card in yu-gi-oh you will never want to find the second to top card, the only thing you care it's the latest and instead of having indexes, you push and pop from the chain.
 

Simon Gust

Member
Data structures are not arrays modified (Not necesarely), yet they are to convey information by the type, and to give behaviour.
A list and a array are almost the same every chance (they even acces in the same way) yet you wont find holes in a list.
A stack it's when you play a chain card in yu-gi-oh you will never want to find the second to top card, the only thing you care it's the latest and instead of having indexes, you push and pop from the chain.
But I could make my own ds_stack using ds_lists except it would be faster than a ds_stack. I'd just have to keep track of the seek position and that doesn't make it 60% times slower.
 

Tsa05

Member
I ran the same test and got expected results, but not results matching those stated above.

I pre-populated a stack and a list in a Create Event, then used your code in a step event:

Pop averaged faster execution time than find_value by a small margin.

I also put the whole thing in a step event and profiled it:

It takes very significantly longer to insert something into the front (Push) than to append to the back (Add)--actually, @rwkay or other YYGers, I'd love to know why push is so much slower; is GMS actually moving every element? Would a linked list be faster?

But, again, pop faster than find.
 

Simon Gust

Member
I ran the same test and got expected results, but not results matching those stated above.

I pre-populated a stack and a list in a Create Event, then used your code in a step event:

Pop averaged faster execution time than find_value by a small margin.

I also put the whole thing in a step event and profiled it:

It takes very significantly longer to insert something into the front (Push) than to append to the back (Add)--actually, @rwkay or other YYGers, I'd love to know why push is so much slower; is GMS actually moving every element? Would a linked list be faster?

But, again, pop faster than find.
Thank you very much for getting your fingers dirty here, I think this can lead to very informative discussions I am just as excited to hear about as you are.
 

NicoFIDI

Member
I'm not internal from game maker but i did code this data structures from zero.
I find this really interesting,
Using linked nodes of malloc, the strucures should take the same time on the add and the push.
Maybe the list it's not a linked list, if the list it's a hidden array that whould explain it.
 

NicoFIDI

Member
But I could make my own ds_stack using ds_lists except it would be faster than a ds_stack. I'd just have to keep track of the seek position and that doesn't make it 60% times slower.
Like @The-any-Key said: if you use an array to emulate a stack for performance issues then you should doit.
Data structures are there like i said to give information by the type.

If you have your array-stacked, then you dont actually have a stack, because i can violate the stack contract takeing elements out of order, sorting it, etc.
 

bbbower

Member
Not sure if this is helpful as its vaguely on topic, I couldn't find the answer I needed searching but your post helped a little. I was using an array to store tilemap data, I thought a 1d array would access faster than a map or other data types, but at least at the initializing / writing the tilemap data the ds_grid worked 130% faster than the array and more than double the speed of the list cutting down my load time to 5.2 seconds from 6.7ish.
 
Top