Simon Arneaud 发布的文章

基本上所有正而八经的算法教材都会解释像 快速排序 quicksort 堆排序 heapsort 这样的排序算法有多快,但并不需要复杂的数学就能证明你可以逐渐趋近的速度有多快。

关于标记的一个严肃说明:

大多数计算机专业的科学家使用大写字母 O 标记来指代“趋近,直到到达一个常数比例因子”,这与数学专业所指代的意义是有所区别的。这里我使用的大 O 标记的含义与计算机教材所指相同,但至少不会和其他数学符号混用。

基于比较的排序

先来看个特例,即每次比较两个值大小的算法(快速排序、堆排序,及其它通用排序算法)。这种思想后续可以扩展至所有排序算法。

一个简单的最差情况下的计数角度

假设有 4 个互不相等的数,且顺序随机,那么,可以通过只比较一对数字完成排序吗?显然不能,证明如下:根据定义,要对该数组排序,需要按照某种顺序重新排列数字。换句话说,你需要知道用哪种排列方式?有多少种可能的排列?第一个数字可以放在四个位置中的任意一个,第二个数字可以放在剩下三个位置中的任意一个,第三个数字可以放在剩下两个位置中的任意一个,最后一个数字只有剩下的一个位置可选。这样,共有 4×3×2×1=4!=24 种排列可供选择。通过一次比较大小,只能产生两种可能的结果。如果列出所有的排列,那么“从小到大”排序对应的可能是第 8 种排列,按“从大到小”排序对应的可能是第 24 种排列,但无法知道什么时候需要的是其它 22 种排列。

通过 2 次比较,可以得到 2×2=4 种可能的结果,这仍然不够。只要比较的次数少于 5(对应 2 5 = 32 种输出),就无法完成 4 个随机次序的数字的排序。如果 W(N) 是最差情况下对 N 个不同元素进行排序所需要的比较次数,那么,

两边取以 2 为底的对数,得:

N! 的增长近似于 N<sup> N</sup> (参阅 Stirling 公式),那么,

这就是最差情况下从输出计数的角度得出的 O(N log N) 上限。

从信息论角度的平均状态的例子

使用一些信息论知识,就可以从上面的讨论中得到一个更有力的结论。下面,使用排序算法作为信息传输的编码器:

  1. 任取一个数,比如 15
  2. 从 4 个数字的排列列表中查找第 15 种排列
  3. 对这种排列运行排序算法,记录所有的“大”、“小”比较结果
  4. 用二进制编码发送比较结果
  5. 接收端重新逐步执行发送端的排序算法,需要的话可以引用发送端的比较结果
  6. 现在接收端就可以知道发送端如何重新排列数字以按照需要排序,接收端可以对排列进行逆算,得到 4 个数字的初始顺序
  7. 接收端在排列表中检索发送端的原始排列,指出发送端发送的是 15

确实,这有点奇怪,但确实可以。这意味着排序算法遵循着与编码方案相同的定律,包括理论所证明的不存在通用的数据压缩算法。算法中每次比较发送 1 比特的比较结果编码数据,根据信息论,比较的次数至少是能表示所有数据的二进制位数。更技术语言点,平均所需的最小比较次数是输入数据的香农熵,以比特为单位。熵是衡量信息等不可预测量的数学度量。

包含 N 个元素的数组,元素次序随机且无偏时的熵最大,其值为 log<sub> 2</sub>​ N! 个比特。这证明 O(N log N) 是一个基于比较的对任意输入排序的最优平均值。

以上都是理论说法,那么实际的排序算法如何做比较的呢?下面是一个数组排序所需比较次数均值的图。我比较的是理论值与快速排序及 Ford-Johnson 合并插入排序 的表现。后者设计目的就是最小化比较次数(整体上没比快速排序快多少,因为生活中相对于最大限度减少比较次数,还有更重要的事情)。又因为 合并插入排序 merge-insertion sort 是在 1959 年提出的,它一直在调整,以减少了一些比较次数,但图示说明,它基本上达到了最优状态。

一点点理论导出这么实用的结论,这感觉真棒!

小结

证明了:

  1. 如果数组可以是任意顺序,在最坏情况下至少需要 O(N log N) 次比较。
  2. 数组的平均比较次数最少是数组的熵,对随机输入而言,其值是 O(N log N)

注意,第 2 个结论允许基于比较的算法优于 O(N log N),前提是输入是低熵的(换言之,是部分可预测的)。如果输入包含很多有序的子序列,那么合并排序的性能接近 O(N)。如果在确定一个位之前,其输入是有序的,插入排序性能接近 O(N)。在最差情况下,以上算法的性能表现都不超出 O(N log N)

一般排序算法

基于比较的排序在实践中是个有趣的特例,但从理论上讲,计算机的 CMP 指令与其它指令相比,并没有什么特别之处。在下面两条的基础上,前面两种情形都可以扩展至任意排序算法:

  1. 大多数计算机指令有多于两个的输出,但输出的数量仍然是有限的。
  2. 一条指令有限的输出意味着一条指令只能处理有限的熵。

这给出了 O(N log N) 对应的指令下限。任何物理上可实现的计算机都只能在给定时间内执行有限数量的指令,所以算法的执行时间也有对应 O(N log N) 的下限。

什么是更快的算法?

一般意义上的 O(N log N) 下限,放在实践中来看,如果听人说到任何更快的算法,你要知道,它肯定以某种方式“作弊”了,其中肯定有圈套,即它不是一个可以处理任意大数组的通用排序算法。可能它是一个有用的算法,但最好看明白它字里行间隐含的东西。

一个广为人知的例子是 基数排序 radix sort 算法,它经常被称为 O(N) 排序算法,但它只能处理所有数字都能放入 k 比特的情况,所以实际上它的性能是 O(kN)

什么意思呢?假如你用的 8 位计算机,那么 8 个二进制位可以表示 2 8=256 个不同的数字,如果数组有上千个数字,那么其中必有重复。对有些应用而言这是可以的,但对有些应用就必须用 16 个二进制位来表示,16 个二进制位可以表示 2 16=65,536 个不同的数字。32 个二进制位可以表示 2 32=4,294,967,296 不同的数字。随着数组长度的增长,所需要的二进制位数也在增长。要表示 N 个不同的数字,需要 k ≥ log<sub> 2</sub>​ N 个二进制位。所以,只有允许数组中存在重复的数字时, O(kN) 才优于 O(N log N)

一般意义上输入数据的 O(N log N) 的性能已经说明了全部问题。这个讨论不那么有趣因为很少需要在 32 位计算机上对几十亿整数进行排序,如果有谁的需求超出了 64 位计算机的极限,他一定没有告诉别人


