how to write an efficient code

之前寫code的時候, 遇到效能瓶頸的時候往往都訴求"multi-thread"的一個方式, 無論是自己寫pthread in POSIX或是 CreateThread in win32或者使用openmp. 但是最近才發現其實除了這些以外, 還得注意自己的coding style. 最是發現基本的要求就是loop optimization.

有一個名詞叫做"嘗試"

距離上一篇文章差不多一年了; 這一年來真的真的發生了很多事情.

在記錄過去一年所發生的事情同時, 也感謝在這些事件當中幫助過我的人; 無論你是我認識的朋友或是不認識的陌生人. :)

1. 人與人之間的相處: 有一個長輩對我很好, 無論是學業或是生活上的問題都會幫忙解決. 不過也可能是因為彼此太熟悉了, 漸漸讓我摸不清楚什麼叫做"分寸". 沒錯, 我變得很傲慢!!! 我記得有一次長輩在教導新人的時候, 我就插嘴進去; 完全不理會長輩. 大概是這件事情埋下了之後的導火線吧. 直到有一次我收到長輩寄過來的信, 信裡面提到"為學之道". 像我目前的作為就是"自以為是，未待持滿而發之; 自以為滿, 未待持滿而拒叩之; 而為學之道如叩鐘，如發弓，如田稼；叩之以待其鳴，持滿以發其弓，斂之以常其熟". 希望我這一輩子都記得這句話. 而得到這句話的後果, 就是跟人的相處上漸漸變的有點距離; 有些人希望可以多認識他/她, 但是又怕在說話上傷到對方, 然後就歷史再度重演. 不過為了符合這篇文章的主旨, 我還是得說服自己多多嘗試.


2. 出國: 自從三年前分手過後(滿三週年了, 真開心?), 就漸漸對一些新鮮事不感興趣了. 整天腦子裡面想的都是"工作, 工作, 還是工作". 有的時候一天會不停的檢查有沒有新信, 有沒有新的計畫. 可以說是忙到都忘了我是誰了. 當然, 也沒想過要出國玩. 因為工作上的關係, 有了一次機會去美國出差, 雖然出差跟旅行差不多, 不過已經忘了嚐鮮的我, 自然而然的就不想到處走走. 現在想想還真的不值得!!! 如果還有機會出國(差)的話, 一定要做些不會讓自己後悔的事情, 那就是"嘗試". 當然在旅途中, 還是發生了一些窘事. 也感謝一些朋友以及陌生人的相助; 讓我趕飛機的途中(因為沒帶台幣)還可以插隊買高鐵車票; 讓我在聽不懂老外問的問題的時候, 熱心的把問題放慢在說一次, 並且幫我cover掉一些"難以回答"的問題. 喔喔, 還有, 並不昰每個Queen U.都是英國那間Queen Mary U.; 還有不是毎個姓金(Kim)都從韓國來; 最後還有就是, 新加坡人很愛台灣. :)


3. 車子被偷: 08/09 因為大學同學聚會所以開車南下嘉義. 會開車過去的原因只是因為聚餐之後還有跟比較熟的一些同學們續攤; 也不確定在地的交通工具夠不夠, 於是就開車過去. 但是卻忘了那台車可是偷兒眼中的肥羊阿!! 才買不到三年的車就這樣被牽走了!!! 不過在被偷之前, 真的有很多預兆,,,,,,要南下嘉義前, 我爸還問我說要不要開他的車過去, 新車放家裡比較安全, 最近竊賊很猖狂; 在載完大學同學到嘉義聚餐地點的時候, 我還跟他說我爸提醒我最近竊賊很猖狂, 停車要小心; 停完車之後, 我還檢查好幾次車門有沒有鎖好; 在吃飯的過程中我還預感到車子會不會被偷, 但是我沒出來查看; 總總的因素都是預感....然後就發生了!! 這跟我說了一件事情, 就是人最忌"忘形", 而忽略了所處在身旁的危險. 也因為這件事情, 更看透了身旁的一些人. 只是要看透這些人的代價真的不小. 現在想想, 我好像真的很容易破財...不過既然會破財, 倒不如"嘗試"把錢拿去做善事, 至少是幫到需要的人而不是偷兒!!!

這三點算是今年的年度大事; 希望可以當作自己的一個警惕; 當迷失或是有小成就的時候再回來看這歷史故事, 借由警惕提醒自己 never do it again.

積極只要多一點，後悔就會少一點

這個就是我活了20多年所得到的心得.

clustering on thousands of songs ?

最近在做自己的research...然後要把數千首的音樂做分群(clustering),,,
input data是一堆mp3的音樂資料(每首約30秒), 透過imdct擷取之後可得到每秒38個frame的imdct值.
目前clustering的作法是以frame為單位做分群,,,
clustering的作法是用cast的作法....
大概評估了一下記憶體的使用量....3k * 30 * 38 * dimensions= 36M * dimensions
如果我們要建一個distance matrix, 則要 n^2 / 2 的memory size, n為matrix的dimension, 以數千首音樂為例, n = 36M.
這個需求量遠大於目前機器可以容納的physical memory 的大小, 所以透過disk的方式記錄distance matrix; 目前的話一個block 約 64M.
然後如果目前cache buffer裡面沒有這個similarity的值的話, 就更新buffer的值, 透過fully buffer I/O.
更進階的做法可以模擬OS的page fault algorithm, 來計算哪個page要被swap出去, 整個還蠻有趣的.
只是分群真的分好久....

Crawling Data in Amazon.com

