回歸原點

作者:周思博 (Joel Spolsky)
譯:Paul May 梅普華
Tuesday, December 11, 2001
屬於Joel on Software, http://www.joelonsoftware.com


我們在這個站花了很多時間討論讓人興奮的大局概念,像是.NET對Java、XML策略、鎖住客戶、競爭策略、軟體設計、架構等等。 這所有的概念就某方面來看就像是個夾心蛋糕。最上層有軟體策略。再下來可以想想.NET之類的架構,然後再下面是個別的產品: 像Java之類的軟體開發產品或Windows之類的平台。

請再向蛋糕下層挖下去。是DLL嗎?還是物件或是函數呢?都不是!再下去! 下到某個地方就會想到用程式語言撰寫,一行又一行的程式。

不過還不夠深。今天我想談的CPU。一片把位元組們搬來搬去的小矽晶片。先假裝你是個新手程式師, 把你所有的程式設計和軟體還有管理知識都丟掉,然後回到最底層的馮紐曼的基本結構。暫時先把J2EE由你腦中拿掉,來想想位元組。

Vancouver BC為什麼要這樣做呢?我認為人們所犯的某些大錯雖然錯在最高的架構層,但其實是因為不夠瞭解或想錯某些在最底層很簡單的事情。 你可能建了一座雄偉的宮殿,可是地基卻是一塌糊塗。本來應該用好的水泥磚,結果卻用了碎石頭。所以宮殿看起來雖然華麗, 可是浴缸卻時常移位,而你根本不知道怎麼回事。

所以今天就來個深呼吸。請跟著我來做個用C語言進行的小小練習吧。

記得C的字串用法吧:它們是由一串位元組後面接一個null字元(值為0)所組成。這裡有兩個明顯的暗示:

  1. 必須整個字串走一遍找到結尾的null字元,才能知道字串在哪裡結束(也就是說字串的長度)。
  2. 字串裡不能有任何零。所以你不能用C字串來儲存JPEG圖片之類的二進位大物件。

為什麼C字串要這樣運作呢?因為發明UNIX和C語言時用的PDP-7微處理器有一種ASCIZ字串型別。 ASCIZ意思是「用Z(零)結尾的ASCII。」

這是儲存字串唯一的方法嗎?並不是,事實上它是儲存字串最爛的方法之一。只要是有作用的程式、API、作業系統、類別庫, 都應該像躲瘟疫一樣避開ASCIZ字串。為什麼呢?

讓我們由撰寫strcat這個把一個字串接到另一個字串的程式開始。

void strcat( char* dest, char* src )
{
     while (*dest) dest++;
     while (*dest++ = *src++);
}

大約讀一下這段程式,想想我們這裡做些什麼。我們先掃描第一個字串尋找結尾的NULL字元。找到之後再掃描第二個字串,掃描時每次把一個字元複製到第一個字串。

這種字串處理和字串連接對Kernighan和Ritchie來說夠好了, 不過還是有些問題。舉例來說。如果你有一大堆名字,全部都要附加到一個大字串後面:

char bigString[1000];     /* 我永遠不知道要配多少記憶體... */
bigString[0] = '\0';
strcat(bigString,"John, ");
strcat(bigString,"Paul, ");
strcat(bigString,"George, ");
strcat(bigString,"Joel ");

這程式能動,對吧?沒錯,而且看起來不錯也很乾淨。

它的效能如何?是不是儘可能的快呢?它能處理更多資料嗎?如果我有一百萬個字串要連接,這樣做適合嗎?

答案是否。這段程式用了油漆工Shlemiel的演算法。Shlemiel是誰?他是下面這個笑話的主角:

Shlemiel得到一個在路上塗油漆的工作,他要漆在路中間的間斷分隔線。第一天他拿了一罐油漆去漆好了300碼的路。 「做得真好!」他的老闆說「你手腳真快啊!」然後就給他一個銅板。

第二天Shlemiel只漆了150碼。「這樣啊,沒有昨天好,不過也還是很快。150碼也很了不起。」也給他一個銅板。

第三天Shlemiel只漆了30碼。「只有30碼而已!」老闆就哇哇大叫了。「這實在是無法接受!第一天你漆了十倍的長度耶! 究竟怎麼回事啊?」

「我也沒辦法啊,」Shlemiel說「我每隔一天就離油漆罐愈來愈遠啊!」