via: https://theartofmachinery.com/2019/01/05/sorting_is_nlogn.html

作者:Simon Arneaud 选题:lujun9972 译者:silentdawn-zz 校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出

我的大部分工作都涉及到部署软件系统,这意味着我需要花费很多时间来解决以下问题:

  • 这个软件可以在原开发者的机器上工作,但是为什么不能在我这里运行?
  • 这个软件昨天可以在我的机器上工作,但是为什么今天就不行?

这是一种调试的类型,但是与一般的软件调试有所不同。一般的调试通常只关心代码的逻辑,但是在软件部署中的调试关注的是程序的代码和它所在的运行环境之间的相互影响。即便问题的根源是代码的逻辑错误,但软件显然可以在别的机器上运行的事实意味着这类问题与运行环境密切相关。

所以,在软件部署过程中,我没有使用传统的调试工具(例如 gdb),而是选择了其它工具进行调试。我最喜欢的用来解决“为什么这个软件无法在这台机器上运行?”这类问题的工具就是 strace

什么是 strace?

strace 是一个用来“追踪系统调用”的工具。它主要是一个 Linux 工具,但是你也可以在其它系统上使用类似的工具(例如 DTracektrace)。

它的基本用法非常简单。只需要在 strace 后面跟上你需要运行的命令,它就会显示出该命令触发的所有系统调用(你可能需要先安装好 strace):

$ strace echo Hello
...Snip lots of stuff...
write(1, "Hello\n", 6)                  = 6
close(1)                                = 0
close(2)                                = 0
exit_group(0)                           = ?
+++ exited with 0 +++

这些系统调用都是什么?它们就像是操作系统内核提供的 API。很久以前,软件拥有直接访问硬件的权限。如果软件需要在屏幕上显示一些东西,它将会与视频硬件的端口和内存映射寄存器纠缠不清。当多任务操作系统变得流行以后,这就导致了混乱的局面,因为不同的应用程序将“争夺”硬件,并且一个应用程序的错误可能致使其它应用程序崩溃,甚至导致整个系统崩溃。所以 CPU 开始支持多种不同的特权模式(或者称为“保护环”)。它们让操作系统内核在具有完全硬件访问权限的最高特权模式下运行,于此同时,其它在低特权模式下运行的应用程序必须通过向内核发起系统调用才能够与硬件进行交互。

在二进制级别上,发起系统调用相比简单的函数调用有一些区别,但是大部分程序都使用标准库提供的封装函数。例如,POSIX C 标准库包含一个 write() 函数,该函数包含用于进行 write 系统调用的所有与硬件体系结构相关的代码。

简单来说,一个应用程序与其环境(计算机系统)的交互都是通过系统调用来完成的。所以当软件在一台机器上可以工作但是在另一台机器无法工作的时候,追踪系统调用是一个很好的查错方法。具体地说,你可以通过追踪系统调用分析以下典型操作:

  • 控制台输入与输出 (IO)
  • 网络 IO
  • 文件系统访问以及文件 IO
  • 进程/线程生命周期管理
  • 原始内存管理
  • 访问特定的设备驱动

什么时候可以使用 strace?

理论上,strace 适用于任何用户空间程序,因为所有的用户空间程序都需要进行系统调用。strace 对于已编译的低级程序最有效果,但如果你可以避免运行时环境和解释器带来的大量额外输出,则仍然可以与 Python 等高级语言程序一起使用。

当软件在一台机器上正常工作,但在另一台机器上却不能正常工作,同时抛出了有关文件、权限或者不能运行某某命令等模糊的错误信息时,strace 往往能大显身手。不幸的是,它不能诊断高等级的问题,例如数字证书验证错误等。这些问题通常需要组合使用 strace(有时候是 ltrace)和其它高级工具(例如使用 openssl 命令行工具调试数字证书错误)。

本文中的示例基于独立的服务器,但是对系统调用的追踪通常也可以在更复杂的部署平台上完成,仅需要找到合适的工具。

一个简单的例子

假设你正在尝试运行一个叫做 foo 的服务器应用程序,但是发生了以下情况:

$ foo
Error opening configuration file: No such file or directory

显然,它没有找到你已经写好的配置文件。之所以会发生这种情况,是因为包管理工具有时候在编译应用程序时指定了自定义的路径,所以你应当遵循特定发行版提供的安装指南。如果错误信息告诉你正确的配置文件应该在什么地方,你就可以在几秒钟内解决这个问题,但如果没有告诉你呢?你该如何找到正确的路径?

如果你有权访问源代码,则可以通过阅读源代码来解决问题。这是一个好的备用计划,但不是最快的解决方案。你还可以使用类似 gdb 的单步调试器来观察程序的行为,但使用专门用于展示程序与系统环境交互作用的工具 strace 更加有效。

一开始, strace 产生的大量输出可能会让你不知所措,幸好你可以忽略其中大部分的无用信息。我经常使用 -o 参数把输出的追踪结果保存到单独的文件里:

