X Window 圖形介面的效能

自從用了 Ubuntu 了以後，發現 X Window 的桌面環境反應有些鈍鈍的，反倒是 Windows 的 GUI 比較流暢 (這裡指的是當 Ubuntu 桌面特效沒開的時侯和 Windows XP 相比)。比較明顯的地方像是以前 XP 在 YouTube 下全螢幕看影片時都不會 lag，但是在 Ubuntu 下看就會；還有瀏覽器在上下捲動網頁時也是，尤其是 background-attachment 屬性設成 fixed 的時侯 (即捲動網頁時背景固定不動只有內容會捲動的時侯，例如像鳥哥的這個網頁) 較容易會 lag，有時甚至連正在播放的 mp3 都會因此停掉。此外，當畫面 lag 的時侯觀看右上角的系統負載指示器



通常會發現 CPU 吃得滿兇的。

會發生上面那些問題可能有很多原因:

1. 有可能是驅動程式的問題，因為顯示卡沒有被正確驅動造成 2D 硬體加速沒被致能。
2. 也有可能是應用程式 Firefox 的問題。
3. 可能是 desktop environment (如 KDE、GNOME 或 Xfce 等...) 或是 toolkit 的問題。
4. 或是 X Window 系統本身的問題。
5. 當然也不排除其它沒列出來的原因。

驅動程式的問題

這是有可能的，舉例來說，有重灌過 Windows 的人可能會發現剛灌完的 Windows 雖然螢幕解析度不高，可能只有 800x600 但是用起來畫面卻會鈍鈍的。一旦驅動程式灌完，即使解析度調高用起來也不會有 lag 的現象。

應用程式 Firefox 的問題

沒記錯的話，曾經在 XP 下比較 Firefox 和 IE 7 捲動的流暢度，在 IE 下捲動網頁比 Firefox 流暢 (但就 JavaScript 而言，依據 CNET 的測試 IE 卻是最慢的)。但這也無可厚非，畢竟 IE 不像 Firefox 支援多種 W3C 的標準，要知道 W3C 所定的一些標準其實是很複雜的 (例如 CSS 和 DOM)，相較於 Firefox，IE 對於 W3C 標準的支援似乎就沒那麼好 (也不支援 SVG)，或許因此在設計上就簡化了許多。

X Window 系統本身的問題

提到 X Window 系統的問題，算得上是一個歷史的包袱。X Window 從 1984 年發展到現在已經將近 25 年了，當初設計時採用的主從式架構 (client-server architecture) 長久發展以來一直都沒有改變，這種架構雖然可以保有良好的網路通透性 (network transparency)，卻因為如此造成圖形上的效能低落，這也就是為什麼當初蘋果電腦決定不採用 X Window 而自行研發 Quartz 作為 Mac OS X 的 window server。Quartz 其中一位作者 Mike Paquette 說: 「一旦蘋果電腦將所有希望被支援的功能加入 X Window，它可能將不再像是一個 X Window 而且也不會和其它的 server 相容」*。由於 X Window 推出已經很久了，累積了許多為 X Window 開發的應用程式，這些程式都是建構在古老的 X Window 架構上，形成 X Window 在架構改善上的一大障礙，一旦 X Window 真的翻新了軟體架構，勢必會造成許多舊有應用程式因相容性的問題而無法執行。

很早之前 X Window 圖型效能不佳的問題就已經被提出來了，造成問題的潛在因素包括:

1. 當 X client 向 X server 發送同步化的請求時 (synchronized request)，client 將訊息發送出去後需等待 server 做出回應，這時 client 的執行就會 block 住，直到取得回應或 timeout 為止。從訊息發出直到取得回應這段時間叫做 round-trip delay time (即一趟訊息往返的時間)，round-trip delay time 對效能有重大的影響。除非 client 可以再開一個執行緒繼續執行下去，用類似這種方式暫時跳過等待的時間，不過這種方式會增加設計上的難度，此外若後續程式的執行與 server 傳回的回應有關，則 client 仍舊必需得到結果才能往下繼續執行。
2. 當 X client 與 X server 都在同一個 CPU 或同一個核心中執行時，系統需要額外的 context switch 才能在 client 與 server 之間輪流執行各別的程式碼。
3. X client 與 X server 都要對傳送的命令作格式化以及緩衝的處理，對於各種請求的回應也必需遵照 X Window 的通訊協定，造成經常性 CPU 資源的浪費 (overhead)。
4. 在一些具有快取 (cache) 機制的處理器中 (例如 ARM 9)，X client 與 X server 間的 context switch 會清除 (flush) 快取的內容，進一步降低執行效率。

X Window 相關後續發展

