觀察不同的loop實作 - C版本

loop是每個程式設計師每天都會寫上好幾遍的program construct(好吧，Lisp programmer是例外 :P)，loop也是structured programming的基本要素之一，現今的計算機都是遵循著von Neumann架構，所以使用loop是相當地貼近機器、有效率。有趣的是，每個程式語言都往往有數種不同的loop方式，並且不同的程式語言對於loop的設計也往往不同，這篇文章以C語言的幾種loop方式作為討論對象，希望促使自己思考不同的loop實作背後的考量。有機會再針對C++/Python/Lisp等語言作討論。

首先，先來看看C語言中最基本常用的loop - for loop：

1. #include <stdio.h>
3. void foo(void)
4. {
5.     printf("do something\n");
6. }
8. int main(void)
9. {
10.     int i = 0;
12.     for (i = 0; i < 10 ; ++i) {
13.         foo();
14.     }  
15. }  

C語言或許是高階語言中最接近von Neumann架構的一種，所以其內建的for loop機制幾乎只是薄薄的一層機器指令的包裝，在接近機器層面的程式碼，這樣的作法幾乎可以肯定帶來最高效的對應。現在我們來想想一個問題：如何找出一個陣列中的最大值？很簡單，程式碼大概會像這樣：

1. #include <stdio.h>
3. int main(void)
4. {  
5.     int i = 0;
6.     int max = 0;
7.     int arr[] = {8, -9, 10, 11, 99, 100, 23};
9.     max = arr[0];
10.     for (i = 1; i < sizeof(arr)/sizeof(arr[0]) ; ++i) {
11.         if (max < arr[i]) { max = arr[i]; }
12.     }
14.     printf("max = %d\n", max);
15. }

問這麼簡單的問題作什麼呢？別急，現在再來解一個問題：如何將每一個陣列中的元素都加上2？又是簡單的問題，程式碼瞬間就可以寫好：

1. int main(void)
2. {  
3.     int i = 0;
4.     int arr[] = {8, -9, 10, 11, 99, 100, 23};
6.     for (i = 0; i < sizeof(arr)/sizeof(arr[0]) ; ++i) {
7.         arr[i] += 2;
8.     }
9. }

你或許開始不耐煩了，簡單的問題居然問了兩題？太無聊了吧？嘿，很多學問就是從一般人習以為常、無法察覺的小細節開始的。讓我們開始觀察這兩個簡單的問題的"共同"與"相異"的地方吧。共同的地方在於：它們都有類似的流程結構：

for each element in some container:

    do something with the element

但是C語言內建的for loop卻沒有提供some container與do something with the element的概念，所以一旦這兩個東西發生了變化，程式設計師就必須再手工寫一遍for loop。所以問題轉變為：要如何提供一個機制，讓程式設計師即使改變了資料結構或對每一個結構中的元素的處理方式時，仍能保持for loop不需更改？


讓我們先從簡單的開始：當元素都只在陣列中，但對元素的處理方式不同，要如何不改變for loop呢？在C語言中，慣用的手法有兩種，第一種是透過callback function：

1. #include <stdio.h>
3. typedef void (*callback)(void *e, void *priv);
5. void for_each(void *arr, int e_size, int arr_size, callback do_something, void *priv)
6. {
7.     int i = 0;
8.     char *arr_imp = arr;
10.     for (;i < arr_size; ++i) {
11.         do_something((arr_imp + (e_size*i)), priv);
12.     }  
13. }
15. void swap_max(void *e, void *priv)
16. {  
17.     int *max = priv;
18.     int *ele = e;
20.     if (*max < *ele) { *max = *ele; }
21. }
23. void plus_two(void *e, void *priv)
24. {  
25.     *(int *)e += 2;
26. }
28. void print(void *e, void *priv)
29. {  
30.     printf("%d ", *(int *)e);
31. }
33. int main(void)
34. {  
35.     int arr[] = {8, -9, 10, 11, 99, 100, 23};
36.     int max = 0;
38.     // find max
39.     max = arr[0];
40.     for_each(arr, sizeof(arr[0]), sizeof(arr)/sizeof(arr[0]), swap_max, &max);
41.     printf("max = %d\n", max);
43.     // plus 2 to every element
44.     for_each(arr, sizeof(arr[0]), sizeof(arr)/sizeof(arr[0]), print, NULL);
45.     printf("\n");
46.     for_each(arr, sizeof(arr[0]), sizeof(arr)/sizeof(arr[0]), plus_two, NULL);
47.     for_each(arr, sizeof(arr[0]), sizeof(arr)/sizeof(arr[0]), print, NULL);
48.     printf("\n");
49. }