$ strace -o /tmp/trace foo
Error opening configuration file: No such file or directory
$ cat /tmp/trace
execve("foo", ["foo"], 0x7ffce98dc010 /* 16 vars */) = 0
brk(NULL)                               = 0x56363b3fb000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=25186, ...}) = 0
mmap(NULL, 25186, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f2f12cf1000
close(3)                                = 0
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\260A\2\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=1824496, ...}) = 0
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f2f12cef000
mmap(NULL, 1837056, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7f2f12b2e000
mprotect(0x7f2f12b50000, 1658880, PROT_NONE) = 0
mmap(0x7f2f12b50000, 1343488, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x22000) = 0x7f2f12b50000
mmap(0x7f2f12c98000, 311296, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x16a000) = 0x7f2f12c98000
mmap(0x7f2f12ce5000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1b6000) = 0x7f2f12ce5000
mmap(0x7f2f12ceb000, 14336, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7f2f12ceb000
close(3)                                = 0
arch_prctl(ARCH_SET_FS, 0x7f2f12cf0500) = 0
mprotect(0x7f2f12ce5000, 16384, PROT_READ) = 0
mprotect(0x56363b08b000, 4096, PROT_READ) = 0
mprotect(0x7f2f12d1f000, 4096, PROT_READ) = 0
munmap(0x7f2f12cf1000, 25186)           = 0
openat(AT_FDCWD, "/etc/foo/config.json", O_RDONLY) = -1 ENOENT (No such file or directory)
dup(2)                                  = 3
fcntl(3, F_GETFL)                       = 0x2 (flags O_RDWR)
brk(NULL)                               = 0x56363b3fb000
brk(0x56363b41c000)                     = 0x56363b41c000
fstat(3, {st_mode=S_IFCHR|0620, st_rdev=makedev(0x88, 0x8), ...}) = 0
write(3, "Error opening configuration file"..., 60) = 60
close(3)                                = 0
exit_group(1)                           = ?
+++ exited with 1 +++

strace 输出的第一页通常是低级的进程启动过程。(你可以看到很多 mmapmprotectbrk 调用,这是用来分配原始内存和映射动态链接库的。)实际上,在查找错误时,最好从下往上阅读 strace 的输出。你可以看到 write 调用在最后返回了错误信息。如果你向上找,你将会看到第一个失败的系统调用是 openat,它在尝试打开 /etc/foo/config.json 时抛出了 ENOENT (“No such file or directory”)的错误。现在我们已经知道了配置文件应该放在哪里。

这是一个简单的例子,但我敢说在 90% 的情况下,使用 strace 进行调试不需要更多复杂的工作。以下是完整的调试步骤:

  1. 从程序中获得含糊不清的错误信息
  2. 使用 strace 运行程序
  3. 在输出中找到错误信息
  4. 往前追溯并找到第一个失败的系统调用

第四步中的系统调用很可能向你显示出问题所在。

小技巧

在开始更加复杂的调试之前,这里有一些有用的调试技巧帮助你高效使用 strace

man 是你的朋友

在很多 *nix 操作系统中,你可以通过 man syscalls 查看系统调用的列表。你将会看到类似于 brk(2) 之类的东西,这意味着你可以通过运行 man 2 brk 得到与此相关的更多信息。

一个小问题:man 2 fork 会显示出在 GNU libc 里封装的 fork() 手册页,而 fork() 现在实际上是由 clone 系统调用实现的。fork 的语义与 clone 相同,但是如果我写了一个含有 fork() 的程序并使用 strace 去调试它,我将找不到任何关于 fork 调用的信息,只能看到 clone 调用。如果将源代码与 strace 的输出进行比较的时候,像这种问题会让人感到困惑。

使用 -o 将输出保存到文件

strace 可以生成很多输出,所以将输出保存到单独的文件是很有帮助的(就像上面的例子一样)。它还能够在控制台中避免程序自身的输出与 strace 的输出发生混淆。

使用 -s 查看更多的参数

你可能已经注意到,错误信息的第二部分没有出现在上面的例子中。这是因为 strace 默认仅显示字符串参数的前 32 个字节。如果你需要捕获更多参数,请向 strace 追加类似于 -s 128 之类的参数。

-y 使得追踪文件或套接字更加容易

“一切皆文件”意味着 *nix 系统通过文件描述符进行所有 IO 操作,不管是真实的文件还是通过网络或者进程间管道。这对于编程而言是很方便的,但是在追踪系统调用时,你将很难分辨出 readwrite 的真实行为。

-y 参数使 strace 在注释中注明每个文件描述符的具体指向。

使用 -p 附加到正在运行的进程中

正如我们将在后面的例子中看到的,有时候你想追踪一个正在运行的程序。如果你知道这个程序的进程号为 1337 (可以通过 ps 查询),则可以这样操作:

$ strace -p 1337
...system call trace output...

你可能需要 root 权限才能运行。

使用 -f 追踪子进程

strace 默认只追踪一个进程。如果这个进程产生了一个子进程,你将会看到创建子进程的系统调用(一般是 clone),但是你看不到子进程内触发的任何调用。

如果你认为在子进程中存在错误,则需要使用 -f 参数启用子进程追踪功能。这样做的缺点是输出的内容会让人更加困惑。当追踪一个进程时,strace 显示的是单个调用事件流。当追踪多个进程的时候,你将会看到以 <unfinished ...> 开始的初始调用,接着是一系列针对其它线程的调用,最后才出现以 <... foocall resumed> 结束的初始调用。此外,你可以使用 -ff 参数将所有的调用分离到不同的文件中(查看 strace 手册 获取更多信息)。

使用 -e 进行过滤

正如你所看到的,默认的追踪输出是所有的系统调用。你可以使用 -e 参数过滤你需要追踪的调用(查看 strace 手册)。这样做的好处是运行过滤后的 strace 比起使用 grep 进行二次过滤要更快。老实说,我大部分时间都不会被打扰。

并非所有的错误都是不好的

一个简单而常用的例子是一个程序在多个位置搜索文件,例如 shell 搜索哪个 bin/ 目录包含可执行文件:

$ strace sh -c uname
...
stat("/home/user/bin/uname", 0x7ffceb817820) = -1 ENOENT (No such file or directory)
stat("/usr/local/bin/uname", 0x7ffceb817820) = -1 ENOENT (No such file or directory)
stat("/usr/bin/uname", {st_mode=S_IFREG|0755, st_size=39584, ...}) = 0
...

“错误信息之前的最后一次失败调用”这种启发式方法非常适合于查找错误。无论如何,自下而上地查找是有道理的。

C 编程指南非常有助于理解系统调用

标准 C 库函数调用不属于系统调用,但它们仅是系统调用之上的唯一一个薄层。所以如果你了解(甚至只是略知一二)如何使用 C 语言,那么阅读系统调用追踪信息就非常容易。例如,如果你在调试网络系统调用,你可以尝试略读 Beej 经典的《网络编程指南》

一个更复杂的调试例子

就像我说的那样,简单的调试例子表现了我在大部分情况下如何使用 strace。然而,有时候需要一些更加细致的工作,所以这里有一个稍微复杂(且真实)的例子。

bcron 是一个任务调度器,它是经典 *nix cron 守护程序的另一种实现。它已经被安装到一台服务器上,但是当有人尝试编辑作业时间表时,发生了以下情况:

# crontab -e -u logs
bcrontab: Fatal: Could not create temporary file

好的,现在 bcron 尝试写入一些文件,但是它失败了,也没有告诉我们原因。以下是 strace 的输出:

# strace -o /tmp/trace crontab -e -u logs
bcrontab: Fatal: Could not create temporary file
# cat /tmp/trace
...
openat(AT_FDCWD, "bcrontab.14779.1573691864.847933", O_RDONLY) = 3
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f82049b4000
read(3, "#Ansible: logsagg\n20 14 * * * lo"..., 8192) = 150
read(3, "", 8192)                       = 0
munmap(0x7f82049b4000, 8192)            = 0
close(3)                                = 0
socket(AF_UNIX, SOCK_STREAM, 0)         = 3
connect(3, {sa_family=AF_UNIX, sun_path="/var/run/bcron-spool"}, 110) = 0
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f82049b4000
write(3, "156:Slogs\0#Ansible: logsagg\n20 1"..., 161) = 161
read(3, "32:ZCould not create temporary f"..., 8192) = 36
munmap(0x7f82049b4000, 8192)            = 0
close(3)                                = 0
write(2, "bcrontab: Fatal: Could not creat"..., 49) = 49
unlink("bcrontab.14779.1573691864.847933") = 0
exit_group(111)                         = ?
+++ exited with 111 +++

在程序结束之前有一个 write 的错误信息,但是这次有些不同。首先,在此之前没有任何相关的失败系统调用。其次,我们看到这个错误信息是由 read 从别的地方读取而来的。这看起来像是真正的错误发生在别的地方,而 bcrontab 只是在转播这些信息。

如果你查阅了 man 2 read,你将会看到 read 的第一个参数 (3) 是一个文件描述符,这是 *nix 操作系统用于所有 IO 操作的句柄。你该如何知道文件描述符 3 代表什么?在这种情况下,你可以使用 -y 参数运行 strace(如上文所述),它将会在注释里告诉你文件描述符的具体指向,但是了解如何从上面这种输出中分析追踪结果是很有用的。

一个文件描述符可以来自于许多系统调用之一(这取决于它是用于控制台、网络套接字还是真实文件等的描述符),但不论如何,我们都可以搜索返回值为 3 的系统调用(例如,在 strace 的输出中查找 =3)。在这次 strace 中可以看到有两个这样的调用:最上面的 openat 以及中间的 socketopenat 打开一个文件,但是紧接着的 close(3) 表明其已经被关闭。(注意:文件描述符可以在打开并关闭后重复使用。)所以 socket 调用才是与此相关的(它是在 read 之前的最后一个),这告诉我们 brcontab 正在与一个网络套接字通信。在下一行,connect 表明文件描述符 3 是一个连接到 /var/run/bcron-spool 的 Unix 域套接字。

因此,我们需要弄清楚 Unix 套接字的另一侧是哪个进程在监听。有两个巧妙的技巧适用于在服务器部署中调试。一个是使用 netstat 或者较新的 ss。这两个命令都描述了当前系统中活跃的网络套接字,使用 -l 参数可以显示出处于监听状态的套接字,而使用 -p 参数可以得到正在使用该套接字的程序信息。(它们还有更多有用的选项,但是这两个已经足够完成工作了。)

# ss -pl | grep /var/run/bcron-spool
u_str LISTEN 0   128   /var/run/bcron-spool 1466637   * 0   users:(("unixserver",pid=20629,fd=3))

这告诉我们 /var/run/bcron-spool 套接字的监听程序是 unixserver 这个命令,它的进程 ID 为 20629。(巧合的是,这个程序也使用文件描述符 3 去连接这个套接字。)

第二个常用的工具就是使用 lsof 查找相同的信息。它可以列出当前系统中打开的所有文件(或文件描述符)。或者,我们可以得到一个具体文件的信息:

# lsof /var/run/bcron-spool
COMMAND   PID   USER  FD  TYPE  DEVICE              SIZE/OFF  NODE    NAME
unixserve 20629 cron  3u  unix  0x000000005ac4bd83  0t0       1466637 /var/run/bcron-spool type=STREAM

进程 20629 是一个常驻进程,所以我们可以使用 strace -o /tmp/trace -p 20629 去查看该进程的系统调用。如果我们在另一个终端尝试编辑 cron 的计划任务表,就可以在错误发生时捕获到以下信息:

accept(3, NULL, NULL)                   = 4
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7faa47c44810) = 21181
close(4)                                = 0
accept(3, NULL, NULL)                   = ? ERESTARTSYS (To be restarted if SA_RESTART is set)
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=21181, si_uid=998, si_status=0, si_utime=0, si_stime=0} ---
wait4(0, [{WIFEXITED(s) && WEXITSTATUS(s) == 0}], WNOHANG|WSTOPPED, NULL) = 21181
wait4(0, 0x7ffe6bc36764, WNOHANG|WSTOPPED, NULL) = -1 ECHILD (No child processes)
rt_sigaction(SIGCHLD, {sa_handler=0x55d244bdb690, sa_mask=[CHLD], sa_flags=SA_RESTORER|SA_RESTART, sa_restorer=0x7faa47ab9840}, {sa_handler=0x55d244bdb690, sa_mask=[CHLD], sa_flags=SA_RESTORER|SA_RESTART, sa_restorer=0x7faa47ab9840}, 8) = 0
rt_sigreturn({mask=[]})                 = 43
accept(3, NULL, NULL)                   = 4
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7faa47c44810) = 21200
close(4)                                = 0
accept(3, NULL, NULL)                   = ? ERESTARTSYS (To be restarted if SA_RESTART is set)
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=21200, si_uid=998, si_status=111, si_utime=0, si_stime=0} ---
wait4(0, [{WIFEXITED(s) && WEXITSTATUS(s) == 111}], WNOHANG|WSTOPPED, NULL) = 21200
wait4(0, 0x7ffe6bc36764, WNOHANG|WSTOPPED, NULL) = -1 ECHILD (No child processes)
rt_sigaction(SIGCHLD, {sa_handler=0x55d244bdb690, sa_mask=[CHLD], sa_flags=SA_RESTORER|SA_RESTART, sa_restorer=0x7faa47ab9840}, {sa_handler=0x55d244bdb690, sa_mask=[CHLD], sa_flags=SA_RESTORER|SA_RESTART, sa_restorer=0x7faa47ab9840}, 8) = 0
rt_sigreturn({mask=[]})                 = 43
accept(3, NULL, NULL

(最后一个 accept 调用没有在追踪期间完成。)不幸的是,这次追踪没有包含我们想要的错误信息。我们没有观察到 bcrontan 往套接字发送或接受的任何信息。然而,我们看到了很多进程管理操作(clonewait4SIGCHLD,等等)。这个进程产生了子进程,我们猜测真实的工作是由子进程完成的。如果我们想捕获子进程的追踪信息,就必须往 strace 追加 -f 参数。以下是我们最终使用 strace -f -o /tmp/trace -p 20629 找到的错误信息:

21470 openat(AT_FDCWD, "tmp/spool.21470.1573692319.854640", O_RDWR|O_CREAT|O_EXCL, 0600) = -1 EACCES (Permission denied)
21470 write(1, "32:ZCould not create temporary f"..., 36) = 36
21470 write(2, "bcron-spool[21470]: Fatal: logs:"..., 84) = 84
21470 unlink("tmp/spool.21470.1573692319.854640") = -1 ENOENT (No such file or directory)
21470 exit_group(111)                   = ?
21470 +++ exited with 111 +++

现在我们知道了进程 ID 21470 在尝试创建文件 tmp/spool.21470.1573692319.854640 (相对于当前的工作目录)时得到了一个没有权限的错误。如果我们知道当前的工作目录,就可以得到完整路径并能指出为什么该进程无法在此处创建临时文件。不幸的是,这个进程已经退出了,所以我们不能使用 lsof -p 21470 去找出当前的工作目录,但是我们可以往前追溯,查找进程 ID 21470 使用哪个系统调用改变了它的工作目录。这个系统调用是 chdir(可以在搜索引擎很轻松地找到)。以下是一直往前追溯到服务器进程 ID 20629 的结果:

20629 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7faa47c44810) = 21470
...
21470 execve("/usr/sbin/bcron-spool", ["bcron-spool"], 0x55d2460807e0 /* 27 vars */) = 0
...
21470 chdir("/var/spool/cron")          = 0
...
21470 openat(AT_FDCWD, "tmp/spool.21470.1573692319.854640", O_RDWR|O_CREAT|O_EXCL, 0600) = -1 EACCES (Permission denied)
21470 write(1, "32:ZCould not create temporary f"..., 36) = 36
21470 write(2, "bcron-spool[21470]: Fatal: logs:"..., 84) = 84
21470 unlink("tmp/spool.21470.1573692319.854640") = -1 ENOENT (No such file or directory)
21470 exit_group(111)                   = ?
21470 +++ exited with 111 +++

