Question

^{1 这里的“管道”和上一节中的“流水线”都来自同一个英文单词 pipeline，它们在本质上的含义也是相同的，只是在不同的领域中习惯译法不同。}

诞生于 20 世纪 60 年代后半的 UNIX，与之前的操作系统相比，具有一些独到的特点，其中之一就是文件的结构。在 UNIX 之前，大多数操作系统中的文件指的是结构化文件。如果熟悉 COBOL 的话解释起来会容易一些，所谓结构化文件就是拥有结构的记录的罗列（图 1）。

图 1 结构化文件与平面文件

但 UNIX 的设计方针是重视简洁，因此在 UNIX 中抛弃了对文件本身赋予结构的做法，而是将文件定义为单纯的字节流。对于这些字节流应当如何解释，则交给每个应用程序来负责。文件的内容是文本还是二进制，也并没有任何区别。

例如，图 1 中所示的平面文件（flat file），是采用每行一条记录、记录的成员之间用逗号进行分隔的 CSV（Comma Separated Values）格式来表现数据的。这并不是说 UNIX 对 CSV 这种文件格式有特别的规定，而只是相应的应用程序能够对平面文件中存放的 CSV 数据进行解释而已。

UNIX 的另一个独到之处就是 Shell。Shell 是 UNIX 用来和用户进行交互的界面，同时也是能够将命令批处理化的一种语言。

在 UNIX 之前的操作系统中，也有类似的命令管理语言，如 JCL（Job Control Language）。但和 JCL 相比，Shell 作为编程语言的功能更加丰富，可以对多个命令进行灵活地组合。如果要重复执行同样的操作，只要将操作过程记录到文件中，就能够很容易地作为程序来执行。像这样由“执行记录”生成的程序，被称为脚本（script），这也是之后脚本语言（script language）这一名称的辞源。

在 UNIX 中至今依然存在 script 这个命令，这个命令的功能是将用户在 Shell 中的输入内容记录到文件中，根据所记录的内容可以编写出脚本程序。script 一词原本是“剧本”的意思，不过命令行输入是一种即兴的记录，也许叫做 improvisation（即兴表演）更加合适。

最后一点就是串流管道（stream pipeline）。UNIX 进程都具有标准输入和标准输出（还有标准错误输出）等默认的输入输出目标，而 Shell 在启动命令时可以对这些输入输出目标进行连接和替换。通过这样的方式，就可以将某个命令的输出作为另一个命令的输入，并将输出进一步作为另一个命令的输入，也就是实现了命令的“串联”。

在现代的我们看来，这三个特征都已经是司空见惯了的，但可以想象，在 UNIX 诞生之初，这些特征可是相当创新的。

管道编程

下面我们来看一看运用了串流管道的实际程序。图 2 是经常被用作 MapReduce ²例题的用于统计文件中单词个数的程序。

^{2 一种通过分布式并行处理对庞大数据库进行高速访问的手法，分为“Map”和“Reduce”两个步骤进行处理。（原书注）}

通过这个程序来读取 Ruby 的 README 文件，会输出图 3 这样的结果。

tr -c '[:alnum:]' '¥n' | grep -v '^[0-9]*$' | sort | uniq -c | sort -r

图 2 单词计数程序

       33 ruby
       23 the
       19 to
       16 prefix
       16 DESTDIR
       13 and
       13 Ruby
       11 lib
       11 is
       11 TEENY
       11 MINOR
       11 MAJOR
        7 of
        6 you
        6 org
        6 lang
        6 in
        6 be
        5 not
(中略)
        1 Author
        1 Aug
        1 Advanced

图 3 单词计数结果（节选）

Shell 中，用“|”连接的命令，其标准输出和标准输入会被连接起来形成一个管道。这个程序是由以下 5 条命令组成的管道。

1. tr -c '[:alnum:]' '\n'
2. grep -v '^[0-9]*$'
3. sort
4. uniq -c
5. sort -r

下面我们来具体讲解一下每个命令的功能。

“tr”是 translate 的缩写，其功能是将输入的数据进行字符替换。tr 会将第一个参数所指定的字符集合（这里的 [:alnum:] 表示字母及数字的意思）用第二个参数所指定的字符进行替换。“-c（complement）”选项的意思是反转匹配，整体来看这条命令的功能就是“将除字母和数字以外的字符替换成换行符”。