kansas(想挑戰的可以回答真實的數字是什麼?) 這個爛笑話正確地說明了使用像我剛剛寫的strcat版本會發生的狀況。由於strcat 的第一段每次都必須掃描目的字串,重複地找尋可惡的結尾NULL字元,所以這個函數會比真正需要的時間慢上許多, 而且完全不能正常處理更多的資料。你每天用的程式中很多都有這個問題。很多檔案系統的實作方式都有問題, 不適合把幾千個檔案放在同一個目錄裡。因為同一個目錄裡有幾千個檔案時效率就會急速下降。試著打開一個塞滿垃圾的 Windows資源回收桶看看有多慢 - 要花幾小時才能顯示出來,顯然並非與內含檔案數量成線性關係。 裡頭某處一定有個油漆工Shlemiel演算法在作怪。當你發現某件事本來應該有線性的效能,實際上卻是次方的效能, 就可以去找隱藏的Shlemiel。他們常常躲在你的程式庫裡。看著一長串的strcat或是迴圈中的strcat 並不會讓你立即喊出「n次方」,不過兇手就是它了。

要怎麼修正這個問題呢?有幾個聰明的C程式師實作了他們自己的mystrcat,內容如下:

char* mystrcat( char* dest, char* src )
{
     while (*dest) dest++;
     while (*dest++ = *src++);
     return --dest;
}

我們在這裡做了什麼?我們多花了一點點成本,傳回指向較長的新字串結尾的指標。 如此呼叫這個函數的程式就可以選擇不必重新掃描,直接把新字串接上去:

char bigString[1000];     /* 我永遠不知道要配多少記憶體... */
char *p = bigString;
bigString[0] = '\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

這段程式的效率當然是線性而非n次方的,所以要連接很多東西時也不會變慢太多。

Pascal的設計者注意到這個問題也加以「修正」了,修正的方法是在字串的第一個位元組存一個位元組數。這就叫做Pascal字串。 Pascal字串裡可以放零也不必用NULL字元結尾。因為一個位元組只能放0到255的數字,所以Pascal字串最長只能到255個位元組, 不過由於他們不用在結尾加NULL字元,所以佔的記憶體和ASCIZ字串一樣。Pascal字串的好處是取字串長度時不必用迴圈了。 在Pascal裡求字串長度不用迴圈,只要一個組合組言指令就夠了。當然是快太多了。

舊的麥金塔作業系統全都是用Pascal字串。很多其他平台的C程式師也為了速度而用Pascal字串。Excel內部就是用Pascal字串, 所以Excel裡很多地方的字串長度最多只能到255個位元組,這也是Excel飛快無比的原因之一。

有很長一段時期,如果想在C程式裡寫一個Pascal字串文字,必須寫成:

char* str = "\006Hello!";

沒錯,你得自己手工算出位元組的數目,然後寫死在字串的第一個位元組。懶惰的程式師會做下面的事,結果就拖慢了程式:

char* str = "*Hello!";
str[0] = strlen(str) - 1;

注意這個例子裡用的字串既是用NULL字元結尾(編譯器做的)又是Pascal字串。我習慣稱之為fucked字串, 因為這比NULL字元結尾的Pascal字串好叫多了。不過這裡是普通級頻道,所以還是用較長的名字吧。

我之前省略了一個很重要的問題。記得這一行程式嗎?

char bigString[1000];     /* 我永遠不知道要配多少記憶體... */

由於我們今天的主題是位元,所以不應該就這樣忽略它。我應該要用正確的寫法:找出需要的位元組數然後配置正確的記憶體量。

我不需要這樣做嗎?

這是一定要的。如果不做的話,某個聰明的駭客讀我的程式時會注意到,我只配置了1000個位元組並期望這數字足夠, 他們會找出某些聰明的方法,讓我把一個長1100位元組的字串strcat到原本1000位元組的記憶體中,然後就會覆蓋堆疊框並改變返回位址,於是當這個函數返回時就會執行到駭客寫的程式。當他們說某個程式有一個緩衝區溢出 漏洞時就是指這種東西。從前這可是駭客和蠕蟲侵入的頭號原因,不過微軟 Outlook出來後,入侵就簡單到連小朋友都會做了(譯註:因為漏洞很多又可以用VBScript寫)。

