[vJASS] need ideas on how to improve this code

[dardas]

hey.. actually managed to do something with my stack code,
which so far amazingly helped me alot.. [percents, enumoration data, etc]
but i need ideas on what to add/how to improve it,
and if there is anything wrong i've done.

library Stack
    globals
        public constant boolean DEBUG_MODE = true
    endglobals
endlibrary

//! textmacro NEW_STACK takes nameHEADER, valueTYPE, ZeroTheValue

function interface enumorationResponse$valueTYPE$ takes $valueTYPE$ data, handle passedKey returns boolean
    
struct $nameHEADER$Stack
    public integer                  LAST_INDEX
    public integer                  instanceCount
    public $valueTYPE$ array        data            [12000]
    public handle array             passedKey       [12000]
    public boolean array            locked          [12000]
    public boolean array            online          [12000]
        
    public method add takes $valueTYPE$ value, handle messageKey returns integer
        if instanceCount < 11999 then
            set data[instanceCount]             = value
            set passedKey[instanceCount]        = messageKey
            set locked[instanceCount]           = false
            set online[instanceCount]           = true
            set instanceCount                   = instanceCount + 1
        elseif instanceCount >= 11999 and Stack_DEBUG_MODE == true then
            call BJDebugMsg("$nameHEADER$Stack has reached data limit, cannot add more values to the stack.")
            return null
        endif
        set LAST_INDEX = instanceCount
        return instanceCount
    endmethod
        
    public method editKey takes integer index, handle key returns boolean
        if locked[index] == true then
            return false
        endif
        
        set passedKey[index] = key
        return true
    endmethod
        
    public method lock takes integer index, boolean lock returns nothing
        set locked[index] = lock
    endmethod
        
    public method swap takes integer indexA, integer indexB returns boolean
        local $valueTYPE$ dataA = data[indexA]
        local $valueTYPE$ dataB = data[indexB]
        local handle keyA       = passedKey[indexA]
        local handle keyB       = passedKey[indexB]
        if locked[indexA] or locked[indexB] or online[indexA] == false or online[indexB] == false then
            return false
        endif
            
        set data[indexA] = dataB
        set data[indexB] = dataA
        set passedKey[indexA] = keyB
        set passedKey[indexB] = keyA
        
        return true
    endmethod
        
    public method clean takes integer index returns boolean
        if online[index] == false then
            return false
        endif
        set online[index]       = false
        
        static if $boolean$ then
            set data[index]     = 0
        else
            set data[index]     = null
        endif
        
        set passedKey[index]    = null
        set locked[index]       = false
        return true
    endmethod
        
    public method enumorate takes enumorationResponse$valueTYPE$ ev, boolean TopToBottom returns nothing
        local integer start = 0
        local integer i
        local integer end = instanceCount
        local integer step = 0
        local integer step2 = 1
        local boolean destroy = false
        if TopToBottom then
            set start = instanceCount
            set end = 0
            set step = -1
            set step2 = 0
        endif
        set i = start
        loop
            set i = i + step
            if online[i] == true then
                set destroy = ev.evaluate(data[i], passedKey[i])
            endif
            if destroy then
                call clean(i)
            endif
            set i = i + step2
            exitwhen i == end
        endloop
    endmethod
endstruct

//! endtextmacro

//! runtextmacro NEW_STACK("i", "integer", "true")
//! runtextmacro NEW_STACK("r", "real", "true")
//! runtextmacro NEW_STACK("d", "destructable", "false")

thanks in advance. [well.. its actually my first code i manged to fix without getting too mad.. TBH just made it 1 hour ago.. guessing this wasnt to hard.. used some functions from my old code too, which saved me lot's of time.] please do not tell me theres the original stack,
as i realise that. and i wanted this cuz i like behing able to customize my own codes to my usage. (like the textmacro)

 

[Berb]

library Stack
    globals
        public constant boolean DEBUG_MODE = true
    endglobals
endlibrary

I don't get why you did this. Just make it all the same library. There's no reason not to, anyhow.

Other than that it looks fine. Stacks are fairly simple data structures.

 

[PurgeandFire]

Here is my feedback.

1) In the method "enumorate" ( it is spelled enumerate ;D ), you don't need the variable i. You can just use "start" as the loop iterator.

2) In that same method, you don't need the variable "destroy". You can make this:

            if online[i] == true then
                set destroy = ev.evaluate(data[i], passedKey[i])
            endif
            if destroy then
                call clean(i)
            endif

Become:

                if online[i] and ev.evaluate(data[i], passedKey[i]) then
                    call clean(i)
                endif

