代码执行次数上限研究

zyl910

名称：代码执行次数上限研究
作者：zyl910
版本：V2.0.0
日期：2006-4-20




简介
~~~~

　　在V1.0的研究（TExecCntV1_0.w3x.log）中，我们将loop语句的执行开销定义为最小执行单元L，从而得到以下结论：
一、执行上限为 300000L。
二、“set var = var + 1”的开销为 6L。

　　但是还有很多语句的开销是未知的，这就是V2.0研究的内容。



结论
~~~~

一、set（赋值）：
　　变量相互赋值：2L
　　将常数赋给变量：2L
　　得到数组元素的值：3L
　　给数组元素赋值：5L

二、local（局部变量）：
　　定义局部变量的开销（不初始化）：1L
　　定义局部变量的开销（初始化）：3L
　　定义局部数组的开销：1L


三、limitop（运算符）：
　　读变量/常量：1L
　　写变量：1L
　　算术运算：3L
　　比较运算：3L
　　or（或）运算：2L
　　and（与）运算：2L
　　not（非）运算：1L


四：exitwhen：1L


五、call（调用函数）：
　　call: 1L
　　跳出函数：1L
　　return: 3L
　　传递参数：2L
　　自动处理参数：1L


六、if语句：
　　比较复杂，具体请看“研究历程”的六



研究历程
~~~~~~~~

一、set（赋值）的开销：

1.1　变量相互赋值的开销
　　测试代码。两个全局变量相互赋值：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        set udg_I = udg_J
    endloop
endfunction

　　执行次数：33333
　　分析：300000/33333 - (1+6) = 9 - 7 = 2 (L)


　　测试代码。两个局部变量相互赋值：
function Trig_run_Test_Actions takes nothing returns nothing
    local integer i = 0
    local integer j = 0
    loop
        set udg_iCount = udg_iCount + 1
        set i = j
    endloop
endfunction

　　执行次数：33332
　　分析：与全局变量的33333很接近，所以变量相互赋值的开销都是一样的，都为 2L。


1.2　将常数赋给变量的开销
　　测试代码：
function Trig_run_Test_Actions takes nothing returns nothing
    local integer i = 0
    loop
        set udg_iCount = udg_iCount + 1
        set i = 1
    endloop
endfunction

　　然后将循环内给i赋值的常数改成其他数值，发现测试结果都一样??是33333。
　　表示将常数赋给变量的开销是 2L。





1.3 得到数组元素的值：
　　测试代码：
function Trig_run_Test_Actions takes nothing returns nothing
    local integer array arr
    loop
        set udg_iCount = udg_iCount + 1
        set udg_I = arr[0]
    endloop
endfunction

　　无论怎么修改 数组的下标，测试结果都是30000。
　　分析：300000/30000 - (1+6) = 10 - 7 = 3 (L)



1.4 给数组元素赋值：
　　测试代码：
function Trig_run_Test_Actions takes nothing returns nothing
    local integer array arr
    loop
        set udg_iCount = udg_iCount + 1
        set arr[0] = 1
    endloop
endfunction

　　无论怎么修改 数组的下标 或 右边的数值，测试结果都是25000。
　　分析：300000/25000 - (1+6) = 12 - 7 = 5 (L)


二、local（定义局部变量）的开销

2.1　定义局部变量的开销（不初始化）
　　编写下面那样的测试代码：
function Trig_run_Test_Actions takes nothing returns nothing
    local integer i1
    local integer i2
    local integer i3
    local integer i4
    local integer i5
    local integer i6
    local integer i7
    local integer i8
    local integer i9
    local integer i10
    loop
        set udg_iCount = udg_iCount + 1
    endloop
endfunction

　　测试结果：
0条local：42857
10条local：42855
20条local：42854
40条local：42851
80条local：42845

　　分析：
0: 30000 - (1+6)*42857 = 300000 - 7*42857 = 300000 - 299999 =  1 (L)
10: 30000 - (1+6)*42855 = 300000 - 7*42855 = 300000 - 299985 = 15 (L)
20: 30000 - (1+6)*42855 = 300000 - 7*42854 = 300000 - 299978 = 22 (L)
40: 30000 - (1+6)*42851 = 300000 - 7*42851 = 300000 - 299957 = 43 (L)
80: 30000 - (1+6)*42845 = 300000 - 7*42845 = 300000 - 299915 = 85 (L)

　　可以看出，开销为 1L。


2.2　定义局部变量的开销（初始化）
　　将变量的初始化值设为0。80个局部变量测试结果为：42822
　　将变量的初始化值设为1。80个局部变量测试结果也是：42822
　　将变量的初始化值设为udg_I。80个局部变量测试结果还是：42822

　　分析：
80: 30000 - (1+6)*42845 = 300000 - 7*42822 = 300000 - 299754 = 246 (L)

　　可以看出，开销为 3L。与定义局部变量后再赋值的开销一致。


2.3　定义局部数组的开销
　　仍是那80行语句，现在加上array关键字。测试结果为：42845。
　　与定义非数组变量一样，开销为1L。



