[vJass] ForLoopHelper

[Captain Griffen]

vJass script for substantially increasing the speed of looping through integers (gets inlined by JassHelper).

Example use:

function X takes nothing returns nothing
    local integer i = 0
    loop
        set i = Increment(i)
        // Do something here.
        exitwhen i>=100
    endloop
    // Something will have been done 100 times.
endfunction

library ForLoopHelper

//*********************************************************************
//* ForLoopHelper
//* ----------
//*
//*  This library has been designed to improve the performance of for
//* loops. Whenever you would normally use "set i=i+1" in a loop,
//* replace it with "set i=Increment(i)". Likewise, "set i=i-1" can be
//* replaced with "set i=Decrement(i)". The two functions get inlined
//* resulting in a simple array read, which is 12% faster than adding
//* or subtracting 1 to/from the variable i.
//*
//*  The obvious limitation here is that the value being incremented
//* must not be smaller than 0 or larger than 8190 and it can only be
//* incremented or decremented by 1, but this should be enough to
//* cover nearly all for loops.
//*********************************************************************

    globals
        // This determines how many indexes will be initialized and affects loading time.
        // The number has to be larger than the longest for loop that uses this library.
        // This number may not be larger than 8190, since that is the maximum array size.
        private constant integer MAX_INDEX = 8190
    endglobals

//=====================================================================

    private module Initialization
        static method onInit takes nothing returns nothing
            local integer i=0
            local integer j
            loop
                exitwhen i>MAX_INDEX
                set j=i+1
                set .next[i]=j
                set .prev[j]=i
                set i=j
            endloop
            set .prev[0]=-1
        endmethod
    endmodule
    private struct Inc extends array
        static integer array next
        static integer array prev
        implement Initialization
    endstruct

//=====================================================================

    function Increment takes integer i returns integer
        debug if i<0 or i>8190 then
        debug    call BJDebugMsg("Increment error: The integer being incremented must not be less than 0 or more than "+I2S(MAX_INDEX)+".")
        debug    return i+1
        debug endif
        return Inc.next[i]
    endfunction

    function Decrement takes integer i returns integer
        debug if i<0 or i>8190 then
        debug    call BJDebugMsg("Decrement error: The integer being decremented must not be less than 0 or more than "+I2S(MAX_INDEX)+".")
        debug    return i-1
        debug endif
        return Inc.prev[i]
    endfunction

endlibrary

 

[Magtheridon96]

Pros:
-Allows loops to be substantially faster
-Jass math is slow, so this helps
-Functions are inlined

Cons:
-Limits indices in loops to be between 0 and 8190

This is actually pretty good :]

Just one tip:
To reduce the load on the CPU, you can change "next" and "prev" to "n" and "p"
Nestharus' Short-Variable-Naming convention isn't THAT bad

 

[Captain Griffen]

Pros:
-Allows loops to be substantially faster
-Jass math is slow, so this helps
-Functions are inlined

Cons:
-Limits indices in loops to be between 0 and 8190

This is actually pretty good :]

Just one tip:
To reduce the load on the CPU, you can change "next" and "prev" to "n" and "p"
Nestharus' Short-Variable-Naming convention isn't THAT bad

Thanks. The name length shouldn't matter, since you should already be using Vex's optimiser.

 

[Magtheridon96]

Thanks. The name length shouldn't matter, since you should already be using Vex's optimiser.

hehe.. someone should tell Nestharus XD

 

[Nestharus]

Thanks. The name length shouldn't matter, since you should already be using Vex's optimiser.

You can't use vex's optimizer since it's broken..

if you have any AI natives in the map, it'll explode.

Also

This depends on how many functions/variables/etc are in the scope. A map with a large amount of variables would actually be slower running on this rather than the +-1.

edit
Just a little thing that prob doesn't matter, but could help decrease loading time by a millisecond or too

exitwhen i>MAX_INDEX

It's faster to loop backwards and compare to 0 =)

 

