please test pooled / buffer list

BlitzMax Forums/BlitzMax Programming/please test pooled / buffer list

dmaz(Posted 2006) [#1]
I'm interested in the timing results at the end and the computer's speed that it was on. It's twice as fast on my machine but the plain list allocation is pretty fast itself. I spent yesterday writing this but was hoping for a little better gain.

thanks

SuperStrict

' make sure to only store one kind of "type" in each since that is what you will get back.
' you can have as many lists as you need.
Type YourType
	Global g:Int	= 0
	
	Field data:Int

	Method New()
		Self.data = g ; g :+ 1
	End Method

	Function Create:Object()		' must return object
		Local yt:YourType = New YourType
		Return yt
	End Function
	
	Function Init( o:Object )    ' must accept object
		Local yt:YourType = YourType(o)
		yt.data = 0
	End Function
	
End Type

' when creating your list you have to pass it a function that creates a new instance of your type.
' I used "Create" in the above type but you can call it anything.  It can do more than just do a "new".
' it can also set varibles too.
'
' you have the option of passing a function that will be called when using AddFirst / AddLast that can be used
' to zero out your fields

'test example
' setup the list with 10 preallocated instances of "YourType".
' YourType.Create (in this case) is what is called when it needs a new instance created.
' Uncomment "YourType.Init", this function will be called whenever something comes off the
' bench to the list.
Local list:TBeList = TBeList.Create(10, YourType.Create)  ', YourType.Init)

Print "~nempty at start... all on the bench"
For Local i:YourType = EachIn list.Values()
	Print i.data
Next
Print "list: " + list.GetTotal() + " Bench: " + list.GetBenchTotal()


Print "~ngoing to add 12 to the list, 10 should come from the bench"
For Local i:Int = 1 To 12
	list.AddLast()	
Next
Print "list: " + list.GetTotal() + " Bench: " + list.GetBenchTotal()


Print "~nlets remove some"
For Local i:TBeLink = EachIn list.Links()
	Local v:YourType = YourType(i.Value())
	If v.data = 3 Or v.data = 5 Or v.data = 8
		list.RemoveLink(i)
		Print "removing "+v.data
	Else
		Print v.data
	EndIf
Next
Print "list: " + list.GetTotal() + " Bench: " + list.GetBenchTotal()


Print "~nadd another, new, not from the bench"
list.AddLast(New YourType)


For Local i:TBeLink = EachIn list
	Print YourType(i.Value()).data
Next
Print "list: " + list.GetTotal() + " Bench: " + list.GetBenchTotal()

Print "~n-----------------------------"
Print "Timings"
Print "-----------------------------"
GCSetMode 2
Delay(100)

Const TOTAL:Int = 100000
Print "adding "+TOTAL+" objects to TList and TBeList after init"

' Time TList
Local rlist:TList = New TList
Local time:Int=MilliSecs()
For Local i:Int = 1 To TOTAL
	rlist.AddFirst(New YourType)
Next
time = MilliSecs()-time
Print "~nTList: "+time+"ms"

' Time TBeList
Delay(100)
list:TBeList = TBeList.Create(TOTAL, YourType.Create, YourType.Init)
Print "~nInit TBeList with " + list.GetTotal() + " Bench: " + list.GetBenchTotal()
Delay(100)

time:Int=MilliSecs()
For Local i:Int = 1 To TOTAL
	list.AddFirst()
Next
time = MilliSecs()-time

Print "list: " + list.GetTotal() + " Bench: " + list.GetBenchTotal()
Print "TBeList: "+time+"ms"
Print "--------------------"



' -- END OF TESTS ----------------------------------------------------------------


' -- START OF TBeList ------------------------------------------------------------

Type TEnumerator
	Field _enumerator:TLinkEnum

	Method ObjectEnumerator:TLinkEnum()
		Return _enumerator
	End Method
End Type

Type TLinkEnum
	Field _link:TBeLink

	Method HasNext:Int()
		If _link Then Return True Else Return False
	End Method

	Method NextObject:Object()
		Local current:TBeLink = _link
		_link = _link._next
		Return current
	End Method
End Type

Type TValueEnum Extends TLinkEnum
	Method NextObject:Object()
		Local value:Object = _link._value
		_link = _link._next
		Return value
	End Method
End Type


Type TBeLink
	Field _next	:TBeLink
	Field _prev	:TBeLink
	Field _value	:Object
	
	Method Value:Object()
		Return _value
	End Method
	
	Method GetNext:TBeLink()
		Return _next
	End Method

	Method GetPrev:TBeLink()
		Return _prev
	End Method

End Type

Type TBeList
	Field _listTotal	:Int		= 0
	Field _benchTotal	:Int		= 0
	Field _first		:TBeLink	= Null
	Field _last		:TBeLink	= Null
	Field _bench		:TBeLink	= Null
	
	Field CallbackCreate:Object()	= Null
	Field CallbackInit(o:Object)	= Null


	Rem
	bbdoc:
	End Rem
	Function Create:TBeList( poolSize:Int, CallbackCreate:Object(), CallbackInit(o:Object)=Null )
		Local list:TBeList = New TBeList
	
		list.CallbackCreate = CallbackCreate
		list.CallbackInit = CallbackInit
	
		For Local i:Int = 1 To poolSize
			Local link:TBeLink = list.AddFirst()
		Next
		list.Clear
		Return list
	End Function

	Rem
	bbdoc:
	End Rem
	Method GetTotal:Int()
		Return _listTotal
	End Method
	
	Rem
	bbdoc:
	End Rem
	Method GetBenchTotal:Int()
		Return _benchTotal
	End Method

	Rem
	bbdoc:
	End Rem
	Method Links:TEnumerator()
		Local le:TLinkEnum = New TLinkEnum
		le._link = _first
		Local enum:TEnumerator = New TEnumerator
		enum._enumerator = le
		Return enum
	End Method

	Method ObjectEnumerator:TLinkEnum()
		Local ve:TLinkEnum= New TLinkEnum
		ve._link = _first
		Return ve
	End Method


	Rem
	bbdoc:
	End Rem
	Method Values:TEnumerator()
		Local ve:TValueEnum = New TValueEnum
		ve._link = _first	
		Local enum:TEnumerator = New TEnumerator
		enum._enumerator = ve
		Return enum
	End Method

	Rem
	bbdoc:
	End Rem
	Method Clear()
		For Local i:TBeLink = EachIn Links()
			RemoveLink(i)
		Next
	End Method

	Rem
	bbdoc:
	End Rem
	Method RemoveLink( link:TBeLink )
		Assert link, "Can't remove Null link"
		If link._prev Then link._prev._next = link._next
		If link._next Then link._next._prev = link._prev
		link._prev = Null
		link._next = _bench
		_bench = link
		If _first = link Then _first = link._next
		If _last = link Then _last = link._prev
		_listTotal :- 1
		_benchTotal :+ 1
	End Method
	
	Rem
	bbdoc:
	End Rem
	Method GetLink:TBeLink( o:Object=Null )
		Local link:TBeLink
		If o
			' user supplied object create new link and add to list
			link = New TBelink
			link._value = o	
		Else If _bench 
			' user didn't supply but there was one on the bench
			link = _bench
			_bench = link._next
			If CallbackInit Then CallbackInit(link.Value())
			_benchTotal :- 1
		Else
			' bench is empty, we will have to create and object and link
			o:Object = CallbackCreate()
			link = New TBelink
			link._value = o				
		EndIf
		_listTotal :+ 1
		Return link
	End Method	
	
	Rem
	bbdoc:
	End Rem
	Method InsertBeforeLink( link:TBeLink, other:TBeLink )
		If other
			link._next = other
			link._prev = other._prev
			other._prev = link
			If _first = other Then _first = link
		Else
			link._next = Null
			link._prev = Null
			If Not _first Then _first = link
			If Not _last Then _last = link
		EndIf
	End Method
	
	Rem
	bbdoc:
	End Rem
	Method InsertAfterLink( link:TBeLink, other:TBeLink )
		If other
			link._next = other._next
			link._prev = other
			other._next = link
			If _last = other Then _last = link
		Else
			link._next = Null
			link._prev = Null
			If Not _first Then _first = link
			If Not _last Then _last = link
		EndIf
	End Method
	
	Rem
	bbdoc:
	End Rem
	Method AddFirst:TBeLink( o:Object=Null )
		Local link:TBeLink = GetLink(o)
		InsertBeforeLink(link,_first)
		Return link
	End Method

	Rem
	bbdoc:
	End Rem
	Method AddLast:TBeLink( o:Object=Null )
		Local link:TBeLink = GetLink(o)
		InsertAfterLink(link,_last)
		Return link
	End Method

End Type

' end of include or mod