1. Updated Resource Submission Rules: All model & skin resource submissions must now include an in-game screenshot. This is to help speed up the moderation process and to show how the model and/or texture looks like from the in-game camera.
    Dismiss Notice
  2. DID YOU KNOW - That you can unlock new rank icons by posting on the forums or winning contests? Click here to customize your rank or read our User Rank Policy to see a list of ranks that you can unlock. Have you won a contest and still haven't received your rank award? Then please contact the administration.
    Dismiss Notice
  3. Lead your forces to battle in the 15th Techtree Contest. The call is yours, commander!
    Dismiss Notice
  4. The reforging of the races is complete. Come see the 14th Techtree Contest Results.
    Dismiss Notice
  5. It's time to choose your horse in the race - the 32nd Modeling Contest Poll is up!
    Dismiss Notice
  6. Check out the Staff job openings thread.
    Dismiss Notice
Dismiss Notice
60,000 passwords have been reset on July 8, 2019. If you cannot login, read this.

[vJASS] need ideas on how to improve this code

Discussion in 'Triggers & Scripts' started by dardas, Apr 1, 2011.

  1. dardas

    dardas

    Joined:
    Sep 12, 2008
    Messages:
    649
    Resources:
    0
    Resources:
    0
    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.
    Code (vJASS):

    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)
     
  2. Berb

    Berb

    Joined:
    Jan 21, 2006
    Messages:
    2,539
    Resources:
    2
    JASS:
    2
    Resources:
    2
    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.
     
  3. PurgeandFire

    PurgeandFire

    Code Moderator

    Joined:
    Nov 11, 2006
    Messages:
    7,426
    Resources:
    18
    Icons:
    1
    Spells:
    4
    Tutorials:
    9
    JASS:
    4
    Resources:
    18
    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:
    Code (vJASS):
                if online[i] == true then
                    set destroy = ev.evaluate(data[i], passedKey[i])
                endif
                if destroy then
                    call clean(i)
                endif

    Become:
    Code (vJASS):
                    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:
    Code (vJASS):
        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:
    Code (vJASS):
        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).
    Code (vJASS):
            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. :p 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
    .
     
  4. dardas

    dardas

    Joined:
    Sep 12, 2008
    Messages:
    649
    Resources:
    0
    Resources:
    0
    thanks for the help, i've fixed all there was to fix in what you told, so thanks :D
     
  5. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,146
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    Code (vJASS):

        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.
     
  6. dardas

    dardas

    Joined:
    Sep 12, 2008
    Messages:
    649
    Resources:
    0
    Resources:
    0
    Edit: sorry, had a lag o.o

    edit2: so nest, to use hashtable? ;p
     
    Last edited: Apr 2, 2011
  7. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,146
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    no, I suggest an array using a linked list ;p
     
  8. Dr Super Good

    Dr Super Good

    Spell Reviewer

    Joined:
    Jan 18, 2005
    Messages:
    25,944
    Resources:
    3
    Maps:
    1
    Spells:
    2
    Resources:
    3
    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.
     
  9. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,146
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    I was talking in scope of wc3 JASS scripts. I almost never see an array stack in wc3 JASS =).
     
  10. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    8,193
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    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.
     
  11. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,146
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    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.
     
  12. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    8,193
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    I fail to see how

    this = this.next

    Is going to be slower than:

    i ++
    this = stack

    In any sense of programming logic.
     
  13. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,146
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    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

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

    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.
     
  14. Dr Super Good

    Dr Super Good

    Spell Reviewer

    Joined:
    Jan 18, 2005
    Messages:
    25,944
    Resources:
    3
    Maps:
    1
    Spells:
    2
    Resources:
    3
    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.
     
  15. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,146
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    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.

    ;D
     
  16. Dr Super Good

    Dr Super Good

    Spell Reviewer

    Joined:
    Jan 18, 2005
    Messages:
    25,944
    Resources:
    3
    Maps:
    1
    Spells:
    2
    Resources:
    3
    Is addition really that slow that it gets beat by multiple array lookups (each array lookup uses addition internally)?
     
  17. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,146
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    Bench it ;D

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

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    8,193
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    The looping structure is:

    Code (vJASS):

    //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.
     
    Last edited: Apr 6, 2011
  19. Berb

    Berb

    Joined:
    Jan 21, 2006
    Messages:
    2,539
    Resources:
    2
    JASS:
    2
    Resources:
    2
    Code (vJASS):
    exitwhen (i < 0)


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

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    8,193
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    I wired that loop so the 0-index is counted, so i == 0 will be fine. My loop structures are a bit... informal.