(如果你在这里迷糊了,你可能需要阅读 我之前有关 *nix 进程管理和 shell 的文章

现在 PID 为 20629 的服务器进程没有权限在 /var/spool/cron/tmp/spool.21470.1573692319.854640 创建文件。最可能的原因就是典型的 *nix 文件系统权限设置。让我们检查一下:

# ls -ld /var/spool/cron/tmp/
drwxr-xr-x 2 root root 4096 Nov  6 05:33 /var/spool/cron/tmp/
# ps u -p 20629
USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
cron     20629  0.0  0.0   2276   752 ?        Ss   Nov14   0:00 unixserver -U /var/run/bcron-spool -- bcron-spool

这就是问题所在!这个服务进程以 cron 用户运行,但是只有 root 用户才有向 /var/spool/cron/tmp/ 目录写入的权限。一个简单 chown cron /var/spool/cron/tmp/ 命令就能让 bcron 正常工作。(如果不是这个问题,那么下一个最有可能的怀疑对象是诸如 SELinux 或者 AppArmor 之类的内核安全模块,因此我将会使用 dmesg 检查内核日志。)

总结

最初,系统调用追踪可能会让人不知所措,但是我希望我已经证明它们是调试一整套常见部署问题的快速方法。你可以设想一下尝试用单步调试器去调试多进程的 bcron 问题。

通过一连串的系统调用解决问题是需要练习的,但正如我说的那样,在大多数情况下,我只需要使用 strace 从下往上追踪并查找错误。不管怎样,strace 节省了我很多的调试时间。我希望这也对你有所帮助。


via: https://theartofmachinery.com/2019/11/14/deployment_debugging_strace.html

作者:Simon Arneaud 选题:lujun9972 译者:hanwckf 校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出

早在 2015 年,Brian Will 撰写了一篇有挑衅性的博客:面向对象编程:一个灾难故事。他随后发布了一个名为面向对象编程很糟糕的视频,该视频更加详细。

我建议你花些时间观看视频,下面是我的一段总结:

OOP 的柏拉图式理想是一堆相互解耦的对象,它们彼此之间发送无状态消息。没有人真的像这样制作软件,Brian 指出这甚至没有意义:对象需要知道向哪个对象发送消息,这意味着它们需要相互引用。该视频大部分讲述的是这样一个痛点:人们试图将对象耦合以实现控制流,同时假装它们是通过设计解耦的。

总的来说,他的想法与我自己的 OOP 经验产生了共鸣:对象没有问题,但是我一直不满意的是面向对象建模程序控制流,并且试图使代码“正确地”面向对象似乎总是在创建不必要的复杂性。

有一件事我认为他无法完全解释。他直截了当地说“封装没有作用”,但在脚注后面加上“在细粒度的代码级别”,并继续承认对象有时可以奏效,并且在库和文件级别封装是可以的。但是他没有确切解释为什么有时会奏效,有时却没有奏效,以及如何和在何处划清界限。有人可能会说这使他的 “OOP 不好”的说法有缺陷,但是我认为他的观点是正确的,并且可以在根本状态和偶发状态之间划清界限。

如果你以前从未听说过“ 根本 essential ”和“ 偶发 accidental ”这两个术语的使用,那么你应该阅读 Fred Brooks 的经典文章《没有银弹》。(顺便说一句,他写了许多很棒的有关构建软件系统的文章。)我以前曾写过关于根本和偶发的复杂性的文章,这里有一个简短的摘要:软件是复杂的。部分原因是因为我们希望软件能够解决混乱的现实世界问题,因此我们将其称为“根本复杂性”。“偶发复杂性”是所有其它的复杂性,因为我们正尝试使用硅和金属来解决与硅和金属无关的问题。例如,对于大多数程序而言,用于内存管理或在内存与磁盘之间传输数据或解析文本格式的代码都是“偶发的复杂性”。

假设你正在构建一个支持多个频道的聊天应用。消息可以随时到达任何频道。有些频道特别有趣,当有新消息传入时,用户希望得到通知。而其他频道静音:消息被存储,但用户不会受到打扰。你需要跟踪每个频道的用户首选设置。

一种实现方法是在频道和频道设置之间使用 映射 map (也称为哈希表、字典或关联数组)。注意,映射是 Brian Will 所说的可以用作对象的抽象数据类型(ADT)。

如果我们有一个调试器并查看内存中的映射对象,我们将看到什么?我们当然会找到频道 ID 和频道设置数据(或至少指向它们的指针)。但是我们还会找到其它数据。如果该映射是使用红黑树实现的,我们将看到带有红/黑标签和指向其他节点的指针的树节点对象。与频道相关的数据是根本状态,而树节点是偶发状态。不过,请注意以下几点:该映射有效地封装了它的偶发状态 —— 你可以用 AVL 树实现的另一个映射替换该映射,并且你的聊天程序仍然可以使用。另一方面,映射没有封装根本状态(仅使用 get()set() 方法访问数据并不是封装)。事实上,映射与根本状态是尽可能不可知的,你可以使用基本相同的映射数据结构来存储与频道或通知无关的其他映射。

这就是映射 ADT 如此成功的原因:它封装了偶发状态,并与根本状态解耦。如果你思考一下,Brian 用封装描述的问题就是尝试封装根本状态。其他描述的好处是封装偶发状态的好处。

要使整个软件系统都达到这一理想状况相当困难,但扩展开来,我认为它看起来像这样:

  • 没有全局的可变状态
  • 封装了偶发状态(在对象或模块或以其他任何形式)
  • 无状态偶发复杂性封装在单独函数中,与数据解耦
  • 使用诸如依赖注入之类的技巧使输入和输出变得明确
  • 组件可由易于识别的位置完全拥有和控制

其中有些违反了我很久以来的直觉。例如,如果你有一个数据库查询函数,如果数据库连接处理隐藏在该函数内部,并且唯一的参数是查询参数,那么接口会看起来会更简单。但是,当你使用这样的函数构建软件系统时,协调数据库的使用实际上变得更加复杂。组件不仅以自己的方式做事,而且还试图将自己所做的事情隐藏为“实现细节”。数据库查询需要数据库连接这一事实从来都不是实现细节。如果无法隐藏某些内容,那么显露它是更合理的。

我对将面向对象编程和函数式编程放在对立的两极非常警惕,但我认为从函数式编程进入面向对象编程的另一极端是很有趣的:OOP 试图封装事物,包括无法封装的根本复杂性,而纯函数式编程往往会使事情变得明确,包括一些偶发复杂性。在大多数时候,这没什么问题,但有时候(比如在纯函数式语言中构建自我指称的数据结构)设计更多的是为了函数编程,而不是为了简便(这就是为什么 Haskell 包含了一些“ 逃生出口 escape hatches )。我之前写过一篇所谓“ 弱纯性 weak purity ”的中间立场

Brian 发现封装对更大规模有效,原因有几个。一个是,由于大小的原因,较大的组件更可能包含偶发状态。另一个是“偶发”与你要解决的问题有关。从聊天程序用户的角度来看,“偶发的复杂性”是与消息、频道和用户等无关的任何事物。但是,当你将问题分解为子问题时,更多的事情就变得“根本”。例如,在解决“构建聊天应用”问题时,可以说频道名称和频道 ID 之间的映射是偶发的复杂性,而在解决“实现 getChannelIdByName() 函数”子问题时,这是根本复杂性。因此,封装对于子组件的作用比对父组件的作用要小。

顺便说一句,在视频的结尾,Brian Will 想知道是否有任何语言支持无法访问它们所作用的范围的匿名函数。D 语言可以。 D 中的匿名 Lambda 通常是闭包,但是如果你想要的话,也可以声明匿名无状态函数:

import std.stdio;

void main()
{
    int x = 41;

    // Value from immediately executed lambda
    auto v1 = () {
        return x + 1;
    }();
    writeln(v1);

    // Same thing
    auto v2 = delegate() {
        return x + 1;
    }();
    writeln(v2);

    // Plain functions aren't closures
    auto v3 = function() {
        // Can't access x
        // Can't access any mutable global state either if also marked pure
        return 42;
    }();
    writeln(v3);
}

via: https://theartofmachinery.com/2019/10/13/oop_and_essential_state.html

作者:Simon Arneaud 选题:lujun9972 译者:geekpi 校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出

在几个月前的一篇文章里,我曾说过“有个一个流行的传言,const 有助于编译器优化 C 和 C++ 代码”。我觉得我需要解释一下,尤其是曾经我自己也以为这是显然对的。我将会用一些理论并构造一些例子来论证,然后在一个真实的代码库 Sqlite 上做一些实验和基准测试。

一个简单的测试

让我们从一个最简单、最明显的例子开始,以前认为这是一个 const 让 C 代码跑得更快的例子。首先,假设我们有如下两个函数声明:

void func(int *x);
void constFunc(const int *x);

然后假设我们如下两份代码:

void byArg(int *x)
{
  printf("%d\n", *x);
  func(x);
  printf("%d\n", *x);
}

void constByArg(const int *x)
{
  printf("%d\n", *x);
  constFunc(x);
  printf("%d\n", *x);
}

调用 printf() 时,CPU 会通过指针从 RAM 中取得 *x 的值。很显然,constByArg() 会稍微快一点,因为编译器知道 *x 是常量,因此不需要在调用 constFunc() 之后再次获取它的值。它仅是打印相同的东西。没问题吧?让我们来看下 GCC 在如下编译选项下生成的汇编代码:

$ gcc -S -Wall -O3 test.c
$ view test.s

以下是函数 byArg() 的完整汇编代码:

byArg:
.LFB23:
    .cfi_startproc
    pushq   %rbx
    .cfi_def_cfa_offset 16
    .cfi_offset 3, -16
    movl    (%rdi), %edx
    movq    %rdi, %rbx
    leaq    .LC0(%rip), %rsi
    movl    $1, %edi
    xorl    %eax, %eax
    call    __printf_chk@PLT
    movq    %rbx, %rdi
    call    func@PLT  # constFoo 中唯一不同的指令
    movl    (%rbx), %edx
    leaq    .LC0(%rip), %rsi
    xorl    %eax, %eax
    movl    $1, %edi
    popq    %rbx
    .cfi_def_cfa_offset 8
    jmp __printf_chk@PLT
    .cfi_endproc

函数 byArg() 和函数 constByArg() 生成的汇编代码中唯一的不同之处是 constByArg() 有一句汇编代码 call constFunc@PLT,这正是源代码中的调用。关键字 const 本身并没有造成任何字面上的不同。

好了,这是 GCC 的结果。或许我们需要一个更聪明的编译器。Clang 会有更好的表现吗?

$ clang -S -Wall -O3 -emit-llvm test.c
$ view test.ll

这是 IR 代码(LCTT 译注:LLVM 的中间语言)。它比汇编代码更加紧凑,所以我可以把两个函数都导出来,让你可以看清楚我所说的“除了调用外,没有任何字面上的不同”是什么意思:

; Function Attrs: nounwind uwtable
define dso_local void @byArg(i32*) local_unnamed_addr #0 {
  %2 = load i32, i32* %0, align 4, !tbaa !2
  %3 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %2)
  tail call void @func(i32* %0) #4
  %4 = load i32, i32* %0, align 4, !tbaa !2
  %5 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %4)
  ret void
}

