HomeUser Control Panel (unavailable in archive)ForumsTutorialsArt GalleryResourcesMaps

alternatives to the relation part of gamecache

07-28-2006, 01:41 PM#1
Vexorian
no matter we create a heap that can store values in an array-like way. It is nothing if we can't relate a heap to a handle.

For units and items that's actually easy because of UserData , unless of course it is taken by some other spell / system.

The rest doesn't even have this alterantive.

And let's accept it, for a thing like this gamecache is really fast and effective with the only need of one variable, it is not that easy to beat.


I tried a binary tree with 2 values, one was x the other y you could have used it like a random access array where you could assing a value of y for an x (x was the value for the node checks and all)

It worked really well.

The only problem is that it was 2x times slower than gamecache.

Any other way to relate 2 integers in a way close to gamecache's effectiveness?

I am gonna try to make a hash table but I doubt that would be faster than gamecache
07-28-2006, 01:59 PM#2
DioD
Rect can store up to 4 integers.
07-28-2006, 04:14 PM#3
blu_da_noob
You might have problems with bounding (maxX must be greater than minX and stuff like that).

Units can store a fair amount of data (potentially). X/Y position, flyheight, userdata and some others. Not sure how workable it would be though.
07-28-2006, 04:25 PM#4
PipeDream
Trees will never work because handles will tend to come in sequence. the overhead for balancing will instantly lose to game cache.

There are several other options. Binary tries are particularly easy to implement with locations. They could also be used in a hash table style way, where one chops the first 13 bits with an array and if any are left over a location trie stretches down.

My implementation is misbehaving, not sure why. maybe real return bug issues. works half the time.
Collapse JASS:
function HtoR takes handle h returns real
    return h
    return 0.
endfunction
function RtoL takes real r returns location
    return r
    return null
endfunction
function ItoR takes integer i returns real
    return i
    return 0.
endfunction
function RtoI takes real r returns integer
    return r
    return 0
endfunction

//all tail recursive so convert to iterative loop for speed
function Handle_trie_lookup takes location trie,integer key returns integer
    local integer next
    if trie == null then
        call BJDebugMsg("Error, null trie in lookup")
        return 0
    elseif key == 0 then
        set next = RtoI(GetLocationY(trie))    //Maybe better to inline return bug
        return next
    else
        set next = key/2
        if(key-next*2 == 1) then
            return Handle_trie_lookup(RtoL(GetLocationX(RtoL(GetLocationX(trie)))),next)
        else
            return Handle_trie_lookup(RtoL(GetLocationY(RtoL(GetLocationX(trie)))),next)
        endif
    endif
endfunction

function Handle_trie_new takes nothing returns location
    return Location(HtoR(Location(0.,0.)),0.)
endfunction

//In practical implementation, subtract 0x100000 from handles
function Handle_trie_insert takes location trie, integer key,integer val returns nothing
    local integer next
    local location links = RtoL(GetLocationX(trie))
    if trie == null then
        call BJDebugMsg("Error, null trie in insert")
    endif
    if key <= 0 then
        call MoveLocation(trie,GetLocationX(trie),ItoR(val))
    else
        set next = key/2
        if(key-next*2 == 1) then
            if(GetLocationX(links) == 0.) then
                call MoveLocation(links,HtoR(Handle_trie_new()),GetLocationY(links))
            endif
            call Handle_trie_insert(RtoL(GetLocationX(links)),next,val)
        else
            if(GetLocationY(links) == 0.) then
                call MoveLocation(links,GetLocationX(links),HtoR(Handle_trie_new()))
            endif
            call Handle_trie_insert(RtoL(GetLocationY(links)),next,val)
        endif
    endif
    set links = null
endfunction
07-28-2006, 04:51 PM#5
karukef
I have been working my ass of for the last days to make at least ONE alternative to assosiating values. It works only for timers, but it works amazingly fast. It is perfect, for example, to use in systems that move units around like projectiles, or spells that have very tight timerloops. Also a perfect match for the Dynamic Arrays.


I just finished writing it up and released it as a resource. Check it out: http://wc3campaigns.net/showthread.p...263#post825263
07-28-2006, 06:54 PM#6
Vexorian
Quote:
Trees will never work because handles will tend to come in sequence
Yeah they had a something that made sure to have things branched correctly, instead of > directly I used another formula, it is meaningless though cause it wasn't faster.

