[好文]將LPC程式最佳化
原始連結
http://bbs.mudbuilder.com/read.php?tid=6205&fpage=2
版主覺得好可以收精華區
我覺得這篇十分重點啊
將 LPC 程式最佳化【好文回顧】
(MudOS 0.9.x 版)
作者: Luke Mewburn
版本: 1.2
日期: 930321
翻譯: Devianth , elon@eastern.stories
(10/29/94)
0. 簡介
我寫這篇文章的原因是我注意到 LPmud 越來越傾向複雜化及玩家驅動的功能.
這是好現象, 但因為 LPC 運作的方法 (一次只解譯一部份的程式) 寫不好的程
式碼不但會使的整個 mud 慢下來, 也會使在 mud 上的玩家感到 'lag'.
因為如此, 我決定去找出方法將一些常用的工作寫成有效率的程式並記錄下來
以供參考. 我假設讀者已有一些 C 或 LPC 的程式經驗. 但是, 如果你是新手,
我依然建議你將本文讀完因才能在一開始就學到正確的程式寫法.
雖然我的研究是關於 MudOS 0.9 的 driver, 但許多經驗還是能在其它 LP v3
型的 driver 下使用. 但這並不保證這裡所講的在非 MudOS driver 下是完全
正確的, (比方說 Amylaar 的 3.2@22 driver), 因為各 driver 程式碼已經
有相當大的差異了.
以下的程式碼, 我們將假設這些定義:
int i, j, max, bitfield;
object *list;
string *arr, name;
LPC, 像 C 一樣, 有支援 '動態配置'. 也就是 driver 只有在需要
時才會將記憶體分給要用的運算 (完成後會收回). 跟 C 不同的是, LPC 會自動
地在你使用完後收回分配的記憶體 (i.e. 當沒有 LPC 程試碼在使用時) - 又叫
'清除收集'. 字串 (string), 陣列 (array) 和 mapping 都是'動態'處理的.
雖然 '動態配置' 在結構化程式裡非常有用, 但相對的它也使用了非
常多的 CPU 時間. 本文的目地之一就是要教你如何正確的運用 '動態配置'
的好處而不要浪費了這項功能.
1. GENERAL POINTS
在我開始教你如何始某段程式碼加速運作前, 我提出以下一些關於電腦程式寫作
的公理:
第一條, '電腦花 80% 的時間執行 20% 的程式' ('80% of the time spent
executing an algorithm is in 20% of the code'), 或是所謂的 '80/20' 法
則. (有些說法是 75/25 或 90/10). 這個經證實的事實可以有效的幫助你寫
LPC 不要花太多時間試著將你所有的 LPC 程試碼最佳化, 你不會有那麼多的時
間. 將精神放在一些較常用, 執行次數較多的區段, 如 for-loops 等.
第二是, 如何選用正確的 algorithm. 大多數的時間, 當一個簡單的 algorithm
就足夠時, 人們會選擇一個複雜 algorithm, 特別是當程式處理少數資料時, 簡單
的 algorithm 通常比較有效率. 要能在簡化及效率上作一番取捨.
因為大部份的 driver 都沒有對 LPC 碼作最佳化的功能 (比方說重寫 expression
或迴圈 strength-reduction), 你能幫的忙就是有智慧的寫自己的程式碼.
一個加速的方法是將一個共用的常數/函式移到迴圈或迴圈測試之外, 並使用一
個暫時的變數. 最長見的就是在 while/for condition (q.v) 時使用 'sizeof(arr)'
在其它狀況下, 有可能某個函式每次都會在迴圈裡被呼叫, 但那個函式每次都會
傳回一個相同的值 - 如果真是這樣, 就在迴圈以外將這個值設定成一個變數, 並
在迴圈內使用這個變數. 例如:
for ( i = 0; i < max; i++)
if ( list == some_condition )
do_something_with( list, this_player()->query("name") );
假設 "name" 是不變的, 則以下的方法會比較好:
name = this_player()->query("name");
for ( i = 0; i < max; i++)
if ( list == some_condition )
do_something_with( list, name );
雖然說好的程式格式並不會真的加快編譯的速度, 但一個簡單好讀的程式比較
好修改及 debug. 大多數的人對程式的格式有不同的看法, 所以我在這裡也不
會強迫讀者使用我的格式, 我只想告訴你, 選擇一個你喜歡的格式, 然後保持
下去.
2. 資料型態 (DATA TYPES)
LPC 至少有以下的資料型態: int, string, object, mixed, mapping.
由以上所組成的陣列也是可能的.
以下是使用這些資料型態的要則:
2.1 整數 (INT)
整數資料型態使用起來非常的有效率, 因為 integer 不需要動態配置.
使用 bitfields (e.g. hand-coded with #defines, (模擬 ANSI C 的 enum's)),
你可以儲存多種的 flags 資料. 這樣會比將資料存成 bit size 來的快, 因為
bitfields 只需要 32 bits.
以下是處理 integer bit fields 的範例程式: (假設 VALUE 為 1,2,4,8, etc.)
bitfield != VALUE; // set bit VALUE
bitfield &= ~VALUE; // reset bit VALUE
bitfield & VALUE // test bit VALUE
如果你要設 bit n, 將 VALUE 取代為 (1 >< n)
2.2 字串 (STRINGS)
字串是最常用的資料型態, 但它需要 '動態配置'. 常數字串(constant string)
(i.e, 單純的 'write' 敘述) 是存放於一個 '字串表' 裡, 所以如果要有多重的
copy 通常不需要多餘的記憶體. 字串的加法 (使用 + 符號) 就是一個非常耗時的
運作 - 每加一段字就要配置記憶體一次. 通常我們會這樣寫:
write("this is a forest\n" +
"and is really boring.\n" +
"You are feeling sleepy\n");
這是最糟的方法來寫一個常數字串 - 當這個 object (物件) 被編譯時會非常的慢,
而且也沒有有效率的運用記憶體. 值得注意的是, 在 MudOS 0.9.15 [我們用
0.9.19.x] 在字串加法裡不一定要用 '+' 這個符號來代表 - 但這樣只是節省了原
始程式的大小 - 它還是需要使用動態記憶體分配來使用每一段在 " " 裡的字串.
試試以下:
write("\
this is a forect\n\
and is really boring.\n\
You are feeling sleepy.\n\
");
這樣的話所有的文字都存在一起. 你通常能用這種方法存取一頁以上的文字, 超過
這個數量時你的 parser 可能會嗆到, 試著將你的文字分段, 並使用分開的 write
statement.
注: 注意, \ 後到一行的結尾(eotl)之間不能有空白字元, 否則 parser 會抱怨.
UPDATE: MudOS 0.9.14.3 以後, 指定常數字串時有一個新的符號 - '@', 所以上
述範例也可以寫成:
write( @ENDMESSAGE
This is a forect
and is really boring
You are feeling sleepy.
ENDMESSAGE
);
('ENDMESSAGE' 是用來作為分界點的, 可以是任何不在 main body(?) 的任何字串,
而且它一定要在一行的最開端使用, 要不然它不會被當做 '訊息結束' 的記號.)
另一個沒有效率的方法:
write("Your name is " + this_player()->query("name") + "\n" +
"and your level is " + this_player()->query("level") + "\n");
如果你的 driver 有 printf(), 試著用以下的方法:
printf(Your name is %s\nand your level is %d\n",
this_player()->query("name"), this_player()->query("level") );
其它還有很多類似的例子, so you get the general idea.
但不要誤解我的意思, 字串加法是很常用的, 所以不要試著去用一些很長的運作或
技巧來避免用到字串加法. (因為這通常會比使用字串加法還慢).
2.3 浮點 (FLOATS)
0.9.15 以後的 driver 都有支援浮點(floating point)資料型態. 在宣告變數時用
'float' 這個 keyword. (對寫 C 程式的人來講, 這和 C 的 'double' type 相同)
像 cos, sin, (和類似的運算), ln, 和 sqrt (平方根) 等的的運算函數也可以使
用. 這種資料型態可以在編輯時暫時跳過, 但我看不出來這有什麼需要.
浮點的運算比整數慢、所以能用整數運算時盡量不要用浮點運算。需要用
到浮點運算時, 盡量先把它們算出來以迴避重複的運算(這點對於任何程式都通).
2.4. 陣列 (ARRAY)
陣列是非常有用的, 但跟字串一樣, 不當的使用會造成低效率的程式.
一個在迴圈內有增加或除掉項目的迴圈通常是較慢的. 解決的方法是適當的運用
記憶體預先配置。
摘自 TMI-2 的 /adm/daemons/cmd_d.c :
bin_ls = get_dir(path + "/");
result = ({ });
for (i = 0; i < sizeof(bin_ls); i++) {
if(sscanf(bin_ls, "_%s.c", tmp) == 1)
result += ({ tmp });
}
cmd_table[path]=result;
這裡, 並不是所有的項目都有選到, 被選到的也是在被修改過後再放到最後
的陣列中.
以下面的方法取代:
bin_ls = get_dir(path + "/");
i = sizeof(bin_ls);
result = allocate(i);
j = 0;
while (i--) { // 使用 'while' 的原因請參考下面
if(sscanf(bin_ls, "_%s.c", tmp) == 1)
result[j++] = tmp;
}
cmd_table[path]=result[0..j-1];
因為我們知道結果一定是 <= sizeof(bin_ls), 我們就只配置這麼多空間. 然
後再依需求增加項目. 最後, 在我們們使用結果前, 將陣列調到正確的大小.
(使用 [0..j-1] 運作).
[這裡的英文原文少了一段, 整節看來沒有意義, 故省略]
預先配置最大的優點就是在用預先配置時, 處理時間和項目數目呈線性正比 (linear)
而用 += 的陣列處理和處理時間成指數比增加 (exponential).
2.5. MAPPINGS
Mappings 就是連接性的陣列 - 能用基本資料型態(int, string, 或 object)
來做索引的資料結構。以資料結構來說, 它通常比陣列來的有效率, 並可以用來
模擬 C 裡的 'structs' 敘述.
基於 mappings 內部儲存的方式, 預先配置的 mapping 比較有效率.
如果你已經知道 mapping 裡的元素會保持在 x 個 (還可以再增加), 而且不會因
為使用 map_delete 而使總元素低於 x 個, 則此法特別有效率. (比方說, 當一個
mapping 已預先配置了 x 個元素, 在大多數的元素都被用 map_delete 刪除後,
你將會浪費很多記憶體因為 map_delete 將不會把預先配置的 mapping 裡沒有用
的記憶體釋放出來.)
一個常見的預先配置方法可在 emote daemon 或像 /std/user (或 /obj/player)
裡的標準物件中找到. 對於前者, 如果你已經有 200 個左右的項目,
不要用下列方法來格式你的 mapping:
emotemap = ([ ]);
應該改用:
emotemap = allocate_mapping( 200 );
3. 控制程序 (CONTROL FLOW) 以及 迴圈 (LOOPING)
在一個完整的 LPC 程式中, 控制程式執行的程序 (由測試, 以及部份的迴圈所
組成) 可以因為正確的使用不同的形式而變得比較有效率.
3.1. WHILE
最簡單的 (也是在簡化型裡最快的) 迴圈使用方式.
常見的是:
list = users();
for ( i = 0 ; i < sizeof(list) ; i++ )
do_something_with_item( list );
這是非常的沒有效率, 因為 sizeof(list) 的值每次都要被重新計算出來 (參考
上面的 GENERAL POINTS 一節). 如果你想將整個 list 反過來排列, 試著使用以
下的方法:
max = sizeof(list); // slight performance gain
i = -1;
while ( ++i < max ) //evaluate and increment at same time
do_something_with_item(list);
如果順序沒有什麼太大的關係, 以下是最快的方式:
i = sizeof(list);
while (i--)
do_something_with_item(list);
這就是 '簡單的調件 while 迴圈' ('simple condition while loop'). 和下列的
實在是沒什麼太大的不同.
for ( i = sizeof(list) ; i-- ; ) ;
以及相對等的 while 迴圈. 但還是有少許利益可得.
3.2. FOR
最常見的迴圈結構之一, 這在當你每次都需要在迴圈結述前執行某個比較複雜的
動作時非常有用. 如果只是使用簡單的指數增加或減少, 用 'while' 敘述會比較
好.
如果 '結述運作' (ending operation) 比較複雜, 則以下的通用例子:
for ( initialise ; test ; final ) {
main body
}
比下列清楚:
initialize
while ( test ) {
main body
final
}
3.3. 開關 (SWITCH)
switch 敘述應該盡可能的用來取代 'if-then-else' 型結構. 因為新的 driver
都有對 switch 敘述作相當程度的簡化. 另一方面, 用 switch 敘述的程試碼看來
也比較 '乾淨'.
用 switch 敘數的另一個優點是 `狀況範圍' (case range) 的支援. (一個 C 沒有
的特色). 如果你的測試設定如下面的範圍:
case 1: case 2: case 3:
可用以下代替:
case 1..3:
可能比較有效率 (至少字少打一些)
4. 結論
我確定這份文件中一定有錯誤, 但是人不是完美的.
以下的人對本文的 1.1 版提出問題, 意見:
@TMI-2: Blackthorn, Mobydick, Square, Alexus, Amylaar, Darin
@Ivory.tower: Telsin, Vampyr
@Underdark: Cynic, Brian
Luke [Zak].
程式的最佳化
==============
在optimizing_code裡已經談到了一些最佳化的簡單注意事項。然而最
佳化並不是少數adm或大巫師的事，而是每一個巫師寫程式都必須注意
的事項。因此請大家在完成一個作品時，再花一些時間重看一下程式
，看看可不可以 藉由一些簡單的更改來避免一些不必要的計算，即使
只是節省一兩個計算也是好的。當然也不必為了省一點點的計算而花
很多時間或是把程式寫得很複雜。但是一些簡單的原則，或是稍微注
意一下，就可能 會有很大的影響。
我們來看一個簡單的例子，底下是/adm/daemons/aim_d.c其中的一段
程式，注意看第七行：
if( random(100) < 30 && !me->query("npc") ) return 0;
本來放在倒數第五行，也就是變成註解的地方。我看到了，就把它移
到現在的位置。這樣有什麼差別呢？如果在原來的位置，中間作了一
堆關於skill的計算，當此行成立，這些計算都浪費了。而移到第七行
的位置，當此行成立，就不會去計算skill，只是更改一下程式的位置
，就可以節省許多不必要的計算。這個程式是醫生每回合攻擊時都會
呼叫到，你可以想像原來的寫法作了多少不必要的計算。
int aim_target(object me, object victim)
{
int skill, diffculty;
string loc;
object weapon;
// difficulty for player
if( random(100) < 30 && !me->query("npc") ) return 0;
skill = (int)me->query_skill("anatomlogy");
loc = (string)me->query("aiming_loc");
if( !skill || !loc ) return 0;
diffculty = diffs[loc];
if( undefinedp(diffculty) ) return 0;
diffculty += diffculty*(int)victim->query("aim_difficulty/"+loc)/100;
[中間省略]
skill /= 10;
skill += (int)me->query_stat("int") * 2 + (int)me->query_stat("kar");
skill -= (int)victim->query_stat("int") * 2 + (int)victim->query_stat("kar");
// if( random(100) < 30 && !me->query("npc") ) return 0;
if( random(skill) < diffculty ) return 0;
return (int)call_other( this_object(), "hit_" + loc, me, victim );
}
在考慮程式最佳化時，先想想這段程式被使用的頻率有多高，如果是
使用頻率很高的程式，那就要多花些心力注意最佳化。一般使用頻率
較高的程式大略是/adm/, /cmds/, /std下的程式，不過這不是一般
巫師可以動的，另外公會的一些程式，武器的特攻、NPC的tactic，以
及一些init,relay_message的程式等等。這些都是使用頻率很高的程式
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.42.238.20
→
01/05 16:01, , 1F
01/05 16:01, 1F
mud 近期熱門文章
PTT遊戲區 即時熱門文章
95
225
27
54