The reason why is because the way if-blocks work. Consider this:
if booleanA and booleanB then
If booleanA is true, then it will evaluate booleanB to see if that is true. If booleanA is false, it will immediately exit the if-check, so booleanB will be left unevaluated. Meaning, it will only perform ev.evaluate() if online[end] returns true. Some useful information.

3) In that same method, I suggest you use an if-block to determine which way to loop. That will compress a lot of it. It can end up looking like this:

    public method enumorate takes enumorationResponse$valueTYPE$ ev, boolean TopToBottom returns nothing
        local integer start
        local integer end   = instanceCount
        if TopToBottom then
            loop
                if online[end] and ev.evaluate(data[end], passedKey[end]) then
                    call clean(end)
                endif
                set end = end - 1
                exitwhen end == 0
            endloop
        else
            set start = 0
            loop
                if online[start] and ev.evaluate(data[start], passedKey[start]) then
                    call clean(start)
                endif
                set start = start + 1
                exitwhen start == end
            endloop
        endif
    endmethod

Which is much better.

4) This way looks a little bit uglier, but it optimizes your swap method:

    public method swap takes integer indexA, integer indexB returns boolean
        local $valueTYPE$ dataA = data[indexA]
        local handle keyA       = passedKey[indexA]
        if locked[indexA] or locked[indexB] or online[indexA] == false or online[indexB] == false then
            return false
        endif
        
        set data[indexA] = data[indexB]
        set data[indexB] = dataA
        set passedKey[indexA] = passedKey[indexB]
        set passedKey[indexB] = keyA
        
        return true
    endmethod

Basically, you use data[indexB] and passedKey[indexB] directly instead of declaring local variables for it.

5) Because you have if instanceCount < 11999 then, the else portion will only be executed if instanceCount >= 11999, so you can remove the elseif check.

6) Instead of having your own debug mode check, use the one provided with the NewGen editor. Those error messages will only show with debug mode enabled (which you should have enabled for editing [JassHelper -> Debug Mode]). In a regular game, any text within the debug mode blocks will be removed (or commented out, I don't remember).

        else
            static if DEBUG_MODE then 
                call BJDebugMsg("$nameHEADER$Stack has reached data limit, cannot add more values to the stack.")
                return null
            endif
        endif

7) When you are done using that code for whatever purposes, you may want to reduce the array count a bit. 12k is quite large. If you leave it just as normal, it will have 8192, which should be completely reasonable for any sane purposes. xD

8) On another note, you may want to look into array structs. (structs that extends arrays) Since you don't really use allocation and deallocation, making your struct extend array and changing the variables to static will optimize it a lot, since JassHelper assumes to allow for that data to have multiple instances. The code will be a bit longer because of the array size extension, but if you remove the array size definition, it will be a lot more compact. (and not to mention, a lot more efficient)

9) Your code has a syntax error. static if $boolean$ then should be static if $ZeroTheValue$ then.

 

[dardas]

thanks for the help, i've fixed all there was to fix in what you told, so thanks

 

[Nestharus]

    public $valueTYPE$ array        data            [12000]
    public handle array             passedKey       [12000]
    public boolean array            locked          [12000]
    public boolean array            online          [12000]

don't use sized arrays like that... that's worse than a hashtable.

A stack is traditionally a type of linked list... trying to do a stack via an array is just a bad idea except in rare situations.

 

[dardas]

Edit: sorry, had a lag o.o

edit2: so nest, to use hashtable? ;p

 

[Nestharus]

A stack is traditionally a type of linked list... trying to do a stack via an array is just a bad idea except in rare situations.

no, I suggest an array using a linked list ;p

 

[Dr Super Good]

A stack is traditionally a type of linked list... trying to do a stack via an array is just a bad idea except in rare situations.

Wrong...

Almost all stacks are done using an array as it is far far far faster than using a linked list system.

Remember a while back there was a crash hack abusing the finite size of the WC3 stack (only allocated so much array space). Stacks in micro controlers all use a finite array size. Stacks often have to be fast and are extreemly simple to impliment even in assembly code using some form of array.

I do agree though that linked list stacks have their uses. When speed is not crutial but the exact capacity requirements are not known or if you need lots of small stacks then a linked list stack is great as it gives you the flexibility needed without wasting space. Ofcourse nearly every purpose can use a linked list sort of stack but do remember that because the items are not stored sequentially that there is time and memory overhead for recycling space (to permit reallocation to other stacks).

In the case of a computer program where you have like 4 GB of memory, an array stack is no problem and of great speed benifit for purposes like the stack accompanying a thread.