The dream objective would be a way to relate an integer to another integer that would have many uses I am gonna check it out karukef's and see.
07-28-2006, 06:59 PM#7
PipeDream
if you just want to do integer maps then you have to deal with either all integers (let end of array run out into gamecache) or collision resolution.

There is an easy way to handle collisions. I was thinking you could not do probing because if you try to remove, you'll break the chain. however, you can just keep a separate array which states whether the parallel element is in use. this is something you would probably want anyway for debugging.

Edit: I knew I had done this at some point. http://www.wc3campaigns.net/showpost...8&postcount=14
07-29-2006, 11:34 AM#8
karukef
I just expanded the SmartTimers idea to also work with units. The approach is both similar and different. The basic idea remains the same: If we could just assign ONE integer to a unit, an integer that can act as an index into global arrays for the lifespan of the unit, then those global arrays can not only contain a static amount of information, but also refer to Dynamic Arrays or gamecache.

But since there are no really safe ways of attaching an integer to a unit that I know of (I assume userdata still resets to 0 once the unit dies, making it hopeless), I had to come up with a new method.

Now, please don't laugh at me. This is a truly strange approach. BUT, it is amazingly efficient, actually about as fast as the SmartTimers system. MUCH faster than getting an attached integer using gamecache:

Collapse JASS:
function SU_Convert takes unit u returns integer
    local integer i = (GetUnitAbilityLevel(u, SU_IntegerAbility1()) * 90) + GetUnitAbilityLevel(u, SU_IntegerAbility2())
    if i > 0 then
        return i
    return SU_New(u)
endfunction

As you can see, it reads the level of two dummy-abilities from the unit. It is very fast, and two abilities with 90 levels is enough to index 8190 different spots. When this integer is retreived, it can access global arrays containing data that is unique for the unit, which obviously is infinitely faster than gamecache.

Also note that if the unit is automatically given a new unique integer by the SU_New function if it doesn't already have one.

Obviously, any unit that has ever been used in the SU_Convert function needs to call SU_Release at some point. This system can attach values to 8190 different units at the same time.

So basically, like the SmartTimers system, you do:
Collapse JASS:
function SomeSpell takes nothing returns nothing
    local integer u = SU_Convert(GetTriggerUnit())
    local real damage = SU_GetReal1(u)
    local unit source = SU_GetUnit1(u)

    //do fancy stuff
endfunction

Now, I am thinking that these functions, both SmartTimers and SmartUnits (yeah, useless name) could be used to give the CSCache more power.

Maybe I will write a unified SmartTimers/SmartUnits and just call it SmartAttach, and make it dependant on CSCache.

A question for Vexorian: Do you think it would be beneficial to integrate a SmartAttach system into the CS itself? Obviously there are speed gains to be had every line of code where it currently reads or sets a variable to/from a unit or a timer through Gamecache.

In any case, I will create the SmartAttach module as a 'addon' to CSCache, and it's up to you whether you wish to include it or not.

For reference, here is the current SmartUnit implementation, 100% untested. It may even have syntax errors.
Hidden information:
Collapse JASS:
globals
    integer udg_SU_Usage = 0

    //Indicates which unit an SU integer currently works for
    string array udg_SU_Unit
    //An array of strings, one for each unit: 
    //Used to effectively associate gamecache values to a unit without any I2S.
    string array udg_SU_String
    //Internal stack of currently free units.
    location udg_SU_Free = null

    //The following are arrays of data associated with each SU integer.
    //They can of course be accessed directly by doing set udg_SU_Integer1[my_SU_unit]
    //but I consider it much better programming practice to use the available 
    //Set/Get functions. (The use of Get functions will be optimized with Vex's script optimizer)

    //To add more arrays is perfectly ok: Just remember to update the SU_Destroy function to
    //correctly nullify those additional arrays.
    integer array udg_SU_Integer1
    integer array udg_SU_Integer2
    integer array udg_SU_Integer3

    real array udg_SU_Real1
    real array udg_SU_Real2
    real array udg_SU_Real3

    unit array udg_SU_Unit1
    unit array udg_SU_Unit2
    unit array udg_SU_Unit3
endglobals

function SU_IntegerAbility1 takes nothing returns integer
    return 'A000'
endfunction

