Make array_push behave like growable lists

Is your feature request related to a problem?

array_push is slow

Describe the solution you'd like

array_push to be faster

Describe alternatives you've considered

ds_lists, but they aren't tracked by the garbage collector which is rather inconvenient, and also they don't have a bunch of the newer functional programming tricks

Additional context

When ds_lists and buffers are appended to, their internal block of memory doubles in size, which means that if you have to add a large number of elements the performance of adding stuff to them is pretty reasonable. Unfortunately, array_push only grows the list by exactly one element, which means that new memory has to be allocated every time, which becomes a noticeable problem before long.

It's worth noting that this is not the case on all platforms. On HTML5 array_push is an exact wrapper for JS arrays, so this isn't a problem, assuming you're on a browser which didn't implement it in a dumb way. It also appears to have already been dealt with in the New Runtime beta.

Test it yourself:

var test = function(size) {
    var array = [];
    var list = ds_list_create();
    var buffer = buffer_create(4, buffer_grow, 4);

    show_debug_message($"Test on {size} elements:");

    var t0 = get_timer();
    repeat (size) array_push(array, 0);
    var t1 = get_timer();
    show_debug_message($"array_push x {size} took {(t1 - t0) / 1000} ms");

    t0 = get_timer();
    repeat (size) ds_list_add(list, 0);
    t1 = get_timer();
    show_debug_message($"ds_list_add x {size} took {(t1 - t0) / 1000} ms");

    t0 = get_timer();
    repeat (size) buffer_write(buffer, buffer_u32, 0);
    t1 = get_timer();
    show_debug_message($"buffer_write x {size} took {(t1 - t0) / 1000} ms");

    show_debug_message("");

    ds_list_destroy(list);
    buffer_delete(buffer);
};

test(10);
test(100);
test(1000);
test(10_000);
test(100_000);

GMS2 VM:

Test on 10 elements:
array_push x 10 took 0.01 ms
ds_list_add x 10 took 0.01 ms
buffer_write x 10 took 0.01 ms

Test on 1000 elements:
array_push x 1000 took 0.71 ms
ds_list_add x 1000 took 0.09 ms
buffer_write x 1000 took 0.12 ms

Test on 100000 elements:
array_push x 100000 took 18323.57 ms
ds_list_add x 100000 took 17.28 ms
buffer_write x 100000 took 6.99 ms

New Runtime beta (arrays appear to be slightly slower overall but the runtime is nlogn-ish):

Test on 10 elements:
array_push x 10 took 0.02 ms
ds_list_add x 10 took 0.01 ms
buffer_write x 10 took 0.01 ms

Test on 1000 elements:
array_push x 1000 took 0.33 ms
ds_list_add x 1000 took 0.11 ms
buffer_write x 1000 took 0.11 ms

Test on 100000 elements:
array_push x 100000 took 13.13 ms
ds_list_add x 100000 took 8.05 ms
buffer_write x 100000 took 6.64 ms

I've started using

if(array_size >= array_max_size)
{
       array_max_size *= 2;
    array_resize(array, array_max_size);
}
array[array_size++] = value;

which preserves all that lovely performance, at the expense of needing to worry about two more variables (also meaning you can't simply turn this into a script without wrapping the array into a data structure, struct, or another array of some form).

The same stays true for array_pop with a simple non-resizing alternative (array_size > 0 ? array[--array_size] : undefined) performing measurably faster.

If you don't care about the order of array elements, array_delete can also be sped up a meaningful amount, so I imagine there would still be a benefit to this behaviour for it and array_insert even if the copying needed to reorder the array is still going to reduce the final speed gains there.

I could see the current behaviour as being advantageous in certain circumstances (such as "I've cleared all the elements from this array but it's still using up all my memory?"), but it would at least be nice to have an option for array behaviour.

YoYoGames / GameMaker-Bugs