Locations vs gamecache (benchmark) (Locations are fast as hell)

07-05-2006, 12:02 AM

All right, some considerations:
- It is obvious that locations are faster, just wanted to how faster.
- Locations can only solve very specific problems unlike gamecache that is extremely flexible.
- I used a linked list that behaves as stack for the test

Anyways:

common:

function A takes nothing returns nothing
 local integer i=500
    set udg_log=0
    loop
        exitwhen i<=0
        call ExecuteFunc("B")
        set i=i-1
    endloop
    call BJDebugMsg("!"+I2S(udg_log))
endfunction

//===========================================================================
function InitTrig_locc takes nothing returns nothing
 local trigger t=CreateTrigger()
    set t = CreateTrigger(  )
    call TriggerRegisterPlayerEventEndCinematic( t, Player(0) )
    call TriggerAddAction( t, function A)
 set t=null
endfunction

Takes 2.81 seconds:

function CS_i2r takes integer i returns real
    return i
    return 0.
endfunction

function CS_h2r takes handle h returns real
    return h
    return 0.
endfunction

function Stack_First takes location l returns location
    return GetLocationX(l)
    return null
endfunction

function Stack_Next takes location l returns location
    return GetLocationY(l)
    return null
endfunction


function Stack_Empty takes location s returns boolean
    set udg_csloc=Stack_First(s)
 return udg_csloc==null
endfunction

function Stack_Push takes location s, real i returns nothing
 local location F=Stack_First(s)
    if (F==null) then
        set F=Location(i,CS_h2r(null))
    else
        set F=Location(i,CS_h2r(F))
    endif
    call MoveLocation(s,CS_h2r(F),0)
 set F=null
endfunction

function Stack_Pop takes location s returns real
 local location F=Stack_First(s)
 local location q
 local real i
    if (F==null) then
        return 0
    endif
    set i=GetLocationX(F)
    set q=Stack_Next(F)
    call RemoveLocation(F)
    call MoveLocation(s,CS_h2r(q),0)
 set F=null
 set q=null
 return i
endfunction

function NewStack takes nothing returns location
   return Location(CS_h2r(null),0)
endfunction

function Stack_Destroy takes location s returns nothing
 local location t=Stack_First(s)
 local location q
 
   loop
       exitwhen (t==null)
       set q=t
       set t=Stack_Next(t)
       call RemoveLocation(q)
   endloop
   call RemoveLocation(s)
 set t=null
 set q=null
endfunction
 


function B takes nothing returns nothing
 local location s=NewStack()
 local integer n=100
 local integer i=0
 local real x

    loop
        exitwhen i>=n
        call Stack_Push(s,3.3)
        set i=i+1
    endloop
set i=0
    loop
        exitwhen Stack_Empty(s)
        call Stack_Pop(s)
        set i=i+1
    endloop
    call Stack_Destroy(s)
    if (i>=n) then
        set udg_log=udg_log+1
    endif
 set s=null
endfunction

Takes 18.03 seconds:

function Stack_Empty takes string s returns boolean
 return not HaveSetField(s,"first",bj_GAMECACHE_INTEGER)
endfunction
//18.03s
function Stack_Push takes string s, real i returns nothing
 local integer Fi=GetTableInt(s,"first")
 local integer q

    if (Fi==0) then
        set Fi=NewTableIndex()
        call SetTableReal(I2S(Fi),"value",i)
        call SetTableInt(s,"first",Fi)
    else
        set q=NewTableIndex()
        call SetTableInt(I2S(q),"next",Fi)
        call SetTableInt(s,"first",q)
    endif
endfunction

function Stack_Pop takes string s returns real
 local string F=I2S(GetTableInt(s,"first"))
 local string q
 local real i
 local integer id
    if (F==null) then
        return 0
    endif
    set i=GetTableReal(F,"value")
    set id=GetTableInt(F,"next")
    set q=I2S(id)
    call DestroyTable(F)
    call SetTableInt(s,"first",id)
 set F=null
 set q=null
 return i
endfunction

function NewStack takes nothing returns string
   return NewTable()
endfunction

function Stack_Destroy takes string s returns nothing
 local integer t= GetTableInt(s,"first")
 local string q
 
   loop
       exitwhen (t==0)
       set q=I2S(t)
       set t= GetTableInt(q,"next")
       call DestroyTable(q)
   endloop
   call DestroyTable(s)
endfunction
 


function B takes nothing returns nothing
 local string s=NewStack()
 local integer n=100
 local integer i=0
 local real x

    loop
        exitwhen i>=n
        call Stack_Push(s,3.3)
        set i=i+1
    endloop
set i=0
    loop
        exitwhen Stack_Empty(s)
        call Stack_Pop(s)
        set i=i+1
    endloop
    call Stack_Destroy(s)
    if (i>=n) then
        set udg_log=udg_log+1
    endif

endfunction

All right, gamecache is 6+ times slower than locations. The intention was to actually try native gamecache usage instead of tables but the difference is so big that it does not matter.

I should say that a test where the values are integers must be done later.

Also I noticed a bizarre fact.
- The gamecache test almost didn't increase the memory usage at all.
- The location test increases memory usage by 20 MB the first time, but it doesn't do so later. Also if I increase the value of n it can increase it by a ton of Megabytes like 250MB but only the first time.

07-05-2006, 12:51 AM	#2
aquilla	I don't see the point of this test? Only time I use locations is when I need to check Z or use GetSpellTargetLoc

07-05-2006, 01:04 AM	#3
Alevice	This is a performance experiment to see if an stack implementation can be faster using locations rather than gamecache.

07-05-2006, 02:10 AM	#4
emjlr3	im not 100% sure about all this stuff, but does it mean this could lead to an even better method of moving locals around?