grep 命令用来搜索与模板相匹配的行。在这里，模板是通过正则表达式³来指定的：

^[0-9]*$

^{3 一种用特殊字符描述字符串匹配模板的手法。（原书注）}

这里，“^”表示匹配行首，“$”表示匹配行尾，“[0-9]*”表 示匹配“0 个或多个数字组成的字符串”。结果，这一模板所匹配的是“只有数字的行或者是空行”。

-v（revert）选项表示反转匹配，也就是显示不匹配的行。因此，这条 grep 命令的执行结果是“删除空行或者只有数字的行”。

之前的 tr 命令已经将字母和数字之外的字符全部替换成了换行符，也就是说将符号、空格等全部转换成了只有一个换行符的行（即空行）。对空行计数是没有意义的，因此需要忽略这些空行。此外，只有数字的行也不能算是单词，因此也需要忽略。

接下来的 sort 是对行进行重新排序的命令。到这条命令之前，数据流已经被转换成每行一个单词的排列形式，通过 sort 命令可以对原文中出现的单词按照字母顺序进行排序。这一排序操作看似没什么用，但接下来我们需要用 uniq 命令去掉重复的行，因此必须事先对输入的数据流进行排序。

uniq 是 unique 的缩写，该命令可以从已排序的文件中去掉重复的行。-c（count）选项表示在去掉重复行的同时显示重复的行数。在这里我们输入的文件是每行一个单词的形式，因此统计出已排序的单词序列中重复的行数，也就相当于是统计出了单词的数量。uniq 命令才是单词计数的本质部分。

最后我们用 sort -r 命令对输出的信息进行整形。uniq 命令执行完毕之后，就完成了“统计单词数量”这一任务，但从人类的角度来看，将单词按出现的数量降序排列才是最自然的，因此我们再执行一次 sort 命令。

我们希望在查看统计结果时将出现数量最多的单词（可以认为是比较重要的单词）放在前面，因此这次我们对 sort 命令加上了 -r（reverse）选项，这个选项代表降序排列的意思。这个命令有一个副作用，就是出现数量相同的单词，会被按照字母逆序排列，这一点就请大家多多包涵吧。

将单词按出现数量降序排列的同时，还要将出现数相同的单词按字母顺序排列，实现起来是出乎意料地麻烦。这里就当是给各位读者留个思考题吧。其实用 Ruby 和 Awk 就可以比较容易地解决这个问题了。

像上面这样，将完成一个个简单任务的命令组合起来形成管道，就可以完成各种各样的工作，这就是 UNIX 范儿的管道编程。

多核时代的管道

在 UNIX 诞生的 20 世纪 60 年代末，多核 CPU 还不存在，因此管道原本的设计也并非以运用多核为前提。然而，不知是偶然还是必然，管道对于多核的运用却是非常有效的。

下面我们来看看在多核环境中，管道的执行是何等高效。

首先，我们来思考一下非常原始的单任务操作系统，例如 MS-DOS。说是“原始”，但其实 MS-DOS 相比 UNIX 来说算是非常年轻的，在这里我们先忽略这一点吧。在 MS-DOS 中，同时只能有一个进程在工作，因此管道是通过临时文件来实现的。例如，当执行下列管道命令时：

command-a | command-b

MS-DOS（准确地说应该是相当于 Shell 的 command.com）会生成一个临时文件，并将“command-a”的输出结果写入文件中。command-a 的执行结束之后，再以该临时文件作为输入源来执行“command-b”。由于 MS-DOS 是一个单任务操作系统，每次只能进行一项处理，当然也就无法对多核进行运用（图 4）。

图 4 单任务操作系统的管道

接下来我们来思考一下单核环境下的多任务操作系统。在这样的环境下，管道的命令是并行执行的。但由于只有一个核心，因此无法做到完全同时进行。和刚才一样，执行下列命令：

command-a | command-b

这次 command-a 与 command-b 是同时启动的。

然后，进程会在不断相互切换中各自执行，command-b 会进入等待输入的状态。当 command-b 为读取数据发出系统调用时，如果暂时没有立即可供读取的数据，则操作系统会在数据准备好之前暂停 command-b 的进程，并使其休眠。

