allocation with one variable

[Ruke]

static method allocate takes nothing returns integer
    local integer instance = recycle[0]

    if ( recycle[instance] == 0 ) then
        set recycle[0] = instance + 1
    else
        set recycle[0] = recycle[instance]
    endif

    return instance
endmethod

static method deallocate takes integer instance returns nothing
    set recycle[instance] = recycle[0]
    set recycle[0] = instance
endmethod

hope helps someone.

greetings.

edit: to understand what happens here:

recycle[0] = here we're going to store a fresh/ready-to-use instance

if ( recycle[instance] == 0 ) -> means, if there are no recycled instances then...

set recycle[0] = recycle[instance] -> this is a chain, it gets a little bit tricky, but here is an example:

a = allocate() = 1
b = allocate() = 2
c = allocate() = 3
d = allocate() = 4

deallocate(c)
deallocate(d)

e = allocate() = d = 4
f = allocate() = c = 3

so, first we deallocate c and then d, what happens in deallocate?

recycle[3] = recycle[0]
recycle[0] = 3

now d:

recycle[4] = recycle[0] // recycle[0] = c = 3 //chain time
recycle[0] = 4

now lets see what happens when i allocate having some recycled ids:

we know that we have a fresh instance in recycle[0] (which is d -> 4), but we have to check if there're more recycled ids in the chain

if ( recycle[instance] == 0 ) -> false, we have recycled ids (a chain).

so update index 0 of recycle with the next one:

set recycle[0] = recycle[instance]

recycle[instance] = c = 3, remember the chain?

but, what happens if i don't have any chain (recycled instances)?

well, if ( recycle[instance] == 0 ) -> true, so:

set recycle[0] = instance + 1

so, first recycle[0] is 0, and then we do recycle[0] + 1 (instance + 1) which is 1 and so on, pretty simple.

 

[edo494]

nice explanation, but this does the very same thing as far as I know. Even has the same variable name

edit: actually no it uses one extra variable, nevermind

 

[Troll-Brain]

You forgot something, in the current state there is no way you will get "1" as the first instance, it will be "0"

 

[Zeatherann]

Nestharus already had something like this?

library Alloc /* v1.1.1.3
*************************************************************************************
*
*	*/uses/*
*
*		*/ ErrorMessage /*
*
************************************************************************************
*
*	module Alloc
*
*		static method allocate takes nothing returns thistype
*		method deallocate takes nothing returns nothing
*
*		readonly boolean isAllocated
*
*		debug static method calculateMemoryUsage takes nothing returns integer
*		debug static method getAllocatedMemoryAsString takes nothing returns string
*
************************************************************************************/
	module Alloc
		private static integer array recycler

		method operator isAllocated takes nothing returns boolean
			return recycler[this] == -1
		endmethod

		static method allocate takes nothing returns thistype
			local thistype this = recycler[0]

			debug call ThrowError(this == 0, "Alloc", "allocate", "thistype", 0, "Overflow.")

			set recycler[0] = recycler[this]
			set recycler[this] = -1

			return this
		endmethod

		method deallocate takes nothing returns nothing
			debug call ThrowError(recycler[this] != -1, "Alloc", "deallocate", "thistype", this, "Attempted To Deallocate Null Instance.")

			set recycler[this] = recycler[0]
			set recycler[0] = this
		endmethod

		private static method onInit takes nothing returns nothing
			local integer i = 0

			set recycler[8191] = 0 //so that the array doesn't reallocate over and over again

			loop
				set recycler[i] = i + 1

				exitwhen i == 8190
				set i = i + 1
			endloop
		endmethod

		static if DEBUG_MODE then
			static method calculateMemoryUsage takes nothing returns integer
				local integer start = 1
				local integer end = 8191
				local integer count = 0

				loop
					exitwhen start > end
					if (start + 500 > end) then
						set count = count + checkRegion(start, end)
						set start = end + 1
					else
						set count = checkRegion(start, start + 500)
						set start = start + 501
					endif
				endloop

				return count
			endmethod

			private static method checkRegion takes integer start, integer end returns integer
				local integer count = 0

				loop
					exitwhen start > end
					if (recycler[start] == -1) then
						set count = count + 1
					endif
					set start = start + 1
				endloop

				return count
			endmethod

			static method getAllocatedMemoryAsString takes nothing returns string
				local integer start = 1
				local integer end = 8191
				local string memory = null

				loop
					exitwhen start > end
					if (start + 500 > end) then
						if (memory != null) then
							set memory = memory + ", "
						endif
						set memory = memory + checkRegion2(start, end)
						set start = end + 1
					else
						if (memory != null) then
							set memory = memory + ", "
						endif
						set memory = memory + checkRegion2(start, start + 500)
						set start = start + 501
					endif
				endloop

				return memory
			endmethod

			private static method checkRegion2 takes integer start, integer end returns string
				local string memory = null

				loop
					exitwhen start > end
					if (recycler[start] == -1) then
						if (memory == null) then
							set memory = I2S(start)
						else
							set memory = memory + ", " + I2S(start)
						endif
					endif
					set start = start + 1
				endloop

				return memory
			endmethod
		endif
	endmodule