三、limitop（运算符）：

3.1　算术运算（加减乘除）：
　　测试代码：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1 //+ udg_I + udg_J + udg_K
    endloop
endfunction

　　然后调整注释符的位置进行测试。测试结果：
0:42857
1:27272
2:20000
3:15789

300000/42857 = 7.0000233334111113703712345707819
300000/27272 = 11.000293341155764153710765620417
300000/20000 = 15.000000000000000000000000000000
300000/15789 = 19.000570017100513015390461713851

　　可看出每加上一个数值，开销增加4L
　　然后将运算符换成减、乘、除，发现测试结果与上面的相同，开销为4L


3.2　or（或）运算：
　　测试代码：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        set udg_bTemp = false //or false or false
    endloop
endfunction

　　测试结果：
0: 33333
1: 25000
2: 20000

　　分析：
300000/33333 - (1+6) = 9 - 7 = 2 (L)
300000/25000 - (1+6) =12 - 7 = 5 (L)
300000/20000 - (1+6) =15 - 7 = 8 (L)

　　开销为3L



3.3　and（与）运算：
　　测试代码：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        set udg_bTemp = false //and false and false and false
    endloop
endfunction

　　测试结果：
0: 33333
1: 25000
2: 25000
3: 25000
4: 25000
……

　　貌似开销为3L。但为什么后面的没有计算呢？
　　原来Jass支持短路运算，如果是全由and组成的表达式，只要发现一次的运算结果为false就立即退出。
　　刚才又测试了一下or运算符，发现它也支持短路运算。


3.4　not（非）运算：
　　测试代码：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        set udg_bTemp = not udg_bTemp
    endloop
endfunction

　　测试结果：30000

　　分析：
300000/30000 - (1+6+2) = 10 - 9 = 1 (L)


3.5　比较运算：
　　测试代码：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        set udg_bTemp = udg_iCount < 0
    endloop
endfunction

　　测试结果：23077

　　分析：300000/23077 - (1+6) = 13 - 7 = 6 (L)


3.5　假说：
　　根据上面的这些测试结果，我设计了如下的假说：
读变量/常量：1L
写变量：1L
算术运算：3L
比较运算：3L
or（或）运算：2L
and（与）运算：2L
not（非）运算：1L

　　该假说是很符合现在的测试数据的。
　　而且能解释为什么“得到数组元素的值是3L”，这是因为：读数组变量、读数组下标、写变量。



四、exitwhen（退出循环）：

　　测试代码：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        exitwhen false or false or false
        set udg_iCount = udg_iCount + 1
    endloop
endfunction

　　测试结果：
1: 33333
2: 25000
3: 00000

　　测试结果与or运算相同，所以exitwhen的开销是1L。
　　还可以这样看：条件运算的结果放入一匿名变量，那个1L是写匿名变量的开销。由于条件不成立，所以exitwhen无开销。


五、call（调用函数）：

5.1　调用CJ函数：
　　测试代码为：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        call ClearSelection()
    endloop
endfunction

　　测试结果：37500
　　分析：300000/37500 - (1+6) = 8 - 7 = 1 (L)


　　调用有返回值的函数ChooseRandomNPBuilding，执行次数仍是37500。


　　调用有两个参数的函数SetStartLocPrioCount、有三个参数的函数AddItemToAllStock 的测试结果：
2: 25000
3: 21429

　　分析：
300000/25000 - (1+6) = 12 - 7 = 5 (L)
300000/21429 - (1+6) = 14 - 7 = 7 (L)

　　表示传递一个参数的开销为 2L


5.2　无返回值的函数：
　　该函数为：
function funvoid takes nothing returns nothing
endfunction

　　测试代码为：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        call funvoid()
    endloop
endfunction

　　测试结果：33333
　　分析：300000/33333 - (1+6) = 9 - 7 = 2 (L)
　　估计call的开销是 1L，然后函数跳出的开销为 1L。

　　将函数改为：
function funvoid takes nothing returns nothing
    local integer i
endfunction

　　测试结果：30000
　　分析：300000/30000 - (1+6) = 10 - 7 = 3 (L)

　　表示执行用户自定义函数时，函数中的代码也得算进去。



5.3　有返回值的函数：
　　该函数为：
function fun0 takes nothing returns integer
    return 0
endfunction

　　测试代码为：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        call fun0()
    endloop
endfunction

　　测试结果：27273
　　分析：300000/27273 - (1+6) = 11 - 7 = 4 (L)

　　可得出return的开销为 3L（可能是 读变量、写变量、跳出函数）。


5.4　带参数的函数：
　　有如下函数：
function fun1 takes integer i1 returns nothing
endfunction

function fun2 takes integer i1, integer i2 returns nothing
endfunction

function fun3 takes integer i1, integer i2, integer i3 returns nothing
endfunction


　　测试代码为：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        call fun1(0)
    endloop
endfunction


　　测试结果：
1: 23077
2: 18750
3: 15790

