Sequence Point

Ref: http://blog.tinlans.org/2010/08/06/sequence-point/

這個名詞就算是國內做 compiler 的實驗室成員可能也未必聽過， 畢竟國內沒什麼教授有種去帶領自己的團隊寫一套新的 compiler； 這原因除了短視近利等心理因素外， 也還牽涉到不得不短視近利(或說隨波逐流)的民生問題。 這個名詞其實也沒有那麼重要， 原則上來說只要負責實作 compiler parser 部分的人懂就好了。 實作 compiler 但不負責寫 parser 的人不懂其實也沒差， 只是要做好被外面不懂工作細節的人取笑的心理準備就是了。

實務上沒有什麼人會真的去寫到非得注意這東西的程式碼， 如果真的有的話他的同事會先讓他整個人黏在牆壁上。 簡而言之這東西的用途除了跟 compiler 內部的最佳化機制有關外， 在使用方面來說就單純只是測試 compiler 到底是否完全符合語言標準， 以及可憐一下那些初學程式設計的新手而給他們一個可以依歸的準則。 國內最容易讓人重新注意到這類問題的主要亂源， 反而是不懂又亂出考題的學校老師和公司的面試官 (雖然我相信有很小一部份是真的故意出來考人)， 其次的亂源是自以為把程式寫到讓大家看不懂或容易看錯就代表很強的神經病。

要記憶就要先理解是我的一貫準則， 所以先來做個名詞解釋。 為什麼 sequence point 要叫做 sequence point？ 叫 sequence 難道只是因為它看起來比較帥， 還是說感覺比較學術化所以會比較容易投上 paper 嗎？ 當然都不是。

在這個連小學生都能輕鬆撰寫平行程式的 2010 年， 要解釋這個名詞我想是再容易不過了。 講到這裡應該很多人明白了， 非 sequence 指的就是 parallel。 所以 sequence point 的最恰當中譯應該稱作循序點。

我想大部分的 C 語言教科書都會說明 side-effect 這個名詞。 i++ 的 side-effect 就是它的值會被偷偷的 +1， 跟 = 這種馬上 +1 的 side-effect 不太相同。 換言之它是在 background 被 +1 的， 所以也可以想像成是在程式執行到 i++ 的時候開了一條 thread 去把 i 的值 update 成 i + 1。 這就是所謂的 parallel。 既然是 parallel 執行的東西總是要有一個 join node 進行會合， 而這個交會的地方就是所謂的 sequence point， 也就是平行執行模式必須回到循序執行模式的分界點。 這邊就定義了所有 side-effect 必須在遇到 sequence point 前完成這件事。

名詞解釋：side-effect

可能有些人還不清楚 side-effect 是什麼意思。
基本上只要是會對變數做修改的動作都算是 side-effect。
譬如 a = b 這種改變 a 狀態的行為就是 = 運算子的 side-effect；
i++ 會把 i 的狀態改變的行為就是 ++ 的 side-effect；
同樣的如果 foo(i) 會改變 i，
那麼這個改變 i 的行為就是 foo() 這個函式呼叫的 side-effect。
當然 side-effect 包含的不只有對變數設值的動作，
不過在這裡只需要知道這樣就可以了。

那麼講到平行程式最常出現的 bug 又是什麼呢？ 當然就是race condition。 回到平行程式設計的角度來看， 你開了一條 thread 去把一個變數 +1， 隨後你又在遇到 join node 之前開了一條 thread 去把同一個變數 +1， 那麼到了 join node 請問這個變數會是多少？ 這答案只有天曉得。 這裡就定義了你不能在遇到 sequence point 前 update 一個變數 2 次。 來看一個典型的惡例：i++ + ++i。 標準規格書說 + 不是一個 sequence point， 所以這個運算式跑完以後 i 會是多少也是只有天才知道。 可能有人會問那 i = i++ 呢？ 首先 = 並不是 sequence point。 再來別忘了以平行程式的角度來看其實 i++ + ++i 有三條 threads， i = i++ 其實有兩條 threads， = 在 main thread 裡 update i 的值， ++ 則是在另一條 thread 裡 update i 的值， 所以當然還是不行。