endlibrary

 

[Almia]

Not sure if this explains/posts a new allocation method or if Ruke doesn't know about Nestharus'/Sevion's Alloc lib so he writes his own one.

 

[Ruke]

yes i know them, but nes' one requires a loop in init, this doesn't (but as troll pointed out, first instance == 0).

 

[Zeatherann]

I personally like the loop because of how it ensured good ordering, and since it's only one variable I'd imagine it to be one of the fastest methods.

 

[PurgeandFire]

I personally like the loop because of how it ensured good ordering, and since it's only one variable I'd imagine it to be one of the fastest methods.

I suppose it depends on what one prefers. Nes' allocation is neat, but from a programming perspective, allocating 8190 slots in a variable when they may not even be used is debatable. Memory is cheap, but it just feels weird to be wasteful with it, especially when we already make such a big deal about simple reference leaks and memory leaks (because conserving memory is good practice, we don't make a distinction of whether it'll actually make a difference).

IMO, I would prefer an implementation like Ruke's, even if it has slightly extra overhead. But that is just me. To each his own.

 

[Zeatherann]

The data for the variable array is already allocated for the entire index field. Also, look at Java, and realize that wasting memory seems to be commonplace now. Which is sad. Memory is cheap, and it's not wasted if it being utilized to quicken calculations and code execution. Though, you are right in that is personal preference. This is coming from a person that writes video games in C++.

 

[edo494]

Arent arrays in Jass dynamicaly allocated in powers of two and since one hardly allocates 2k instances at once, you basically wastefully allocated 6k integers in memory. While memoy is cheap, that is 14k+ bytes per struct

 

[Nestharus]

I'm still debating over which one is better to use. I'm leaning in the direction of this one, but the other excels at heavy operations as it more easily avoids the op limit, which is a huge pro in my book. It makes libraries like Trigger not require nested trigfer evaluations like BigInt did , which makes the code easier to write, read, and maintain. This one has like double the operations, no?

It'll require more thought, but right now i'm pretty happy with the very low cost of allocation in mine. I'm probably going to tighten it a little more when i do the dds update.

 

[PurgeandFire]

@Zeatherann: edo's post.

I'm still debating over which one is better to use. I'm leaning in the direction of this one, but the other excels at heavy operations as it more easily avoids the op limit, which is a huge pro in my book. It makes libraries like Trigger not require nested trigfer evaluations like BigInt did , which makes the code easier to write, read, and maintain. This one has like double the operations, no?

It'll require more thought, but right now i'm pretty happy with the very low cost of allocation in mine. I'm probably going to tighten it a little more when i do the dds update.

It may vary from case to case. I think you're right that it is better to use your other method for things like BigInt (wherever one operation becomes costly). If I were designing a default struct implementation, I would probably go for this one though, since it has the least amount of opposition/controversy. For most situations, it is comparing apples to apples.

 

[Zeatherann]

@edo; While the memory is allocated, the old space is deallocated once the data is copied over.

 

[edo494]

once you allocate space for jass arrays they will not shrink down on their size, so the memory will persist until the end of map for user.

Also yea 14k memory is not much, but it may slow down the map initialization drastically with few hundred structs, because you loop over 8191 indexes of array per struct, causing you to iterate over 800,000 indexes with 100 structs. That will slow your map down drastically for pretty much no effect.

Like, I dont even know why you go over the indexes, because the allocate looks the very same as allocate on any other alloc, which dont use onInit loops

 

[Nestharus]

How about both?

Just use module based on your needs. Heavy op use one, all rest use other. Seems like best solution. I'll draw a library up.

 

[Zeatherann]

What I think would be a nice fix for that is have the Allocation struct have an array that's initialized to all the default values. The index array inside the structs that use the Allocation struct should set values in that array only when the changed the first time. This limits the array space allocation on map initialization to a minimum. I don't write vJASS therefore I can't provide a code example for this.

 

[Waffle]

hmm.. that does sound kind of nice..
but wouldn't that like need a permanent proxy that would slow down all future array accesses?

 

[Zeatherann]

It would only slow down once it creates a new instance past the old maximum instance count. But, if the number of instances decreased, then creating more up to the maximum would have no delay caused by this. When I say maximum, I mean the highest number of instances existing at any given time.

 

[HerlySQR]

Just in case, following this

You forgot something, in the current state there is no way you will get "1" as the first instance, it will be "0"

The correct code will be like this:

static method allocate takes nothing returns integer
    local integer instance = recycle[0]

    if ( recycle[instance] == 0 ) then
        set instance = instance + 1
        set recycle[0] = instance
    else
        set recycle[0] = recycle[instance]
    endif

    return instance
endmethod

static method deallocate takes integer instance returns nothing
    set recycle[instance] = recycle[0]
    set recycle[0] = instance
endmethod