; Function Attrs: nounwind uwtable
define dso_local void @constByArg(i32*) local_unnamed_addr #0 {
  %2 = load i32, i32* %0, align 4, !tbaa !2
  %3 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %2)
  tail call void @constFunc(i32* %0) #4
  %4 = load i32, i32* %0, align 4, !tbaa !2
  %5 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %4)
  ret void
}

某些有作用的东西

接下来是一组 const 能够真正产生作用的代码:

void localVar()
{
  int x = 42;
  printf("%d\n", x);
  constFunc(&x);
  printf("%d\n", x);
}

void constLocalVar()
{
  const int x = 42;  // 对本地变量使用 const
  printf("%d\n", x);
  constFunc(&x);
  printf("%d\n", x);
}

下面是 localVar() 的汇编代码,其中有两条指令在 constLocalVar() 中会被优化掉:

localVar:
.LFB25:
    .cfi_startproc
    subq    $24, %rsp
    .cfi_def_cfa_offset 32
    movl    $42, %edx
    movl    $1, %edi
    movq    %fs:40, %rax
    movq    %rax, 8(%rsp)
    xorl    %eax, %eax
    leaq    .LC0(%rip), %rsi
    movl    $42, 4(%rsp)
    call    __printf_chk@PLT
    leaq    4(%rsp), %rdi
    call    constFunc@PLT
    movl    4(%rsp), %edx  # 在 constLocalVar() 中没有
    xorl    %eax, %eax
    movl    $1, %edi
    leaq    .LC0(%rip), %rsi  # 在 constLocalVar() 中没有
    call    __printf_chk@PLT
    movq    8(%rsp), %rax
    xorq    %fs:40, %rax
    jne .L9
    addq    $24, %rsp
    .cfi_remember_state
    .cfi_def_cfa_offset 8
    ret
