Struct versus Array Performance

samspade

Member
When I first switched my steering behaviors from arrays to structs about a year ago, I noticed a major performance hit. However, I'm performance testing my steering behaviors now, and I see no difference in performance between structs and arrays on either VM or YYC (although obviously YYC performs much better than VM in both cases).

Are structs as fast as arrays now?
 

Roldy

Member
Are structs as fast as arrays now?
It is a strange question because you have just as many tools as anyone else to answer it. Have you attempted to answer it?

structs, like instances, implement some sort of map for their reflection (e.g. varaible_instance_*, variable_struct_*) Depending on how a map is implemented it could have constant time for random access (e.g. a hashmap with a very good hashing function).

Even though arrays in GML seem to have alot of 'list' like functionality I would assume they have constant time for random access.

We don't have access to the implementations so we (you) could test those empirically. I would suggest making an array with 10000 elements and a struct with 10000 variables, and randomly access the elements a few million times. Measure the difference in performance between the two and you will have your answer for access. Then do the same for adding and inserting, deleting, resizing etc..


More importantly, structs are not arrays. They lack the interfaces and aren't really replicable. Arrays can act like structs, but structs can't act like arrays. e.g. you can't sort the elements of a struct. variable_struct_get_names is a very poor substitute for iteration.

I think it is a bit sad the manual recommends using structs as maps. Even if they have a map implementation for their member access, its still convoluted af. Using structs in place of arrays would be facepalm worthy. So even if they had similar performance I would still say structs in place of arrays would be a bad idea. I know you aren't suggesting that, and your question comes more from before 2.3 we used arrays like structs, since we didn't have structs.
 
Last edited:

samspade

Member
It is a strange question because you have just as many tools as anyone else to answer it. Have you attempted to answer it?
Yes (mostly), see original post. In the actual implementation of the system I saw no difference even when testing with 10,000+ instances at 60fps. However, that was an implementation of a full vector movement system, not a pure test of structs versus arrays (although almost all of the code was array/struct creation and modification).

We don't have access to the implementations so we (you) could test those empirically.
True, but perhaps someone already has and knows the answer. Or noticed something in one of the patch updates about struct performance improvements that I missed.

Doing a test it does seem like arrays are still significantly faster (and more so using the YYC)

GML:
array = [0, 0];

var _t_start = get_timer();

repeat (1000000) {
    array[0] += 1;
    array[1] += 1;
}

var _t_end = get_timer();
var _microseconds = _t_end - _t_start;
show_debug_message("Array Total Time: " + string(_microseconds));

struct = {
    x : 0,
    y : 0
}

var _t_start = get_timer();

repeat (1000000) {
    struct.x += 1;
    struct.y += 1;
}

var _t_end = get_timer();
var _microseconds = _t_end - _t_start;
show_debug_message("Struct Total Time: " + string(_microseconds));
In VM
Array Total Time: 343208
Struct Total Time: 412972

In YYC
Array Total Time: 42782
Struct Total Time: 97983

But I don't see that reflected when actually using them in a more complex system. For reference, a ship which does nothing but flies straight basically has that code in their step event and some of the more complicated ships would be accessing and changing the struct/array vector dozens of times or more per step.
 

8BitWarrior

Member
Last I checked, arrays were still faster. This may become more pronounced in situations where you don't know the array index or struct (member?) that will be used.

GML:
///Some Event 
global.index = 5;
global.member = "Johnny 5";

/// Some Other Event
value = some_array[global.index];
value = some_struct[$ global.member];
I feel like I should do more tests on this soon! Thanks for sharing your findings so far.
 

Cameron

Member
I remember when the 2.3 update first came out they had mentioned that structs would become faster than they were at release. Maybe this has already happened and this is what you are noticing?

Edit:
It seems the version 2.3.3.560 release had performance improvement that affected structs.
"improves the garbage collector for a little more in-game performance "
 
Last edited:

Roldy

Member
I remember when the 2.3 update first came out they had mentioned that structs would become faster than they were at release. Maybe this has already happened and this is what you are noticing?
Maybe struct performance has improved since release, however that is not the question of OP.

Are structs as fast as arrays now?
If we refine this question and make it more precise the question is:

Can we access the index for any arbitrary key in a map as fast/er as we can access an index in a linear array?
The answer should always be no. If the answer was not 'no' it would only indicate that GML arrays are poorly implemented. They can have asymptotic equivalent performance (both have constant access) but not in terms of raw operation.
 
Last edited:

chamaeleon

Member
Compiling to YYC and looking at the generated C++ for the increments in the loops
GML:
array[0] += 1;
array[1] += 1;
Code:
YYRValue* sself_array_62DEE183 = &((CInstanceBase*)pSelf)->GetYYVarRefL(kVARID_self_array); /* set ContextID to 533 */
/* First usage */(PushContextStack( (YYObjectBase*)pSelf ), (*sself_array_62DEE183))((int)(0))+=1;
PopContextStack(2)
;
...
YYRValue* sself_array_7BC5D0C2 = &((CInstanceBase*)pSelf)->GetYYVarRefL(kVARID_self_array); /* set ContextID to 533 */
/* First usage */(PushContextStack( (YYObjectBase*)pSelf ), (*sself_array_7BC5D0C2))((int)(1))+=1;
PopContextStack(2)
;
vs
GML:
struct.x += 1;
struct.y += 1;
Code:
sself_struct = &((CInstanceBase*)pSelf)->GetYYVarRefL(kVARID_self_struct); /* set ContextID to 538 */
YYGML_ErrCheck_Variable_GetValue( /* context id changed from 32 to 539*/(*sself_struct), g_VAR_x.val, (int)ARRAY_INDEX_NO_INDEX, &ostruct1122F7B91_x );
/* First usage */ostruct1122F7B91_x+=1;
Variable_SetValue( /* context id changed from 32 to 539*/(*sself_struct), g_VAR_x.val, (int)ARRAY_INDEX_NO_INDEX, &ostruct1122F7B91_x );
;
...
sself_struct = &((CInstanceBase*)pSelf)->GetYYVarRefL(kVARID_self_struct); /* set ContextID to 538 */
YYGML_ErrCheck_Variable_GetValue( /* context id changed from 538 to 540*/(*sself_struct), g_VAR_y.val, (int)ARRAY_INDEX_NO_INDEX, &ostruct1D05102D9_y );
/* First usage */ostruct1D05102D9_y+=1;
Variable_SetValue( /* context id changed from 538 to 540*/(*sself_struct), g_VAR_y.val, (int)ARRAY_INDEX_NO_INDEX, &ostruct1D05102D9_y );
;
From this we can deduce that the array code does not perform the equivalent of getting and setting the value of a struct member, of unknown complexity in the function Variable_GetValue() and Variable_SetValue(), it simply uses the address of the array element and modifies it directly. Offsetting this, there's unknown amount of work involved in pushing and popping some kind of context from a stack using PushContextStack() and PopContextStack(). Does the C++ compiler optimize away any of the underlying code? Not sure (I'm not one to look at the assembly of a generated executable). The ostruct1122F7B91_x and ostruct1D05102D9_y variables are file global variables being reused.

Edit: Getting the address to modify the array is part of the context stack calls, so the question is how different this is from getting the member variable.
 

Cameron

Member
Maybe struct performance has improved since release, however that is not the question of OP.
@Roldy While it wasn't the primary question, the OP's original comment implied there was a difference between struct performance now and when they were first released. I was merely confirming that this was a planned improvement and then in my edit I cited a version release where a performance improvement had been stated. I don't think there was any harm in addressing this aspect of OP's comment.

Edited: For reasons
 
Last edited:
Top