Sortable and Reallocatable

Monkey Forums/Monkey Programming/Sortable and Reallocatable

Raz	(Posted 2014) [#1]

I currently use the Diddy ArrayList which is great for sorting isometrically drawn sprites. However, I'd like to be able to reallocate entries instead of straight up creating new ones in the same way you can in BRL.POOL.

Does anyone know if such a thing exists?

Ta! :)

Nobuyuki

(Posted 2014) [#2]

You can use two separate lists, an active and inactive object list, and keep the active list sorted whereas the inactive list gets reset. Actually that sounds exactly like what brl.pool already does, so why not just use it?

You'll need reset methods for your object or interface, to free up an object for later use. Instead of instancing you'll pop from the pool, and instead of destroying, you push to it.

Raz	(Posted 2014) [#3]

Oh... can I sort a pool then? Or is it relatively trivial to implement pool sorting?

Paul - Taiphoz

(Posted 2014) [#4]

Diddy's ArrayList is being replaced you should check out the new code their creating to see if it has the functionality that you need.

As for brl.pool I myself have still to actually look at it, i really should tho, at the moment with my little orbit project I have a bool field on each object class, so any of my objects are either active or inactive, when they are active they get drawn and updated, when they are not they are ignored, in my new method I only call new upto a max number of objects, for example 50 asteroids, if I then need a 51'st asteroid my code looks for an asteroid that's no longer active and relocates it to its new position resets its values and then sets its bool to active so its once again in play.

I'm going to use orbit as my test for using the brl.pool class but before I do I want to see how fast things are my way, I think I will try giving each object an Active and Inactive list next to see how that changes the performance, and then finally I will try implementing this brl.pool and see how quick that is.

jondecker76

(Posted 2014) [#5]

If you look at the generic Pool class, you will see that internally it uses a stack:

Class Pool<T>

	Method New( initialCapacity:Int=10 )
		For Local i:=0 Until initialCapacity
			_pool.Push New T
		Next
	End

	Method Allocate:T()
		If _pool.IsEmpty() Return New T
		Return _pool.Pop()
	End
	
	Method Free:Void( t:T )
		_pool.Push t
	End
	
	Private
	
	Field _pool:=New Stack<T>

End

Too bad that _pool is private, or you could just extend it and add a sort method. The good thing though is that the class is so simple and small that you can just implement your own pool class and provide a method to sort the internal stack using the stack's Sort method (which oddly enough is absent from the documentation)

Class MyPool<T>

	Method New( initialCapacity:Int=10 )
		For Local i:=0 Until initialCapacity
			_pool.Push New T
		Next
	End

	Method Allocate:T()
		If _pool.IsEmpty() Return New T
		Return _pool.Pop()
	End
	
	Method Free:Void( t:T )
		_pool.Push t
	End
                
               Method Sort:Void(ascending:Bool)
                 _pool.Sort(ascending)
               End	
  
	
	Field _pool:=New Stack<T>

End

Edit:
You'd likely have to re-implement stack as well, giving it a Compare method for whichever class you are using. This one you could just extend though, and overload the Compare method with your object

jondecker76

(Posted 2014) [#6]

Just looked at it a bit more. Here's a quick example that could get you started (not really tested, but compiled without any errors)

Import brl.pool
Import monkey.stack

Class Sprite
  Field x:Int
  Field y:Int
  Field zOrder:Int
End

' Extend the stack class so we can overload the compare method for
' sorting sprites based on zOrder.  
' Look at how FloatStack/IntStack/StringStack extend Stack in the monkey.stack module for clues...
Class MyStack Extends Stack<Sprite>
  Method New( data:Sprite[] )
		Super.New( data )
  End
  Method Equals:Bool( lhs:Sprite,rhs:Sprite )
		Return lhs.zOrder=rhs.zOrder
  End
  Method Compare:Int( lhs:Sprite,rhs:Sprite )
		Return lhs.zOrder-rhs.zOrder
  End
End

' Create our own pool class with the ability to sort the stack
Class MyPool<T>
  Method New( initialCapacity:Int=10 )
		For Local i:=0 Until initialCapacity
			_pool.Push New T
		Next
	End

	Method Allocate:T()
		If _pool.IsEmpty() Return New T
		Return _pool.Pop()
	End
	
	Method Free:Void( t:T )
		_pool.Push t
	End
	
	Method Sort:Void(ascending:Bool=True)
	  _pool.Sort(ascending)
	End
	
	Field _pool:=New MyStack<T>
End

Raz	(Posted 2014) [#7]

Nice one, cheers Jon, will give it a look :)

Samah

(Posted 2014) [#8]

Yeah the new DiddyStack class will handle most of the sorting stuff for you if you make your class implement IComparable or if you assign a comparator to the stack.
DiddyStack extends the official Monkey Stack class and adds the extra functionality ArrayList supports.

Edit:
I could probably make a simple DiddyPool class that extends DiddyStack to do this kind of thing.

Raz	(Posted 2014) [#9]

That'd be great Samah, if I can keep it all within the same module, perfik.

Samah

(Posted 2014) [#10]

Righto, done. Basically it's a DiddyStack with another internal DiddyStack to hold unallocated objects. If your class implements IPoolable, it will automatically call Reset() when you Free() an object.

Edit:
Grab it from the tip of the containers branch.
http://diddy.googlecode.com/archive/containers.zip

Edit 2:
Added some comparison stuff to the example and print values before and after sorting.

Example:

Import diddy

Class Foo Implements IPoolable, IComparable
	Field val:Int
	
	Method New()
		val = Rnd(1,100)
	End
	
	Method Reset:Void()
		Print "resetting"
		val = Rnd(1,100)
	End
	
	Method CompareTo:Int(other:Object)
		If Foo(other) Then
			Local f:Foo = Foo(other)
			Return Self.val-f.val
		End
		Return 0
	End
End

Function Main()
	' creates a DiddyPool with an empty "active" stack and 10 objects in the "free" stack
	Print "Instantiating with 10 free items"
	Local p:DiddyPool<Foo> = New DiddyPool<Foo>(10)
	
	' Count() and FreeCount() to get "active" and "free" counts respectively
	Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount()
	
	' removes one instance of Foo from the "free" stack, adds it to the "active" stack, and returns it
	Print "Allocating 1"
	Local f:Foo = p.Allocate()
	Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount()
	
	' removes the object from the "active" stack and puts it back in the "free" stack
	' also prints "resetting", because Foo implements IPoolable
	Print "Freeing 1"
	p.Free(f)
	Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount()
	
	' removes 30 items from the "free" stack and adds them to the "active" stack, creating new instances if necessary
	Print "Allocating 30"
	p.Allocate(30)
	Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount()
	
	' frees the item at index 10 - same as p.Free(p.GetItem(10))
	Print "Freeing at index 10"
	p.FreeIndex(10)
	Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount()
	
	' loop on the elements
	Print "Looping on all active (unsorted)"
	For Local f:Foo = EachIn p
		Print f.val
	Next
	
	' sort the items in the "active" stack
	Print "Sorting active"
	p.Sort()
	
	' loop on the elements
	Print "Looping on all active (sorted)"
	For Local f:Foo = EachIn p
		Print f.val
	Next
	
	' loop on the free elements, if you need to
	Print "Looping on all free"
	For Local f:Foo = EachIn p.FreeItems
		' do something with f
		Print "one loop on a free item"
	Next
	
	' free all the active elements
	Print "Freeing all active"
	p.FreeAll()
	Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount()
	
	' clear the free elements
	Print "Clearing all free"
	p.ClearFree()
	Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount()
End

Raz	(Posted 2014) [#11]

Hey Samah, thanks for that :D

I understand ArrayLists are on the way out (and are not present in the above version of Diddy either) so am wondering what exactly I should be replacing them with? Below is how I've been using them.

For Local i:Int = 0 Until activeObjects.Size()
	activeObjects.Get(i).FullUpdate()
End

Ta:)

EDIT: Think I've figured it, am updating my code to use DiddyList

EDIT 2 : Hmm maybe not, DiddyList seems much slower than ArrayList

therevills

(Posted 2014) [#12]

I understand ArrayLists are on the way out

Not if I have anything to do with it ;)

Samah IS going to keep them as I have several projects using them myself... and he is going to benchmark the new stuff to see if they are worthwhile - that's why they are on a different branch.

Samah

(Posted 2014) [#13]

ArrayList has been replaced with DiddyStack, because it extends the official Monkey Stack which basically works the same way as ArrayList.
Using the containers branch is of course optional. therevills is just scared of change. :)

In fact, DiddyStack should be FASTER than ArrayList, because ArrayList used a lot of boxing. Stack uses the actual generic type.

therevills

(Posted 2014) [#14]

Using the containers branch is of course optional. therevills is just scared of change. :)

I'm not... I've just got lots of previous projects using ArrayList and I don't want to go thru them.

In fact, DiddyStack should be FASTER than ArrayList

Sounds like you need to benchmark it... "In fact" and "should" shouldn't be used in the same sentence ;)

Raz	(Posted 2014) [#15]

Ooooo intermodule beef right here!

Thanks you two :D I'll give DiddyStack a look

therevills

(Posted 2014) [#16]

Ooooo intermodule beef right here!

Haha! Samah and myself normally have healthy discussions regarding programming - its all good :)

Samah

(Posted 2014) [#17]

Edit: Ran it again without the string manipulation, and also trying with an object rather than a primitive.
(HTML5 in Chrome 35.0.1897.2 dev-m)

Function Main:Int()
	Local total:Int = 0
	For Local a:Int = 0 Until 10
		Local s:DiddyStringStack = New DiddyStringStack
		Print "adding 5000000 items"
		Local startTime:Int = RealMillisecs()
		For Local i:Int = 0 Until 5000000
			s.AddItem("Item")
		Next
		Local endTime:Int = RealMillisecs()
		total += endTime-startTime
		Print "took "+(endTime-startTime)+"ms"
	Next
	Print "total "+total+"ms"
	Print "average "+(total/10)+"ms"
	Return 0
End

adding 5000000 items
took 386ms
adding 5000000 items
took 339ms
adding 5000000 items
took 352ms
adding 5000000 items
took 362ms
adding 5000000 items
took 353ms
adding 5000000 items
took 335ms
adding 5000000 items
took 329ms
adding 5000000 items
took 343ms
adding 5000000 items
took 338ms
adding 5000000 items
took 307ms
total 3444ms
average 344ms

Function Main:Int()
	Local total:Int = 0
	For Local a:Int = 0 Until 10
		Local s:StringArrayList = New StringArrayList
		Print "adding 5000000 items"
		Local startTime:Int = RealMillisecs()
		For Local i:Int = 0 Until 5000000
			s.Add("Item")
		Next
		Local endTime:Int = RealMillisecs()
		total += endTime-startTime
		Print "took "+(endTime-startTime)+"ms"
	Next
	Print "total "+total+"ms"
	Print "average "+(total/10)+"ms"
	Return 0
End

adding 5000000 items
took 1451ms
adding 5000000 items
took 1254ms
adding 5000000 items
took 1305ms
adding 5000000 items
took 1229ms
adding 5000000 items
took 1231ms
adding 5000000 items
took 1291ms
adding 5000000 items
took 1203ms
adding 5000000 items
took 1171ms
adding 5000000 items
took 1224ms
adding 5000000 items
took 1161ms
total 12520ms
average 1252ms

Function Main:Int()
	Local total:Int = 0
	For Local blah:Int = 0 Until 10
		Local s:DiddyStack<Test> = New DiddyStack<Test>
		Local t:Test = New Test
		Print "adding 5000000 items"
		Local startTime:Int = RealMillisecs()
		For Local i:Int = 0 Until 5000000
			s.AddItem(t)
		Next
		Local endTime:Int = RealMillisecs()
		total += endTime-startTime
		Print "took "+(endTime-startTime)+"ms"
	Next
	Print "total "+total+"ms"
	Print "average "+(total/10)+"ms"
	Return 0
End

Class Test
End

adding 5000000 items
took 379ms
adding 5000000 items
took 332ms
adding 5000000 items
took 353ms
adding 5000000 items
took 340ms
adding 5000000 items
took 344ms
adding 5000000 items
took 354ms
adding 5000000 items
took 386ms
adding 5000000 items
took 374ms
adding 5000000 items
took 357ms
adding 5000000 items
took 368ms
total 3587ms
average 358ms

Function Main:Int()
	Local total:Int = 0
	For Local blah:Int = 0 Until 10
		Local s:ArrayList<Test> = New ArrayList<Test>
		Local t:Test = New Test
		Print "adding 5000000 items"
		Local startTime:Int = RealMillisecs()
		For Local i:Int = 0 Until 5000000
			s.Add(t)
		Next
		Local endTime:Int = RealMillisecs()
		total += endTime-startTime
		Print "took "+(endTime-startTime)+"ms"
	Next
	Print "total "+total+"ms"
	Print "average "+(total/10)+"ms"
	Return 0
End

Class Test
End

adding 5000000 items
took 528ms
adding 5000000 items
took 553ms
adding 5000000 items
took 556ms
adding 5000000 items
took 504ms
adding 5000000 items
took 545ms
adding 5000000 items
took 555ms
adding 5000000 items
took 505ms
adding 5000000 items
took 514ms
adding 5000000 items
took 563ms
adding 5000000 items
took 498ms
total 5321ms
average 532ms

Raz	(Posted 2014) [#18]

After a slight hiccup (involving me freeing items as I was iterating through the pool instead of just calling freeall() afterwards), I am now happily using DiddyPool and DiddyStack and finding much less memory and CPU usage :)

Thanks for all the help, I'm mighty impressed!

Samah

(Posted 2014) [#19]

You're welcome. :)
Now I just have to actually work on my own game. XD
(inb4 therevills)