好吧,所以說這些程式師都只是些漏洞百出的傻瓜。他們應該要算出要配置的記憶體數量才對。

不過實際上在C裡並不是這麼容易。讓我們回到我們的小小範例:

char bigString[1000];     /* 我永遠不知道要配多少記憶體... */
char *p = bigString;
bigString[0] = '\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

我們應該要配置多少記憶體呢?讓我們試試正確的方式。

char* bigString;
int i = 0;
i = strlen("John, ")
     + strlen("Paul, ")
     + strlen("George, ")
     + strlen("Joel ");
bigString = (char*) malloc (i + 1);
/* 記得預留結尾NULL字元的空間! */
...

我已經暈了。你可能正打算放棄去別的地方。我不怪你,不過請再忍耐一下,因為快要變得很好玩了。

我們必須把每個字串掃描一次才能算出所有字串的總長度,然後在連接字串時又要再掃描一遍。既然用Pascal字串時 strlen動作會變快。或許我們可以寫一個能替我們配置記憶體的strcat

這時就出現另一種蠕蟲(譯註:指下面所討論的可用鏈結):記憶體配置器。你知道malloc的運作原理嗎?malloc的特性是有一長串由可用記憶體組成的鏈結串列,名為可用鏈結(free chain)。當你呼叫malloc時會掃描鏈結串列, 找尋大小滿足要求的記憶體區塊。然後把區塊切成兩塊,一塊是你所要求的大小,另一塊則是剩下的記憶體,把你要的那塊傳給你, 再把另一塊(如果有的話)放回鏈結串列中。當你呼叫free時會把釋放的區塊加回可用鏈結。 最後可用鏈結會被切割成很多小塊,當你要求大塊記憶體時就會找不到大小適合的記憶體。於是malloc 就會逾時並開始掃描可用鏈結,嘗試把相鄰的小可用區塊合併成較大的區域。這個動作會花個三天半(譯註:就是說很慢啦)。 這一團混亂的最後結論就是說malloc的效能特性絕不會非常快(一定要掃描可用鏈結),而且偶而(無法預測) 要清理時還會慢到暈倒。(補充一下,令人驚訝的是這和garbage collected系統的效能特性是一樣的。 所以人們說garbage collection的效能損失有多麼巨大,不完全是事實,因為一般的malloc 實作都有著相同類型的效能損失,只不過稍為好一點點。)

聰明的程式師在配置記憶體時會用2的次方為大小(比如4位元組,8位元組,16位元組,18446744073709551616位元組等等), 讓malloc的潛在不隱定性降到最低。這樣可以讓可用鏈結裡小碎塊的數量降到最低, 而有玩樂高積木的人應該都能直覺理解其原因。雖然似乎有點浪費空間,不過很容易就會看出浪費的空間不會超過總空間的一半。 所以你的程式最多只會佔用所需空間的兩倍,這應該不是什麼大問題才對。

假設你寫了一個聰明的strcat函數,可以自動重新配置目的緩衝區。這個函數是否應該每次都重新配置 到剛好的大小呢?我的老師兼心靈導師Stan Eisenstat建議,當你呼叫realloc時每次都應該用原本配置大小的兩倍。意思是永遠不必呼用 realloc超過lg n次,即使是對很大的字串來說也會有很不錯的效率特性, 而且也絕不會浪費超過一半的記憶體。

總而言之,在這往下到最底層的位元組世界中,生命愈來愈混亂。現在是不是很慶幸不需要再用C寫程式呢?我們現在有像Perl、Java、VB、XSLT之類的偉大程式語言,讓你永遠都不用考慮這種事情,因為程式語言都想辦法替你處理好了。不過偶而鉛管等基礎設施 還是會在客廳地板中央突出來,這時候我們就得考慮要用String類別還是StringBuilder類別, 或是想想某些類似的差異,因為編譯器還不夠聰明,無法理解我們嘗試完成的每件事,也無法幫助我們不會疏忽寫出油漆工 Shlemiel演算法。

[Image]

上星期我寫過如果你的資料是以XML方式儲存的話,就無法實作出快速的SQL敘述SELECT author FROM books。為了避免有人不懂我在說什麼,我再強調一次今天整天都在講CPU層次的事。這樣子應該比較看得懂上面的意思吧。

