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

GML Data structure comparison

Simon Gust

Member
I want to test the speeds of data structures in certain jobs. Some are better at certain things so I'm trying to find the fastest.

I am building a caching system, where I have to store data to be used later due to:
- seperating writing data saves time on some calculations:
I have an array (4000x1000 currently) and each entry can store multiple numbers via bitmasking.
So the base data (the first 8 bytes) don't have complex calculation and can be added with adding or subtracting. But I have some other type of data (byte 31 to 34 and 35 to 42) that are added somewhere between the array population. The problem of course, is that setting an entry without the bitwise is faster but will overwrite the whole entry. So all later bytes I store in a cache that adds all the data at the end. This allows me to do easier calculations first.

- seperating drawing:
My rendering requires a double for loop to draw all pixels onto a surface etc. But I want so save looking up different types of data in different loops, so I can look up all data inside a single double-for-loop. I cannot always setting and resetting surface targets, that is way too slow, so I cache all the data and have it sorted.

My caches can be:
- arrays (1D)
- lists
- queues

So now of course, I'm searching for the fastest to:
- just write data
- the position of each entry is meaningless
- just read data

testing code
Code:
Q = ds_queue_create();
L = ds_list_create();
A[64000] = false;
num = 0;

var time = current_time;
//FUNCTIONS STARTØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØ
for (var i = 0; i < 4000; i++)
{
    for (var j = 0; j < 4000; j++)
    {
        if (i mod 1000 == 0)
        {
            // array
            A[num] = true;
            A[num+1] = true;
            A[num+2] = true;
            A[num+3] = true;
            num += 4;
  
            // queue
            ds_queue_enqueue(L, true, true, true, true);
          
            // list
            ds_list_add(L, true, true, true, true);
        }
    }
}

repeat (16000)
{
    // queue
    var a = ds_queue_dequeue(Q);
    var b = ds_queue_dequeue(Q);
    var c = ds_queue_dequeue(Q);
    var d = ds_queue_dequeue(Q);
}

for (var i = 0; i < 64000; i += 4)
{
   // array
   var a = A[i];
   var b = A[i+1];
   var c = A[i+2];
   var d = A[i+3];
  
   // list
   var a = ds_list_find_value(L, i);
   var b = ds_list_find_value(L, i+1);
   var c = ds_list_find_value(L, i+2);
   var d = ds_list_find_value(L, i+3);
}
//FUNCTIONS END ØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØØ
var time = current_time - time;
show_debug_message("| Delay: " + string(time) + " ms");
The structure that isn't used I have commented out during the tests.

Code:
// previous records
array
5043 ms / 3266 ms

queue
4074 ms / 1521 ms

list
3049 ms / 718 ms
left: without yyc
right: with yyc

So what are your thoughts?
Is this a fair comparison?
Are there alternatives?
 

nicognito

Member
When you mention "cache", I guess you mean some kind of data storage?