[Magtheridon96]

It's faster to loop backwards and compare to 0 =)

That is some BACKWARDS thinking dude xD
See what I did there... Anyone? ... meh, I'm lame =P

 

[tooltiperror]

I suspect either of the following

• WC3 uses the same size byte for all integers so comparing to zero is equally slow
• WC3 uses a one-bit byte for zero and the speed difference is completely negligible.

EDIT Interesting, so this replaces JASS arithmetic with an array lookup, using a two way list. Very clever.

I'm wondering if even a hashtable read is faster than a math operation.

 

[Troll-Brain]

I don't know about the 0 comparaison, i would just assume as the truth what a such speedfreak as Nestharus says (i mean it's most likely he has already made such speed tests).

But one thing is obvious, backward is indeed faster.
Since arrays are dynamic is jass, it's just faster to size the array only one time (max index directly used), instead of X times (heard it's made by power of 2, but i don't see how to test it).
You probably figured it, but i guess more precisions can't be bad.

PS : Jass is so fun, an array read faster than a simple math operation.

 

[PurgeandFire]

debug if i<0 or i>8190 then

Shouldn't that be:
debug if i<0 or i>MAX_INDEX then

 

[Bribe]

Off-topic:

Someone making a working optimizer to shorten names wouldn't be too bad. That someone will probably end up being me, I'll just break off a part of Lucky Parser's optimization process and make it a standalone thing.

On-topic:

Array read speed being faster than JASS math simply makes my head spin. Someone needs to make a stress test (high-speed timer running lots of iterations) and paste it here within a map. That someone will probably end up being me as well...

Did you test this percentage with or without the optimizer's "shorten names" feature?

If you want completeness for this library, include an array read for zero: "IsZero".

boolean array iszero
 
onInit:
    set iszero[0] = true
 
function IsZero takes integer i returns boolean
    return iszero[i]
endfunction

Increment and Decrement are pretty generic names which may conflict with other setups. IncInteger or DecInteger sound more appropriate.

Applying these suggestions and those in the previous posts (compare against 0 in the initialization, fixing the debug things) this looks plenty reasonable.

 

[WaterKnight]

PS : Jass is so fun, an array read faster than a simple math operation.

+normal integer variable read for the array's index

 

[Troll-Brain]

+normal integer variable read for the array's index

Yeah i know, that was implicit.

 

[Magtheridon96]

Someone needs to make a stress test (high-speed timer running lots of iterations) and paste it here within a map. That someone will probably end up being me as well...

> Reserved post >

edit
Meh,.. I tried.. They were too fast =P

 

[Bribe]

You have to really load on the instances

Probably needs about 30K iterations per 0.03125 interval to start to feel the effects.

 

[Nestharus]

Try creating 1000+ variables and 500 functions in the map and then compare them to the +-1 iteration =).

 

[Bribe]

Any opinions on the naming convention suggestions? Love/hate? Ignore?

 

[Magtheridon96]

Honestly, the names should be like this:
Increment -> increment
Decrement -> decrement

OR

-> increase
-> decrease

 

[Bribe]

As they are normal functions, they should be capitalized according to JASS convention (CreateUnit, ModuloInteger, etc.)

The things that don't start with uppercase are variables and struct methods.

 

[Magtheridon96]

I thought you were hinting the 'bad' naming with this:

Any opinions on the naming convention suggestions? Love/hate? Ignore?

Yeah, I'm always wrong

 

[Bribe]

I was referring to my earlier post "Increment and Decrement are pretty generic names which may conflict with other setups. IncInteger or DecInteger sound more appropriate."

 

[Magtheridon96]

Or simply IncInt and DecInt

 

[Nestharus]

It'd be nicer if you just had a Loop struct with a readonly next and readonly previous >.>.

No need for the functions. Just make 8191.next go to 0 and 0.previous go to 8191.

 

[Magtheridon96]

Is this what you mean?

