Wc3C.net (http://www.wc3c.net/forums.php)
-   Triggers & Scripts (http://www.wc3c.net/forumdisplay.php?f=8)
-   -   Benchmark request (http://www.wc3c.net/showthread.php?t=106386)

ToukoAozaki 06-15-2009 05:27 AM

Benchmark request
Collapse 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)  
    exitwhen (N == 0) 
        call GroupAddGroup(Group2, Group1)  
        set UnitAmount = CountUnitsInGroup(Group1) 
        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 
            set UnitAmount = UnitAmount - 1 
            call GroupRemoveUnit(Group1, First) 
        call GroupAddUnit(Group3, Closest)
        call GroupRemoveUnit(Group2, Closest) 
        set Distance = Radius * Radius
        set N = N - 1  

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

Collapse Test subject two:
library GetNClosestUnits
        private group temp
        private real temp_x
        private real temp_y
    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)
                    call .left.addChild(node)
                // put right
                if .right == 0 then
                    call .addRight(node)
                    call .right.addChild(node)
        public method addLeft takes TreeNode node returns TreeNode
            local TreeNode old = .left
            set .left = node
            return old
        public method addRight takes TreeNode node returns TreeNode
            local TreeNode old = .right
            set .right = node
            return old
        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
        private method onDestroy takes nothing returns nothing
            set .u = null

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

    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)
        return temp

Collapse Test script:
function Trig_Test_Actions takes nothing returns nothing
    local group grp
    local integer i = 0
    local group g
        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

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

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

Anitarf 06-15-2009 12:40 PM

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

ToukoAozaki 06-15-2009 03:08 PM


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.

Anitarf 06-15-2009 05:02 PM

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.

Anitarf 06-15-2009 11:54 PM

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

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.

Number of units (picked/total):1/105/101/3020/30
Test subject one:51513130
Test subject two:8.593032
Control subject:5.56.51421

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

ToukoAozaki 06-16-2009 03:41 AM

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++ :)

All times are GMT. The time now is 04:16 AM.

Powered by vBulletin (Copyright ©2000 - 2020, Jelsoft Enterprises Ltd).
Hosted by www.OICcam.com
IT Support and Services provided by Executive IT Services