Slices speed 'bumps'

BlitzMax Forums/BlitzMax Programming/Slices speed 'bumps'

simonh

(Posted 2006) [#1]

I noticed major slowdown in my code which seems to be caused by slices.

I have a loop that uses slices to make several arrays one size bigger each iteration.

With one array the speed is ok. With more than one array though the time it takes to perform the slices seems to be non-linear - more arrays equals more severe slowdown.

I tried looking into it and with slices there seems to be a speed 'bump' every so often - whereas normally it takes 0-1ms to perform, it might takes 10ms or more on occasion.

I thought this might be caused by the GC system but even using GCCollect every frame doesn't seem to get rid of the speed bumps.

So, is this normal behaviour or should slices be working faster?

Here's a small test function:

Strict

GCSetMode 1

Global a[1]
Global b[1]
Global c[1]
Global d[1]
Global e[1]
Global f[1]
Global g[1]
Global h[1]

Global ms0=MilliSecs()
Global ms=0

Global i=0

For i=1 To 10000

	ms=MilliSecs()

	a=a[..i+1]
	b=b[..i+1]
	c=c[..i+1]
	d=d[..i+1]
	e=e[..i+1]
	f=f[..i+1]
	g=g[..i+1]
	h=h[..i+1]

	ms=MilliSecs()-ms
	If ms>10 Print "Loop Time: "+ms+" (i="+i+")"

	GCCollect()

Next

Print "Program Time: "+String((MilliSecs()-ms0)/1000.0)

End

Dreamora

(Posted 2006) [#2]

Slices are slow, thats the tradeof for being able to resize them at runtime without losing their content.
If you need to resize a lot, TList is the way to go, as it is a dynamic structure without an overhead for its dynamic sizing.

Yan	(Posted 2006) [#3]

Can you not just resize in batches?

Dreamora

(Posted 2006) [#4]

The optimal way for resizing arrays is only doing *2 , /2 in size ... that way the averange cost per operation goes to 1 ie optimum.

-> if you need more elements that the array can hold, double its size. If you have less objects in the array than half of its length, resize it to half of its length.
That should give some acceptable results :)

*still, arrays would not be a highly dynamic structure, so if it happens that you put and remove half of the data every frame, it won't help much*

Dreamora

(Posted 2006) [#5]

To proof my little "blubb" on slicing with *2 which comes from theoretical informatics science, I've a little testapp here:

Strict

Rem

	Array Slicing Performance Test
	
End Rem

Local testarray:Int[0]


Local time1:Int	 = MilliSecs()

For Local i:Int = 1 To 65536
	If i > testarray.length	testarray	 = testarray[..testarray.length + 1]
	testarray[i-1]	= i
Next

time1	 = MilliSecs() - time1

Print "Testrun 1 (slice with size 1): " + time1

Local time2:Int	 = MilliSecs()

For Local i:Int = 1 To 65536
	If i > testarray.length	testarray	 = testarray[..testarray.length * 2]
	testarray[i-1]	= i
Next

time2	 = MilliSecs() - time2



Print "Testrun 2 (slice with factor 2): " + time2

Print "Ratio of Run 2 to Run 1: " +  (Float(time2) / time1)

End

You can replace the "to value" with any power of 2 + 1. I first wanted to do it with 1 to 1048577, but after 30 seconds I got bored.
As I already know that the *2 will only call slice 20 times compared to 1048577, I don't think its hard to see what ration will result from that ;)