最近因為research會用到music data，所以就利用Amazon提供的一個Web services(AWS) 。
第一步當然就先註冊一個userid，然後再看Amazon提供的programmer guide就可以抓data了。
不過有幾點事情比較有趣...主要的原因是因為需要music的content data，而Amazon所能提供的只有大概30秒左右的sample。當然，我還是把sample的曲目爬下來了...Orz(不知道有沒有違反著作權..不過我也只是做研究沒有商業用途)。
不過有趣的地方在於要找到某個mp3的原始url是一個耗時的地方(1. 從amazon抓html本身就耗時了； 2.要parse html找到正確的mp3 location也是個耗時的地方)，所以就模擬了HTTP 1.1的作法...XD
先把系統預設(daemon thread)有10個可以跑的thread，然後每當要抓mp3 data的時候就叫醒一個thread(稱為mp3 thread)。 mp3thread只有一個動作就是抓mp3的url， 再利用stream的方式把mp3 download，然後繼續回去睡覺。daemon thread如果發現目前10個mp3thread都有再執行的話，就等待直到有其他mp3thread可以被使用為止。概念很簡單，不過卻是一個很基本的利用java做synchronize的問題。
不過mp3thread太多就會被Amazon reject掉，因為太短時間內有太多的request了..Orz

mail server被駭

幾天前學長告知才知道mail server企圖攻擊別人的server...
然後檢查底下的log檔(主要在/var/log/secure, /var/log/messages)才知道別人利用server裡面既有的user account以及密碼進行登入, 主要原因就是密碼太過於簡單.
所以就做了底下處理
1. 允許登入SSH的帳號, 只允許一個非root的帳號登入(參考FreeBSD-安裝到SSH遠端登入)
2. 全面修改過於簡單的密碼

雖然這樣做並不是最好...不過我覺得要破就不容易了...

A performance comparison between openmp and traditional multi-thread

上學期修了一堂網路的課，其中一個作業要拿目前慢慢興起的openMP與傳統multi-thread的作法做個效能上的評比。所以就把結果拿上blog給需要的人參考...如果有任何問題，歡迎底下留言or mail to me. but請勿抄襲!!
-----------------
Requirement and Architecture:
此實驗主要針對web上的application做效能上的評比，我們在這是做個file transfer protocol(簡稱FTP)。我們實做了RFC959底下幾個指令：USER、CWD(current work directory)、CDUP(up folder)、QUIT(exit)、PORT(data port)、TYPE(representation type)、RETR(retrieval file)、STOR(store)、PWD(parent work directory)、LIST(list current directory)、STAT(server status) 、SYST(server system)，並成功的測試使用FileZilla Client可以自由的連線操作。系統架構方面實作了三種模式: single-thread, multi-thread, single-thread with openMP, 三種模式的FSM參考下圖。


Testing program:
在測試方面，為了同時模擬多人連線的狀態，我們開發了一個可以同時fork出多個Process送出定義好的ftp指令。我們在這邊所用到Client端的ftp軟體是Windows底下內建的FTP Command，Testing的FSM可以參考下圖:


Experiment:
硬體環境
Server: Intel(R) Core(TM)2 Duo CPU 1.80GHz 1GB RAM
Client: (Intel(R) Pentium(R) 4 CPU 3.00GHz 1GB RAM)*2
開發環境
Microsoft Visual Studio 2005 C++
Windows XP SP2

三個不同的應用程式作下列的實驗比較

1. 調整不同的緩衝區大小

2.調整不同的使用者個數

3.調整不同的使用者進入時間

調整不同的緩衝區大小:

在這個實驗的部份，我們主要是利用不同緩衝區的大小來測試系統的反應能力；這個實驗的目的在於如果伺服器反應時間越快，代表可以處理越小的緩衝區；相對的，伺服器的反應時間慢的話，代表只能處理大的緩衝區。在實驗參數方面，User=150個process(每台測試電腦150個process)，delay time是350ms；(0.35 secs)，每個process對伺服器的指令為：60次的LIST和一個8M的影像檔。從下圖的實驗可以發現，Multi與OpenMP都能夠處理緩衝區為30的狀況； 但是Single只能處理緩衝區為50的情況。針對Multi與OpenMP這兩種方法，我們可以發現Multi的時間花費比OpenMP的還要少；可以大概推測Multi是有一個額外的執行緒處理目前存在緩衝區的Client，但是OpenMP則要對所有存放在等待佇列的元素用多個執行緒的方式同步處理。等到處理結束時，才會處理存放在緩衝區的Client；所以Multi的處理時間會比OpenMP的少。

調整不同的使用者個數:

在這個實驗的部份，我們主要測試系統可以處理使用者的最大上限(Upper bound)；一個強固性高的系統應該能夠允許最多使用者連到主機，並提供服務；所以這個實驗主要在測試哪種架構有最好的強固性。實驗參數方面，我們設定緩衝區大小(Buffersize)設為100，delay time為50ms(0.05 secs)。每個process對伺服器的指令為：2次的LIST。由底下的實驗數據可以顯示出Multi可以達到最高上限User=450的狀況下，整個processed time還能維持30秒以內；OpenMP則是對多只能處理User=400，但是processed time維持低於30秒以內；Single的方式只能處理User=150，但是整個時間需要134秒左右。

調整不同的使用者進入時間:

在這個實驗的部份，我們主要測試系統可以接受測試端多少delay time；越穩定的系統架構，所用的delay time要越低。這代表可以接受多個同時連線近來的使用者。在實驗參數方面，我們將緩衝區大小設為100，User=150；每個process對伺服器的指令為：60次的LIST和一個8M的影像檔。在下圖實驗我們可以發現Multi與OpenMP都可以接受每個process有delay time=200ms(0.2 secs)的效能；但是Multi所展現的成果最好，約134秒；而Single只能接受每個process以delay time=350ms(0.35 secs)的連線速度；有此可知Multi與OpenMP的效能差異不大，都比Single的效能好。