多核 CPU 编程

现代 CPU

我们怎样编写在多核心 CPU 上运行更快的程序呢？这一切都与可变状态和并发有关。

在过去（二十多年前），有两种并发模型。

共享状态的并发
消息传递的并发

编程界走了一条路（朝着共享状态）。Erlang 社区则走的是另一条路。(很少有其他语言循着 “消息传递的并发” 这条道路；这些别的语言有 Oz 及 Occam）。

在消息传递的并发下，是没有共享状态的。所有计算在进程中完成，交换数据的唯一方式，是经由异步的消息传递。

为何这很不错？

共享状态的并发，涉及 “可变状态”（可被更改的内存）的这一概念 -- 诸如如 C、Java、C++ 等所有语言，都有着这种概念：有一种叫状态的东西，而我们可以改变他。

在咱们只有一个进程进行更改时，这不会有问题。

当咱们有正共用并修改同一内存的多个进程时，咱们就会后患无穷 -- 疯狂就在这里。

知识点：

a receipe for disaster, 后患无穷

要防止共享内存的同时修改，我们就要使用某种加锁机制。咱们可以把这叫做互斥锁、同步方法或其他任何东西，但他仍是把锁。

当程序在临界区（当其持有锁）崩溃时，就会导致灾难。所有其他程序都不知道要做什么。当程序破坏了处于共享状态的内存时，灾难也将发生。其他程序将不知道要做什么。

程序员怎么解决这些问题呢？困难重重。在单核处理器上，他们的程序可能恰好工作了 -- 但在多核处理器上......就是灾难。

对此，有一些不同解决方案（事务内存可能是最好的），但这些充其量也就是些 “蹩脚货”。最糟糕的是，它们简直就是噩梦。

Erlang 没有可变数据结构（这也不全对，但也足够正确）。

没有可变数据结构 == 没有锁；
没有可变数据结构 == 易于并行化。

我们怎么做到并行化？很简单。程序员会把问题解法，分解成若干并行进程。

这种编程风格有自己的术语；他被叫做 面向并发的编程。

Erlang 程序员的好消息

好消息是：咱们的 Erlang 程序在 n 个核心的处理器上，可能会以 n 倍快速度运行 -- 无需对程序的任何修改。

但咱们必须遵循一套简单规则。

若咱们希望咱们的应用，在多核 CPU 上运行更快，咱们就必须确保其有着大量互不干扰的进程，并且咱们的程序中，没有顺序（代码）瓶颈。

当咱们把咱们的代码，写成了一大堆顺序代码，并从未使用 spawn 创建一个并行进程，那么咱们的程序，就可能不会更快。

请勿绝望。即使咱们的程序一开始是个巨大的顺序程序，对程序的几个简单改动，就将使其并行化。

在这一章中，我们将讨论以下主题：

我们必须完成哪些事情，使咱们的程序在多核 CPU 上高效运行；
怎样并行化某个顺序程序；
顺序化瓶颈问题；
如何避免一些副作用。

在我们完成上述主题后，我们将研究一个更复杂问题中所涉及的一些设计问题。我们将实现一个名为 mapreduce 的高阶函数，并展示他怎样用于并行化计算。 mapreduce 是谷歌开发的一个，用于在处理元素集上执行并行计算的抽象概念。

知识点：

sets of processing elements

怎样令到程序在多核心 CPU 上高效运行

要高效运行，我们必须完成以下几点：

要使用大量进程；
要避免一些副作用；
要避免顺序化的一些瓶颈；
要编写 “小消息，大计算” 的代码。

当我们完成全部这些要求时，我们的 Erlang 程序，就应会在多核心 CPU 上高效运行。

我们为何应关注多核心 CPU？

咱们可能想知道，这大惊小怪是为啥。我们真的有必要费心将程序并行化，使其能在多核心上运行吗？答案是肯定的。如今，带有超线程的四核已经司空见惯。智能手机也有四核心。就连我那低端的 MacBook Air，也有带超线程的双核心，而我的台式机，则有带超线程的八核心。

构造一个在双核心机器上以两倍的速度运行的成型，并不那么令人兴奋（但确实有点令人兴奋）。但我们不要自欺欺人。双核心处理器的时钟速度，比单核心 CPU 慢，因此性能的收益可能很小。

现在，虽然两倍提升还不能让我（作者）兴奋，但十倍就会，而一百倍就真的非常非常让人兴奋了。现代处理器如此之快，一个核心可运行 4 个超线程，那么一个 32 核心的 CPU，就可以提供 128 个线程使用。这意味着，百倍的速度指日可待。

一个一百的系数，确实让我（作者）兴奋。

我们要做的就是，写下代码。

使用大量线程

这点很重要 -- 我们必须让 CPU 忙起来。所有 CPU 都应该一直处于忙碌状态。要做到这一点，最简单方法就是要有大量进程。

在我（作者）讲到大量进程进程时，我指的是与 CPU 数量相关的大量。当我们有很多进程时，那么我们将无需担心让 CPU 忙碌了。这表现为一种纯粹的统计效应。当我们有着少量的进程时，他们可能不小心占用一个 CPU；当我们有着很大数量的进程时，这种效应似乎就消失了。当我们想要咱们的程序不过时，我们就应该考虑到，即使现今的芯片可能只有少量 CPU，但将来我们可能就会有每个芯片的成千上万个 CPU。

这些进程的工作量最好相近。编写出其中一个进程完成很多工作，而别的进程完成很少工作的程序，是个糟糕的主意。

在许多应用中，我们都 “免费” 获得了大量进程。当应用 “本质上是并行的” 时，那么我们就不必担心，并行化代码的问题。例如，当我们正编写某个管理数万个并发连接的消息系统时，那么我们会获得这数万个连接中的并发性；而处理某单个连接的代码，则将不必担心并发性问题。

避免副作用

一些副作用会阻止并发。就在本书的开头，我们曾谈到了 “不变化的变量” 问题。这是理解为何 Erlang 程序在多核心 CPU 上，比以哪些会破坏性修改内存语言编写的程序，可以运行更快的关键所在。

在有着共享内存及线程的某门语言中，当两个线程在同一时刻写入共用内存时，灾难就可能发生。有着共享内存并发的系统，会通过在共享内存被写入时，给这些共享内存加锁，防止这种情况。这些锁对程序员隐藏，在他们的编程语言中表现为互斥锁或同步方法。共享内存的主要问题，是某个线程会破坏另一线程用到的内存。因此，即使我的程序是正确的，另一线程也会弄乱我的数据结构，进而导致我的程序崩溃。

Erlang 没有共享内存，因此这个问题就不存在。事实上，这不完全正确。共享内存的方式只有两种，并且这个问题可轻松避免。共享内存的两种方式，都与共享 ETS 或 DETS 数据表有关。

不使用共享的 ETS 或 DETS 数据表

ETS 数据表可被多个进程共享。在 19.3 节，创建 ETS 数据表 中，我们介绍了创建 ETS 数据表的不同方式。采用这些选项中的一种来 ets:new，我们就可以创建一个 public 的数据表类型。回顾这样做曾完成了以下内容：

创建一个公共数据表。任何知道该数据表标识符的进程，都可以读写这个数据表。

这样做会很危险。只有在我们能保证以下两个条件时，才是安全的：

某个时刻只有一个进程写入该数据表，所有别的进程都读取该数据表中的数据；
写入该 ETS 数据表的进程正确无误，且未将不正确数据写入该数据表。

这些属性一般无法获得系统的保证，而是依赖于程序逻辑。

注 1：对 ETS 数据表的一些单项操作，均是原子的。将一系列 ETS 的操作，作为一个原子单元执行是不可行的。虽然我们无法破坏 ETS 数据表中的数据，但当多个进程在未协调他们的活动下，试图同时更新某个共享数据表时，数据表就会在逻辑上变得不一致。

注 2：protected 的 ETS 数据表类型，则安全得多。只有一个进程（即所有者）可写入这个数据表，但多个进程可读取该表。这一属性由系统 提供保证。但请记住，即使只有一个进程可写入某个 ETS 数据表，当这个进程破坏了该数据表中的数据时，那么所有读取该表的进程，都将被影响。

当咱们使用 ETS 数据表类型 private 时，那么咱们的程序将是安全的。类似情况也适用于 DETS。我们可以创建多个不同进程都可写入的 DETS 数据表。这种做法应加以避免。

注：ETS 和 DETS 是为实现 Mnesia 而创建的，原本就不为单独使用。意图是当应用程序打算模拟进程间的共享内存时，他们应使用 Mnesia 的事务机制。

避免顺序（代码）的瓶颈

一旦我们已并行化咱们的程序，并已确认咱们有了大量进程，且没有共享内存操作，那么下一个要考虑的问题，就是顺序的瓶颈。某些事情本质上是顺序的。当 “顺序性” 存在于（要解决的）问题中时，我们就无法让其消失。某些事件会按一定顺序发生，无论如何尝试，我们都无法改变这种顺序。我们出生、成长、死亡。我们无法改变顺序。我们无法同时完成这些事情。

所谓顺序的瓶颈，是指多个并发进程需要访问某项顺序资源的情况。一个典型示例就是 I/O。通常情况下，我们只有一个磁盘，所有到磁盘的输出，最终都是顺序的。磁盘只有一组磁头，而不是两组，我们无法改变这点。

每次我们构造一个注册进程时，我们都在创建某种潜在的顺序瓶颈。因此，要尽量避免注册进程的使用。当咱们确实创建了一个注册进程，并将其用作一个服务器时，要确保他会尽可能快地响应所有请求。

通常，顺序瓶颈的唯一解决方案，是改变相关算法。这里并没有某种简单易行的办法。我们必须将算法从某种非分布式算法，修改为某种分布式算法。这一主题（分布式算法）有大量的研究文献，但在一些传统编程语言库中的应用却相对较少。（分布式算法）未被采用的主要原因，是直到我们尝试对带有网络通信的算法，或多核计算机编程前，此类算法的需求并不明显。

对永久连接到互联网的计算机，及多核心 CPU 的计算机编程，将迫使我们深入研究文献，并实现一些这种令人惊叹的算法。

一种分布式的订票系统

设想我们有某种单一的资源，即一套 Strolling Bones 下一场音乐会的门票。为保证咱们买票时能真正拿到票，我们通常会使用预订所有门票的单一代理公司。但这样做会引入顺序瓶颈。

单一代理公司的瓶颈问题，可通过引入两家票务代理公司加以避免。在销售开始时，第一家票代公司会给到所有偶数票，第二家代理公司会给到所有奇数票。在这种方式下，两家代理公司就保证了不会卖出同一张票两次。

当其中一家机构的票用完了时，那么他可以向另一家申请一捆门票。

我（作者）没说这是个好方法，因为在咱们听音乐会时，可能真的想坐在朋友旁边。但他确实通过一个售票处改为两个，消除了瓶颈。

以 n 个分布式的代理机构，取代单个预订代理，其中 n 可随时间变化，并且这些单独机构可以随时加入和离开网络，并可以随时崩溃，这是分布式计算中，一个活跃的研究领域。这项研究被称为 分布式哈希表。当咱们在谷歌上检索这个术语时，咱们将发现有关这个主题的大量文献。

知识点：

distributed hash table, DHT

并行化序列代码

还记得我们对一次列表操作，特别是函数 lists:map/2 所强调的东西吗？ map/2 被定义为下面这样：

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

加快咱们顺序程序速度的一种简单策略，就是用我（作者）称之为 pmap，会并行地计算其所有参数的新版本 map，替换所有对 map 的调用。


pmap(F, L) ->
    S = self(),
    %% make_ref() returns a unique reference
    %%   we'll match on this later
    Ref = erlang:make_ref(),
    io:format("Ref: ~p~n", [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)]

pmap 会像 map 那样工作，但当我们调用 pmap(F, L) 时，他会创建一个并行进程，计算 L 中的每个参数。请注意，计算 L 参数的那些进程，可以按任意顺序完成。

gather 函数中的那个选择性的 receive，确保了返回值中参数的顺序，与原始列表中的顺序对应起来。

map 与 pmap 在语义上略有不同。在 pmap 中，当我们将函数映射到列表上时，我们使用了 (catch F(H))。而在 map 中，我们只使用了 F(H)。这是因为我们要确保 pmap 在计算 F(H) 抛出异常的情形下，会正确地终止。在没有异常抛出的情形下，这两个函数的行为是相同的。

译注：关于 catch 这个原语，请参考使用 catch 捕获异常。

重点：最后一句话严格来说并不正确。当 map 和 pmap 有副作用时，他们将不会以同一方式行事。设想 F(H) 有一些修改进程字典的代码。当我们调用 map 时，对进程字典的修改，将在调用 map 的那个进程的进程字典中进行。

而当我们调用 pmap 时，每个 F(H) 都在会其自己的进程中计算，因此当我们用到进程字典时，该字典中的变化，将不会影响调用 pmap 的那个进程中的进程字典。

因此，请注意：那些有副作用的代码，无法简单地以 pmap 替换 map 调用并行化。

我们何时可以使用 `pmap`？

使用 pmap 而非 map，并不是加快咱们程序的万能药。以下是一些需要考虑的问题。

并发的粒度

当函数种完成的工作量很小时，就不要使用 pmap。设想我们有如下表述：

map(fun(I) -> 2*I end, L)

这里那个 fun 内部完成的工作量很小。设置进程和等待回复的开销，大于使用并行进程完成这项工作的好处。

不要创建太多进程

请记住，pmap(F, L) 会创建 length(L) 个并行进程。当 L 非常大时，咱们将创建出很多进程。最好的办法是创建一个适当数量的进程。Erlang 来自瑞典，lagom 这个词翻译过来的意思是 “不要太少，也不要太多，差不多就行”。有人说这概括了瑞典人的性格。

译注：这个 pmap 实现的验证如下：
$ erl -boot start_sasl -config elog4
..
1> Fac = fun(X) -> lib_misc:fac(X) end.
#Fun<erl_eval.42.113135111>
2> lib_misc:pmap(Fac, [16, 32, 64]).
[20922789888000,263130836933693530167218012160000000,
 126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000]
其中 lib_misc:fac/1 为：
fac(0) -> 1;
fac(N) -> N * fac(N-1).
但是我们不能在 Erlang shell 下，执行以下命令会报出相应错误。
3> lib_misc:pmap(lib_misc:fac, [10, 100, 1000]).
* 1:15: illegal expression
请思考这是为什么。

考虑咱们所需的抽象

pmap 可能并非正确的抽象。我们可以想到以并行方式，将某个函数映射某个列表上的许多不同方式；我们在这里选择了最简单的一种可行方式。

我们使用的 pmap 版本，关注了返回值中元素的顺序（我们使用了一种选择性接收做到这点）。当我们不在乎返回值顺序时，我们可以写出下面这样：

gather([], _) -> [].

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

对这段代码的简单修改，就可将其转换为一个并行的 foreach。这段代码与前面的类似，但我们没有建立任何返回值。我们只注意了程序的终止。

另一种方式，将是使用最多 K 个进程实现 pmap，其中 K 是个固定常数。当我们打算对一些非常大的列表使用 pmap 时，这种方式就可能会很有用。

而另一版本的 pmap，不仅可将计算映射到多核心 CPU 种的进程上，还可映射到分布式网络中的一些节点上。我（作者）不会在这里向咱们演示如何做到完成一点。咱们可自己思考一下这个版本。

本节的目的是要指出，从基本的生成、发送和接收基元出发，可以很容易地建立起一个庞大的抽象体系。你可以使用这些基元创建自己的并行控制抽象，以提高程序的并发性。

Erlang 编程