理論上最好的編程語言: 並行因果篇

zhuanlan.zhihu.com

早期的計算機只有一個 CPU，CPU 也只有一個核。這一個 CPU 只能一條一條地從人類那裡接收指令，然後依據指令發送信號控制計算機里的其他器件。但即便如此，人們依然在這種早期計算機上建立了多用戶多任務的操作系統。

什麼是「多用戶多任務」呢？一言以蔽之，就是有多個 RDS-IR 同時存在於該 RD 之上。但是由於該 RD 上只有一塊 CPU，且一塊 CPU 只能一條一條地順序執行指令，所以這個「同時」並非真正的同時，而是操作系統通過時分復用的方式使用該塊 CPU 來虛擬出多個 RDS-IR 存在。

這裡說的「時分復用」，就是指該 CPU 在一段人類不易覺察的時間內執行屬於某一個 RDS-IR 的一些指令，而在下一段時間內（之前還需執行「上下文切換」）又去執行屬於另一個 RDS-IR 的一些指令。通過這種方式，CPU 製造了多個 RDS-IR 同時存在的現象，以迎合人類需要的響應效果。

一般的書里，都會將這裡所說的 RDS-IR 換為「進程」這個東西。然而，這種「時分復用」的方式，實際上可以把單進程化為多進程（線程），把單線程化為多線程——也就是利用該機制，可以將任何一個 RDS-IR 存在化為多個 RDS-IR 並發存在。是的，「並發」就是指這種虛擬出來的「偽」並行。（實際上對人類而言是效果上的真並行）

而現在，當一台電腦里有多個 CPU ，每個 CPU 又有多個核心時，我們可以實現真正地同時進行多個任務了（就是讓多個 RDS-IR 並行存在）。但是我們發現，有些程序用單 CPU 單核完成所花的時間，和它用多 CPU 多核完成所花時間是相同的（也就是並行完全沒發揮加速計算的作用），這又是為什麼？

這裡可以用一個有趣的例子來解釋這個現象：假如我們將工作量等同於人數乘以時間，並假設每一件事情，要完成它所花的工作量是恆定的（也就是只要工作量達標，該事情肯定會被完成）；這時，假設一棟房子，要一個人花一年時間蓋好，那麼可以等效為要 12 個人花一個月時間蓋好，進而等效為要 360 個人花一天蓋好，再進而等效為只要 8640 個人花一小時就能蓋好了。

最後一個等效情形，是明顯不可能成立的。

先不考慮 8640 個人能不能同時在一個狹小空間內同時工作，最大的問題還是，造房子要先有設計圖，然後按設計圖打地基，然後再按地基結構在其上一層層地築牆，這裡有一個因果順序問題。假如不能壓縮畫設計圖的時間，不能壓縮打地基的時間，那麼一天時間的工作量，光靠增加人數，是無法被壓縮成一小時完成的。

同樣的，回到程序的並行執行問題上，假如 A 步驟是 B 步驟開始之前必須先完成的步驟（也就是 A 為 B 的前提條件，A 為 B 的因，此處有因果順序），那麼 A 步驟和 B 步驟通常不可能同時並行或者並發執行（這裡說「通常」，是因為有不少反例，比如「移位寄存器」）。若 A 步驟與 B 步驟之間沒有直接或間接的因果關係，那麼 A 步驟和 B 步驟必然能被並行或並發執行。

目前，絕大多數的編程語言，都是從單 CPU 單核的時代發展過來的，這就導致了它們的一個特點：若源代碼中 A 行在 B 行之前，通常即默認 A 行先於 B 行被執行。這種出於文學習慣而添上的因果序，給多 CPU 多核乃至 GPU 和 FPGA 的時代的 RDS 帶來了不可進一步並行化的缺陷。

這裡用八個數(a[1]~a[9])的累加為例來說明解釋這個現象：

先用 javascript 將這個過程寫一遍：

var sum=0;for(var i=1;i<9;i++){sum=sum+a[i];}return sum；

實際上，這個過程可以用下圖表示清楚：

從圖中可以看出，這個累加過程是有因果次序的，要加上 a[8] 就需要等 a[1]~a[7],因而 7 次加法必須花費 7 個時間段完成。

但是，用 lisp 可以將這個過程這樣寫：

(+ a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8])

考慮到得到的結果，其實跟 a[1]~a[8] 的計算次序無關，因而可以用下圖結構計算：

同樣是 7 次加法，但是在有 4 個加法器同時工作的情況下，只要花費 3 個時間段就可以完成了。

這是一個典型的並行優化過程。但如果按照最初 javascript 的那種寫法，則相當於將計算的方式固定，不給編譯器結合可並行的編譯環境進行並行優化的機會。

也就是說，在程序源代碼中，大量使用默認的因果序關係，會減少編譯器結合可並行環境進行並行優化的可能。因此，應盡量減少這種默認的因果序關係，將非因果序視為常態（即代碼行的前後關係不代表執行順序），而有因果序的代碼才需特殊註明。這個特點才能真正讓一種編程語言適應高並發或者高並行的環境，因此也將成為 OOWA 的特性之一。

根據 When we share, everyone wins - Creative Commons 網站的協議，本文

署名-非商業性使用-相同方式共享

CC BY-NC-SA

下篇：