erlang - multicore

對 erlang 來說，不需要修改程式，就可以運作在多核新的 CPU 上，提昇執行速度。唯一的條件是，必須要以 spawn 多個行程的方式實作程式，不能用巨大的序列程式實作，序列化程式必須要改寫成行程的方式。

如何讓程式在多核心 CPU 上執行地更快

原則如下

1. 使用多個行程
   要讓 CPU 保持忙碌，唯一的方式就是使用多個行程

2. 避免副作用 side effect
   具有共享記憶體，兩個thread可同時寫入相同記憶體位置的共時系統，會利用上鎖的方式來保護寫入的區域，一般是由程式語言在內部以 mutex 或同步化的方式來實現 lock。
   erlang 不具有共享記憶體，不存在這個問題，共享資料可透過 ETS/DETS

   "public" ETS table 可被多個行程共享，只要知道 table 識別字的行程都可以讀寫此 table，這相當危險，所以 programmer 必須注意程式邏輯，加上使用的限制：
   2.1 同一時間只有一個行程會去寫入資料，其他行程只會讀取資料
   2.2 負責寫入 ETS table 的行程永遠要正確，不能寫入錯誤的資料

   "protected" ETS table 比較安全，只有一個行程可以寫入 table，其他行程可讀取資料。

   ETS/DETS 的目的是用來實現 Mnesia，如果要在行程之間共享記憶體，應用程式應該使用 Mnesia 的 transaction，盡可能不要獨立使用 ETS/DETS。

3. 避免序列化瓶頸
   序列化瓶頸就是數個共時行程需要存取序列資源，最常見的序列化瓶頸是 disk IO，這是無法避免的。

   每一次產生了「註冊行程」，就會產生一個潛在的序列瓶頸，盡量避免使用「註冊行程」，如果使用「註冊行程」實作 server，必須確定它會很快地回應 request。

   解決序列瓶頸的唯一方法就是改變演算法，改成分散式演算法，這在網路程式或多核心程式常常會用到。

   分散式訂票系統：如果要賣票，通常會用單一售票處處理所有票務，但這會產生序列瓶頸，解決方式就是開設兩個售票處，第一個售票處分配偶數號，第二個售票處分配奇數號，如果售票處1賣完了，再把第二個售票處的票移到第一個賣。雖然解決問題，但兩張票的座位就會不在隔壁，這是 distributed hash table 的研究範圍。

4. 小訊息，大運算

平行化序列程式碼

lists:map 的用途是可將 list 內所有元素都放入 F 估算一次。