另一方面，command-a 继续执行，其结果会输出到某个地方。这样一来 command-b 就有了可供读取的数据，command-b 的进程就会被唤醒并恢复执行。

像这样，数据输出以接力棒的形式进行运作，多个进程交替工作，就是单核多任务环境中的执行方式（图 5）。

图 5 多任务操作系统的管道（单核）

和单任务相比，多任务环境下的优势在于没有了无谓的文件输入输出操作，从而削减了相应的开销。

而且，由于多个进程是依次执行的，先得出的结果会立即通过管道传递，因此获取结果也会比较快一些。

不过，在多任务环境下，进程的切换也需要一定的开销，从总体来看，执行时间也未必会缩短。接下来终于要讲到多核环境下的管道了。简单起见，在这里我们假设将 command-a 和 command-b 分别分配给两个不同的核心，在这样的情况下，管道执行如图 6 所示。

图 6 多任务操作系统的管道（多核）

我们可以看出，和图 5 相比，同时执行的部分增多了。非常粗略地数了一下，图 4 中需要 11 步完成的处理，这里只需要 8 步就完成了。不过我们投入了两个核心，理想状态下应该比单核缩短一半，但这样的理想状态是很难实现的。

假设操作系统足够聪明的前提下，只要增加管道的级数，使能够重叠的部分也相应增加，即便不特意去管多个核心的配置，只要自然编写程序形成管道，操作系统就会自动利用多个核心来提高处理能力。之所以说串流管道是非常适合多核的一种编程模型，原因也正是在于此。

xargs——另一种运用核心的方式

大家知道 xargs 这个命令吗？ xargs 是用于将标准输入转换成命令行参数的命令。

例如，要在当前目录下搜索所有文件名中以“~”结尾的文件，需要执行 find 命令：

# find . -name '*~'

这样就会将符合条件的文件名在标准输出中列出。

那么，如果我要将这些文件全部删除的话又该怎么做呢？这时就该轮到 xargs 命令出场了。

# find . -name '*~'|xargs rm

这样一来，传递到 xargs 标准输入的文件名列表就作为命令行参数传递给了 rm 命令，于是就删除了符合条件的所有文件。

还有一个很少有人会实际碰到的问题，那就是命令行参数的数量是有上限的，如果传递的参数过多，命令执行就会失败。xargs 也考虑了这一点，当参数过多时会分成几条命令分别执行。

上面所讲的内容与多核没什么关系，不过 xargs 提供了一个用于多核的命令行参数“-P”。

如图 7 所示，是用于将当前目录下未压缩的（即扩展名不是 .gz 的）文件全部进行压缩的管道命令。

# find . \! -name *.gz -type f -print0 | xargs -null -P 4 -r gzip -9

图 7 文件压缩管道命令

首先是 find 命令，它的含义如下：

· “.”表示当前目录下

· “! -name *.gz”表示文件名不以 .gz 结尾

· “-type f”表示一般文件（而不是目录等特殊文件）

· “-print0”表示将符合上述条件的文件名打印到标准输出。为了应对包含空格的文件名，采用 null 作为分隔符。

这样我们就得到了“当前目录下未压缩的文件名列表”。得到该列表之后，xargs 命令被执行。xargs 命令中的“-P”选项，表示同时启动指定数量的进程，这里我们设定为同时执行 4 个进程。“-r”选项表示当输入为空时不启动命令，即当不存在符合条件的文件时就表示不用进行压缩，因此我们在这里使用了“-r”选项。

为了应付空格，find 命令使用了“-print0”选项，相应地，必须同时使用“-null”选项。通过这样的操作，就实现了将要压缩的对象文件名作为参数传递给“gzip -9”命令来执行。

gzip 命令的“-9”选项表示使用较高的压缩率（会花费更多的时间）。

我们知道，文件的压缩比单纯的输入输出要更加耗时，而且，多个文件的压缩操作之间没有相互依赖的关系，这些操作是相互独立进行的。对于这样的操作，如果能够分配到多个进程来同时进行，应该说是最适合多核环境的工作方式。

在多核环境中，是否对 xargs 命令使用“-P”选项，直接影响了处理所需要的时间。由于 gzip 命令的输入输出等操作也需要一定的处理时间，因此 -P 设定的进程数应该略大于实际的核心数。我用手上的双核电脑进行了测试，用两个核心设定 4 个进程来执行时，可以获得最高的性能。