07-05-2006, 02:22 AM

PipeDream

Huzzah!
Yes emjlr. The most practical method is probably to store the head of a list for an object in game cache which you then peel apart for data.

Actually we could toss out game cache entirely using one global (associative) array of lists. Since handles are unique we can get away with ModuloInteger(HtoI(),8192) as a key into which list to crawl looking for our object. No I2S at all...

Alternatively we could use a non array variable and build a tree, but I wouldn't expect that to beat game cache.

07-05-2006, 08:02 AM	#6
Anitarf	So, what are the uses of a location-based list? You said it can be used only for very specific purposes. What kind of functionality does such a data structure offer, in comparison to a hash table (I think I remember reading that the game cache is a sort of hash table, whatever those are, I'm not too familiar with programming terminology)?

07-05-2006, 05:32 PM

Alevice

Quote:

Originally Posted by Anitarf

(I think I remember reading that the game cache is a sort of hash table, whatever those are, I'm not too familiar with programming terminology)?

Put horribly simply and not that precise, a hash table is like an array, only that instead to be indexed by a number, you can index them by a name. For example, we store the age of our employees, we can do something like

age["pedro"] = 25
age["john"] = 31
age["bulma"] = 16

In theory, a name, and depending of the hash table implementation, doesn't have to be an string, it can be any type of variable (allowed by the language we are working with, :P). Using the same example, we could do:

employee1 = Create Employee
employee2 = Create Employee
employee3 = Create Employee

age[employee1] = 25
age[employee2] = 31
age[employee3] = 16

and so on.

Now as to the benefits of using location rather than game cache and viceversa, a few are:

Location
- We don't encounter an explicit limit, unlike gamecache, where we can only have at most 255
- They are faster
Game Cache
- They can be used across maps in single player
- Association through category and title is a little more precise.

Note I am not talking specifically about the stack implementation, and probably when Vex said "Locations can only solve very specific problems unlike gamecache that is extremely flexible.", he probably implied the same.

07-05-2006, 10:42 PM

Vexorian

hmnn the best method to transport locals is to use globals...

Proposition If I was able to store strings on locations I could code my own hash table and it would probably be faster than gamecache.

Quote:

- The location test increases memory usage by 20 MB the first time, but it doesn't do so later. Also if I increase the value of n it can increase it by a ton of Megabytes like 250MB but only the first time.

This is actually worrying me, anyone could find a leak in the code? else there is some leaky behaviour in locations.

Quote:

Double Linked lists are the love of my life. And normal linked lists are not that bad either. But well in JASS they are kind of limited but still can be useful wait for next cscache I say. Also raw use of locations + return bug can even allow you to have a tree, and trees are just useful for everything

07-05-2006, 10:56 PM	#9
Anitarf	Could it be just the handle indexes being reserved for the locations? And can't you returnbug strings? I thought that it was well established that strings are held in an array of some sort and string variables are nothing but indexes in that array?

07-05-2006, 11:05 PM	#10
Vexorian	Sure you can return bug strings. The problem is that it will eventually crash...

07-05-2006, 11:14 PM	#11
iNfraNe	Why would it eventually crash? Dont strings always stay in memory?

07-05-2006, 11:16 PM	#12
Vexorian	Do strings stay memory? Yes. Do strings have a chance of getting lost or changing indexes? Yes.

07-05-2006, 11:20 PM	#13
iNfraNe	I see. Well then that blows, you could however make your own string array? only problem then is the array length..

07-05-2006, 11:20 PM

#14

PipeDream

- There's no way you could hash a string as fast as gamecache does it. Do we really need this though? I think something like this takes care of all our needs:

JASS:

function InsertAssocArr takes integer key, real value returns nothing
    local integer i = key - (key/8192)*8192    //Positive keys
    loop
        exitwhen udg_hash_taken[i] = 0
        set i = i + 1    //Could use whatever probing you like
        if i == 8192 then
            set i = 0
        endif
    endloop
    set udg_hash_taken[i] = true
    set udg_hash_key[i] = key
    set udg_hash_value[i] = value
endfunction

function GetAssocArr takes integer key returns real
    local integer i = key - (key/8192)*8192
    loop
        exitwhen udg_hash_key[i] == key
        set i = i + 1
        if i== 8192 then
            set i = 0
        endif
    endloop
    return udg_hash_value[i]
endfunction

function DeleteAssocArr takes integer key returns nothing //Will die a terrible death if key doesn't exist or you double free
    local integer i = key - (key/8192)*8192
    loop
        exitwhen udg_hash_key[i] == key
        set i = i + 1
        if i == 8192 then
            set i = 0
        endif
    endloop
    set udg_hash_taken[i] = false
endfunction

- Large allocation: As long as it isn't a leak and it just makes a big heap, no big deal. Also if you hit the execution limit (maybe n = 1000 or so) you start leaking a bunch of memory.

- Double linked lists: You could do something like http://en.wikipedia.org/wiki/Xor_linked_list with a different operator

- Strings can't be return bugged as those indices are temporary cache indices. They float about and generally misbehave. Variables in JASS are all pointers, we happen to be lucky that for floats and ints and handles the object it points to is all 4B. Not strings though it seems.

07-06-2006, 02:16 AM

#15

Vexorian

Still, gamecache is a hash of hashes with mission and key and that stuff then it also can store strings. Can't replace it with locations and arrays

I am thinking about peppar's heap. Besides of not using handles at all it uses integers directly I wonder if a heap based replacement would be faster than using locations.

Edit: Getting my hands on peppar's heap would be kind of hard, but I was thinking on making a replacement myself anyways.