注意到for_each的宣告與實作是完全"只依賴於元素是位於陣列中"這個事實，接著會迭代依次對每個陣列元素do_something，而do_something是易變化的部份，所以交由使用者自行定義，do_something運作時要怎樣才能正常呢？觀察之前提到的兩個問題：為每個元素加上2，只需知道目前元素的值就好；但是找最大值則需知道目前元素的值與目前最大值才行，所以我們多加了一個priv的欄位，callback介面便成為：

typedef void (*callback)(void *e, void *priv);


void *e參數是for_each給callback的，而void *priv則是使用者自己的資訊，可以在for_each運行時改變狀態以進行不同判斷。這種設計方式給了我們設計介面時的一個方向：將不變的抽取出來，將會易變的提供出介面供外部使用者修改。如果這件事可以確實作的好，自然就會符合所謂的模組化設計。著名軟體開發先驅Jim Coplien在其博士論文中花了很大篇幅介紹如何進行＂共通性/相異性＂的分析與設計，是很好的參考資料。

(練習題：如果想要將"元素是位於陣列中"這個假設從for_each去除，需要如何修改for_each的實作？提示：引入iterator以隔離資料結構與演算法")

第二種抽象化loop的手法則是透過macro。手法如下：

1. #include <stdio.h>
3. #define for_each(cur, arr, size) cur = &arr[0]; for (int i = 0; i < size ; ++i, cur = &arr[i])
5. int main(void)
6. {
7.     int arr[] = {8, -9, 10, 11, 99, 100, 23};
8.     int *cur = NULL;
9.     int max = 0;
11.     // find max
12.     max = arr[0];
13.     for_each(cur, arr, sizeof(arr)/sizeof(arr[0])) {
14.         if (max < *cur) { max = *cur; }
15.     }  
16.     printf("max = %d\n", max);
18.     // plus two to every element
19.     for_each(cur, arr, sizeof(arr)/sizeof(arr[0])) {
20.         printf("%d ", *cur);
21.     }  
22.     printf("\n");
23.     for_each(cur, arr, sizeof(arr)/sizeof(arr[0])) {
24.         *cur += 2;
25.     }  
26.     for_each(cur, arr, sizeof(arr)/sizeof(arr[0])) {
27.         printf("%d ", *cur);
28.     }  
29.     printf("\n");
30. }

使用macro的好處是可以避免callback function所帶來的額外開銷，所以這種手法在Linux kernel中隨處可見，幾乎Linux kernel中的每個資料結構都有一份for_each，但callback function的方式可以有更多其他好處：

1. 可以放在.c中。我們這邊處理的是for loop的化簡，但如果你要提供的API是不想公開內部實作的話，放在.c中，然後開出可改變的部份給使用者定義，才是比較好的選擇。
2. 可以避免複雜的macro實作。這邊只實作了for loop，但其實該macro實作是有一些問題的(練習題：什麼情況下會有問題？)，而更複雜的API如果用macro實作，在除錯上會較為不易，畢竟大部份的debugger都無法觀察preprocess時的錯誤。
3. macro會使得程式碼膨脹。一旦程式碼膨脹，造成cache miss增加，很可能將callback的開銷打平，並且如果產品是用在小型的嵌入式系統，大量的macro很可能造成需要更大的flash size，增加...嗯，製造成本。

為了讓for loop可以變得通用，所以需要付出一點代價，這個代價不只出現在代碼的效能損失，也出現在觀察共通概念與流程的時間，也出現在使用何種手法抽取出共通程式碼的設計上(當然，這個例子對絕大多數的程式設計師都微乎其微，而且可以藉由學習以縮短分析與設計時間)，這些代價在開發時是否值得？端看情況而定。尤其當愈複雜的概念與流程要變得通用時，付出的代價會更高(試試看讓binary search tree的操作通用化)，所以這時越要思考是否划算。概念或程式碼有所重複不總是罪惡，有時僅僅是工程上的設計選擇(不過我們要先知道有哪些選擇，對吧？)。

當然啦，很多時候我們都是在開發了一段時間後，發現了一些共同的流程、概念，然後才進行整理，而無法在事前預知。雖然loop的抽象化手法在coding上是很簡單的一件事情，但唯有當我們了解不同的手法的優缺點後，面對我們自身更複雜的應用時才有可能作出有把握的選擇。Keep walking!!