multi-threaded and side-effect
日前在 cubeat 上加上 multi-thread, 應該算是我頭一次真的接觸
多執行序的程式吧？因為以往使用 multi-thread, 通常都是毫無關係，
沒有任何會碰到跟 side-effect 有關的事，最多最多也只有 IO 的部份，
例如輸出 stdout 需要 lock, 也僅僅如此，非常單純。
後來因此去讀了 EventMachine 的原始檔，藉此了解為什麼 single-threaded
可以做到同時 serve 許多的 request, 又有著如此高的效能？
所以寫下了 EventMachine 這篇，當作是一個簡單的筆記。
完成 boost::object_pool 的 lock 之後，又想了很多為什麼需要 lock,
（啊靠，現在有 singleton_pool 是 thread-safe 的！？白做了？ lol）
再加上老林在該篇的回應：
[quote="老林"]
我想或許我們可以把運算架構分成兩種，一種是 multi-threaded,
也就是我們最直覺做同步運算（concurrency?）的方式；
而另一種則是類似 EventMachine 裡的 event-driven 的方式，
也就是上述老林提到的把 algorithm 拆開，並一步步計算的方式。
開門見山，愚公移山，哪個比較好？想來想去，總覺得還是要看情況才能判定，
因為我也覺得這只是在搬移複雜度而已，就像我之前寫非常複雜的 template
所體悟道的。繁複的實作（e.g. branch）與繁複的架構，前者簡化架構，
而後者簡化實作。不管哪個做法，程式的複雜度仍然在那裡，只是哪個方法
比較容易讓我們上手罷了。
就像〈沒有銀彈〉（No Silver Bullet）那篇裡面也提到的，如果我們的
problem domain 就是如此複雜，那軟體技術再進步，我們一樣會遭遇
（encounter）相同的問題。我記得在 Grady Booch 那本好像有爭議的
OOAD 那本書裡也有提到類似的問題。不過我完全想不起來了 XD
雖然講到這不禁就想到 lukhnos 提過關於錯誤引用這件事... XD
儘管如此還是要引用，就像後面的留言所提到的；再說，也算是個聯想紀錄吧。
*
那麼什麼時候該用什麼方法？我們先看直覺的 multi-threaded,
我想這個基本概念也是非常簡單，很容易就可以釐清出來，就是所有的
會有跨 thread 的 side-effect 行為，都需要 lock. 而 lock 的
實作應該也很簡單，就是一個 mutex 一次只能有一個 thread 可以取得，
第二個 thread 要取得，就只能等待原本的 mutex 被 unlock. (release)
這部份可以去看 Modern C++ Design 那書，裡面有提到用多個 if
和 atomic operation 可以做到 lock. 細節不多提了，那是另一回事。
簡單地說，具有跨 thread 的 side-effect 的行為應該視為一種 atomic
operation, 也就是這一段的操作，不能被其他人所干擾。或許也可以看成是
一種 transaction, 這個操作只能是「成功」或是「失敗」，不能只做一半。
例如我們要輸出 stdout, 如果第一個 thread 要吐出 "Hello World",
而在吐出到 "Hell" 時忽然被中斷，被第二個 thread 吐出 "fire",
整個句子最後就是爛掉。就算我們有多核 CPU 同時進行這件事，由於
stdout 是獨一無二的，兩個句子被混在一起也是很正常的。
也就是說，我們會希望 "Hello World" 能一次被吐出，而不是切成片段片段。
也就是說，這個動作就是一個 atomic operation, 需要一次完成，不能做一半被干擾。
不然 stdout 的狀態就會進入非我們預期的狀態。因為 stdout 就是那個被跨
thread 存取，並有 side-effect 的東西。在這邊可以把 stdout 看成一種
string stream, 就很好理解成這是一種「狀態」了。這是一個不可逆的操作！
至於 read, 如果有 side-effect, 例如 PRNG（pseudo-random number
generator）的讀取，就具有 side-effect! 因為內部需要維持一個 seed,
每次存取時，這個 seed 都會有所改變，這種具有 side-effect 的 read,
依然需要做 lock, 使之成為 atomic. 這也是為什麼我們會說 C 的 rand
不是 thread-safe 的。
而 write 更不用說了，只要兩個 thread 同時 write, 問題就會產生。
因為在 C/C++ 裡看似 atomic 的 assignment, 切成 assembly 也不是
atomic 的。gcc 好像也有提供一些基本的 atomic operation,
像是之前提到的 _GTHREAD 就有 atomic 或 mutex 的版本可用。
不過細節我就不清楚了，我電腦上試出來是只有 mutex.
但如果是只有一個 thread 做 write, 其他是 read 呢？
我不是很確定，但或許沒有問題也說不定。這完全要看有沒有 "side-effect".
那麼最簡單的辦法，就是所有的 access 都加上 lock, 這樣就保證沒問題了。
但這樣的程式會跑得很慢，因為 lock 本身就是一種緩慢的動作，（我不知道為什麼）
再加上一旦執行了 lock, 其他要 lock 的 thread 就必須停下來等待 unlock.
更慘的是，如果在 lock 期間又要執行一次相同的 lock, 程式就 deadlock,
就會完全停止運作！這種事可能比程式執行當掉還慘...
也就是說，我們必須好好分析 problem domain 究竟是有哪些地方是真的需要
lock 的。要盡量在最少的地方 lock, 而且 lock 的範圍也要是最小才好。
問題是 multi-threaded 的程式，在一般 imperative programming 裡，
會有大量的 side-effect, 可以說是 side-effect 無所不在！
如果 shared memory 很多，則可能需要 lock 的點，也會無所不在。
分析到底哪裡需要 lock, 則會變成一種非常困難的作業...
至此我才理解為什麼 C/C++ 的東西往往都不是 thread-safe,
假使我們的程式都是 single-threaded, 那麼何要 lock?
假使我們的程式會是 multi-threaded, 那麼在最恰當的地點做 lock,
也會是 client code, 而非 library code 所要執行的。
例如，如果我們有需要 lock 的點，如果只有一個，那就 lock 該處即可，
沒有必要讓整個 vector 的 write 全部都 lock 起來。
不過有時候我們確實也會需要這樣全面性的 lock, 所以提供兩個版本，
我覺得大概也會變成必須的。而且 multi-threaded 程式不見得需要用上
multi-threaded 版。像 Loki 那樣提供一個 macro global 改變
default, 而且任何時候都可以 explicitly 表明要用哪個 policy,
也算是相當方便且強大的方式。
或許這也表示，如果我們需要一個又快又小的程式，或許最好的辦法，
就是一個 library 也不用，全部自己打造最適合自己的東西....
綜觀而言，就是說如果分析何處需要 lock 變成一件很困難的工作時，
或許比較好的辦法，就是完全捨棄 multi-threaded 的架構。
取代的方法有 multi-processes, 絕對不共享任何記憶，
改用所謂 message 進行 process 與 process 之間的溝通。
這個後來似乎被叫成 actor model, 就是完全避開 lock 的一種方式。
另一個，則是捨棄 side-effect, 改用 purely functional 之類的方式... XD
當然這個困難度就非常高了，整個程式架構會完全改變。
最後就是改用 event-driven 的方式，如老林所說的拆解演算法，
從演算法架構上去著手了。
*
於是架構就會變成像是模擬多工的 CPU, 把 task 硬生生拆成好幾部份，
然後每個 task 分配一點 CPU time, 只要我們的 event loop 跑得夠快，
看起來就會像是 concurrency. 如果某個 event 花費的 CPU time 太多，
整個程式就會像是進入 deadlock 般... 或許 event loop 也可以計時，
超過時間太多，就整個 task 殺掉！至於要怎麼殺嘛，可能又是個問題...
如果是用 thread 的方式，要暫停也是可以。不過這樣不就又回到老路？
或許所謂混合式的方式，就是這兩種架構都同時用上，先把問題拆成好幾個部份，
看看這邊套用 event-driven 比較容易，那邊套用 multi-thread 比較容易...
整個架構就會變得越來越複雜，其實也就只是希望避開實作上的複雜：
「到底哪裡需要 lock??」
有的演算法拆解容易，有的演算法拆解困難，又是每個演算法不同...
所以光是決定用哪個架構，本身也是很困難的一件事。
架構選錯最後要打掉重練，大概也不會是什麼怪事吧...
問題大概是出在，現實世界就是充滿著 side-effect 吧...
實在沒什麼是大家所喜歡聽，能夠是一言以蔽之的 :s
多執行序的程式吧？因為以往使用 multi-thread, 通常都是毫無關係，
沒有任何會碰到跟 side-effect 有關的事，最多最多也只有 IO 的部份，
例如輸出 stdout 需要 lock, 也僅僅如此，非常單純。
後來因此去讀了 EventMachine 的原始檔，藉此了解為什麼 single-threaded
可以做到同時 serve 許多的 request, 又有著如此高的效能？
所以寫下了 EventMachine 這篇，當作是一個簡單的筆記。
完成 boost::object_pool 的 lock 之後，又想了很多為什麼需要 lock,
（啊靠，現在有 singleton_pool 是 thread-safe 的！？白做了？ lol）
再加上老林在該篇的回應：
[quote="老林"]
差不多吧，像我的 AI 目前設定 0.4 秒開 thread 來思考一次，[/quote]
但假設我已知 simulation 會做 100 次，
改用純 timer 的寫法就變成一個 callback 做一次 simulation，
並把結果 cache，0.004 秒跑一趟，跑一百趟後再合併結果。
但我覺得這種寫法是在邏輯簡單的情況下可用，
也就是拆解運算很容易時。感覺就好像以前我們寫 Flash 時還把
actionscript 大量寫在 frame 上，然後為了某些 delay 視覺效果
常常要把 for loop 拆掉，更甚者要把 recursive algorithm
拆掉意思一樣；拆 for loop 簡單啊，拆 recursive algo 就不見得了。
而且拆歸拆，這樣程式雖然省去的 mt 的麻煩，
但在演算法本身一定會看起來較不直觀、甚至也會有較複雜之感 (因為被拆了)
所以我個人覺得在不考量其他因素的情況下
(譬如說某些情況絕對要用 thread 或絕對不能用 thread 之外)，
選擇兩者不同的方法只是在搬動複雜度而已。
2009年1月29日 上午 1:29
我想或許我們可以把運算架構分成兩種，一種是 multi-threaded,
也就是我們最直覺做同步運算（concurrency?）的方式；
而另一種則是類似 EventMachine 裡的 event-driven 的方式，
也就是上述老林提到的把 algorithm 拆開，並一步步計算的方式。
開門見山，愚公移山，哪個比較好？想來想去，總覺得還是要看情況才能判定，
因為我也覺得這只是在搬移複雜度而已，就像我之前寫非常複雜的 template
所體悟道的。繁複的實作（e.g. branch）與繁複的架構，前者簡化架構，
而後者簡化實作。不管哪個做法，程式的複雜度仍然在那裡，只是哪個方法
比較容易讓我們上手罷了。
就像〈沒有銀彈〉（No Silver Bullet）那篇裡面也提到的，如果我們的
problem domain 就是如此複雜，那軟體技術再進步，我們一樣會遭遇
（encounter）相同的問題。我記得在 Grady Booch 那本好像有爭議的
OOAD 那本書裡也有提到類似的問題。不過我完全想不起來了 XD
雖然講到這不禁就想到 lukhnos 提過關於錯誤引用這件事... XD
儘管如此還是要引用，就像後面的留言所提到的；再說，也算是個聯想紀錄吧。
*
那麼什麼時候該用什麼方法？我們先看直覺的 multi-threaded,
我想這個基本概念也是非常簡單，很容易就可以釐清出來，就是所有的
會有跨 thread 的 side-effect 行為，都需要 lock. 而 lock 的
實作應該也很簡單，就是一個 mutex 一次只能有一個 thread 可以取得，
第二個 thread 要取得，就只能等待原本的 mutex 被 unlock. (release)
這部份可以去看 Modern C++ Design 那書，裡面有提到用多個 if
和 atomic operation 可以做到 lock. 細節不多提了，那是另一回事。
簡單地說，具有跨 thread 的 side-effect 的行為應該視為一種 atomic
operation, 也就是這一段的操作，不能被其他人所干擾。或許也可以看成是
一種 transaction, 這個操作只能是「成功」或是「失敗」，不能只做一半。
例如我們要輸出 stdout, 如果第一個 thread 要吐出 "Hello World",
而在吐出到 "Hell" 時忽然被中斷，被第二個 thread 吐出 "fire",
整個句子最後就是爛掉。就算我們有多核 CPU 同時進行這件事，由於
stdout 是獨一無二的，兩個句子被混在一起也是很正常的。
也就是說，我們會希望 "Hello World" 能一次被吐出，而不是切成片段片段。
也就是說，這個動作就是一個 atomic operation, 需要一次完成，不能做一半被干擾。
不然 stdout 的狀態就會進入非我們預期的狀態。因為 stdout 就是那個被跨
thread 存取，並有 side-effect 的東西。在這邊可以把 stdout 看成一種
string stream, 就很好理解成這是一種「狀態」了。這是一個不可逆的操作！
至於 read, 如果有 side-effect, 例如 PRNG（pseudo-random number
generator）的讀取，就具有 side-effect! 因為內部需要維持一個 seed,
每次存取時，這個 seed 都會有所改變，這種具有 side-effect 的 read,
依然需要做 lock, 使之成為 atomic. 這也是為什麼我們會說 C 的 rand
不是 thread-safe 的。
而 write 更不用說了，只要兩個 thread 同時 write, 問題就會產生。
因為在 C/C++ 裡看似 atomic 的 assignment, 切成 assembly 也不是
atomic 的。gcc 好像也有提供一些基本的 atomic operation,
像是之前提到的 _GTHREAD 就有 atomic 或 mutex 的版本可用。
不過細節我就不清楚了，我電腦上試出來是只有 mutex.
但如果是只有一個 thread 做 write, 其他是 read 呢？
我不是很確定，但或許沒有問題也說不定。這完全要看有沒有 "side-effect".
那麼最簡單的辦法，就是所有的 access 都加上 lock, 這樣就保證沒問題了。
但這樣的程式會跑得很慢，因為 lock 本身就是一種緩慢的動作，（我不知道為什麼）
再加上一旦執行了 lock, 其他要 lock 的 thread 就必須停下來等待 unlock.
更慘的是，如果在 lock 期間又要執行一次相同的 lock, 程式就 deadlock,
就會完全停止運作！這種事可能比程式執行當掉還慘...
也就是說，我們必須好好分析 problem domain 究竟是有哪些地方是真的需要
lock 的。要盡量在最少的地方 lock, 而且 lock 的範圍也要是最小才好。
問題是 multi-threaded 的程式，在一般 imperative programming 裡，
會有大量的 side-effect, 可以說是 side-effect 無所不在！
如果 shared memory 很多，則可能需要 lock 的點，也會無所不在。
分析到底哪裡需要 lock, 則會變成一種非常困難的作業...
至此我才理解為什麼 C/C++ 的東西往往都不是 thread-safe,
假使我們的程式都是 single-threaded, 那麼何要 lock?
假使我們的程式會是 multi-threaded, 那麼在最恰當的地點做 lock,
也會是 client code, 而非 library code 所要執行的。
例如，如果我們有需要 lock 的點，如果只有一個，那就 lock 該處即可，
沒有必要讓整個 vector 的 write 全部都 lock 起來。
不過有時候我們確實也會需要這樣全面性的 lock, 所以提供兩個版本，
我覺得大概也會變成必須的。而且 multi-threaded 程式不見得需要用上
multi-threaded 版。像 Loki 那樣提供一個 macro global 改變
default, 而且任何時候都可以 explicitly 表明要用哪個 policy,
也算是相當方便且強大的方式。
或許這也表示，如果我們需要一個又快又小的程式，或許最好的辦法，
就是一個 library 也不用，全部自己打造最適合自己的東西....
綜觀而言，就是說如果分析何處需要 lock 變成一件很困難的工作時，
或許比較好的辦法，就是完全捨棄 multi-threaded 的架構。
取代的方法有 multi-processes, 絕對不共享任何記憶，
改用所謂 message 進行 process 與 process 之間的溝通。
這個後來似乎被叫成 actor model, 就是完全避開 lock 的一種方式。
另一個，則是捨棄 side-effect, 改用 purely functional 之類的方式... XD
當然這個困難度就非常高了，整個程式架構會完全改變。
最後就是改用 event-driven 的方式，如老林所說的拆解演算法，
從演算法架構上去著手了。
*
於是架構就會變成像是模擬多工的 CPU, 把 task 硬生生拆成好幾部份，
然後每個 task 分配一點 CPU time, 只要我們的 event loop 跑得夠快，
看起來就會像是 concurrency. 如果某個 event 花費的 CPU time 太多，
整個程式就會像是進入 deadlock 般... 或許 event loop 也可以計時，
超過時間太多，就整個 task 殺掉！至於要怎麼殺嘛，可能又是個問題...
如果是用 thread 的方式，要暫停也是可以。不過這樣不就又回到老路？
或許所謂混合式的方式，就是這兩種架構都同時用上，先把問題拆成好幾個部份，
看看這邊套用 event-driven 比較容易，那邊套用 multi-thread 比較容易...
整個架構就會變得越來越複雜，其實也就只是希望避開實作上的複雜：
「到底哪裡需要 lock??」
有的演算法拆解容易，有的演算法拆解困難，又是每個演算法不同...
所以光是決定用哪個架構，本身也是很困難的一件事。
架構選錯最後要打掉重練，大概也不會是什麼怪事吧...
問題大概是出在，現實世界就是充滿著 side-effect 吧...
實在沒什麼是大家所喜歡聽，能夠是一言以蔽之的 :s
0 retries:
Post a Comment
Note: Only a member of this blog may post a comment.