一個關聯式資料庫會如何實作SELECT author FROM books呢?在關聯式資料庫中, 資料表的每一行(舉例來說是books資料表)的位元組數都完全相同,而且各個欄位由列開頭起算的偏移量都是固定的。 所以舉個例子來說,如果books資料表中每個記錄的長度都是100個位元組,而author 欄是位於偏移量23的地方,那麼各個作者就會存在第23, 123, 223, 323等位元組的位址。在這個SQL查詢中要移到下一個記錄時要怎麼做呢? 基本上只要這樣就好:

pointer += 100;

只要一個CPU指令。夠快了吧。

現在讓我們來看看用XML格式儲存的books資料表。

<?xml 廢話...>
<books>
     <book>
          <title>UI Design for Programmers</title>
          <author>Joel Spolsky</author>
     </book>
     <book>
          <title>The Chop Suey Club</title>
          <author>Bruce Weber</author>
     </book>
</books>

來個小問題。要移到下一個記錄的程式要怎麼寫?

呃...

這時候一個好的程式師可能會說,好吧,讓我們分析XML轉成樹狀結構存在記憶體裡,這樣處理起來會相當快。 不過這時候CPU要處理SELECT author FROM books所做的工作量絕對會無聊到讓你哭出來。 每個編譯器作者都知道字彙和語法分析是編譯過程中最慢的部份。簡單的說,字彙分析和語法分析時牽涉到大量的字串處理 (前面已經發現這是很慢的)和大量的記憶體(也是已知很慢的),然後還要在記憶體中建立一個抽象文法樹。 而且還要假設你擁有足夠的記憶體可以一次載入所有資料。 在關聯式資料庫中,在記錄間移動的速度是固定的,而且實際上只要一個CPU指令。這是刻意設計出來的。 另外利用記憶體映對檔案,就只要把真正要用的資料由載入對應的磁碟區塊即可。在用XML的時候,如果有作前處理預先分析, 在記錄間移動的速度也是固定的,不過需要大量的啟動時間,如果不預先分析,那麼在記錄間移動的速度就要看之前的記錄有多長了, 而且不管怎麼都要幾百個CPU指令。

對我來說,這表示當資料量很大又要求速度時不能用XML。如果資料不多或做的事並需要速度,XML是個不錯的格式。 如果你想魚與熊掌兼得,就得想個方法在XML以外加些詮釋資料(metadata),儲存類似Pascal字串中位元組數目的資料。 這樣能提示資料在檔案中的位址,就不需要再去掃描分析了。不過當然不能用文字編輯器去編輯檔案了, 因為會把詮釋資料弄亂,所以其實這也不能算上真正的XML了。

對於那些一直跟著我撐到這裡的讀者,我希望你已經學到或是重新思考了某些事情。我希望探討像strcatmalloc究竟如何運作這種枯燥的電腦科學一年級課程,能在你面對XML等技術時, 協助你思考最新的高層次策略與架構上的決策。至於今天的作業,可以想想為什麼全美達(Transmeta)的晶片好像總是賣不好。 或者想想為什麼最早HTML規格的TABLE設計會爛到讓撥接上網的人不能快速的顯示大型表格。也可以想想COM既然這麼快, 為什麼跨越行程邊界時又快不起了。或者NT設計者為什麼會把顯示驅動程式放入核心空間而不留在使用者空間呢。

這所有的問題都需要你考慮位元組的層次,而它們也影響到我們在各種架構和策略上所做整體而高層次的決策。 我認為電腦科系一年級學生應該由基礎開始學起,使用C並由CPU開始一路建立觀念,這正是原因。 很多電腦科學計劃認為Java很「容易」,不用碰無聊的字串/記憶體配置就能學習最酷的物件導向技術,能讓你的大程式更加模組化, 所以很適合當作入門學習的電腦語言。我對這種想法其實非常的反感。這是一個蘊釀中的教學災難。畢業生一代代下來會愈來愈墮落, 到處寫出油漆工Shlemiel演算法而完全不自知,因為他們完全不知道,雖然perl指令看不出來,但是字串的底層操作其實是很困難的。 如果你想把某人教好,就得從最底層開始。就像電影「小子難纏」一樣。不斷的上蠟打蠟。三個星期後輕輕鬆鬆就把別的小鬼幹掉了。

Emacs

 

這些網頁的內容為表達個人意見。
All contents Copyright © 1999-2006 by Joel Spolsky. All Rights Reserved.