.L9:
    .cfi_restore_state
    call    __stack_chk_fail@PLT
    .cfi_endproc

在 LLVM 生成的 IR 代码中更明显一点。在 constLocalVar() 中,第二次调用 printf() 之前的 load 会被优化掉:

; Function Attrs: nounwind uwtable
define dso_local void @localVar() local_unnamed_addr #0 {
  %1 = alloca i32, align 4
  %2 = bitcast i32* %1 to i8*
  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %2) #4
  store i32 42, i32* %1, align 4, !tbaa !2
  %3 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 42)
  call void @constFunc(i32* nonnull %1) #4
  %4 = load i32, i32* %1, align 4, !tbaa !2
  %5 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %4)
  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %2) #4
  ret void
}

好吧,现在,constLocalVar() 成功的省略了对 *x 的重新读取,但是可能你已经注意到一些问题:localVar()constLocalVar() 在函数体中做了同样的 constFunc() 调用。如果编译器能够推断出 constFunc() 没有修改 constLocalVar() 中的 *x,那为什么不能推断出完全一样的函数调用也没有修改 localVar() 中的 *x

这个解释更贴近于为什么 C 语言的 const 不能作为优化手段的核心原因。C 语言的 const 有两个有效的含义:它可以表示这个变量是某个可能是常数也可能不是常数的数据的一个只读别名,或者它可以表示该变量是真正的常量。如果你移除了一个指向常量的指针的 const 属性并写入数据,那结果将是一个未定义行为。另一方面,如果是一个指向非常量值的 const 指针,将就没问题。

