Bug/Feature Request: Arrays in types

BlitzMax Forums/BlitzMax Programming/Bug/Feature Request: Arrays in types

fredborg

(Posted 2006) [#1]

Hi,

After spending a good 12 hours to find out why something sloved down on all secondary runs, I found the problem stemmed from the fact that I was using Arrays for type fields.

On the first run everything is snappy, but on all secondary runs the allocation slows down. Tests have indicated that the first run is as much as 150% faster than secondary runs.

Additionally it seems to slow down over time to some extent.

I have now replaced the array field with statics, but it does result in messier code, because I have to use pointers to index values in some situations.

Here's a simple example that should demonstrate the problem:

SuperStrict

Type TWithArray
	Global store:TWithArray[]	
	Global index:Int
	
	Field abc:Float[3]
	Field def:Float[3]
	
	Function SetCount(count:Int)
		store = store[..count]
		index = 0
	EndFunction
	
	Method New()
		store[index] = Self
		index:+1
		
		abc[0] = 0.1
		abc[1] = 0.2
		abc[2] = 0.3
		
		def[0] = 0.4
		def[1] = 0.5
		def[2] = 0.6
	EndMethod
	
	Function Destroy()
		store = Null
		index = 0
	EndFunction
	
EndType

Type TWithStatic
	Global store:TWithStatic[]	
	Global index:Int
	
	Field abc0:Float,abc1:Float,abc2:Float
	Field def0:Float,def1:Float,def2:Float

	Function SetCount(count:Int)
		store = store[..count]
		index = 0
	EndFunction
	
	Method New()
		store[index] = Self
		index:+1

		abc0 = 0.1
		abc1 = 0.2
		abc2 = 0.3
		
		def0 = 0.4
		def1 = 0.5
		def2 = 0.6
	EndMethod

	Function Destroy()
		store = Null
		index = 0
	EndFunction
		
EndType

Const loops:Int = 20
Const count:Int = 1000000

'
' Create a lot of types array fields
Print "~nTest with arrays"
For Local i:Int = 0 Until loops
	TWithArray.SetCount(count)
	Local ms:Int = MilliSecs()
	For Local j:Int = 0 Until count
		New TWithArray
	Next
	ms = MilliSecs()-ms
	Local ms2:Int = MilliSecs()
	TWithArray.Destroy()
	GCCollect()
	ms2 = MilliSecs()-ms2
	Print "Loop "+i+" MemAllocated: "+GCMemAlloced()+" Time: "+ms+"ms Cleaning: "+ms2
Next

'
' Create a lot of types with static fields
Print "~nTest with statics"
For Local i:Int = 0 Until loops
	TWithStatic.SetCount(count)
	Local ms:Int = MilliSecs()
	For Local j:Int = 0 Until count
		New TWithStatic
	Next
	ms = MilliSecs()-ms
	Local ms2:Int = MilliSecs()
	TWithStatic.Destroy()
	GCCollect()
	ms2 = MilliSecs()-ms2
	Print "Loop "+i+" MemAllocated: "+GCMemAlloced()+" Time: "+ms+"ms Cleaning: "+ms2
Next

You will also notice that the first clean up from the array type takes an excessive amount of time.

I assume this is all related to the fact that arrays are completely dynamic, so the field with arrays assigned can be resized at will. My suggestion/feature resuest is that a static option is added to the arrays, so they cannot be resized, and therefore act as regular variables. Like this:

Field abc:Float[3] Static

Which would make the compiler lock down the size of the array at compile time.

marksibly

(Posted 2006) [#2]

Hi,

Lack of static arrays is not a bug, although if you can provide some code that demonstrates 'slowing down over time' please post it in bug reports as that may well be.

The trouble with adding static arrays is simply that it introduces a whole new type to the system, along with issues such as 'what happens when you go t[]=p[]', 'what happens when you pass a static array to a function expecting a dynamic array? Can you? Vice versa?' and other related goodies.

Frankly, I'd rather concentrate on speeding up dynamic arrays.

fredborg

(Posted 2006) [#3]

Ok, fair enough. But surely 35 seconds to clean up from the first run of the above code, is suspicious isn't it? It shouldn't take that long to free 1 million type instances.

I will post an example later that demonstrates the slowing down over time. It seems the above example doesn't suffer from it to the same extent.

Dreamora

(Posted 2006) [#4]

I would assume that has to do with the counter-speedoptimal behavior of the GC which try to minimize the RAM usage instead the same way as "professional" GCs (C#, JAVA, Eiffel) work. (they do not minimize the usage ... there is no real reason for it, if there is free RAM anyway)

Found a similar behavior (but much worse on freeing - thought it was broken as it hadn't freed 5 mins later) when trying to find something that lets the GC fail. But that was influenced by strings in the list and this strings length as well. (you can do a simple while loop and add a string to a list until a given memory alloced border is reached. When doing with string = string + string it will need forever to clean, with string = string + "a" it will take quite long on first run as well but not nearly as worse as with the first version)

fredborg

(Posted 2006) [#5]

Ok, it appears it's the garbage collector that slows down secondary runs. If I clean up manually, secondary runs are actually faster, but if I don't they are much slower.

SuperStrict

Type T1
	Global store:T1[]	
	Global index:Int
	
	Field abc:Float[3]
	Field def:Float[3]
	
	Function SetCount(count:Int)
		store = store[..count]
		index = 0
	EndFunction
	
	Method New()
		store[index] = Self
		index:+1
	EndMethod
	
	Function Create:T1(a:Float,b:Float,c:Float,d:Float,e:Float,f:Float)
		
		Local j:T1 = New T1
		
		j.abc[0] = a
		j.abc[1] = b
		j.abc[2] = c
		
		j.def[0] = d
		j.def[1] = e
		j.def[2] = f
		
		Return j
		
	End Function
	
	Function Destroy()
		store = Null
		index = 0
	EndFunction
	
EndType

Type T2
	Global store:T2[]	
	Global index:Int
	
	Field abc:Float[3]
	Field def:Float[3]
	
	Function SetCount(count:Int)
		store = store[..count]
		index = 0
	EndFunction
	
	Method New()
		store[index] = Self
		index:+1
	EndMethod
	
	Function Create:T2(a:Float,b:Float,c:Float,d:Float,e:Float,f:Float)
		
		Local j:T2 = New T2
		
		j.abc[0] = a
		j.abc[1] = b
		j.abc[2] = c
		
		j.def[0] = d
		j.def[1] = e
		j.def[2] = f
		
		Return j
		
	End Function
	
	Function Destroy()
		store = Null
		index = 0
	EndFunction
	
EndType

Const loops:Int = 20
Const count:Int = 100000

Const doT2:Int	= True
Const doManualClean:Int = False

'
' Create a lot of types array fields
Print "~nTest with arrays"
For Local i:Int = 0 Until loops
	
	Local ms:Int = MilliSecs()
	PerformTest()
	ms = MilliSecs()-ms
	
	Local ms2:Int = MilliSecs()
	T1.Destroy()
	If doT2 Then T2.Destroy()
	If doManualClean Then GCCollect()
	ms2 = MilliSecs()-ms2
	
	Print "Loop "+i+" MemAllocated: "+GCMemAlloced()+" Time: "+ms+"ms Cleaning: "+ms2
Next

Function PerformTest()

	T1.SetCount(count)
	For Local j:Int = 0 Until count
		AddT1
	Next

	If doT2
		T2.SetCount(count)
		For Local j:Int = 0 Until count
			AddT2()
		Next
	EndIf
	
End Function

Function AddT1:T1()
	Return T1.Create(0.1,0.2,0.3,0.4,0.5,0.6)
EndFunction

Function AddT2:T2()
	Return T2.Create(0.1,0.2,0.3,0.4,0.5,0.6)
EndFunction

It does look like the same applies to statics, but to a much lesser extent:

SuperStrict

Type T1
	Global store:T1[]	
	Global index:Int
	
	Field a:Float,b:Float,c:Float,d:Float,e:Float,f:Float
	
	Function SetCount(count:Int)
		store = store[..count]
		index = 0
	EndFunction
	
	Method New()
		store[index] = Self
		index:+1
	EndMethod
	
	Function Create:T1(a:Float,b:Float,c:Float,d:Float,e:Float,f:Float)
		
		Local j:T1 = New T1
		
		j.a = a
		j.b = b
		j.c = c
		
		j.d = d
		j.e = e
		j.f = f
		
		Return j
		
	End Function
	
	Function Destroy()
		store = Null
		index = 0
	EndFunction
	
EndType

Type T2
	Global store:T2[]	
	Global index:Int
	
	Field a:Float,b:Float,c:Float,d:Float,e:Float,f:Float
	
	Function SetCount(count:Int)
		store = store[..count]
		index = 0
	EndFunction
	
	Method New()
		store[index] = Self
		index:+1
	EndMethod
	
	Function Create:T2(a:Float,b:Float,c:Float,d:Float,e:Float,f:Float)
		
		Local j:T2 = New T2
		
		j.a = a
		j.b = b
		j.c = c
		
		j.d = d
		j.e = e
		j.f = f
		
		Return j
		
	End Function
	
	Function Destroy()
		store = Null
		index = 0
	EndFunction
	
EndType

Const loops:Int = 20
Const count:Int = 100000

Const doT2:Int	= True
Const doManualClean:Int = False

'
' Create a lot of types array fields
Print "~nTest with statics"
For Local i:Int = 0 Until loops
	
	Local ms:Int = MilliSecs()
	PerformTest()
	ms = MilliSecs()-ms
	
	Local ms2:Int = MilliSecs()
	T1.Destroy()
	If doT2 Then T2.Destroy()
	If doManualClean Then GCCollect()
	ms2 = MilliSecs()-ms2
	
	Print "Loop "+i+" MemAllocated: "+GCMemAlloced()+" Time: "+ms+"ms Cleaning: "+ms2
Next

Function PerformTest()

	T1.SetCount(count)
	For Local j:Int = 0 Until count
		AddT1
	Next

	If doT2
		T2.SetCount(count)
		For Local j:Int = 0 Until count
			AddT2()
		Next
	EndIf
	
End Function

Function AddT1:T1()
	Return T1.Create(0.1,0.2,0.3,0.4,0.5,0.6)
EndFunction

Function AddT2:T2()
	Return T2.Create(0.1,0.2,0.3,0.4,0.5,0.6)
EndFunction

fredborg

(Posted 2006) [#6]

Here's the original test, that caused my report:

SuperStrict

Const pcount:Int = 10000
Const mcount:Int = 10

Local minmem:Int
Local maxmem:Int

Local mintime:Int
Local maxtime:Int

For Local loops:Int = 0 To 19
	
	GCCollect()
	
	Local mem:Int = GCMemAlloced()
	
	If loops = 0
		minmem = mem
		maxmem = mem
	Else
		minmem = Min(mem,minmem)
		maxmem = Max(mem,maxmem)
	EndIf
	
'	Print "~n"
'	Print "Loop "+loops
'	Print "Memory allocated: "+mem
	
	Local ms:Int = MilliSecs()
	Local sms:Int = ms

	SeedRnd 1234
	
	For Local j:Int = 0 To mcount
		
		I_AddModel(pcount,pcount)
	
		For Local i:Int = 0 To pcount-1
			Local K:iVert = New iVert
		Next
	
		For Local i:Int = 0 To pcount-1
			Local K:iTri = New iTri
		Next
	Next
	
	ms = (MilliSecs()-ms)
	
	Print "Loop "+loops+"  "+mcount+" Models with "+pcount+" triangles uploaded in "+ms+"ms"
	
	sms = MilliSecs()-sms
	
	iTri.Clean()
	iVert.Clean()
	GCCollect()
	
	If loops = 0
		mintime = sms
		maxtime = sms
	Else
		mintime = Min(mintime,sms)
		maxtime = Max(maxtime,sms)
	EndIf
		
Next

Print "~n~n"
Print "Time Variation (min,max) = ("+mintime+","+maxtime+")"
Print "Statistical Variation "+((maxtime/Float(mintime))*100.0)+"%"

Print "~n~n"
Print "Memory Variation (min,max) = ("+minmem+","+maxmem+")"
Print "Statistical Variation "+((maxmem/Float(minmem))*100.0)+"%"

Global VertOffset:Int = 0

Type iVert
	
	Global array:iVert[]
	Global current:Int
	
	Field pos:Float[3]
	Field nor:Float[3]
	
	Field col:Float[4]
	
	Field uv0:Float[2]
	Field uv1:Float[2]

	Method New()

		iVert.Array[iVert.Current] = Self
		iVert.Current :+ 1

	EndMethod

	Function Clean()
		iVert.Array = Null
		iVert.Current = 0
	EndFunction

EndType

Type iTri

	Global array:iTri[]
	Global current:Int

	Field flags:Int
	Field surf:Object
	Field index:Int

	Field vert:iVert[3]
	Field nor:Float[3]
	Field nu:Float
	Field nv:Float
	Field nd:Float
	Field k:Int
	Field bnu:Float
	Field bnv:Float
	Field cnu:Float
	Field cnv:Float

	Field hit:Int

	Field re:Int
	
	Method New()
		iTri.Array[iTri.Current] = Self
		self.re = iTri.Current
		iTri.Current :+ 1
	EndMethod

	Function Clean()
		iTri.Array = Null
		iTri.Current = 0
	EndFunction
	
End Type


Function I_AddModel:Int(verts:Int,tris:Int)

	VertOffset = iVert.Array.length

	If verts>0
		iVert.Array = iVert.Array[..iVert.Array.length+verts]
	EndIf
	If tris>0
		iTri.Array = iTri.Array[..iTri.Array.length+tris]
	EndIf

	Return True

EndFunction