Array timing

BlitzMax Forums/BlitzMax Beginners Area/Array timing

sswift(Posted 2006) [#1]
Well now that I got it working, I wanted to do some timing on accessing arrays in Max in various ways, and I decided to check the speed against Bitzplus.

Here is the code for Max:
Local A:Int[10000]

StartTime = MilliSecs()

For Loop = 1 To 1000

	For Y = 0 To 99
		For X = 0 To 99
			A[Y*100 + X] = 10
		Next
	Next
Next

EndTime = MilliSecs()

Print "Totaltime = " + (EndTime-StartTime)


And the code for Blitzplus:
Dim A(10000)

StartTime = MilliSecs()

For Loop = 1 To 1000

	For Y = 0 To 99
		For X = 0 To 99
			A(Y*100 + X) = 10
		Next
	Next
Next

EndTime = MilliSecs()

Print "Totaltime = " + (EndTime-StartTime)

WaitKey()



Max is the winner here:
Max: 27
BP: 78

Replacing the inner loop with the following, gets the following results:

For Y = 0 To 99
	Y2 = Y*100
	For X = 0 To 99
		A(Y2 + X) = 10
	Next
Next


Max: 23
BP: 86


And using a two dimensional array, instead of doing the multiplication manually:
Max: 43
BP: 94

What?!

Compare those results to the first test, and you'll see the times are significantly GREATER, even though in both instances, a single multiplication and addition should be being done each array access.

Mark? Explanation pelase?


Well, at the very least, I've learned Max is about 3x as fast as BP when accessing arrays.


skidracer(Posted 2006) [#2]
A two dimensional array is infact an array of arrays, so your single array packing is indeed faster, but not quite as flexible.


sswift(Posted 2006) [#3]
Skid:
Well I know in Blitzmax there are some weird things you can do with arrays, but I don't see why you would need to have "an array of arrays" in Blitzplus, since every array is a collection of longints, even when it's an array of types.

Maybe string arrays are a special case?


The other thing that surprises me with these results is that having that multiply in there every loop doesn't really slow things down nearly as much as I thought it might. It's almost not worth optimizing it out. But it is definitely worth using the single dimensional array rather than the 2D one.

I still don't get though why you would have an array of arrays rather than packing the array as I have done. It would seem that in every case, I could do what I am doing here.


tonyg(Posted 2006) [#4]
Could you give the code for the failing example as well as the working examples?


sswift(Posted 2006) [#5]
What failing example? The one from my other post that was not printing the results?

Or my third example above?


Here's the code for the second example:

Max:


BP:



And here's the code for the third example:

Max:



BP:



And this is the code which should show a crash message in Max when not in debug mode, but just exits, because I wrote outside the arrays by accident:




skidracer(Posted 2006) [#6]
An array of arrays doesn't have to be square, each dimension can have it's own dimension, maybe for a list of variable length samples:

Local a[][]=[New Int[2],New Int[3],New Int[7]]

Local b[][]=[[1,2,3],[4,5,6,7,8],[9]]


sswift(Posted 2006) [#7]
Skid:
Huh? My example doesn't have to be square. Unless you mean rectangular. Which I guess you must.

Are you saying that you can have an array like this?

########
#####
#######
###
###########


That seems like a 1D array of strings to me. If I wanted to have a 2D or 3D array of strings, I'd just have a longer 1D list of strings, and then index into it with the same method I showed before.

Of course, that only works if each element is a pointer to a string. But I don't see how you can index quickly into even a 1D array of strings if you store all the strings one after the other in memory and don't have a list of pointers to the start of each string.


tonyg(Posted 2006) [#8]
Sorry, by failing I meant the one you wanted an explanation for.
Oddly, running the same with Bmax and B3D shows HUGE improvement in Bmax. I realise B3D is creating a graphics window by default but not sure it should affect the timings.
I am getting similar results to yourself (39,29,88).
I was interested in whether you were using 2d arrays, a:int[,] or array of arrays a:int[][]


sswift(Posted 2006) [#9]
Skid:
So in this example:

Local b[][] =[[1,2,3],[4,5,6,7,8],[9]]

You have an array where each element is a pointer to another array, and each of those arrays can be of arbitrary length.

That's not a 2D array. It's a 1D array pointing to a bunch of other 1D arrays.

It'd be as if I did this:

Local b[3]
For Loop = 0 to 2
B[Loop] = Malloc(Rand(10))
Next

(Or however you allocate memory in Max.)


So I think what you're saying is that instead of Mark coding a special case for arrays with more than one dimension, he just did some general case code where instead of allocating one continugous chunk of memory, he allocates one chunk of memory and fills it with pointers to other chunks, and if you've got a 3D array then those chunks would themselves contain pointers to further chunks.

I understand that you probably did this because it saved on writing additional code for the "special" case of regular multidimensional arrays containing pointers and ints, but... it still seems wrong.


sswift(Posted 2006) [#10]
"I was interested in whether you were using 2d arrays, a:int[,] or array of arrays a:int[][]"

Well from what Skidracer is saying it sounds like it doesn't matter which way I did it, because any multi-dimensional array in Blitz gets converted to an array of arrays.