(note: I'm a newbie here) I feel like technically, for a video game, an array might be better than a list or queue to store data in memory.

Why?
  • If you know approximately the number of entries to store, you can pre-allocate your array with the expected capacity. That's basically what you did in your test script ("A[64000]"). If you need to add more elements, say a new entry at position 64000 (basically the 64001-th element), then the runtime will reallocate more space for your array (a reallocation for the game engine could be something like: if the new entry over the current capacity, create a new buffer with twice the capacity: 64000 * 2). Normally (at least in other languages like C/C++) the allocated memory should be contiguous, contrary to lists and queues.
    • When you keep adding entries to a list or queue, a new "node" in your list/queue will be added to the end: the allocated memory for each node might be allocated in different locations in the memory heap (each node having a reference to the next node).
    • What this means is that for list and queues, you'd have many calls to the allocation API (each of them will have to be destroyed by the engine as well). In the case of array, the engine would have to find enough space for the allocation "once" ; the allocation would probably fail if it can't find enough space.
    • Theoretically the memory space occupied by an array could be less than a queue/list of the same capacity., if the memory for the underlying buffer in the array is contiguous. There's extra memory footprint for every node in your list/array.
  • The complexity of a read/write in an array is a O(1) (big-O of 1). I don't remember how to explain it, but what this notation means is that the operation is fast / instantaneous, as it doesn't depend on the size of your array. The complexity to find, insert/remove a particular element in a list/queue is a O(N), meaning that the engine would have to go through N elements in your data structure in the worst case. However the complexity of adding an element at the beginning/end of a list/queue should be O(1), which is instantenous (because the data structures should probably keep a pointer to the start/end of the structure, and keep them updated after each operation)
In my case and my game I'm writing now, I need to precompute and store a lot of data like you, and I chose to store the data in a preallocated "buffer" of 32-bits data, i..e 4-bytes data (https://docs.yoyogames.com/source/dadiospice/002_reference/buffers/index.html). Performance is important in my case and for the player experience, that's why I didn't choose lists or queues as the data storage for my game. I chose buffers over arrays, because it's even more lower level (so potentially fast) and I can probably save the data somewhere to resume the game with the same data. What I store in my buffer is some small numbers and IDs, which are stored within those 32-bits data (e.g. 1 32-bits data can contain a lot of information). No bits are left unused, I process my buffer as if it was a one giant bit buffer, using bitwise operations.
 
Last edited:

nicognito

Member
Did some experiments, seems like lists and queues are a little little bit faster in read/write access than array (Yoyo probably optimized those data structures a lot, maybe having underlying arrays :p). However allocation seems to be faster with arrays, and very slow with queues. I haven't tested buffers, but it's probably ok like arrays :)

Here's my experiment:
Code:
var capacity = 200000;

// ------------------------------------------------------------------------------------------------
// allocation test
// ------------------------------------------------------------------------------------------------

// array
var start = current_time;
var array = array_create(capacity, 0); // create an array filled with 0
show_message("Array allocation: " + string(current_time - start) + " ms.");

// list
start = current_time;
var list = ds_list_create();
for (var i = capacity; i--; ) {
  ds_list_add(list, 0);
}
show_message("List allocation: " + string(current_time - start) + " ms.");

// queue
start = current_time;
var queue = ds_queue_create();
for (var i = capacity; i--; ) {
  ds_queue_enqueue(queue, 0);
}
show_message("Queue allocation: " + string(current_time - start) + " ms.");

// ------------------------------------------------------------------------------------------------
// Read test (random)
// ------------------------------------------------------------------------------------------------

var iteration_count = 10000000;

// array
var tmp = 0;
random_set_seed(0);
start = current_time;
for (var i = iteration_count; i--; ) {
  var index = irandom(capacity - 1);
  tmp += array[index];
}
show_message("Array read: " + string(current_time - start) + " ms.");

// list
tmp = 0;
random_set_seed(0);
start = current_time;
for (var i = iteration_count; i--; ) {
  var index = irandom(capacity - 1);
  tmp += ds_list_find_value(list, index);
}
show_message("List read: " + string(current_time - start) + " ms.");

// ------------------------------------------------------------------------------------------------
// Read test (worst case: reading the last element multiple times)
// ------------------------------------------------------------------------------------------------

// array
var tmp = 0;
start = current_time;
for (var i = iteration_count; i--; ) {
  tmp += array[capacity - 1];
}
show_message("Array read (worst case): " + string(current_time - start) + " ms.");

// list
tmp = 0;
start = current_time;
for (var i = iteration_count; i--; ) {
  tmp += ds_list_find_value(list, capacity - 1);
}
show_message("List read (worst case): " + string(current_time - start) + " ms.");

// queue, no access at specified index

// ------------------------------------------------------------------------------------------------
// Write test (random)
// ------------------------------------------------------------------------------------------------

