BlitzMax optimization - Resizing arrays

BlitzMax comes with a number of data structures. Arrays are a staple of the BASIC dialect, but they can be a pain to use if items need to be frequently added and removed. BlitzMax’s TList structure is more flexible, but comes with a performance hit when casting objects.

Resizing arrays

Normally I’d do something like this to resize an array:

Framework brl.basic

' Create initial array.
Local original:Int[] = [1, 2, 3, 4, 5]
Print original.length
' => 5

' Resize to hold 6 elements.
original = ResizeArray(original, 6)
Print original.length
' => 6

Function ResizeArray:Int[](target:Int[], newSize:Int)
    Local dest:Int[newSize]

    For Local i:Int = 0 to target.Length - 1
        dest[i] = target[i]
    Next
    
    Return dest
End Function

It works, but it’s not the most efficient. Things slow down when the target array is large. The main For loop can be unrolled or converted to a Repeat...Until loop, but that’s a small optimization. It would be nice to remove the loop entirely.

bmk-ng comes with a handy function called ArrayCopy for copying the contents of one array to another.

I wrote a quick performance test to compare ArrayCopy against copying elements using a For...Next loop. It’s probably not that accurate, but the results are encouraging.

Time to copy a 1,000 element array 1,000,000 times:

For simple Integer arrays, ArrayCopy is about twice as fast as copying using a For...Next loop. Copying objects is slower, but still shows a good speed improvement. Nice!

But I wondered if there was a better way to implement resizing.

BlitzMax has built-in (and mostly undocumented) functionality for copying and resizing arrays using “slices”.

Instead of creating a larger array and copying the contents, resizing can be done in a single command:

Local myArray:Int[10]

' Resize array to be 20 elements.
myArray = myArray[..20]

Copying can be done in a single line too:

Local target:Int[10]
Local destination:Int[10]

destination = myArray[..]

Using slices reduces the ResizeArray method to this:

Method ResizeArray:Int[](target:Int[], newCapacity:Int)
    Return target[..newCapacity]
End Method

I’ve resized arrays using For...Next loops in a few of my modules. ObjectBag#_grow used it when resizing the internal storage array.

A quick performance test gave the following results for adding 10,000 items to a bag 10,000 times:

ArrayCopy is a big improvement, but slices are even faster (and work with vanilla BlitzMax too).

The original issue that spawned this post: #2 Array growing using ArrayCopy