不过，在我所做的测试中，当文件数量较少时，即便使用了 -P 选项，也只能启动一个进程，无法充分利用多核。在这种情况下，对 xargs 命令使用 -n 选项来设定 gzip 一次性处理的文件数量，也许是个好主意。

例如，如果使用“-n 10”选项，就可以对每 10 个文件启动一个 gzip 进程。在我所做的测试中，启动 4 个进程进行并行压缩时，处理速度可以提高大约 40%。理想状态下，两个核心应该可以得到 100% 的性能提升，因此 40% 的成绩比我预想的要低。当然，这也说明在实际的处理中，有很大一部分输入输出的开销是无法通过增加核心数量来弥补的。

注意瓶颈

在这里需要注意的是，瓶颈到底发生在哪里。

多核环境是将任务分配给多个 CPU 来提高单位时间处理能力的一种手段。也就是说，只有当 CPU 能力成为处理瓶颈时，这一手段才能有效改善性能。

然而，一般的多核计算机上，尽管搭载了多个 CPU，但其他设备，如内存、磁盘、网络设备等是共享的。当处理的瓶颈存在于 CPU 之外的这些地方时，即便投入多个核心，也丝毫无法改善性能。

在这种情况下，我们需要的不仅是多个 CPU，而是由多台“计算机”组成的分布式计算环境。分布式计算也是一项相当重要的技术，我们在这里不再过多赘述。

阿姆达尔定律

阿姆达尔定律是一个估算通过多核并行能够获得多少性能提升的经验法则，是由吉 · 阿姆达尔（Gene Amdahl，1922 ～ ）提出的，它的内容是：

（通过并行计算所获得的）系统性能提升效果，会随着无法并行的部分而产生饱和。

正如在刚才 xargs 的示例中所遇到的，即便是多核计算机，一般也只有一个输入输出控制器，而这个部分无法获得并行计算所带来的效果，很容易成为瓶颈。

而且，当数据之间存在相互依赖关系时，在所依赖的数据准备好之前，即便有空闲的核心也无法开始工作，这也会成为瓶颈。

综上所述，大多数的处理都不具备“只要增加核心就能够提高速度”这一良好的性质，这一点与在 CPU 内部实现流水线的艰辛似乎存在一定的相似性。

根据阿姆达尔定律，并行化之后的速度提升比例可以通过图 8 的公式来估算。假设 N 为无穷大，速度的提升最多也只能达到：