In WC3 jass scripts. A linked list approach may be advisable due to the limited array allocation ability you have available.

 

[Nestharus]

I was talking in scope of wc3 JASS scripts. I almost never see an array stack in wc3 JASS =).

 

[Bribe]

Linked Lists are superior to Stacks in iteration speed, which is where it counts. Linear Stacks are important for random-data acces / arbitrary slot access.

A Stack that cannot be created/destroyed might be considered a StaticStack, Berb developed such a module and it's the fastest Stack implementation. There is also the StaticList module that I developed that's soon to see a nice update, which is already the fastest linked-list method and soon to be even faster.

In development, I have written a List library, a Stack library and a Pool library, all of which are based on the Table library making it possible to have unlimited instances of any of these structures. Key features being nearly all operations O(1) in complexity, which means a lot of reverse-lookups.

 

[Nestharus]

Bribe, linked list is only faster in the JASS language =P. In any other language, an array is going to be faster to iterate over.

This is a testament to just how slow JASS math is.

 

[Bribe]

I fail to see how

this = this.next

Is going to be slower than:

i ++
this = stack

In any sense of programming logic.

 

[Nestharus]

No, the increment by 1 is faster than the variable lookup.

http://stackoverflow.com/questions/393556/when-to-use-a-linked-list-over-an-array-array-list

Array Lists (like those in .Net) give you the benefits of arrays, but dynamically allocate resources for you so that you don't need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around. Performance-wise, arraylists are slower than raw arrays.

And keep in mind that an array list is a linked list.

Arrays are preferable when:

c) you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.

Don't use an array list when you need speed


In languages other than JASS, iterating through an array is faster than iterating through a list.

 

[Dr Super Good]

And keep in mind that an array list is a linked list.

I do not think so...

An array list is a list backed by a dynamic array storing the data sequentially.
A linked list is a list backed by a chain of nodes which store the data.

A list is a sequential ordered collection of data.
Sequential means that there are no gaps in the data (and what is put in can be recalled). An ordered means that the way data is placed in it determines the order of recolection. A collection supports duplicate data (unlike a set where every element must be unique).

An array list has the main advantage of O(1) random acess. A linked list has a worst case performance of O(n) random acess.

A linked list main advantage is its ability to dynamically allocate and deallocate elements meaning that within the same data space, many linked lists could exist. This avoids problems with fragmenetation that dynamic arrays suffer from.

Keep in mind that all arrays in WC3 JASS are dynamic arrays with an upperbound capacity of 2^13 (8192).

Using a single array as an array list is very easy in JASS. The problem comes with being able to dynamically allocate array list structures into a single array (or multiple in series) as you then need to handle fragmentation and bulk copying of data which is slow. Using a linked list is easier as the positioning of nodes does not mater in the array so recycling space is easy.

 

[Nestharus]

ok, ok >.>

the point I was making was that iterating through a linked list is JASS being faster than iterating through an array in JASS is a testament to just how slow JASS math is as in like any other language, iterating through an array would be faster as it's just incrementing the pointer by 1 rather than looking up a node.

c) you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.

;D

 

[Dr Super Good]

Is addition really that slow that it gets beat by multiple array lookups (each array lookup uses addition internally)?

 

[Nestharus]

Bench it ;D

I do know that node = next[node] is faster than node = node + 1 in JASS though ; P

 

[Bribe]

Is addition really that slow that it gets beat by multiple array lookups (each array lookup uses addition internally)?

The looping structure is:

//Linked list
loop
    set this = this.next
    exitwhen this == 0
    //Activity
endloop
//Stack
loop
    exitwhen i == 0
    set i = i - 1
    set this = stack[i]
    //Activity
endloop

No way that JASS stack is going to be looping faster than that simple linked list.

 

[Berb]

exitwhen (i < 0)

Only in the JASS struct do you not have the 0 index available.

 

[Bribe]

I wired that loop so the 0-index is counted, so i == 0 will be fine. My loop structures are a bit... informal.

 

[Dr Super Good]

//Stack
loop
exitwhen i == 0
set i = i - i
set this = stack
//Activity
endloop

This does not even make sense.... Why you returning the 0th index of the stack all the time?

set i = i - i
is the same as
set i = 0

 

[Berb]

I wired that loop so the 0-index is counted, so i == 0 will be fine. My loop structures are a bit... informal.

Oh yea you decrement the counter before referencing it. Gosh.

This does not even make sense.... Why you returning the 0th index of the stack all the time?

Haha it's likely he meant to decrement it by 1 rather than i. Funny typo.