那麼哪裡有明確定義 sequence point？ C99 標準規格書的 Annex C 裡其實有明確整理出來。 我懶得打字和排版直接貼圖不曉得犯不犯法：

第一點在說的就是 foo(i++) 在 call 進 foo() 之前 i++ 的 side-effect 必須完成。 請特別注意這不代表傳進 foo() 的值會是 i + 1 的結果， 要知道傳進去的值是 i++ 這條運算式的運算結果而不是受附加效果影響後的值， 所以傳進去的還是 i 的原值。

現在更具體一點我們來假設 i 的初值是 1， 考慮一下 foo(i++, i++, i++)。 請注意 argument list 上的 , 只是 syntax 上所謂的標點(punctuation)， 請勿把它想成是 comma operator 然後套用上圖的第二項。 根據上一段的說明似乎這樣會得到 foo(1, 1, 1)... 但是你的 compiler 跑出來的結果卻可能是 foo(3, 2, 1)。 可是不是前面才說過 i++ 的運算結果應該是它的原值嗎？ 我確實是這樣說過沒錯， 但是請特別注意一件事。 所有 side-effect 必須在遇到 sequence point 前完成並不代表剛好到了 sequence point 才完成。 side-effect 完成的時間點是一個範圍， 也就是有 side-effect 的子運算式到 sequence point 之間的這段期間都有可能。 所以概念上你等於開了三條 threads 去 update i， 而 join node 是在 arguments 全部求值完畢進入 foo() 前的瞬間。 此外標準並沒有保證 arguments 的求值順序， 所以哪條 thread 先開起來還是個未知數。 foo(3, 2, 1) 只是剛好你的 compiler 是倒著順序求值， 而且 update i 的時間點剛好都落在對下一個 argument 求值之前而已。

標準裡提的第二項並不讓人意外。 logical AND 和 OR 會根據 LHS 的求值結果決定是否要對 RHS 求值。 這是一種會發生條件分支的動作， 所以 sequence point 落在它們上面可說是理所當然。 conditonal operator 的狀況也是一樣。 至於 comma operator 本身就是所謂的循序運算子， 所以它本身同時也是循序點應該沒有說不過去的地方。

第三第四點其實講了一堆全部都是廢話。 statement 本身就是由 expressions 組成， full-expression 補上特定標點如分號就能構成 statement。 譬如 a = a + ++i 是一個 expression， ++i 可以說是一個 sub-expression。 把 a = a + ++i 結尾補上一個 ; 就會構成一個 simple-statement， 而此時 a = a + ++i 就會成為一個 full-expression。 於是乎 sequence point 會落在 a = a + ++i 和 ; 之間。 這個不用特別講大家也都是知道的。 至於 if/switch/for/while 等等的部分當然就是指圓括號裡決定條件分支的運算式， 這其實也非常直觀。

關於第六點跟第八點， 我的建議是不要去管一個 function 到底是不是 library function， 也不要管它是不是一個 comparison function... 可能有人會認為我接下來要說的是反正只要一概假設進去前跟出來後都是 sequence point 就可以了， 但是這是不可能的。 因為這樣假設是比較寬鬆的假設， 會讓更多人歡樂的在一個含 function call 的 full-expression 內 update 同一個變數多次。 較嚴格的假設應該是請把這兩點當作不存在， 這樣大家才會乖乖的把硬擠在一行的 expression 拆開來寫在不同 statements 上。 在 C++ 標準裡會對這些狀況做更明確的定義， 主要是 C++ 有比 C 更多退出一個 function 的方法 (如 throw exceptions)。 所以像是 b = a = foo(); 會明確指出有一個 sequence point 在 a = foo() 結束後。 這些其實只有 compiler 的設計者才需要特別去關心。 不過根據可靠消息， sequence point 這名詞在下一代的 C++ 會用更明確的說法和詞彙取代。