1 / (1 - P）

图 8 并行化后速度提升比例的公式

例如，即便在 P 为 90% 这一非常理想的情况下，无论如何提高并行程度，整体上最多能够获得的性能提升也无法超过基准的 10 倍。这是因为，“(1 - P)”所代表的无法并行化的部分成为了瓶颈，使得并行化效果存在极限。

多核编译

像我们这些工程师在用电脑时，最消耗 CPU 的工作恐怕就是编译了。当然，编译也伴随一定的输入输出操作，但预处理、语法解析、优化、代码生成等操作对于 CPU 的开销是相当大的。

要编译一个文件，首先需要将 C 语言源文件（*.c）进行预处理（cpp）。cpp 会进行头文件（*.h）加载（#include）、宏定义（#define）、宏展开等操作。

cpp 的运行结果被送至编译器主体（ccl）。ccl 会进行语句、语法解析和代码优化，并输出汇编文件（*.s）。随后，汇编器会将汇编文件转换为对象文件（*.o），也有些编译器可以不通过汇编器直接输出对象文件。

当每个 C 语言源文件都完成编译，并生成相应的对象文件之后，就可以启动连接器（ld）来生成最终的可执行文件了。连接器会将对象文件与各种库文件（静态链接库 *.a 和动态链接库 *.so）进行连接（某些情况下还会进行一些优化），并输出最终的可执行文件（图 9）。

图 9 C 语言编译流程

UNIX 的“make”工具中提供了一个正好可以用于多核的选项——“-j（jobs）”，通过这个选项可以设定同时执行的进程数量。例如：

# make -j4

就表示用 4 个线程进行并行编译。从过去的经验来看，-j 的设置应该略大于实际的核心数量为佳。

ccache

我们先放下多核的话题，说点别的。有一个叫做 ccache 的工具，可以有效提高编译的速度。ccache 是通过将编译结果进行缓存，来减少再次编译的工作量，从而提高编译速度的。

使用方法很简单，编译时在编译器名称前面加上 ccache 即可。例如：

# CC='ccache gcc' make -j4

这样就可以让再次编译时所需的时间大幅缩短。每次都指定的话比较麻烦，也可以一开始就写到 Makefile 中。

当源代码或者其所依赖的头文件等发生修改时，make 会重新执行编译。不过，源文件中也有很多行是和实际变更的部分无关的，而 ccache 会将（以函数为单位的）编译结果保存在主目录下的“.ccache”目录中，然后，在实际执行编译之前，与过去的编译结果进行比较，如果源代码的相应部分没有发生修改，则直接使用过去的编译结果。

在 CPU 中，缓存是高速化的一个重要手段，而在改善编译速度的场景中，也可以应用缓存技术。像这样，类似的手段出现在各种不同的场景中，的确是很有意思的事情。

distcc

还有其他一些改善编译速度的方法，例如 distcc 就是一种利用多台计算机来改善编译速度的工具。

和 ccache 一样，只要在编译器名称前面加上 distcc 就可以改善编译性能了。不过在此之前，需要先配置好用哪些计算机来执行编译操作。在下列配置文件中：

# ~/.distcc/hosts

填写用于执行编译的主机名（多个主机名之间用逗号分隔）。

当然，并不是随便填哪台主机都可以的。基本上，用于执行编译的主机应该是启动了 distccd 服务的主机，或者是可以通过 ssh 来登录的主机才行。启动 distccd 服务的主机直接填写主机名，可在 ssh 登录的主机前面加上一个“@”。当登录的用户名和本机不同时，需要在 @ 前面写上用户名。

通过 ssh 来执行会提高安全性（distccd 没有认证机制），但由于加密等带来的开销，编译性能会下降 25% 左右，因此用户需要在性能、安全性和易用性之间做出选择。

准备妥当之后，执行：

# CC='distcc gcc' make -j4

就可以实现分布式编译了。

distcc 的伟大之处在于，虽然是分布式编译，但无需拥有所有的头文件和库文件等完整的环境，只要（在同一个 CPU 下）安装了编译器，并能够运行 ssh 的主机，就可以很容易地实现分布式编译。之所以能够实现这一点，秘密在于预处理器和连接器是在本地执行的，而发送给远程主机的是已经完成预处理的文件。

编译性能测试

那么，通过使用上述这些手段，到底能够对编译性能带来多大的改善呢？我们来实际测试一下。

表 1 显示了运用各种手段后的测试结果，其中编译的对象是最新版的 Ruby 解释器。用于执行编译的是我那台有 些古老的爱机——ThinkPad X61 Core2 duo 2.2GHz（双核）。distcc 分布式编译使用的是一台 Quad-Core AMD Opteron 2.4GHz（四核）的计算机。

表1 编译性能测试

编译条件

编译时间（秒）

仅gcc -j1

18.464

仅gcc -j2

10.611

仅gcc -j4

10.823

仅gcc -j8

11.006

ccache -j1 20.874

ccache -j1（第2次）

0.454

distcc -j2

11.649

distcc -j4

7.138

distcc -j8

7.548

使用未经过任何优化的 gcc 进行编译时，整个编译过程需要约 18.5 秒。使用 make 的 -j 选项启动多个进程时，由于充分利用了两个核心，使得速度提高了 40% 以上。

ccache 首次执行时比通常情况还要慢一点，但由于编译结果被缓存起来，在删除对象文件之后，用完全相同的条件再次编译时，由于完全不需要执行实际的编译操作，只需要取出缓存的内容就可以完成处理，因此编译速度快得惊人。

distcc 的测试中只用了一台主机，在 make -j2 的情况下，由于 ssh 的开销较大，因此和本地执行相比性能改善不大，但如果设置更多的进程数量，执行时间就可以大大缩短。

小结

阿姆达尔定律指出，并行性是存在极限的，因此只靠多核无法解决所有的问题。但是大家应该能够看出，只要配合适当的编程技巧，还是能够比较容易地获得很好的效果。可以说，多核在将来还是颇有前途的。