function SU_IntegerAbility2 takes nothing returns integer
    return 'A001'
endfunction

function SU_PushFree takes integer i returns nothing
    //Internal function for putting an SU integer onto the list of free SU integers
    if udg_SU_Free == null then
        set udg_SU_Free = SU_Location_IntLoc(i, null)
    else
        set udg_SU_Free = SU_Location_IntLoc(i, udg_SU_Free)
    endif
endfunction

function SU_PopFree takes nothing returns integer
    //Internal function for removing an SU integer onto the list of free SU integers
    local integer free = 0
    local location front = udg_SU_Free
    if udg_SU_Free == null then
        call BJDebugMsg("|cffff0000Critical SmartUnit Error:|r No more handles available")
        //Return 0, which actually means no-unit
        return 0
    endif
    set free = SU_GetLocationX_Int(front)
    set udg_SU_Free = SU_GetLocationY_Loc(front)
    call RemoveLocation(front)
    set udg_SU_UsedTimers = udg_SU_UsedTimers + 1
    return free
endfunction

function SU_InitB takes nothing returns nothing
    //Prevent the init from timing out
    local integer i = 4096
    loop
        exitwhen i == 8192
        call SU_PushFree(i)
        set i = i+1
    endloop
endfunction

function SU_Init takes nothing returns nothing
    local integer i = 0
    loop
        exitwhen i == 4096
        call SU_PushFree(i)
        set i = i+1
    endloop
    call ExecuteFunc("SU_InitB")
endfunction

function SU_New takes unit u returns integer
    local integer i = SU_PopFree()
    local integer a = i / 90
    local integer b = i - (i/90) * 90

    call UnitAddAbility(u, SU_IntegerAbility1())
    if a > 0 then
        call SetUnitAbilityLevel(u, SU_IntegerAbility1(), a)
    else
        call UnitRemoveAbility(u, SU_IntegerAbility1())
    endif

    call UnitAddAbility(u, SU_IntegerAbility2())
    if b > 0 then
        call SetUnitAbilityLevel(u, SU_IntegerAbility2(), b)
    else
        call UnitRemoveAbility(u, SU_IntegerAbility2())
    endif

    set udg_SU_Unit[i] = u
    set udg_SU_Usage = udg_SU_Usage + 1
    return i
endfunction

function SU_Convert takes unit u returns integer
    local integer i = (GetUnitAbilityLevel(u, SU_IntegerAbility1()) * 90) + GetUnitAbilityLevel(u, SU_IntegerAbility2())
    if i > 0 then
        return i
    return SU_New(u)
endfunction

function SU_Release takes integer u returns nothing
    call SetUnitAbilityLevel(udg_SU_Unit[u], SU_IntegerAbility1(), 0)
    call SetUnitAbilityLevel(udg_SU_Unit[u], SU_IntegerAbility2(), 0)
    set udg_SU_Unit[u] = null

    set udg_SU_Integer1[u] = 0
    set udg_SU_Integer2[u] = 0
    set udg_SU_Integer3[u] = 0
    
    set udg_SU_Real1[u] = 0
    set udg_SU_Real2[u] = 0
    set udg_SU_Real3[u] = 0
    
    set udg_SU_Unit1[u] = null
    set udg_SU_Unit2[u] = null
    set udg_SU_Unit3[u] = null

    //If using gamecache, may want to autoclear the cache
    //call FlushStoredMission(CSCache(), udg_SU_String[u])

    set udg_SU_Usage = udg_SU_Usage - 1
    call SU_PushFree(u)
endfunction

//All get functions take an "SU" integer and returns a value attached to it.
function SU_GetString takes integer i returns string
    return udg_SU_String[i]
endfunction

function SU_GetInt1 takes integer i returns integer
    return udg_SU_Integer1[i]
endfunction

function SU_GetInt2 takes integer i returns integer
    return udg_SU_Integer2[i]
endfunction

function SU_GetInt3 takes integer i returns integer
    return udg_SU_Integer3[i]
endfunction

function SU_GetReal1 takes integer i returns real
    return udg_SU_Real1[i]
endfunction

function SU_GetReal2 takes integer i returns real
    return udg_SU_Real2[i]
endfunction

function SU_GetReal3 takes integer i returns real
    return udg_SU_Real3[i]
endfunction

function SU_GetUnit1 takes integer i returns unit
    return udg_SU_Unit1[i]