map(_, []) -> [];
map(F, [H|T] -> [F(H)|map(F,T)].

改呼叫新版的 pmap 就可以馬上加速序列程式

pmap 是呼叫 (catch F(H))，而 map 是呼叫 F(H)，因為 pmap 必須確保當估算 F(H) 產生例外時，pmap 能正常結束。

如果 F(H) 有使用到 process dictionary，則 pmap 跟 map 的行為就不一樣了，因為 pmap 是用另一個行程來估算 F(H)，所以就無法用 pmap 平行化

pmap(F, L) -> 
    S = self(),
    %% make_ref() returns a unique reference
    %%   we'll match on this later
    Ref = erlang:make_ref(), 
    Pids = map(fun(I) -> 
                       spawn(fun() -> do_f(S, Ref, F, I) end)
               end, L),
    %% gather the results
    gather(Pids, Ref).

do_f(Parent, Ref, F, I) ->    
    Parent ! {self(), Ref, (catch F(I))}.

gather([Pid|T], Ref) ->
    receive
        {Pid, Ref, Ret} -> [Ret|gather(T, Ref)]
    end;
gather([], _) ->
    [].

使用 pmap 取代 map 之前，下面這些是必須考慮的重點

1. 共時性的單位大小 granularity
   工作量很小的時候，不要使用 pmap，因為產生 process 消耗掉的成本比直接執行 map 還多。
   例如 map(fun (I) -> 2*I, L)

2. 不要建立太多行程
   pmap(F, L) 建立了 length(L) 個平行行程，如果 L 很大，就會一下子建立了很多行程。

3. 思考抽象邏輯
   pmap 重視回傳值的元素順序，如果不在意回傳值的順序，可以改寫為

    pmap1(F, L) -> 
        S = self(),
        Ref = erlang:make_ref(),
        foreach(fun(I) -> 
                        spawn(fun() -> do_f1(S, Ref, F, I) end)
                end, L),
        %% gather the results
        gather1(length(L), Ref, []).
   
    do_f1(Parent, Ref, F, I) ->                        
        Parent ! {Ref, (catch F(I))}.
   
    gather1(0, _, L) -> L;
    gather1(N, Ref, L) ->
        receive
            {Ref, Ret} -> gather1(N-1, Ref, [Ret|L])
        end.

   另外的方式，可使用固定數量 K 個行程來實現 pmap，K 可對應到 multicore 的核心數量。

小訊息，大運算

L = [L1, L2, ..., L100],
map(fun lists:sort/1, L).
其中 L的每個元素都是 1000 個亂數整數 的 list

L = [27, 27, ... , 27],
map(fun ptests:fib/1, L).
其中 L是100個數字27，計算 fibonacci(27) 一百次

分別測量兩個函數花的時間，改成 pmap，再測量一次時間。第一個排序運算，使用 pmap 時，排序本身速度快，不同 process 之間傳送的資料比較多。第二個 fibonacci 有遞迴運算，要花比較多時間計算，但傳送的資料較少。

因為 fibonacci 的資料量少，工作量大，因此可以預測在多核心環境，第二個的效率改進會比第一個大。

SMP erlang

從 Erlang R11B-0 開始，在 Intel duo/quad CPU 預設就開啟了 SMP(symmetric multiprocessing)，這是指具有兩個或多個一樣的CPU，連接到單一共享記憶體的運算環境，這些CPU可能是單或多晶片。

在其他平台要開啟SMP，必須要使用 --enable-smp-support 設定。

SMP erlang 有兩個設定值，用來決定如何運作
erl -smp +S N

1. -smp
   啟動 SMP Erlang
2. +S N
   以 N scheduler 執行 erlang，每一個 erlagn scheduler 都是一個完整的 VM，如果不用此參數，預設數量為 SMP 機器上的邏輯處理器數量。

-module(ptests).
-export([tests/1, fib/1]).
-import(lists, [map/2]).
-import(lib_misc, [pmap/2]).

tests([N]) ->
    Nsched = list_to_integer(atom_to_list(N)),
    run_tests(1, Nsched).

run_tests(N, Nsched) ->
    case test(N) of
        stop ->
            init:stop();
        Val ->
            io:format("~p.~n",[{Nsched, Val}]),
            run_tests(N+1, Nsched)
    end.

test(1) ->
    %% Make 100 lists 
    %%   Each list contains 1000 random integers
    seed(),
    S = lists:seq(1,100),
    L = map(fun(_) -> mkList(1000) end, S),
    {Time1, S1} = timer:tc(lists,    map,  [fun lists:sort/1, L]),
    {Time2, S2} = timer:tc(lib_misc, pmap, [fun lists:sort/1, L]),
    {sort, Time1, Time2, equal(S1, S2)};
test(2) ->
    %% L = [27,27,27,..] 100 times
    L = lists:duplicate(100, 27), 
    {Time1, S1} = timer:tc(lists,    map,  [fun ptests:fib/1, L]),
    {Time2, S2} = timer:tc(lib_misc, pmap, [fun ptests:fib/1, L]),
    {fib, Time1, Time2, equal(S1, S2)};
test(3) ->
    stop.

%% Equal is used to test that map and pmap compute the same thing
equal(S,S)   -> true;
equal(S1,S2) ->  {differ, S1, S2}.

%% recursive (inefficent) fibonacci
fib(0) -> 1;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

%% Reset the random number generator. This is so we
%% get the same sequence of random numbers each time we run
%% the program

seed() -> random:seed(44,55,66).

%% Make a list of K random numbers
%%    Each random number in the range 1..1000000
mkList(K) -> mkList(K, []).

mkList(0, L) -> L;
mkList(N, L) -> mkList(N-1, [random:uniform(1000000)|L]).

測試結果，使用 pmap 在 smp 數量超過 2 之後，速度大約都會快兩倍。

> erl -boot start_clean -noshell -smp +S 1 -s ptests tests 1 >> results
> erl -boot start_clean -noshell -smp +S 2 -s ptests tests 2 >> results
> erl -boot start_clean -noshell -smp +S 3 -s ptests tests 3 >> results

{1,{sort,37334,45348,true}}.
{1,{fib,1615806,1625368,true}}.
{2,{sort,36983,24956,true}}.
{2,{fib,1641762,812359,true}}.
{3,{sort,36484,24912,true}}.
{3,{fib,1590642,902385,true}}.

參考

Erlang and OTP in Action
Programming Erlang: Software for a Concurrent World