Visual C++ 2010 Express 使用

這篇文章零碎紀錄了一些初學 Visual C++ 2010 Express 的事項。

Q: IDE 的選單變的好簡潔，一些項目都不見了，要怎麼找出來?
A: 使用 Tools->Settings->Expert Settings ，從預設的 Basic Settings 換成 Expert Settings。

Q: 我沒有辦法直接設定全域的路徑。在 Tools->Options->Projects and Solutions->VC++ Directories 中無法編輯。
A: Visual C++ 2010 做了一些更動，必須要在Property Manager中修改，詳情請參考 VS Project Team Blog 的文章。

Q: 哪邊可以找到 IDE 的配色
A: 推薦 Studio Styles。我是選用 Son-of-obsidian 這個主題。

加減乘除需多久? -- 估計C語言中基本運算所需的時間

隨著個人電腦的時脈不斷增加，同一個程式的執行速度也越來越快，但是你可有估計過，在現今 2GHz 的 CPU 上，執行一個C語言的加法指令要花多少時間? 而乘法、除法要花多少時間呢?

在 Jon Bentley 的經典著作 Programming Pearls 中，他給了一個範例程式 timemod.c (註1) 來估計計算所需的時間成本。他的方法是跑一個雙層 for 迴圈，在裡面執行各種運算，並計算所花費的時間。

我以一台2009年的個人電腦來做實驗，

CPU為 Intel Core 2 Quad Q8200，時脈為 2.33GHz，Cache大小如下:

  L1 Data Cache = 4*32 KBytes

  L1 Inst. Cache = 4*32 KBytes

  L2 Cache=2048 KBytes*2

編譯器為Visual C++ 2010 Express，Optimization選項全部關掉。

以下為列出各種運算的執行時間，單位均是奈秒(nanosecond):

C Time Cost Model, n=5000

Integer Arithmetic (n=5000)

 {}                    44    44    45    44    45     1.8

 k++                   60    59    57    55    57     2.3

 k = i + j             65    65    65    65    65     2.6

 k = i - j             65    65    65    65    65     2.6

 k = i * j             64    65    65    65    64     2.6

 k = i / j            106   102   100   100    91     4.0

 k = i % j            114   101   100   100   100     4.1

 k = i & j             65    65    65    64    65     2.6

 k = i | j             65    65    65    65    64     2.6

首先看整數運算，先看最上面的藍色底色部分，{}是指兩層空迴圈所消耗的時間。前面五個數字是執行n^2=25000000次花的時間(milliseconds)，一共執行五次，最後面的數字是統計這五次執行總共花費的時間，計算每次迴圈內部所花的時間(nanoseconds)。

第二行是在迴圈中放入單一的指令 k++，由最後的數字可知迴圈內部花費了 2.3-1.8 = 0.5 nanoseconds(ns)。相較於 Bentley 的結果是45倍的速度!

接下來是加法和減法，一個指令花費約 0.8ns。令我有點驚訝的是乘法和加法一樣快。至於除法也很快，一個的花費是 2.2ns，不過是加法的 2.75 倍而已。取餘數和除法幾乎相同。

Floating Point Arithmetic (n=5000)

 fj=j;                 87    87    88    87    89     3.5

 fj=j; fk = fi + fj;   87    86    86    86    86     3.4

 fj=j; fk = fi - fj;   87    86    86    86    86     3.4

 fj=j; fk = fi * fj;   88    87    88    88    88     3.5

 fj=j; fk = fi / fj;  216   215   215   215   215     8.6

浮點數加、減、乘法花費 1.6ns。

Array Operations (n=5000)

 k = i + j             65    65    65    64    64     2.6

 k = x[i] + j          75    75    76    75    75     3.0

 k = i + x[j]          75    75    76    75    76     3.0

 k = x[i] + x[j]       88    86    86    86    86     3.5

Comparisons (n=5000)

 if (i < j) k++        70    70    70    70    70     2.8

 if (x[i] < x[j]) k++  86    86    75    96    86     3.4

原本以為 if 很慢，沒想到只花了 2.8-2.3 = 0.5 ns。

Array Comparisons and Swaps (n=5000)

 k = (x[i]<x[k]) ? -1:1  119   120   119   120   119  4.8

 k = intcmp(x+i, x+j)    141   140   140   140   140  5.6

 swapmac(i, j)           131   131   131   131   131  5.2

 swapfunc(i, j)          224   226   224   217   231  9.0

Max Function, Macro and Inline (n=5000)

 k = (i > j) ? i : j   91    92    92    93    92     3.7

 k = maxmac(i, j)      97    97    97    97    97     3.9

 k = maxfunc(i, j)    184   185   185   185   185     7.4

Math Functions (n=1000)

 fk = j+fi;             3     2     2     3     3     2.6

 k = rand();           27    27    27    27    27    27.0

 fk = sqrt(j+fi)       24    23    23    24    24    23.6

 fk = sin(j+fi)        44    44    44    44    44    44.0

 fk = sinh(j+fi)      475   476   475   474   475   475.0

 fk = asin(j+fi)       60    60    60    60    60    60.0

 fk = cos(j+fi)        44    44    45    44    45    44.4

 fk = tan(j+fi)        56    59    55    56    56    56.4