endfunction

function SU_GetUnit2 takes integer i returns unit
    return udg_SU_Unit2[i]
endfunction

function SU_GetUnit3 takes integer i returns unit
    return udg_SU_Unit3[i]
endfunction

//Set functions

//All set functions take an "SU" integer and attaches a value to it.
function SU_SetInt1 takes integer i, integer value returns nothing
    set udg_SU_Integer1[i] = value
endfunction

function SU_SetInt2 takes integer i, integer value returns nothing
    set udg_SU_Integer2[i] = value
endfunction

function SU_SetInt3 takes integer i, integer value returns nothing
    set udg_SU_Integer3[i] = value
endfunction

function SU_SetReal1 takes integer i, real value returns nothing
    set udg_SU_Real1[i] = value
endfunction

function SU_SetReal2 takes integer i, real value returns nothing
    set udg_SU_Real2[i] = value
endfunction

function SU_SetReal3 takes integer i, real value returns nothing
    set udg_SU_Real3[i] = value
endfunction

function SU_SetUnit1 takes integer i, unit value returns nothing
    set udg_SU_Unit1[i] = value
endfunction

function SU_SetUnit2 takes integer i, unit value returns nothing
    set udg_SU_Unit2[i] = value
endfunction

function SU_SetUnit3 takes integer i, unit value returns nothing
    set udg_SU_Unit3[i] = value
endfunction
07-29-2006, 12:05 PM#9
Vexorian
Well units don't need SmartUnit now that I think of, we have user data and if the unit is a dummy there is no way userdata is gonna be used by anything else, and the moments when user data is kept I don't think we can use SmartUnits. Requiring 2 90 level abilities just for an storage system is not right. Also are you sure that's faster than gamecache? gamecache is slow but I doubt it is that slow.

SmartTimers work but I'd like to see if there could be more flexible options or an alternative that doesn't require 5000 timers at startup. But If I don't find anything I would have to include it or something like that

Let's see if pipedream's thing works and then we will compare speeds
07-29-2006, 01:40 PM#10
PipeDream
Problem with the probed hash table is its performance rapidly and severely degrade after roughly 4096 inserts. It will also do very poorly if you insert a few things, create 8000 handles so it wraps around, then insert a few more things. I do not see a good solution for this.
The abilities is a good idea. I don't see anything wrong with attached var systems tuned to the individual types. But I am skeptical that using abilities that way is a great idea. Abilities with lots of levels seem to slow the crap down out of the WE for me. you could use a lower base and more abilities but then you're a little slower. You're also still stuck scaling unless you use a multi array approach.

Here's a hybrid approach. It's a generic whole number->int map at the moment. for normal handles, subtract 0x100000 before insertion/lookup
works by looking up the first 13 bits into an array, then crawling the rest of the bits into a trie.
Collapse JASS:
function HtoR takes handle h returns real
    return h
    return 0.
endfunction

function ItoR takes integer i returns real
    return i
    return 0.
endfunction
function RtoIcast takes real r returns integer
    return r
    return 0
endfunction
function RtoI takes real r returns integer
    local integer i = RtoIcast(r)
    return i
endfunction
function RtoL takes real r returns location
    local integer x = RtoI(r)
    return x
    return null
endfunction

//all tail recursive so convert to iterative loop for speed
function Handle_trie_lookup takes location trie,integer key returns integer
    local integer next
    if trie == null then
        call BJDebugMsg("Error, null trie in lookup")
        return -1
    elseif key <= 0 then
        set next = RtoI(GetLocationY(trie))    //Maybe better to inline return bug
        return next
    else
        set next = key/2
        if(key-next*2 == 1) then
            return Handle_trie_lookup(RtoL(GetLocationX(RtoL(GetLocationX(trie)))),next)
        else
            return Handle_trie_lookup(RtoL(GetLocationY(RtoL(GetLocationX(trie)))),next)
        endif
    endif
endfunction

function Handle_trie_new takes nothing returns location
    return Location(HtoR(Location(0.,0.)),0.)
endfunction