　　分析：
300000/23077 - (1+6) = 13 - 7 = 6 (L)
300000/18750 - (1+6) = 16 - 7 = 9 (L)
300000/15790 - (1+6) = 19 - 7 =12 (L)

　　每多一个参数就多 3L。估计那多出来的 1T 是自定义函数对参数的自动处理。
　　但是还是存在无法理解的：6 - (1 + (2+1)*1 + 1) = 1


六、if语句：

6.1　空if
　　测试代码为：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        if true then
        endif
    endloop
endfunction

　　测试结果：37500
　　分析：300000/37500 - (1+6) = 8 - 7 = 1 (L)


　　测试代码为：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        if true or false then
        endif
    endloop
endfunction

　　测试结果：27273
　　分析：300000/27273 - (1+6) = 11 - 7 = 4 (L)

　　只是单纯计算表达式。


6.2　一般if
　　测试代码为：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        if true then
            set udg_I = udg_J
        else
            set udg_I = udg_J
        endif
    endloop
endfunction

　　测试结果：25000
　　分析：300000/25000 - (1+6) = 12 - 7 = 5 (L)



　　测试代码为：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        if true then
            set udg_I = udg_J + 1
        else
            set udg_I = udg_J + 1
        endif
    endloop
endfunction

　　测试结果：18750
　　分析：300000/18750 - (1+6) = 16 - 7 = 9 (L)

　　无论将true改成false，还是去掉else部分，执行次数都不会发生改变的。
　　我估计这 3L 是：计算条件表达式（读入true）、跳转到then部分、if执行完后跳到if后面的代码


6.3　多行if
　　下面这两种测试代码的执行结果都是相同的：
function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        if false then
        elseif true then
            set udg_I = udg_J
        else
            set udg_I = udg_J
        endif
    endloop
endfunction

function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        if false then
        else
            if true then
                set udg_I = udg_J
            else
                set udg_I = udg_J
            endif
        endif
    endloop
endfunction

　　测试结果：20000
　　分析：300000/20000 - (1+6) = 15 - 7 = 8 (L)
　　这 8L 分别为：
1.读false
2.跳转到（外层if的）else块
3.读true
4.跳转到（内层if的）then块
5.读udg_J
6.写udg_I
7.跳转到内层if的后面
8.跳转到外层if的后面




更新
~~~~
[2006-4-20] V2.0.0
V2.0开始。


[2006-4-19] V1.0.0
V1.0完毕。请看TExecCntV1_0.w3x.log

zyl910

名称：代码执行次数上限研究
作者：zyl910
版本：V1.0.0
日期：2006-4-19



测试代码
~~~~~~~~

function Trig_run_Test_Actions takes nothing returns nothing
    loop
        set udg_iCount = udg_iCount + 1
        //set udg_I = udg_I + 1
        //set udg_J = udg_J + 1
        //set udg_K = udg_K + 1
    endloop
endfunction




测试结果
~~~~~~~~

　　一：iCount 一行
[Test]
Count: 42857
I: 0
I: 0
I: 0

　　二：iCount、I 二行
[Test]
Count: 23077
I: 23076
I: 0
I: 0

　　三：iCount、I、J 三行
[Test]
Count: 15790
I: 15789
I: 15789
I: 0

　　四：iCount、I、J、K 四行
[Test]
Count: 12000
I: 12000
I: 12000
I: 12000



分析数据
~~~~~~~~

先定义以下未知数：
T: 触发器开始执行的开销
L: loop语句的开销
S: 每执行一条set语句的开销
max: 上限


列方程组：
T + (L + S*1) * 42857 = max
T + (L + S*2) * 23076 + (L + S) = max
T + (L + S*3) * 15789 + (L + S) = max
T + (L + S*4) * 12000 = max


展开系数：
T + 42857*L + 42857*S = max
T + 23077*L + 46153*S = max
T + 15790*L + 47371*S = max
T + 12000*L + 48000*S = max


前一式 减 后一式：
19780*L - 3304*S = 0
7287*L - 1218*S = 0
3790*L -  629*S = 0


变成一个齐次线性方程组了，麻烦！
将S移过去：
S = (19780/3304)*L = 5.9866828087167070217917675544794*L
S = ( 7287/1218)*L = 5.9827586206896551724137931034483*L
S = ( 3790/ 629)*L = 6.0254372019077901430842607313196*L

现在定义L为最小执行单元，则S的开销为6*L


现在来计算max：
max = T + 42853*L + 42853*S = T + 42853*L + 42853*6*L = T + 299971*L
max = T + 23077*L + 46153*S = T + 23077*L + 46153*6*L = T + 299995*L
max = T + 15790*L + 47371*S = T + 15790*L + 47371*6*L = T + 300016*L
max = T + 12000*L + 48000*S = T + 12000*L + 48000*6*L = T + 300000*L


可以认为max为300000

zyl910

保留

illlusion

一大清早起床就看见这个~~爽
坚决支持“无用”的基础研究！！！！

ady1212

精華文章 怎麼可以下沉 頂~