library ForLoopHelper
    private module I
        static method onInit takes nothing returns nothing
            local integer i=0
            local integer j
            loop
                exitwhen i>8190
                set j=i+1
                set thistype.n[i]=j
                set thistype.p[j]=i
                set i=j
            endloop
            set thistype.p[0]=8190
            set thistype.n[8190]=0
        endmethod
    endmodule
    
    private struct Loop extends array
        readonly static integer array n
        readonly static integer array p
        implement I
    endstruct
endlibrary

 

[Nestharus]

no... public readonly thistype next inside of a Loop struct or something.

 

[Magtheridon96]

Nah, it's fine the way it is
Or:

library Loop
    globals
        public integer array n
        public integer array p
    endglobals
    
    private module I
        private static method onInit takes nothing returns nothing
            local integer i = 0
            loop
                exitwhen i > 8191
                set p[i] = i-1
                set n[i] = i+1
                set i=n[i]
            endloop
        endmethod
    endmodule
    private struct Loop
        implement I
    endstruct
endlibrary

 

[Nestharus]

why not just readonly thistype next and readoly thistype previous... it gets rid of the functions, thus keeping scope from being spammed.

and n/p are not intuitive.. never do short names in the API >.<

 

[Magtheridon96]

never do short names in the API >.<

Don't worry, they're public, so they're going to be referred to as Loop_n and Loop_p

 

[Nestharus]

.... then that means you can write to them ....

 

[Magtheridon96]

Then don't >.> (Have some self-control lol )

 

[Nestharus]

mag mag, you need to learn about encapsulation.

 

[Magtheridon96]

That made me laugh a bit
I know it's best to be readonly, but.. nah
Anyway, third time's the charm:

library Loop
    private module I
        private static method onInit takes nothing returns nothing
            local thistype this = 1
            loop
                exitwhen integer(this) > 8190
                set this.next = this + 1
                set this.prev = this - 1
                set this = this.next
            endloop
        endmethod
    endmodule
    struct Loop extends array
        readonly thistype next
        readonly thistype prev
        implement I
    endstruct
endlibrary

 

[Nestharus]

nop..

private struct Loop

 

[Magtheridon96]

fixed it

 

[Nestharus]

No you didn't.. it doesn't extend an array.

 

[Magtheridon96]

I always forget to do that xD

edit
done..

 

[Nestharus]

Nop.. still not done

0 doesn't point to 1

and 0.prev doesn't point to 8191

and 1.prev doesn't point to 0

 

[Magtheridon96]

Meh, forget it. I'm too tired to care (It's 5:27 AM and I g2g to sleep )

 

[Nestharus]

Ok.. I just stress tested small operations like +,-,*,/ against array reads and the small operations won.

45 fps vs 60 fps (math had yet to go down)


Math is faster than an array read

Looping through an array is faster than looping through a linked list

Myth debunked.



This is officially useless.

 

[Troll-Brain]

I've myself tested simple incrementation VS array read, and array read seems 2 times less efficient (or at least it's less efficient, because i don't know if the fps drop should be linear or not) than simple incrementation.

20 fps for array vs 40 fps for simple incrementation with this code :

library BenchmarkTest initializer init

globals
    private constant real TIMEOUT = 0.02
    private constant boolean ARRAY_TEST = false
endglobals

globals
    integer array I
    integer array J
    integer array K
    integer array L
    integer array M
endglobals

function F takes nothing returns nothing
    local integer i = 0
    local integer j = 0
    local integer k = 0
    local integer l = 0
    local integer m = 0
    local integer x = 0
    
    loop
    
        static if ARRAY_TEST then
            set i = I[i]
            set j = J[i]
            set k = K[i]
            set l = L[i]
            set m = M[i]
        else
            set i = i+1
            set j = j+1
            set k = k+1
            set l = l+1
            set m = m+1
        endif
            
    exitwhen x == 6950
    set x = x+1
    endloop
    
    //call BJDebugMsg("limit op not reached")