Memory Allocation (n=500)

 free(malloc(4000));    85    83    85    84    85   337.6
 free(malloc(16000));   83    83    83    82    83   331.2
 free(malloc(64000));   97    97    98    97    96   388.0
 free(malloc(128000));  94    95    94    94    93   376.0
Secs: 18.17

記憶體配置花費的時間和大小有關，在16KBytes以下需要花費約340ns，在128KBytes左右增加為380ns。

參考資料

[1] 關於此程式的詳細說明，請見 Programming Pearls 的附錄3

推薦 Linux入門書籍 -- Linux kernel in a nutshell

有興趣學習Linux的朋友，推廌可以從"Linux kernel in a nutshell"(註1)這本書開始看。無須大量基本知識，只需要基本的指令操作就可以開始動手編譯、設定kernel。而且還不到200頁，很快就能夠看完。

不過我一開始遇到一點麻煩。由於書中使用的kernel版本為2.6.18，所以我去找了Ubuntu 6.10(2006年10月發行的版本)，安裝好了之後發現沒辦法編譯程式，理由是沒有安裝libc6-dev套件。
嘗試使用下面的指令安裝
$ sudo apt-get install libc6-dev

但是套件已經找不到了，就錯誤訊息來看，我認為是此版本的套件更新服務已經終止。到wikipedia查了一下之後得到確認(註2)。原來ubuntu對於每個版本的支援期間才約兩年而已。不過其中有特別為伺服器設計的Long Term Support (LTS)版本，像6.06, 8.04, 10.04這三個，就有約五年的更新支援。
所以我有兩個選擇，一個是採用6.06，另一個是改用最新的版本10.10。

好，實際跑跑看。我使用VirtualBox來建立虛擬硬碟，編譯kernel 2.6.35-2在我的Intel Q8400上花了約40分鐘。Try it yourself!

參考資料
[1] 此書可由作者 Greg Kroah-Hartman 的網頁下載
[2] 請參見Wikipedia:Ubuntu的發行版本

翟本喬談雲端運算

雲端運算喊得很熱，不過我是看了翟本喬在COSCUP 2010的演講才清楚甚麼叫雲端運算
他提到與其人云亦云，不如看看NIST(美國國家標準暨技術研究院)的定義吧
http://csrc.nist.gov/groups/SNS/cloud-computing/
事實上文件中也提到雲端計算的定義隨時再改進，目前的版本是第15版，2009年所制定。

簡單的說，雲端計算是一種按使用量計費的服務，而可使用的資源包含網路頻寬、磁碟空間、記憶體、應用軟體等等。一個服務要稱得上雲端必須具備以下條件:
五種特徵

1. On-demand self-service - 使用者要使用服務時可自行索取，無須人力協調(像自助餐)
2. Broad network access - 可使用各式網路存取(如PC、手機、iPad等等)
3. Resource pooling - 服務提供者的資源可分散世界各地，而使用者無須知道服務所發生的地點
4. Rapid elasticity - 使用者能快速地取得服務和停止服務
5. Measured Service - 可量化資源的使用量 (當然，這是計算價錢的基礎)

限制Windows程式的記憶體使用量

和朋友討論到，在windows下如何限制一個程式的記憶體使用量，以避免佔用過多的系統資源。

其中一個解法為使用 SetProcessWorkingSetSize()，最簡單的情況下只需要三行程式:

int pid = GetCurrentProcessId();
HANDLE hProcess = OpenProcess(PROCESS_SET_QUOTA, FALSE, pid);
SetProcessWorkingSetSize(hProcess, minMemBytes, maxMemBytes);

不過實際執行程式會發現，只要記憶體還算充足，程式還是能獲得超過上限的記憶體。在我的4GB電腦上，大概可以使用到1.8G的記憶體，才會無法配置新的記憶體。

加快遞迴函數的計算

演算法中有一個簡單但是實用的技巧叫 memoization，可用於加快遞迴函數的計算，基本的想法就是把計算過的值儲存起來，並在呼叫前檢查是否已經計算過。

比如說我們要計算Fibonacci數列的值，公式為

F(0) = 0

F(1) = 1

F(n) = F(n-1), F(n-2)

用C++來實作並配合memoization的話程式如下

int fibonacci(int n)
{
    if (n<2)
        return n;
    static map<int,int> mymap;
    map<int,int>::iterator it;
    it = mymap.find(n);
    if (it==mymap.end())
    {
        int f = fibonacci(n-1) + fibonacci(n-2);
        mymap[n] = f;
        return f;
    }
    else
        return it->second;
} 

主要的概念在於使用 map 來儲存計算過的 f(n)。

上述的方法需要自己在程式中檢查傳入的參數是否有計算過，
然而人是懶惰的，在某些程式語言中可以將一個函數直接"升級"，
獲得memoization的能力。
比如說下面是ypcat提供的python的範例

def memoize(f, cache={}):
  def g(*args):
    key = tuple(args)
    if key not in cache:
      cache[key] = f(*args)
    return cache[key]
  return g

def fib(n):
  return n if n<2 else fib(n-1)+fib(n-2)

fib = memoize(fib)
print fib(300) 

比C++更方便的地方在於使用了一個函數 memoize 來包裝遞迴函數，執行的時候還可以把 fib() 直接替換為包裝過的函數。

Python, C#, Java, Lisp 等支援 first-class function 的語言都能達成以上功能，
那C++有沒有辦法自動memoization呢? 我目前還不確定。