# 二、深入底層 我在自己的Web站點上花了許多時間聊關于令人激動的“巨幅圖畫”素材方面的內容， 比如說.NET與Java啦，XML策略啦，鎖定啦，競爭策略啦，軟件設計啦，體系結構啦，不一 而足。所有這些素材在某種意義上講，都是一塊夾心蛋糕。位于頂層的是軟件策略，接下來 是諸如.NET之類的體系結構，然后是各種產品，即Java之類的軟件開發產品，或者Windows 之類的平臺。 請繼續往蛋糕的底層看。是動態連接庫DLL?對象？函數？不！還要看得更低一些！在 某個點上，要考慮用編程語言書寫的代碼行。 這樣的層次還不夠低，今天我要考察的是CPU—一不停地向四周傳輸字節的小塊硅片。 假設您是一位編程新手，現在不妨拋棄業己建立的編程、軟件與管理等方面的所有知識，重 新回到底層的馮?諾依曼（Von Neumann)基本素材上來，并且暫時將」2EE踢出腦海，而只 考慮“字節”。 這樣做的意義何在？我覺得，人們所犯的一些最大錯誤（即使在體系結構的最高層）的 根源在于，對處于最底層的幾個簡單事物理解不夠或者一知半解。雖然金碧輝煌的宮殿己經 建起來了，但地基卻是一團糟。所用的建材不是上好的水泥板，而是零亂的碎石。于是乎， 宮殿雖然很好看，但浴缸不時在浴室的地面滑來滑去，而讓人不知所措。 好了，現在做一次深呼吸。看著我，這個小小的練習將用C語言來完成。 記住C語言中字符串的工作方式：字符串由系列字節組成，后跟一個取值為0[1]的空 (null)字符。這里很明確地表明了兩點： 1. 如果不遍歷字符串并查找末尾的空字符，就沒有辦法知道字符串在何處結束（即字 符串長度）。 2. 字符串中不能包含任何零。因此，C字符串中不能存放諸如JPEG圖片之類的任何二進制數據塊。 為什么C字符串要以這種方式工作？那是因為在上面開發了 UNIX與C程序設計語言的 PDP-7微處理器有一種ASCIZ字符串類型。ASCIZ的中文意思是“末尾有一個零的ASCII”。 這是存放字符串的惟一途徑嗎？不是。事實上，這是存放字符串最差的方式之一。對于 重要程序、API、操作系統與類庫，用戶應該像躲避瘟疫一樣地避開使用ASCIZ字符串。為 什么呢？ 下面從編寫函數strcat的一個代碼版本入手進行討論。該函數的功能是將一個字符串附 加在另一個字符串之后。 ``` void strcat( char* dest, char* src ) { while (*dest) dest++; while (*dest++ = *src++); } ``` 對代碼稍作研究，就可以明白這個函數正在做些什么。首先，它遍歷第一個字符串以尋 找空終止字符。一旦找到空字符，就逐字符將第二個字符串一次性拷貝到第一個字符串之后。 雖然這種_*_作與串接字符串的方法對于Kernighan與Ritchie[2]來說己經足夠好了，但 是也有它的問題。比如，假設有一串名字要在一個大字符串中串接起來，那就會暴露出來一 些問題： ``` char bigString[1000]; /*永遠也不知道需要分配多大的存儲空間...*/ bigString[0] = '\0'; strcat(bigString,MJohn,"); strcat(bigString,"aul,"); strcat(bigString,"George,"); strcat(bigString,"Joel "); ``` 這能夠應付，不是嗎？是的。并且，看起來也很漂亮整潔。 函數性能如何？能夠運行得盡可能快嗎？可擴展性如何？要是有一百萬個字符串要追 加，這樣處理還算得上很好的方式嗎？ 不，該代碼使用的是蹩腳的Shlemiel噴涂算法。Shlemiel是誰？他是下面這則笑話中的 人物： Shlemiel得到一份當街道油漆匠的工作，工作內容是在馬路中間噴涂點畫線。第一天， 他拿出一罐漆來到他負責的路段，噴涂了 300碼長的線。“干得不錯！ ”他的老板稱贊道， “真是一位麻利的工匠”，然后賞給他一個戈比（一種俄羅斯輔幣，譯者注）。 第二天，Shlemiel只噴涂了 150碼。“喏，雖然不如昨天那樣好，但你仍然算得上一位 麻利的工匠！ 150碼還是值得肯定的一個長度，”老板說完又賞給他一戈比。 接下來的一天，Shlemiel只噴涂了30碼長的馬路。“才30碼！”他的老板吼道。“這太 令人難以接受了！第一天你干的工作量是今天的10倍！接下來是怎么回事？〃 “我盡力了，”Shlemiel說道。“一天一天下去，我離油漆罐越來越遠！〃 (對于規模特大的應用來說，到底要“賒”多大存儲空間[3] ?)這則蹩腳的笑話很貼 切地說明了，如果像前面給出的代碼那樣使用strcat函數將會出現什么結果。由于strcat 的第一部分代碼必須每次都掃描整個目的字符串，以反復尋找那個捉摸不定的空終止字符， 因此該函數將比所希望的速度慢得多，并且它根本談不上存在伸縮性。你每天使用的許多代 碼都有這個問題。很多文件系統是以一種在一個目錄中放太多的文件的不恰當方式來實現的。 說它不恰當的原因在于，一旦目錄中達到成千上萬個條目時，其運行性能就開始急劇下降。 試著打開一個裝填過度的Windows垃圾箱來看看運行情況如何一一要花幾個小時才能顯示出 文件，它與所包含的文件數目基本上不成線性關系。這里面的某個地方必定存在一個Shlemiel噴涂算法。不管什么時候，只要某個應用項目看起來應該具有線性性能，可它卻表 現出n2的性能，那么就得尋找隱藏于其中的那些Shlemiel們。它們通常是被庫文件隱藏起來 了。看到一個循環體中出現一列或者一個strcat函數未必要大聲嚷嚷“找到n2 了”，但那 一定是問題之所在。 如何修正strcat函數呢？有幾個聰明的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,"aul,"); p = mystrcat(p,"George,"); p = mystrcat(p,"Joel "); ``` 這個性能當然是線性而不是n2的，因此它不會在串接許多字符串時而導致性能下降。 Pascal語言的設計人員意識到了這個問題，并通過將字符串的首字節用于存放字節個數，對該問題加以解決。由此得到的字符串稱為Pascal字符串。這樣的字符串可以包含取值為0 的字節，它不會被當做空終止字符。由于一個字節可以表示的最大數值為255,因此Pascal 字符串只能限于255個字節的長度。但由于它們不是以空字符作為終止符，所以占據與ASCIZ 字符串相同數量的存儲器。Pascal字符串最主要的亮點在于用戶完全沒有必要僅僅為了弄清 字符串的長度而使用一個循環語句體。確定一個Pascal字符串的長度只用到一條匯編指令， 而不是整整一個循環體。這是非常快的。 舊的Macintosh***作系統處處用到了 Pascal字符串。許多C程序員在其他平臺上也用到 了Pascal字符串以提高處理速度。Excel在內部使用Pascal字符串，這就解釋了為什么Excel 中許多地方的字符串限于255個字節的原因，同時它也是Excel的速度快得出奇的一個原因。 在相當長的一段時間內，如果想在C代碼中放一個Pascal字符串文本，就不得不寫一條 如下形式的代碼： ``` char* str = "\006Hello!"; ``` 對啰，用戶得親自動手計算字節的數目，并將它以編碼的形式放在字符串的第一個字節 之中。偷懶的程序員會按如下形式來實現該功能，但得到的程序運行起來很慢： ``` char* str = "*Hello!"; str[0] = strlen(str) - 1; ``` 需要引起注意的是，在這種情況下得到的字符串，同時也是以空字符作為終止符的（由 編譯器來做這件事）。我習慣于將它們稱為雜交串，因為這比稱它們是以空字符結尾的Pascal 串要簡潔一些。不過，這是一個高速變化的頻道，因此將來得使用較長的名稱。 前面忽略了一個重要的問題。還記得這樣的一個代碼行嗎？ ``` char bigString[1000]; /*從不知道要分配多少存儲空間 */ ``` 既然現在談到了位，就不應該忽略掉這個問題。我本來應該正確地處理該問題：弄清楚 到底需要多少個字節，并分配合適的內存量。 難道不應該嗎？ 大家知道，如果不這樣做，那么聰明的黑客會讀取該代碼，并注意到用戶只分配了 1000 個字節而覺得它夠用了。黑客們還會找到一些比較聰明的方式，誘騙用戶將1100個字節的字 符串用strcat放到1000個字節的內存中，從而重寫堆棧頁面并改變返回地址。結果造成在該 函數返回時，它執行了黑客自己寫的一些代碼。這就是他們在說某特殊程序具有緩沖區溢出 易感性（buffer overflow susceptibility)時所談論的內容。在那一段Microsoft Outlook 使黑客攻擊行為容易得讓十來歲的小孩也可以做到之前的歲月里，這曾經是出現黑客和蠕蟲 的首要成因。 好了，看來那些程序員都不過是些跛腳驢。他們本來應該去弄清需要分配多少內存的。 不過，說實在話，對于一般程序員而言，C語言并沒有使該問題變得容易解決。還是回 過頭來看看前面有關那個披頭士的例子吧： ``` char bigString[1000]; /*從不知道要分配多少內存*/ char *p = bigString; bigString[0] = '\0'; p = mystrcatCp'John,"); p = mystrcat(p,"aul,"); p = myst「cat(p,"Geo「ge,"); p = mystrcat(p,"Joel "); ``` 應該分配多少內存？不妨試著以合理的方式來做這件事。 ``` char* bigString; int i = 0; i = strlen("John,") + strlen("aul,") + strlen("George,") + strlen("Joel "); bigString = (char*) malloc (i + 1); /*別忘了存放空終止字符也要空間！ */ ``` 我的眼睛花了。或許讀者己經準備換頻道了。我不責怪你，但煩請忍耐一下，因為真正 令人感興趣的內容到來了。 僅僅為了弄清字符串有多大，就必須一次掃描完所有的字符串，然后在串接時還要再次 對它們進行掃描。如果使用Pascal字符串，至少strlen***作是很快的。也許，我們可以編 寫一個能夠為我們重新分配內存的strcat函數版本。 它將另外一整罐蠕蟲（內存分配器）打開。你知道malloc函數是如何工作的嗎？ malloc 函數的實質體現在，它有一個將可用的內存塊連接為一個長長的列表的所謂空閑鏈表。調用 malloc函數時，它沿連接表尋找一個大到足以滿足用戶請求所需要的內存塊。然后，將該內 存塊一分為二（一塊的大小與用戶請求的大小相等，另一塊的大小就是剩下的字節）。接下 來，將分配給用戶的那塊內存傳給用戶，并將剩下的那塊（如果有的話）返回到連接表上。 調用free函數時，它將用戶釋放的內存塊連接到空閑鏈上。到最后，空閑鏈會被切成很多的 小內存片段，如果這時用戶申請一個大的內存片段，那么空閑鏈上可能沒有可以滿足用戶要 求的片段了。于是，malloc函數請求延時，并開始在空閑鏈上翻箱倒柜地檢查各內存片段， 對它們進行整理，將相鄰的小空閑塊合并成較大的內存塊。 這要用去三天的時間。經過一通“雞飛狗跳”的混亂狀況之后所得到的最終結果變成： malloc的性能表現為永遠也快不起來（總是要遍歷空閑鏈），有時候甚至顯得不可預測，在 清理內存時慢得使人害怕。（順便說一下，這與垃圾收集系統的性能特征類似，不令人吃驚 才怪呢。可見，人們做出的關于垃圾收集行為如何導致性能損失的所有斷言都不完全成立。 因為典型的malloc實現形式具有同樣的性能損失，盡管略顯溫和。） 聰明的程序員通過總是分配大小為2的冪的內存塊，而最大限度地降低潛在的malloc性 能喪失。也就是說，所分配的內存塊大小為4字節、8字節、16字節、18446744073709551616 字節，等等。至于說原因，任何與Lego打過交道的人應該是一目了然的，這樣做最大限度地 減少了進入空閑鏈的怪異片段（各種尺寸的小片段都有）的數量。盡管看起來這好像浪費了 空間，但也容易看出浪費的空間永遠不會超過50%。因此，程序不會使用大小超過所需尺寸 兩倍的內存，這并不是大得不得了。 現在，不妨假設自己要編寫可以自動重新分配目的緩沖區的“智能〃st「cat函數。總是 應該分配所需要的實際尺寸嗎？我的老師兼顧問Stan Eisenstat [4]建議，在調用realloc 函數時，應分配出兩倍于以前所分配的內存。這意味著，用戶決不會調用「ealloc函數達lg (n)次以上。該性能特征即使對于大型字符串也可以忍受，并且決不會浪費多于50%的內存。 總而言之，在字節領地里，越往下走，生活就顯得越來越凌亂。你難道不對自己再也用 不著使用C語言編寫內存分配函數而感到高興嗎？我們擁有Perl、Java、VB與XSLT這些偉大 的編程語言，它們再也不會讓你去考慮此類事情。不用問為什么，它們只管去做好了。 不過，豎直的基礎結構偶爾也會從起居室的中部凸現出來，于是我們就得考慮是否使用 String類，或者StringBuilde「類，或者相關方面的一些差別，因為編譯器仍然沒有聰明到 能夠理解我們正在盡力完成的一切，從而試圖幫助我們不在無意之中寫出一些Shlemiel噴涂 算法。 這篇隨筆文章在我寫了一篇說明以XML形式存儲的數據不能用SELECT author FROM books 實現性能很快的SQL語句的即興網評[1]之后，受到了不友善攻擊。正是因為大家沒有理解我 在說些什么，以及既然我們整天都在CPU周圍打滾，這個主張可能才更顯得有意義。 關系數據庫是如何實現SELECT author FROM books的？在關系數據庫里，關系表（例如 books表）的每一行具有相同的字節長度，而每個字段距離各行開頭的偏移量是大小固定的。 因此，如果books表的每條記錄是100個字節長，并且autho「字段處在偏移量為23的位置， 那么作者們的名字就存放在第23, 123, 223, 323等位置的字節處。移到該查詢結果的下一 條記錄的代碼是什么？大體上講，這條代碼為： ``` pointer += 100; ``` 只用了一條CPU指令！快，快，實在是快！ 現在我們來看XML中的books表。 ``` <?xml blah blah> <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解析成內存中的樹結構吧，以便能夠相當快 速地處理它。在這里，針對SELECT author FROM books語句，CPU必須完成的工作量絕對會 將人折磨至瘋。正如每個編譯器設計人員都知道的那樣，語法分析與解釋是在編譯處理過程 中最慢的部分。只要談我們在解釋、分析與建立抽象的內存語法樹時，發現它涉及許多處理 起來很慢的字符串素材，以及許多執行起來很慢的內存分配內容就夠了。 況且，這還假定了有足夠的內存用于一次性加載整個內容。對于關系數據庫來說，在記 錄之間執行移動_*_作的性能是固定不變的，實際上它不過是一條指令的事。這是費了好大 的力氣有意為之的。同時，因為得益于內存映像文件，用戶只需加載將要實際使用的那些磁 盤頁面。 對于XML來說，如果要做預分析的話，那么在記錄之間執行移動操作的性能是固定不變 的，只是啟動時間極大；如果不做預分析，那么在記錄之間執行移動操作的性能根據它前 面的記錄長度而變化，并且CPU指令長達好幾百條。 這在我看來意味著，如果用戶講究性能，并且數據量很大，那么就不能使用XML。如果 只有一點兒數據，或者事情做得不必很快，那么XML不失為一個好的形式。并且，如果用戶 確實希望魚與熊掌兼得，就必須找出一種途徑用于緊***XML存放元數據。元數據跟Pascal 字符串中用于計數的字節的作用差不多，它向用戶給出提示信息，以便不用去分析與掃描字 符串就能確定它們在文件的什么地方。當然，這樣一來用戶就不能使用文本編輯器去編輯文 件了，因為那會搞亂元數據，從而它不再是真正的XML了。 對于聽眾中三個仍然在這一點上支持我的和顏悅色者，我希望你們己經學到了些東西或 者重新考慮過一些事情。我希望針對諸如strcat與malloc函數到底如何工作之類的那些令人 厭煩的一年級計算機課程素材所做出的思考，己經向你們提供了新的工具手段，從而在處理 XML之類的技術問題時，制定出最新的關于頂層策略和體系方面的決定。 作為家庭作業，思考一下為什么Transmeta芯片總是會覺得行動遲緩？為什么關于 TABLES的原始HTML說明設計得如此之差，以致Web頁面的大型表不能夠快速地顯示給使用調 制解調器的人們？為什么COM是如此棒，但在跨越進程邊界時卻不是這樣的？還有，為什么 NT人將顯示器驅動程序放在內核空間，而不是用戶空間？ 所有這些事情都要求用戶去思考字節，字節影響著用戶在各種體系與策略方面做出決定。 這就是我為什么堅持一種教學觀點一一大學一年級學生需要從基礎學起，即用C語言以及從 CPU開始向上逐步構建自己程序設計技能一一的原因。我真的從心底里厭煩在多得出奇的計 算機課程計劃中，將Java看做是一門好的入門語言的做法。這些計劃的理由是：Java語言雖 然很“簡易”且不會陷入所有那些令人厭煩的字符串與malloc素材之中，但是可以學習特別 棒的OOP知識，從而使大型程序具有如此之多的模塊化特性。 這是一場即將發生的教學災難。一屆又一屆的畢業生正在侵襲我們，他們正在忽左忽右 地創建著Shlemiel油漆匠算法，而他們甚至還沒有意識到這一點。原因在于，他們根本就沒 有那種字符串在深層次上處理起來很困難的理念，即使在Perl腳本上也不能很好地看到那一 點。如果想在某個方面把別人教好，自己首先得從最底層開始研究。這就像空手道功夫小子 要做的事情一樣。打蠟，剝蠟。打蠟，剝蠟。這樣的過程要進行三個星期。然后，他就可以 輕松擊敗其他小孩了。