endfunction

private function init takes nothing returns nothing
    local integer i = 0
    
    loop
        set I[i] = i+1
    exitwhen i == 6950
    set i = i+1
    endloop
    
    call TriggerSleepAction(0)
    set i = 0
    loop
        set J[i] = i+1
    exitwhen i == 6950
    set i = i+1
    endloop
    
    call TriggerSleepAction(0)
    set i = 0
    loop
        set K[i] = i+1
    exitwhen i == 6950
    set i = i+1
    endloop
    
    call TriggerSleepAction(0)
    set i = 0
    loop
        set L[i] = i+1
    exitwhen i == 6950
    set i = i+1
    endloop
    
    call TriggerSleepAction(0)
    set i = 0
    loop
        set M[i] = i+1
    exitwhen i == 6950
    set i = i+1
    endloop
    
    call TimerStart(CreateTimer(),TIMEOUT,true,function F)
    call BJDebugMsg("init done")
endfunction

endlibrary

EDIT : Btw, from Captain Griffen i wouldn't be suprised if it was just an evil joke for speedfreaks.

 

[Nestharus]

Hm... I tested it by just having tons of identical lines inside of a method (avoiding loops and etc).

The math operations still hadn't gone down tho, so I stopped testing ;D.

 

[Magtheridon96]

Ok.. I just stress tested small operations like +,-,*,/ against array reads and the small operations won.

45 fps vs 60 fps (math had yet to go down)


Math is faster than an array read

Looping through an array is faster than looping through a linked list

Myth debunked.



This is officially useless.

Don't you mean:

 

[Troll-Brain]

Hm... I tested it by just having tons of identical lines inside of a method (avoiding loops and etc).

The math operations still hadn't gone down tho, so I stopped testing ;D.

I think you can do "textmacros loops" in cjass (at least it was one of my suggestion), maybe that's what you did, while i'm totally agree that you have a more accurate result than mine, it's also just a theoric case.
But in fact you should be shot if you do something like that without "loop and such" stuff in a real map.

 

[BBQ]

Looping through an array is faster than looping through a linked list

Can you please post the code that you used? Because if it is true (and I don't really doubt your tests), we can bid farewell to Timer32.

I wonder where did Jesus4Lyf come up with those benchmarks of his (it was something like 36k execs/s vs 55k execs/s for array vs doubly linked list).

 

[Nestharus]

Well, for Timer32, you'd just change it to an indexed array that compares to 0.

 

[Magtheridon96]

Well, for Timer32, you'd just change it to an indexed array that compares to 0.

I bet my ass that you're creating a T32 module based on an indexed array exactly now -_-

 

[Nestharus]

I bet my ass that you're creating a T32 module based on an indexed array exactly now -_-

Nope, I'm working on a timer system that'll be faster than timers by themselves

 

[Magtheridon96]

Nope, I'm working on a timer system that'll be faster than timers by themselves

You're updating TimerQueque?
I'm going to use it in my map btw
Or are you creating a new one?

I can't imagine how you could pull that off ... then again, you did write the BigInt library.

 

[Bribe]

This doesn't mean to stop using linked lists, it just means to not use
arrays instead of simple math.

local thistype this
local integer i = stackTop - 1
loop
    exitwhen i < 0
    set this = stack[i]
    
    //Loop - actions
    
    set i = i - 1
endloop

The benchmark has definitely not proven that the above is faster than:

local thistype this = next[0]
loop
    exitwhen this == 0
    
    //Loop - actions
    
    set this = next[this]
endloop

 

[Nestharus]

That is besides the point... this would be used exactly like your first example, but with array reads rather than math.


This is not for linked lists, this is removing +1/-1.


Your statement isn't relevant.

 

[Bribe]

Well, for Timer32, you'd just change it to an indexed array that compares to 0.

I was responding to your quote here. You basically said that the
indexed array (1st example) would be faster than the linked list
in T32 (2nd example).