• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!

[Benchmarks] HandleTable.exists() and GetRandomInt()

Status
Not open for further replies.

Cokemonkey11

Spell Reviewer
Level 30
Joined
May 9, 2006
Messages
3,544
Hello,

I'm in the process of developing a new system and one of the important things I needed to know was about the performance difference between IsUnitInGroup() and HandleTable.exists().

Before I can begin this though I first need to know how the cost of HandleTable.exists() varies as more handles are added to it.

I've used Vexorian's Table 3.1. My machine's specifications are as follows: Intel i5-2410M @ 2.3GHz, 6GB DDR3-SDRAM, Windows 7 x64.

The first notable test I've conducted compared the cost of HandleTable.exists(u) when the handle table instance contains 10 and 1000 units.

http://i.imgur.com/ZLaBaq8.png

From this graph we can see that for realistic counts of units, the cost of HandleTable.exists() is relatively constant.

We can also infer from the script which derived the data that GetRandomInt() has fairly constant cost in relation to the values of its arguments.

JASS:
scope thousandTable initializer i
    globals
        private integer kIPS=0
        private HandleTable ht
        private unit array list[1000]
        private group grp=CreateGroup()
    endglobals
    
    private function p takes nothing returns nothing
        local integer j=0
        local unit u=list[GetRandomInt(0,999)]
        loop
            exitwhen j>=kIPS
            call ht.exists(u)
            set j=j+1
        endloop
    endfunction
    
    private function c takes nothing returns boolean
        set kIPS=kIPS+10
        call DisplayTimedTextToPlayer(Player(0),0.,0.,3.,I2S(kIPS))
        return false
    endfunction
    
    private function i takes nothing returns nothing
        local trigger t=CreateTrigger()
        local integer j=0
        set ht=HandleTable.create()
        loop
            exitwhen j>=1000
            set list[j]=CreateUnit(Player(1),'hfoo',0.,0.,0.)
            call GroupAddUnit(grp,list[j])
            set ht[list[j]]=0
            set j=j+1
        endloop
        call TimerStart(CreateTimer(),1./1000.,true,function p)
        call TriggerRegisterPlayerEvent(t,Player(0),EVENT_PLAYER_END_CINEMATIC)
        call TriggerAddCondition(t,Condition(function c))
        call SetTimeOfDayScale(0.)
        set t=null
    endfunction
endscope

Above: Script used to test FPS for HandleTable.exists() with unit count of 1000.
 

Attachments

  • inGroupTest001.w3m
    20 KB · Views: 51

Cokemonkey11

Spell Reviewer
Level 30
Joined
May 9, 2006
Messages
3,544
Sorry for the double post.

I've acquired more data which should be useful for comparing IsUnitInGroup() and HandleTable.exists():

http://i.imgur.com/y23zEKL.png

By extrapolation, we can estimate that a group would need to contain about 600 units before HandleTable.exists(u) would be less expensive than IsUnitInGroup(u).

I hope others will find this useful!
 

Attachments

  • inGroupTest002.w3m
    20.7 KB · Views: 38

Cokemonkey11

Spell Reviewer
Level 30
Joined
May 9, 2006
Messages
3,544
Have you "wc3mapoptimize" the codes before the test ?

I mean, it does matter.

No, I haven't. Do you mean because it will increase the performance of HandleTable?

Edit: Wait, I have JNGP "Disable Script Optimization" unchecked (so it's optimizing) is that what you're talking about?
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
Yes it will, but for both tests.
It's just because jass is interpreted, more characters = slower, as simple as that.

For JNGP i suppose it's just for function inlining so it shouldn't matter if you use wc3mapoptimizer (or a such tool)
 

Cokemonkey11

Spell Reviewer
Level 30
Joined
May 9, 2006
Messages
3,544
As far as I know, Hashtable operations becomes slower when more datas are stored into it.
Sorry for this phrase coming out from a person who has 0 external programming language.

That's correct. That's why I carefully worded this sentence:

From this graph we can see that for realistic counts of units, the cost of HandleTable.exists() is relatively constant.

Hashtables are not so complicated (you would certainly understand them)

  1. A hash function uses some math to create a key given some data. For example if the data is just an integer, and we want the hash function to create a key on [0,99] we might say hash(data)=data mod 100.
  2. An array of linked lists stores the (key,data) tuple at the array[key]'s index
  3. When data is requested from the hashtable, it calls hash(data) again, and then searches for (key,data) in the linked list at array[key]'s linked list

Thus, an ideal hashmap:

  • Has an array which minimizes the length of its linked lists stored, while minimizing the memory footprint of the map itself
  • Has a hash function which maximizes the uniformity of the distribution (eg hash(data) should produce a random number on [0,99] in our case)
  • Has a hash function which is as computationally inexpensive as possible
 
Level 23
Joined
Apr 16, 2012
Messages
4,041
yes, but you should think about collision detection and avoidance as well in hashtables case

yes, ideal hashtable has O(1) when empty, but slowly drops as more items are put in because of the collisions

Worst case is O(n) (n = number of items in hashtable) but that is very bad hashtable
 
Status
Not open for further replies.
Top