• Hello [name]! Thanks for joining the GMC. Before making any posts in the Tech Support forum, can we suggest you read the forum rules? These are simple guidelines that we ask you to follow so that you can get the best help possible for your issue.

 ds_list accessor [BUG?!]

xDGameStudios

GameMaker Staff
GameMaker Dev.
Is this behavior expected for the list accessor?! is it suppose to take so much time adding items to the list?!
when using accessors?!

Code:
global.a = ds_list_create();

global.b = ds_list_create();

global.c = ds_list_create();

var i = 0;
var time = get_timer();
repeat(100000) {
    global.a[| i++] = 12;
}
show_debug_message(get_timer()-time);   // 5382399 micro

i = 100000
var time = get_timer();
repeat(100000) {
    global.b[| i--] = 12;
}
show_debug_message(get_timer()-time);   // 33399 micro

var time = get_timer();
repeat(100000) {
    ds_list_add(global.c, 12);
}
show_debug_message(get_timer()-time);   // 34842 micro

if the backend code was something like (in pseudocode):

if (index == ds_list_size + 1)
ds_list_add(...);
else
ds_list_insert(...);

it should be faster!!

something really odd is happening:


Code:
i = 100000
var time = get_timer();
repeat(100000) {
    ds_list_insert(global.d, i--, 12);
}
show_debug_message(get_timer()-time);   // 28095

var i = 0;
var time = get_timer();
repeat(100000) {
    ds_list_insert(global.d, i++, 12);
}
show_debug_message(get_timer()-time);   // 2705950
as it is the same list... and it is already 100000 in size it shouldn't take more time.. should it!?
 
Last edited:

Nocturne

Friendly Tyrant
Forum Staff
Admin
Okay, this does seem like an excessive amount of time... but I would assume it's because every time you add to the list you are forcing a reallocation of memory. If you do this, for example:

Code:
var time = get_timer();
global.a[| 99999] = 12;
repeat(100000) {
    global.a[| i++] = 12;
}
Then the time is as short as all the others, so preallocating the list size is the way to go (much like you would large arrays?).

I would also say your second test is flawed as you are not actually changing values already in the list but INSERTING more values which would give the allocation change again. However, that said, there does indeed seem to be something screwy with the insert function (or my understanding of it!) as when I do this:

Code:
global.d = ds_list_create();

var i = 100000
var time = get_timer();

repeat(100000) {
    ds_list_insert(global.d, i, 12);
    i--;
}

show_debug_message(get_timer()-time);
show_debug_message(i);
show_debug_message(ds_list_size(global.d));
I'm getting a ds_list_size of ZERO! I would expect to end up with a list of 200000 entries (since it's being initialised to 100000 and then having 100000 inserted). Something odd indeed...
 

GMWolf

aka fel666
Okay, this does seem like an excessive amount of time... but I would assume it's because every time you add to the list you are forcing a reallocation of memory. If you do this, for example:

Code:
var time = get_timer();
global.a[| 99999] = 12;
repeat(100000) {
    global.a[| i++] = 12;
}
Then the time is as short as all the others, so preallocating the list size is the way to go (much like you would large arrays?).

I would also say your second test is flawed as you are not actually changing values already in the list but INSERTING more values which would give the allocation change again. However, that said, there does indeed seem to be something screwy with the insert function (or my understanding of it!) as when I do this:

Code:
global.d = ds_list_create();

var i = 100000
var time = get_timer();

repeat(100000) {
    ds_list_insert(global.d, i, 12);
    i--;
}

show_debug_message(get_timer()-time);
show_debug_message(i);
show_debug_message(ds_list_size(global.d));
I'm getting a ds_list_size of ZERO! I would expect to end up with a list of 200000 entries (since it's being initialised to 100000 and then having 100000 inserted). Something odd indeed...
When using ds_list_add, I think GM doubles the array size rather than simply increasing it by one when you reach the end. Accessors dont do anything fancy. So I think thats where the huge diff. comes from.

As for the insert, I dont think you can insert in a position greater than the list size, but accessors should let you do that.
 

Nocturne

Friendly Tyrant
Forum Staff
Admin
Does ds_list_insert() silently fail if you try to insert a value beyond the current maximum of the list? Probs what's happening here.
Hmmm, yeah, it could very well be. Need to check up on that as it should be in the documentation too if that is the case. Cheers!
 

xDGameStudios

GameMaker Staff
GameMaker Dev.
Does ds_list_insert() silently fail if you try to insert a value beyond the current maximum of the list? Probs what's happening here.
But then if ds_list_insert is used to insert item within the list size... why does the second test is slower... when the index goes up and faster when it goes down?! :O well I'm all confused here...

:: SECOND TEST ::

it should NOT add items whether going up or down...
if a list has size = 0... ds_list_insert(list, index, value) should NOT work either...
because has it says in the manual index goes from max index should be size-1 ... (0 - 1 = -1)
ds_list_insert should not work!!
 

rwkay

GameMaker Staff
GameMaker Dev.
OK, I just checked and profiled the Runner properly and

1) The first loop is getting swamped by memory allocations as it is going through the list (Nocturne is quite right in saying that hitting the end of the list first will vastly improve the timings).

2) The list has already been allocated so this is fast

3) ds_list_add uses a different allocation algorithm to the list accessor set method.

4) JuJu is quite right and ds_list_insert will just silently fail if the entry is not in range which is why Nocturnes code does not work.

Russell
 
Top