// array
random_set_seed(0);
start = current_time;
for (var i = iteration_count; i--; ) {
  var index = irandom(capacity - 1);
  array[index] = 42;
}
show_message("Array write: " + string(current_time - start) + " ms.");

// list
random_set_seed(0);
start = current_time;
for (var i = iteration_count; i--; ) {
  var index = irandom(capacity - 1);
  ds_list_replace(list, index, 42);
}
show_message("List write: " + string(current_time - start) + " ms.");

// queue, no access at specified index

// ------------------------------------------------------------------------------------------------
// Write test (random: writing at the last position)
// ------------------------------------------------------------------------------------------------

// array
start = current_time;
for (var i = iteration_count; i--; ) {
  array[capacity - 1] = 42;
}
show_message("Array write (worst case): " + string(current_time - start) + " ms.");

// list
start = current_time;
for (var i = iteration_count; i--; ) {
  ds_list_replace(list, capacity - 1, 42);
}
show_message("List write (worst case): " + string(current_time - start) + " ms.");

// queue, no access at specified index

// ------------------------------------------------------------------------------------------------
// Reading values from the end until to the start
// ------------------------------------------------------------------------------------------------

// array
random_set_seed(0);
tmp = 0;
start = current_time;
for (var i = capacity; i--; ) {
  tmp += array[i];
}
show_message("Array read from end: " + string(current_time - start) + " ms.");

// list
random_set_seed(0);
tmp = 0;
start = current_time;
for (var i = capacity; i--; ) {
  tmp += ds_list_find_value(list, i);
}
show_message("List read from end: " + string(current_time - start) + " ms.");

// queue
random_set_seed(0);
tmp = 0;
start = current_time;
for (var i = capacity; i--; ) {
  tmp += ds_queue_dequeue(queue);
}
show_message("Queue read from end: " + string(current_time - start) + " ms.");
 

Simon Gust

Member
When you mention "cache", I guess you mean some kind of data storage?

