如何在Erlang中优化数千条消息的接收循环？

Question

在编程Erlang书的"编程多核CPU"一章中,Joe Armstrong给出了一个很好的并行化map函数的例子:

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([], _) ->
    [].

它工作得很好,但我相信它有一个瓶颈,导致它在100,000多个元素的列表上工作得非常慢.

gather()执行该功能时,它开始匹配列表中的第Pid一个Pids与主进程邮箱中的消息.但是如果邮箱中最旧的邮件不是来自这个Pid呢？然后它会尝试所有其他消息,直到找到匹配项.话虽如此,有一定的可能性,在执行gather()函数时,我们必须循环遍历所有邮箱消息,以找到与Pid我们从Pids列表中获取的匹配项.对于大小为N的列表,这是N*N最坏情况.

我甚至设法证明了这个瓶颈的存在:

gather([Pid|T], Ref) ->
    receive
        {Pid, Ref, Ret} -> [Ret|gather(T, Ref)];
        %% Here it is:
        Other -> io:format("The oldest message in the mailbox (~w) did not match with Pid ~w~n", [Other,Pid])
    end;

我怎样才能避免这个瓶颈？

Answer 1

在这种情况下，您可以使用dict（从生成进程的 pid 到原始列表中的索引）作为Pids替代。