这份 constFunc() 的可能实现揭示了这意味着什么:

// x 是一个指向某个可能是常数也可能不是常数的数据的只读指针
void constFunc(const int *x)
{
  // local_var 是一个真正的常数
  const int local_var = 42;

  // C 语言规定的未定义行为
  doubleIt((int*)&local_var);
  // 谁知道这是不是一个未定义行为呢?
  doubleIt((int*)x);
}

void doubleIt(int *x)
{
  *x *= 2;
}

localVar() 传递给 constFunc() 一个指向非 const 变量的 const 指针。因为这个变量并非常量,constFunc() 可以撒个谎并强行修改它而不触发未定义行为。所以,编译器不能断定变量在调用 constFunc() 后仍是同样的值。在 constLocalVar() 中的变量是真正的常量,因此,编译器可以断定它不会改变 —— 因为在 constFunc() 去除变量的 const 属性并写入它会是一个未定义行为。

第一个例子中的函数 byArg()constByArg() 是没有可能优化的,因为编译器没有任何方法能知道 *x 是否真的是 const 常量。

补充(和题外话):相当多的读者已经正确地指出,使用 const int *x,该指针本身不是限定的常量,只是该数据被加个了别名,而 const int * const extra_const 是一个“双向”限定为常量的指针。但是因为指针本身的常量与别名数据的常量无关,所以结果是相同的。仅在 extra_const 指向使用 const 定义的对象时,*(int*const)extra_const = 0 才是未定义行为。(实际上,*(int*)extra_const = 0 也不会更糟。)因为它们之间的区别可以一句话说明白,一个是完全的 const 指针,另外一个可能是也可能不是常量本身的指针,而是一个可能是也可能不是常量的对象的只读别名,我将继续不严谨地引用“常量指针”。(题外话结束)

但是为什么不一致呢?如果编译器能够推断出 constLocalVar() 中调用的 constFunc() 不会修改它的参数,那么肯定也能继续在其他 constFunc() 的调用上实施相同的优化,是吗?并不。编译器不能假设 constLocalVar() 根本没有运行。如果不是这样(例如,它只是代码生成器或者宏的一些未使用的额外输出),constFunc() 就能偷偷地修改数据而不触发未定义行为。

你可能需要重复阅读几次上述说明和示例,但不要担心,它听起来很荒谬,它确实是正确的。不幸的是,对 const 变量进行写入是最糟糕的未定义行为:大多数情况下,编译器无法知道它是否将会是未定义行为。所以,大多数情况下,编译器看见 const 时必须假设它未来可能会被移除掉,这意味着编译器不能使用它进行优化。这在实践中是正确的,因为真实的 C 代码会在“深思熟虑”后移除 const

简而言之,很多事情都可以阻止编译器使用 const 进行优化,包括使用指针从另一内存空间接受数据,或者在堆空间上分配数据。更糟糕的是,在大部分编译器能够使用 const 进行优化的情况,它都不是必须的。例如,任何像样的编译器都能推断出下面代码中的 x 是一个常量,甚至都不需要 const

int x = 42, y = 0;
printf("%d %d\n", x, y);
y += x;
printf("%d %d\n", x, y);

总结,const 对优化而言几乎无用,因为:

  1. 除了特殊情况,编译器需要忽略它,因为其他代码可能合法地移除它
  2. 在 #1 以外的大多数例外中,编译器无论如何都能推断出该变量是常量

C++

如果你在使用 C++ 那么有另外一个方法让 const 能够影响到代码的生成:函数重载。你可以用 const 和非 const 的参数重载同一个函数,而非 const 版本的代码可能可以被优化(由程序员优化而不是编译器),减少某些拷贝或者其他事情。

void foo(int *p)
{
  // 需要做更多的数据拷贝
}

void foo(const int *p)
{
  // 不需要保护性的拷贝副本
}

int main()
{
  const int x = 42;
  // const 影响被调用的是哪一个版本的重载函数
  foo(&x);
  return 0;
}