前面提到 5 點可能的問題中，第 4 點即 X Window 的問題應該算是比較嚴重且普遍存在的問題。至於其它，大部份是出自個人的懷疑，到底對效能的影響有多大可能還要很多時間去研究才能得知了。不過在網路上找到的，大部份都是在討論 X Window 架構對 GUI 的影響，所以我想這應該是目前最迫切的問題。

針對 X Window 的問題，目前所找到的兩個解決方法 Wayland 與 MicroXwin 是我個人認為比較有希望的。依我個人的了解 Wayland 是透過 DRI/DRI2 的方法，讓應用程式能夠直接取得 framebuffer 或是 offscreen pixmap 讓應用程式能夠直接在上面繪圖，因此等於是跳過了 X server 讓應用程式直接透過 kernel 存取繪圖裝置；至於 MicroXwin 所用的方法就是大家以前常提的: 「將 X server 搬進 kernel」，這麼一來不但可以改善 GUI 效能，也可以保持對既有應有程式的相容性。MicroXwin 或許可以在短時間內得到 GUI 效能的提升，不過長期而言或許 Wayland 才是真正的解決之道，因為大家都知道目前的 X.Org 已經是一個過於擁腫龐大的系統，而 client-server 架構也增加 X Window 程式設計上的困難與複雜度 *，程式可能會因此變得 buggy，所以走極簡路線的 Wayland 應該能大幅改善當前的情況。

MADtv 上的 Shakira

個人還滿喜歡聽西洋音樂的，mp3 裡面約有八成都是西洋音樂。在電腦桌前精神不振時，常會打開 Rhythmbox 找一些比較有節奏感或是能提神醒腦的歌曲，有時聽著聽著，耳機中又會傳來那高低起伏且唱腔獨特的嗓音，原來是 Shakira 的 Whenever, Wherever 又開始在播放了，Shakira 這種時而吭腔時而帶笑不時還穿插著泣音的獨特唱法，偶爾聽聽倒還滿提振精神的。不過聽了那麼多次，不免會好奇這首歌的 MV 究竟是怎麼一回事。於是就到 YouTube 搜尋了一下，不但找到了 Whenever, Wherever 的 英語版和西語版，還找到了一個頗令人噴飯的版本:

Shakira Parody

電腦真的夠快了嗎

現代電腦科技發展迅速，電腦的運算能力也愈來愈強大。如果按照摩爾定律的推論，IC 上可容納的電晶體數目，每隔約 18 個月便可以增加一倍，因而電腦的性能每隔 18 個月也會跟著增加一倍，那麼換句話說，電腦的性能就不只是呈現線性而是呈指數的速度在成長。聽過阿基米德故事的人都應該知道，這種指數的成長速度是相當驚人的，但是回過頭來仔細思考，摩爾定律的基礎是建構在 IC 上電晶體的數量，試想如果不斷地在一塊小小的 IC 晶片上塞進大量的電晶體，到最後會是什麼結果？摩爾定律的提出者，戈登．摩爾說:「任何指數函數一旦外推到一定程度都會遇到阻礙。物質由原子構成這一事實就是根本的局限所在。我們不可能做得更小了。」* 這一番話說明了摩爾定律最終還是會失效的，那麼當摩爾定律失效以後，電腦未來的發展該何去何從？

演算法的效率

曾聽過幾位寫程式的朋友告訴我:「現在電腦跑得這麼快，程式就算寫得不好、沒做最佳化 (optimization)，一樣還是可以跑得很快」類似這樣的話。的確，在許多情況下確實是如此，電腦的執行速度快到讓一些多餘程式碼所造成的延遲微小到無法被察覺，特別是一些比較簡單的小程式。不過有學過演算法的人應該會了解，在某些情況下如果程式沒有用對演算法，那麼不管電腦執行的速度再怎麼快，仍舊是杯水車薪，無法讓一個程式在合理的時間內執行完畢的。就舉我們常用的排序來說，以插入排序法排序 n 個項目平均大約需要做 n² 次比較，因此平均的時間複雜度 (time complexity) 為 O(n²) (見 big O notation)；而以快速排序法排序 n 個項目平均大約需要做 n log₂(n) 次比較，因此平均的時間複雜度為 O(n log₂(n))。相較於快速排序法，插入排序法是一種頗為直觀而且簡單的排序方式，對於比較沒有演算法及排序背景知識的程式設計師而言，他可能會直覺地實作出插入排序法來完成程式中排序的任務。當排序項目的數量 n 不大時，使用插入排序法來排序是沒有問題的，但是當 n 大於某數時 (視電腦的執行速度而定)，插入排序法的效能便開始有了戲劇性的轉變。

圖 1: n、n log2(n) 與 n2 之比較 (n 在 1 到 101 之間)。