(note: I'm a newbie here) I feel like technically, for a video game, an array might be better than a list or queue to store data in memory.

Why?
  • If you know approximately the number of entries to store, you can pre-allocate your array with the expected capacity. That's basically what you did in your test script ("A[64000]"). If you need to add more elements, say a new entry at position 64000 (basically the 64001-th element), then the runtime will reallocate more space for your array (a reallocation for the game engine could be something like: if the new entry over the current capacity, create a new buffer with twice the capacity: 64000 * 2). Normally (at least in other languages like C/C++) the allocated memory should be contiguous, contrary to lists and queues.
    • When you keep adding entries to a list or queue, a new "node" in your list/queue will be added to the end: the allocated memory for each node might be allocated in different locations in the memory heap (each node having a reference to the next node).
    • What this means is that for list and queues, you'd have many calls to the allocation API (each of them will have to be destroyed by the engine as well). In the case of array, the engine would have to find enough space for the allocation "once" ; the allocation would probably fail if it can't find enough space.
    • Theoretically the memory space occupied by an array could be less than a queue/list of the same capacity., if the memory for the underlying buffer in the array is contiguous. There's extra memory footprint for every node in your list/array.
  • The complexity of a read/write in an array is a O(1) (big-O of 1). I don't remember how to explain it, but what this notation means is that the operation is fast / instantaneous, as it doesn't depend on the size of your array. The complexity to find, insert/remove a particular element in a list/queue is a O(N), meaning that the engine would have to go through N elements in your data structure in the worst case. However the complexity of adding an element at the beginning/end of a list/queue should be O(1), which is instantenous (because the data structures should probably keep a pointer to the start/end of the structure, and keep them updated after each operation)
In my case and my game I'm writing now, I need to precompute and store a lot of data like you, and I chose to store the data in a preallocated "buffer" of 32-bits data, i..e 4-bytes data (https://docs.yoyogames.com/source/dadiospice/002_reference/buffers/index.html). Performance is important in my case and for the player experience, that's why I didn't choose lists or queues as the data storage for my game. I chose buffers over arrays, because it's even more lower level (so potentially fast) and I can probably save the data somewhere to resume the game with the same data. What I store in my buffer is some small numbers and IDs, which are stored within those 32-bits data (e.g. 1 32-bits data can contain a lot of information). No bits are left unused, I process my buffer as if it was a one giant bit buffer, using bitwise operations.
I really apprechiate your response, you brought some very technical thoughts into this, I like that.
Some things though:
- once you allocated an array, you cannot allocate more later, so a temporary counter "num" is needed, so that if num is approaching the max array size I can
Code:
continue;
the loops.
I'm pretty sure lists and queues were made to have data allocated at the end, so it's not like with arrays when they take ages for that.
Last time I checked, buffers were a good chunk slower than arrays, which is unfortunate.

As said, my game uses bitmasking:
upload_2017-9-8_8-46-11.png
the yellow part is the one I can speed up by caching all other data to be added later.
Because overwriting an array entry is easier than to do this
Code:
/// setTile(i, j, value)
global.TILE[@ argument0, argument1] &= ~255;
global.TILE[@ argument0, argument1] |= argument2;
My records showed that lists were 450% faster than arrays using the yyc. But of course only arrays (no one cares about grids) can be 2D reliably and easy.
 

nicognito

Member
Good info about buffers, I need to compare their performance vs. arrays... But I'll probably need to stick with buffers if I need to save the results :/

Code:
/// setTile(i, j, value)
global.TILE[@ argument0, argument1] &= ~255;
global.TILE[@ argument0, argument1] |= argument2;
Just a note this code sample. It looks readable and natural to do. The code can be slow if you don't try to guess what the compiler does :p Modern compilers are probably better than the GameMaker one.

If the compiler is not super smart, think about it:

When you write something like:
Code:
global.TILE[@ argument0, argument1] &= ~255;
It will translate your code into instructions to execute something like that:
Code:
global.TILE[@ argument0, argument1] = global.TILE[@ argument0, argument1] & ~255;
(read the data at the array location, do a "&" operation, reassign the results to the array location)

Combining your two lines of code is probably faster:
Code:
/// setTile(i, j, value)
global.TILE[@ argument0, argument1] = (global.TILE[@ argument0, argument1] & ~255) | argument2;
Proof tests (done in test VM mode on my machine):
Code:
// Takes 2564 ms
var start = current_time;
var count = 2000;
global.matrix = [];

for (var i = count; i--; ) {
  for (var j = count; j--; ) {
    global.matrix[@i, j] = 0;
    global.matrix[@i, j] &= 255;
    global.matrix[@i, j] |= 42;
  }
}
show_message("time: " + string(current_time - start) + "ms.")

// Takes 1697 ms
start = current_time;
count = 2000;
global.matrix = [];

for (var i = count; i--; ) {
  for (var j = count; j--; ) {
    global.matrix[@i, j] = 0;
    global.matrix[@i, j] = (global.matrix[@i, j] & 255) | 42;
  }
}
show_message("time (optimized): " + string(current_time - start) + "ms.")
 

Simon Gust

Member
It probably is faster, and I used to have it like that, but for now I'll leave it for readability.
The are some other functions that take multiple setter arguments.

Code:
/// placeTile(x, y, type, mask, slope)
global.TILE[@ argument0, argument1] &= ~251662335;
global.TILE[@ argument0, argument1] |= (argument2) | (argument3 << 8) | (argument4 << 24);

with (obj_terrain)
{
surface_set_target(tileRender);
var col = make_color_rgb(argument2, argument3, argument4);
var xx = argument0 - new_gridx;
var yy = argument1 - new_gridy;
draw_point_color(xx, yy, col);
surface_reset_target();
}
(code may not resemble reality, this is from my memory)
 
Top