//In practical implementation, subtract 0x100000 from handle
function Handle_trie_insert takes location trie, integer key,integer val returns nothing
    local integer next
    local location links
    if trie == null then
        call BJDebugMsg("Error, null trie in insert")
    elseif key <= 0 then
        call MoveLocation(trie,GetLocationX(trie),ItoR(val))
    else
        set links = RtoL(GetLocationX(trie))
        set next = key/2
        if(key-next*2 == 1) then
            if(RtoL(GetLocationX(links)) == null) then
                call MoveLocation(links,HtoR(Handle_trie_new()),GetLocationY(links))
            endif
            call Handle_trie_insert(RtoL(GetLocationX(links)),next,val)
        else
            if(RtoL(GetLocationY(links)) == null) then
                call MoveLocation(links,GetLocationX(links),HtoR(Handle_trie_new()))
            endif
            call Handle_trie_insert(RtoL(GetLocationY(links)),next,val)
        endif
    endif
    set links = null
endfunction

//First fan out over an array
//For handles, subtracting 0x100000 will speed this up a bunch
function AA_lookup takes integer key returns integer
    local integer next = key/8192
    local integer index = key-next*8192
    return Handle_trie_lookup(udg_lookup[index],next)
endfunction

function AA_insert takes integer key, integer val returns nothing
    local integer next = key/8192
    local integer index = key-next*8192
    if(udg_lookup[index] == null) then
        set udg_lookup[index] = Handle_trie_new()
    endif
    call Handle_trie_insert(udg_lookup[index],next,val)
endfunction
It should scale very well and there's a lot of room for optimization, so if it's competitive with gamecache right now I can run with it.

The first trie didn't work as somereal == 0. misbehaved, but RtoL(somereal) == null worked fine. bizarre.
07-29-2006, 01:41 PM#11
Vexorian
Quote:
Abilities with lots of levels seem to slow the crap down out of the WE for me.
And cause long loading times
07-29-2006, 01:43 PM#12
karukef
First of all, why critisize the SmartTimers system? It is completely incomparable in speed in all possible ways. Requiring X timers at startup is not inflexible, it is the perfect solution. You cannot possibly retreive data faster than getting the handle of a timer and subtracting a value from it. There is just no way.

Second, as for smart units, it works for all possible units. And it IS fast, I tested that. Doing GetAttachedInt 2 million times for a unit takes 24 seconds on my computer, doing ST_Convert takes 7 seconds.

In the past, GetUnitUserData would reset to 0 the second the unit died, making it impossible to clean up or work with units as soon as they died. Now I just tested it and realize this has changed. Obviously, it is much better to use GetUnitUserData than to two abilities. (No other system should be allowed to touch a unit's UserData!)

Which again means that it will be even faster.

In any case, this kind of system, retrieving a handle to index global arrays, is as fast as it can become.


EDIT: (Just a side-note: Abilities with tons of levels do not have any impact in-game according to my experience. The only reason it lags when loading is because War3 has to do a lot of parsing. Once converted to the internal datastructures I am rather sure that an ability with 1 level is indistinguishable from one with 90. But I digress, those abilities seem unnecessary now.)
07-29-2006, 01:55 PM#13
PipeDream
Karukef, warcraft's performance seems to scale poorly with respect to the number of handles. However, I speculate this is due to strings. As SmartTimers avoids strings, I conclude that 5000 is fine. Since I've not demonstrated strings as the cause conclusively, it is still a legitimate cause for concern.

Plus it scales poorly. Requiring the map maker to figure out how many timers he'll needs is a con, if he happens to need more than the default. If you haven't done it already, you can make it easy by giving debug messages for maximum timers in use so far. Obviously if it's 5000 at the moment this'll be rare, but the fact remains there's room for individual tuning from map to map.

Criticism is a necessary component of improvement. Even evaluations, with no improvement suggestions, are useful when one has multiple systems to choose between.

Edit: It occurs to me that a whole number->int map is exactly what we need for the base of a dynamic array. This is an appropriate alternative to gamecache or if/then/elseing arrays. If I add another two arrays, for values less than 8192, it will be a straight array and for values greater it will take two to three location fiddles per power of two. Ought to be faster than gamecache up to 16384 and at least as fast up to 32768.
07-29-2006, 02:08 PM#14
Toadcop
I think every sys unsing handle objects to store info will have poor performance ! because after some created (handle) objects War begins to slow down the creation of new one ! it will be EXTEREME slow... to use several array (across or pararel) its the best method.
07-29-2006, 02:29 PM#15
Vexorian
Any non-dynamic approach is out of the question