Benchmark request

06-15-2009, 04:27 AM

Test subject one:

function GetNClosestUnits takes group Group1, real X1, real Y1, real Radius, integer N returns group
    local unit First  
    local unit Closest 
    local integer UnitAmount 
    local real Distance 
    local real TestDistance 
    local real X2
    local real Y2
    local real X3
    local real Y3
    local group Group2 
    local group Group3
    set Distance = Radius * Radius  
    set Group2 = CreateGroup()
    set Group3 = CreateGroup()
    call GroupAddGroup(Group1, Group2)  
    
    loop   
    exitwhen (N == 0) 
        call GroupAddGroup(Group2, Group1)  
        set UnitAmount = CountUnitsInGroup(Group1) 
     
        loop 
        exitwhen (UnitAmount == 0) 
            set First = FirstOfGroup(Group1) 
            set X2 = GetUnitX(First)
            set Y2 = GetUnitY(First)
            set X3 = X1 - X2
            set Y3 = Y1 - Y2 
            set TestDistance = X3 * X3 + Y3 * Y3
            if (TestDistance < Distance) then   
                set Closest = First 
                set Distance = TestDistance 
            endif  
            set UnitAmount = UnitAmount - 1 
            call GroupRemoveUnit(Group1, First) 
        endloop
        
        call GroupAddUnit(Group3, Closest)
        call GroupRemoveUnit(Group2, Closest) 
        set Distance = Radius * Radius
        set N = N - 1  
    endloop

    call DestroyGroup(Group1)
    call DestroyGroup(Group2)
    set Group1 = null
    set Group2 = null
    set First = null
    set Closest = null
    
    return Group3
endfunction

Test subject two:

library GetNClosestUnits
    globals
        private group temp
        
        private real temp_x
        private real temp_y
    endglobals
    
    private struct TreeNode
        integer value
        unit u
        TreeNode left
        TreeNode right

        public method addChild takes TreeNode node returns nothing
            if node.value < .value then
                // put left
                if .left == 0 then
                    call .addLeft(node)
                else
                    call .left.addChild(node)
                endif
            else
                // put right
                if .right == 0 then
                    call .addRight(node)
                else
                    call .right.addChild(node)
                endif
            endif
        endmethod
        
        public method addLeft takes TreeNode node returns TreeNode
            local TreeNode old = .left
            set .left = node
            return old
        endmethod
        
        public method addRight takes TreeNode node returns TreeNode
            local TreeNode old = .right
            set .right = node
            return old
        endmethod
        
        public static method create takes unit u, real x, real y returns TreeNode
            local TreeNode inst = TreeNode.allocate()
            
            set inst.u = u
            set x = GetUnitX(u) - x
            set y = GetUnitY(u) - y
            set inst.value = R2I(x * x + y * y)
            
            set inst.left = 0
            set inst.right = 0
            return inst
        endmethod
        
        private method onDestroy takes nothing returns nothing
            set .u = null
        endmethod
    endstruct

    globals
        private TreeNode root
    endglobals
    
    private function cleanup takes TreeNode node returns nothing
        if node != 0 then
            call cleanup(node.left)
            call cleanup(node.right)
            call node.destroy()
        endif
    endfunction
    
    private function enumerate takes nothing returns nothing
        // build a Binary Tree
        if root == 0 then
            set root = TreeNode.create(GetEnumUnit(),temp_x,temp_y)
        else
            call root.addChild(TreeNode.create(GetEnumUnit(),temp_x,temp_y))
        endif
    endfunction
    
    private function get_n_units takes TreeNode node, integer n returns integer
        if node == 0 or n <= 0 then
            return n
        endif
        
        set n = get_n_units(node.left, n) - 1
        if n < 0 then
            return 0
        endif
        call GroupAddUnit(temp, node.u) // actually visit the node        
        return get_n_units(node.right, n)
    endfunction

    function GetNClosestUnits takes group sourceGroup, real x, real y, real unused, integer n returns group
        set temp = CreateGroup()
        if n > 0 then
            set temp_x = x
            set temp_y = y
            set root = 0
            // process units
            call ForGroup(sourceGroup, function enumerate)
            // retrieve n units
            call get_n_units(root,n)
            // cleanup
            call cleanup(root)
        endif
        return temp
    endfunction
endlibrary

Test script:

function Trig_Test_Actions takes nothing returns nothing
    local group grp
    local integer i = 0
    local group g
    
    loop
        exitwhen i == 2
        set g = CreateGroup()        
        call GroupEnumUnitsOfPlayer(g, Player(0), null)
                
        set grp = GetNClosestUnits(g, GetUnitX(u), GetUnitY(u), 99999, 5)
        
        call DestroyGroup(grp)
        set i = i + 1
    endloop

    set grp = null    
    call BJDebugMsg("execution completed successfully")
endfunction

Could anyone benchmark these? I have no idea how to do it.

06-15-2009, 11:40 AM	#2
Anitarf	Could you at least confirm your code works before requesting benchmarks? I get an uninitialised variable error in your first example.

06-15-2009, 02:08 PM

ToukoAozaki

Quote:

Originally Posted by Anitarf

Could you at least confirm your code works before requesting benchmarks? I get an uninitialised variable error in your first example.

Subject one and two should have no problem at all...
BTW I fixed the only problem I could find. Original code had global group named g, added a local instead.

06-15-2009, 04:02 PM	#4
Anitarf	Ok, I see now, the function destroys the group that you pass to it. That's messy. Anyway, the second example is faster, but I'm not sure what the result would be if the first one were properly coded.

06-15-2009, 10:54 PM

Anitarf

Alright, here are the full benchmarks. I used the following code:

JASS:

function Trig_Testing_Actions takes nothing returns nothing
    local group grp
    local group g

    local integer sw = StopWatchCreate()
    local real t0
    local real t1
    local integer i = 0
    
    set t0 = StopWatchMark(sw)
    loop
        exitwhen i>=10


        set g = CreateGroup()
        call GroupEnumUnitsOfPlayer(g, Player(0), null)
        set grp = GetNClosestUnits(g, 0.0, 0.0, 99999, 20) // The last number was different for different test cases.
        call DestroyGroup(grp)


        set i = i + 1
    endloop
    set t1 = StopWatchMark(sw)
    call BJDebugMsg(R2S(1000*(t1-t0))) // Output in miliseconds.
    call StopWatchDestroy(sw)

    set grp = null    
    set g = null    
    call BJDebugMsg("execution completed successfully")
endfunction

//===========================================================================
function InitTrig_Testing takes nothing returns nothing
    set gg_trg_Testing = CreateTrigger(  )
    call TriggerRegisterPlayerEventEndCinematic( gg_trg_Testing, Player(0) )
    call TriggerAddAction( gg_trg_Testing, function Trig_Testing_Actions )
endfunction

I pressed escape ten times for each test, then I estimated the average output value. Individual values were very rarely more than 1 milisecond away from this estimated average, my estimate for the possible error of my estimate is +-0.25.

results:

Number of units (picked/total):	1/10	5/10	1/30	20/30

Test subject one:	5	15	13	130
Test subject two:	8.5	9	30	32
Control subject:	5.5	6.5	14	21

In case you are wondering what the control subject is, it's a little something I'm working on.

06-16-2009, 02:41 AM	#6
ToukoAozaki	Thanks for your work. I rewrote some lame code from unknown source and wondered if the new code is faster than the old one. Turns out it performs better as number of picked units grow, as I expected... Anyway, rep++ :)