n n2 (插入排序) n log2(n) (快速排序) 1 1 0 11 121 38.05 21 441 92.24 31 961 153.58 41 1681 219.66 51 2601 289.29 61 3721 361.77 71 5041 436.63 81 6561 513.53 91 8281 592.21 101 10201 672.48 表 1

為比較插入排序與快速排序，我們取樣一些數據製成表 1 並將對應的曲線繪製在圖 1 中，其中橫軸代表 n，縱軸代表比較的次數。由圖中我們可以看到插入排序法 (紅色) 隨著 n 值的遞增而快速地發散，而快速排序法 (綠色) 的發散速率則慢了許多，並且比較接近線性 (藍色) 的走向。由表中我們可以看出當 n = 11 時插入排序法所需要的比較次數約是快速排序法的 3 倍，然而當 n = 101 時所需要的比較次竟是快速排序法的 15 倍之多。如果我們把 n 的範圍再加大，如表 2 及圖 2 所示，我們可以看到更大的差距。當 n = 1001 時插入排序法所需要的比較次數將會是快速排序法的 100 倍左右，假設快速排序法排序 1001 項目所需的時間為 0.1 秒，那麼插入排序法排序 1001 項目將需要 10 秒鐘的時間。由此可知，在某些情況下演算法的不同或是程式設計上的不同，在程式執行的效率上將造成極大的差別。

圖 2: n、n log2(n) 與 n2 之比較 (n 在 1 到 1001 之間)。

n n2 (插入排序) n log2(n) (快速排序) 1 1 0 101 10201 672.48 201 40401 1537.86 301 90601 2478.32 401 160801 3467.63 501 251001 4493.3 601 361201 5547.96 701 491401 6626.74 801 641601 7726.17 901 811801 8843.66 1001 1002001 9977.19 表 2

演算法的極限

除了演算法的選擇會影響到程式的執行效率以外，仍有許多問題至今即使運用已知最快的演算法，當問題的 n 值較大時甚至連得到解答的希望都沒有。例如著名的旅行推銷員問題 (Traveling Salesman Problem, TSP):

有 n 個城市，一個推銷員要從其中某一個城市出發，並造訪所有的城市，再回到他出發的城市，在造訪的過程中行經的路線不能重覆，請問推銷員要如何造訪這些城市才能以最短的路線走完全程？

解決 TSP 其中的一個辦法是運用窮舉法，由於所有可能的路線線共有 (n－1)! 種排列方式，因此窮舉法的時間複雜度為 O(n!)，如果改用動態規劃 (Dynamic Programming)，我們可以將解題的時間複雜度降為 O(n²2ⁿ)，雖然比 O(n!) 好很多但是仍比之前提到的插入排序法 O(n²) 差上許多，只要 n 值稍微大一點，一般的電腦便無法應付如此龐大的計算量，所以 TSP 也被歸類為 NP-hard 問題。O(n²2ⁿ) 的複雜度甚至比前面阿基米德故事裡提到的米粒數量 O(2ⁿ) 發散得還要快，只不過一個指的是時間複雜度而另一個指的是米粒的數量，也算是另一種空間複雜度 (space complexity) 吧。以目前的計算機科技而言，或許還能應付多項式時間 (polynomial time) O(n^k) 以內的演算法，其中 k 為一大於或等於 2 的常數，但是對於複雜度的等級大於多項式時間再加上一個大一點的 n 則毫無希望。

計算機的發展

綜合以上的論述，我們可以看到以半導體元件為基礎的計算機，在許多應用上仍有很大的限制。從 BOINC 的項目中我們就可以看到許多這樣的應用，這些項目的共同點就是都需要進行一些計算量龐大的工作。藉由 BOINC 這個分散式的平台，希望能夠募集世界各地自願者所提供的電腦運算能力，來執行各項大計算量的研究計畫。除了像 BOINC 透過平行處理的技術來暫緩半導體計算機計算能力的不足，發展其它非傳統式計算機 (unconventional computer) 也將成為無可避免的趨勢，因為摩爾定律終將失效，而始終有電腦無法決解的問題需要被解決。

開始使用 Ubuntu

大約是最近這一兩年開始，開始大量接觸 Linux 的東西，雖然之前也曾嚐試過 Red Hat Linux 但是也荒廢好久沒有碰了。後來跟前一家公司 ADT 的品保經理 Eric 討論公司內部 wiki 的事情時，才知道他也有在玩 Linux，他說他玩了許多 Linux 的發行套件 (distribution) 像是 Fedora、SuSE 及 Ubuntu 等…，試過了這些套件後他發現 Ubuntu 是他認為最容易上手的，因此推薦給我。剛開始我聽說時雖然有想裝的意圖，但是因為工作繁忙而作罷。結果某一個週休，我在上 YouTube 時心血來潮就在搜尋欄打 Ubuntu 搜尋，結果讓我找到這個