一方面,我不认为这会在实际的 C++ 代码中大量使用。另一方面,为了导致差异,程序员需要假设编译器无法做出,因为它们不受语言保护。

用 Sqlite3 进行实验

有了足够的理论和例子。那么 const 在一个真正的代码库中有多大的影响呢?我将会在代码库 Sqlite(版本:3.30.0)上做一个测试,因为:

  • 它真正地使用了 const
  • 它不是一个简单的代码库(超过 20 万行代码)
  • 作为一个数据库,它包括了字符串处理、数学计算、日期处理等一系列内容
  • 它能够在绑定 CPU 的情况下进行负载测试

此外,作者和贡献者们已经进行了多年的性能优化工作,因此我能确定他们没有错过任何有显著效果的优化。

配置

我做了两份源码拷贝,并且正常编译其中一份。而对于另一份拷贝,我插入了这个特殊的预处理代码段,将 const 变成一个空操作:

#define const

(GNU) sed 可以将一些东西添加到每个文件的顶端,比如 sed -i '1i#define const' *.c *.h

在编译期间使用脚本生成 Sqlite 代码稍微有点复杂。幸运的是当 const 代码和非 const 代码混合时,编译器会产生了大量的提醒,因此很容易发现它并调整脚本来包含我的反 const 代码段。

直接比较编译结果毫无意义,因为任意微小的改变就会影响整个内存布局,这可能会改变整个代码中的指针和函数调用。因此,我用每个指令的二进制大小和汇编代码作为识别码(objdump -d libsqlite3.so.0.8.6)。举个例子,这个函数:

000000000005d570 <sqlite3_blob_read>:
   5d570:       4c 8d 05 59 a2 ff ff    lea    -0x5da7(%rip),%r8        # 577d0 <sqlite3BtreePayloadChecked>
   5d577:       e9 04 fe ff ff          jmpq   5d380 <blobReadWrite>
   5d57c:       0f 1f 40 00             nopl   0x0(%rax)

将会变成这样:

sqlite3_blob_read   7lea 5jmpq 4nopl

在编译时,我保留了所有 Sqlite 的编译设置。

分析编译结果

const 版本的 libsqlite3.so 的大小是 4,740,704 字节,大约比 4,736,712 字节的非 const 版本大了 0.1% 。在全部 1374 个导出函数(不包括类似 PLT 里的底层辅助函数)中,一共有 13 个函数的识别码不一致。

其中的一些改变是由于插入的预处理代码。举个例子,这里有一个发生了更改的函数(已经删去一些 Sqlite 特有的定义):

#define LARGEST_INT64  (0xffffffff|(((int64_t)0x7fffffff)<<32))
#define SMALLEST_INT64 (((int64_t)-1) - LARGEST_INT64)

static int64_t doubleToInt64(double r){
  /*
  ** Many compilers we encounter do not define constants for the
  ** minimum and maximum 64-bit integers, or they define them
  ** inconsistently.  And many do not understand the "LL" notation.
  ** So we define our own static constants here using nothing
  ** larger than a 32-bit integer constant.
  */
  static const int64_t maxInt = LARGEST_INT64;
  static const int64_t minInt = SMALLEST_INT64;

  if( r<=(double)minInt ){
    return minInt;
  }else if( r>=(double)maxInt ){
    return maxInt;
  }else{
    return (int64_t)r;
  }
}

删去 const 使得这些常量变成了 static 变量。我不明白为什么会有不了解 const 的人让这些变量加上 static。同时删去 staticconst 会让 GCC 再次认为它们是常量,而我们将得到同样的编译输出。由于类似这样的局部的 static const 变量,使得 13 个函数中有 3 个函数产生假的变化,但我一个都不打算修复它们。

Sqlite 使用了很多全局变量,而这正是大多数真正的 const 优化产生的地方。通常情况下,它们类似于将一个变量比较代替成一个常量比较,或者一个循环在部分展开的一步。(Radare toolkit 可以很方便的找出这些优化措施。)一些变化则令人失望。sqlite3ParseUri() 有 487 个指令,但 const 产生的唯一区别是进行了这个比较:

test %al, %al
je <sqlite3ParseUri+0x717>
cmp $0x23, %al
je <sqlite3ParseUri+0x717>

并交换了它们的顺序:

cmp $0x23, %al
je <sqlite3ParseUri+0x717>
test %al, %al
je <sqlite3ParseUri+0x717>

基准测试

Sqlite 自带了一个性能回归测试,因此我尝试每个版本的代码执行一百次,仍然使用默认的 Sqlite 编译设置。以秒为单位的测试结果如下:

const非 const
最小值10.658s10.803s
中间值11.571s11.519s
最大值11.832s11.658s
平均值11.531s11.492s

就我个人看来,我没有发现足够的证据来说明这个差异值得关注。我是说,我从整个程序中删去 const,所以如果它有明显的差别,那么我希望它是显而易见的。但也许你关心任何微小的差异,因为你正在做一些绝对性能非常重要的事。那让我们试一下统计分析。

我喜欢使用类似 Mann-Whitney U 检验这样的东西。它类似于更著名的 T 检验,但对你在机器上计时时产生的复杂随机变量(由于不可预测的上下文切换、页错误等)更加健壮。以下是结果:

const非 const
N100100
Mean rank121.3879.62
Mann-Whitney U2912
Z-5.10
2-sided p value<10-6
HL median difference-0.056s
95% confidence interval-0.077s – -0.038s

U 检验已经发现统计意义上具有显著的性能差异。但是,令人惊讶的是,实际上是非 const 版本更快——大约 60ms,0.5%。似乎 const 启用的少量“优化”不值得额外代码的开销。这不像是 const 启用了任何类似于自动矢量化的重要的优化。当然,你的结果可能因为编译器配置、编译器版本或者代码库等等而有所不同,但是我觉得这已经说明了 const 是否能够有效地提高 C 的性能,我们现在已经看到答案了。

那么,const 有什么用呢?

尽管存在缺陷,C/C++ 的 const 仍有助于类型安全。特别是,结合 C++ 的移动语义和 std::unique_pointerconst 可以使指针所有权显式化。在超过十万行代码的 C++ 旧代码库里,指针所有权模糊是一个大难题,我对此深有感触。

但是,我以前常常使用 const 来实现有意义的类型安全。我曾听说过基于性能上的原因,最好是尽可能多地使用 const。我曾听说过当性能很重要时,重构代码并添加更多的 const 非常重要,即使以降低代码可读性的方式。当时觉得这没问题,但后来我才知道这并不对。


via: https://theartofmachinery.com/2019/08/12/c_const_isnt_for_performance.html

作者:Simon Arneaud 选题:lujun9972 译者:LazyWolfLin 校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出