至於第七點。 什麼叫做 conversion specifier 呢？ 你常看到的 %d %s 的 d 和 s 就是 conversion specifiers。 所以在對 printf() 這類格式化輸出輸入的 function call 來說， argument list 上的 , 確實看起來像是 sequence point， 不過賦予這種 sequence point 特性的是 conversion specifiers 而不是 , 本身。 所以實際發生的點是在這個 function 處理完整個 conversion specifier 的效果後， 而不是立即發生在單一 argument 的求值動作之後。 雖然對 compiler 的 user 來說沒有什麼差別就是了。

除了這些東西之外還有什麼東西要注意的？ 那就是 a[i] = i++ 這個邪惡的運算式了。 前面我的確只有講到不能在遇到 sequence point 之前 update 一個變數兩次， 但是這並不代表 a[i] 的 i 會在 side-effect 生效之前被讀出來。 想想看你開一條 thread 去 update i， 然後你的 main thread 去讀 i， 你能保證 main thread 讀到的 i 是 update 之前的嗎？ 所以標準也說了只有上一個 sequence point 之前所產生出來的值是可信的。

到這邊其實該講的差不多都講完了。 雖然舉的例子並不夠多， 但是本意就只是要講什麼叫做 sequence point， 而不是在講哪些東西有 side-effect 以及怎樣寫是不對的。

必須補充的一點是， 雖然前面都用平行程式和 thread 的觀念去闡述 parallel， 但其實並不會真的開什麼 thread 去 update 變數。 要知道每條 thread 的 time slice 在現代 OS 至少有 1ms， 但 CPU 的時脈隨便就上 3GHz， 指令週期等於是用 1/3GHz = 0.333...ns 來當單位算的。 真的開 thread 去跑簡直就是神經病。 所以前面我也一直很強調概念上這三個字。

修過 advanced compiler 或 architecture 的應該知道， compiler 有一個很重要的最佳化步驟叫 instruction scheduling。 所謂 side-effect 必須在到達 sequence point 之前完成的意思， 真正代表的意義是 update 變數的那道指令可以自由排在某個區間的任意位置。 以 a = i++ + j + k + l; 來說， update i 的動作可以在對 i 求值瞬間到 a 被 update 完畢之後。 如果附近有其它硬體指令因為各種 hazards 的因素從上面卡進來， 但是卡得太後面會使得更多相依於其結果的指令需要往後移而使得效能變差， 這時如果有個能自由活動的指令存在， 就可以放心的把它往後推到空閒的位置上 (本來就有 pipeline stall 只能填 nop 的位置) 去做事而不損失效能。 對於能在一個 cycle 塞進數道指令的 architecture 來說， 寫這什麼 i++ + ++i 得到的意外性和衝擊性也遠比普通架構高， 當然這也是在 compiler 已經設計得超強的前提下才會發生就是了。

這裡最後提醒一些出錯題目又死要面子想說輸一半就好的人。 標準明確提到以下兩件事為 undefined behaviors：

1. Between two sequence points, an object is modified more than once, or is modified and the prior value is read other than to determine the value to be stored.
2. An attempt is made to modify the result of a function call, a conditional operator, an assignment operator, or a comma operator, or to access it after the next sequence point.

並針對 undefined behavior 做了以下解釋：

behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements

NOTE
Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

C FAQ 也明確提及：

undefined: Anything at all can happen; the Standard imposes no requirements. The program may fail to compile, or it may execute incorrectly (either crashing or silently generating incorrect results), or it may fortuitously do exactly what the programmer intended.

請不要再硬拗 i 初值為 1 時 i++ + ++i 只可能是哪些值， 所以沒寫到其中任何一個值的不給分。 以為這是在開獎嗎？ 這個運算出來是隨機亂數值或是其它臨時變數的遺跡都有可能。 前面那個 foo(i++, i++, i++) 的某個 argument 運算結果也可能不是落在個位數的正整數範圍內， 太小看指令集架構的多變性和 compiler 最佳化的複雜度只會讓自己淪為笑柄。