WINDOWS VISTA AERO VS LINUX UBUNTU BERYL


是在比較 Vista 和 Ubuntu 的桌面。看過了之後讓我感到有點驚喜，原來現在的 Linux 的桌面已經超越了 Vista，能做出這麼華麗的桌面特效…。Linux 已不是我印象中的那樣生硬及單調，而是慢慢朝 Mac OS X 的方向邁進，且相較於 Vista 而言 Ubuntu 佔用的資源也比較少，稍微舊一點的機器也跑得動，但不論是 Vista 或是 Ubuntu，都需要有硬體加速的支援，否則桌面特效不是跑起來慢到無法使用，不然就是沒硬體跟本沒就辦法跑。

事隔不到一年，美國陷入金融風暴危機，ADT 生意開始走下坡，因此上班時空閒的時間也變多了，在這個機緣之下，我開始試用 Ubuntu，看看能不能把桌面特效弄出來。後來在網路上找到了一個叫做 Wubi 的安裝程式，透過 Wubi 就可以在 Windows 下，如同一般安裝程式的方式安裝 Ubuntu，不需重灌系統或重新分割硬碟。但是家中的電腦配備太差了，記憶體和硬碟空間都不足，而且也沒有硬體加速卡，因此想到即然 ADT 有兩台電腦，何不拿一台來灌 Ubuntu，ADT 的電腦雖然較舊但是記憶體和硬碟空間都還能符合 Ubuntu 的需求，這樣一來也不需要再使用 Wubi 了，且 ext3 應該要比 Wubi 的檔案系統來的有效率。打開 ADT 的桌電查看一下裡面居然有一塊 NVidia 的加速卡，真是一個重大的發現，這代表離目標又更進一步了。跟著 Ubuntu 安裝光碟的導引，系統就在 ADT 那台桌電上裝完了，但是卻沒有看到期待中的桌面特效，經過一番摸索，原來是外觀設定裡面的視覺效果沒設好，

照理說，只要在視覺效果的對話方塊中選擇第二個或第三個選項桌面特效就會被打開了，但每次一選系統又會自動跳回第一個選項。會造成這樣的結果，是因為硬體加速沒被驅動的關係，這可是一個棘手的問題，接下來的整整一個星期都在為顯示卡的驅動努力，中間的過程就不再贅述…最後好不容易總算是被我弄出來了，看到桌面特效的感覺真棒，再裝一個 CCSM 還可以作更多更炫的設定，坐在我後面的 Wayne 經過幾次看到我的畫一直都是特效，最後還忍不住問：「你是不是玩上癮了」，沒錯正是如此，特效如此之多，一時之間要全部玩遍也不是件容易的事。就因為 Eric 的一句話，看了 YouTube 的影片，而使我開始想玩特效，灌了 Ubuntu，到最後連 XP 都沒沒什麼在用了，這大概也算之前始料未及的一種意外吧。

Wiki & Blog

受到最近景氣衝擊的影響，公司 ADT 的生意真是愈來愈差了。在連續 idle 了兩個多月了以後，終於被 ADT 給資遣了。

在 idle 的這兩個多月期間，每天幾乎都在 ADT 內部的 wiki 還有 Wikipedia 之間來來去去，不時會在上面增加及修改內容，然後不斷地檢查我的 watchlist 看之前在上面的編輯造成了些什麼回應。wiki 這種互動式的編輯方式，其實是十分有趣的，但是 Wikipedia 基於一個百科全書，不得不對使用者所編輯的內容有所規範，以維持其應有的品質，例如：使用者所編輯的內容必需要客觀且能夠被驗證的 (Verifiability)、編輯的內容必需是非原創研究，等…。因此有些內容是不適合放在 Wikipedia 的 (像是個的人見解與言論)。

然而 Wikipedia 背後的 wiki 引擎是 MediaWiki，而 MediaWiki 本身又是自由軟體，所以任何人只要有能力都可以自己架設一個 wiki 並在上面發表文章而不需受到 Wikipedia 的種種規範。事實上，網路上早已充斥著許多個人的或是由公司或組織所建立的 wiki (見 Sites using MediaWiki)，在自行架設的 wiki 上可以自己定義網站規範，分享任何形式的文章或媒體，然而，在 wiki 背後還是得花一些心思去經營網站及管理各種站務，這將是需要足夠的時間來完成的。

相較於自行架設 wiki，建立 blog 似乎顯得簡單了許多，現成的許多網誌服務，都可以免費申請，而且有許多內建的小工具，讓知識分享這件事變得容易上手許多，況且目前處於待業的狀態，隨時都有可能接到上工的通知，因此還是先建一個 blog 來寫寫東西，至於自行架設 wiki 的那件事 take it easy！