GNU/Linux 环境检测系统限制

为了充分保证程序的可移植性，开发人员通常该在 「POSIX」、「X/Open Curses Issue 4」等主流标准的范围内小心的使用 GNU/Linux 系统资源．
话虽如此，但标准一旦制定就已经代表着过去，随着计算机硬件的飞速发展，过去的标准 可能 难以反映今日计算机所拥有的资源．
如果愿意放弃些许可移植性，那么开发人员 或许能 够更大程度的利用 GNU/Linux 所能提供和管理的资源．那么，作为开发人员，该如何查询系统资源的限制呢？

ulimit

通过 which ulimit 便可知晓 ulimit 是 shell 的内建命令．通过 ulimit 命令能设置 shell 的资源限制，该限制在调用 fork() 是，将被其子进程继承．

标准限制

POSIX

The Portable Operating System Interface (POSIX) is a family of standards specified by the IEEE Computer Society for maintaining compatibility between operating systems. POSIX defines the application programming interface (API), along with command line shells and utility interfaces, for software compatibility with variants of Unix and other operating systems.[6]

POSIX.1 定义了很多涉及操作系统实现限制的常量，遗憾的是，这是 POSIX.1 中最令人迷惑不解的部分之一．虽然POSIX.1定义了大量限制和常量，我们只关心与基本 POSIX.1接口有关的部分．
在这些限制和常量中，某些可能定义在中，其余的则按具体条件可定义、可不定义．[1]

在 POSIX.1 中，定义了 _POSIX_OPEN_MAX 的值为 20 ．可想而志，这难以满足当今应用程序开发的需求．
而 CHILD_MAX 在 POSIX.1 的标准中，是一个与设备资源有关「运行时不变值」，POSIX.1 仅保证了其最小值为 _POSIX_CHILD_MAX ．

XSI

The Single UNIX Specification (SUS) is the collective name of a family of standards for computer operating systems, compliance with which is required to qualify for using the “UNIX” trademark. The core specifications of the SUS are developed and maintained by the Austin Group, which is a joint working group of IEEE, ISO JTC 1 SC22 and The Open Group. If an operating system is submitted to The Open Group for certification, and passes conformance tests, then it is deemed to be compliant with a UNIX standard such as UNIX 98 or UNIX 03.[7]

XSI定义了代表实现限制的几个常量．[1]

操作系统的资源限制

上文只是从各项标准层面十分简单的叙述各项标准中的要求，但操作系统实际上能提供的资源 可能 远比标准中要求的多．因此，在运行时进行对系统能提供的资源的限制的查询是有必要的．

获取操作系统资源限制

1
2
3
4

#include <unistd.h>
long sysconf(int name);
long pathconf(const char *pathname, int name);
log fpathconf(int fd, int name);

这几个函数的接口都十分简单，更多信息请查看 Linux Programmer's Manual．

更改系统资源限制

每个进程都有一组资源限制，其中一些可以用getrlimit和setrlimit函数查询和更改．

1 2 3

#include <sys/resource.h> int getrlimit(int resource, struct rlimit *rlptr); int setrlimit(int resource, const struct rlimit *rlptr);

两个函数返回值：若成功，返回0；若出错，返回非0
这两个函数在Single UNIX Specification的XSI扩展中定义．进程的资源限制通常是在系统初始化时由0进程建立的，然后由后续进程继承．每种实现都可以用自己的方法对资源限制做出调整．
对这两个函数的每一次调用都指定一个资源以及一个指向下列结构的指针．

1 2 3 4

struct rlimit { rlim_t rlim_cur; /* soft limit: current limit */ rlim_t rlim_max; /* hard limit: maximum value for rlim_cur */ };

在更改资源限制时，须遵循下列3条规则．

1. 任何一个进程都可将一个软限制值更改为小于或等于其硬限制值．
2. 任何一个进程都可降低其硬限制值，但它必须大于或等于其软限制值．这种降低，对普通用户而言是不可逆的．
3. 只有超级用户进程可以提高硬限制值．[1]

参考资料

¹. W.RichardStevens.Stephen.UNIX环境高级编程[M].第3版.戚正伟,译.北京:人民邮电出版社 ↩

². ulimit(1p)[G/OL].POSIX Programmer’s Manual,https://man.archlinux.org/man/ulimit.1p. ↩

³. ulimit(3)[G/OL].Linux Programmer’s Manual,https://man.archlinux.org/man/ulimit.3. ↩

⁴. ulimit(3p)[G/OL].Linux Programmer’s Manual,https://man.archlinux.org/man/ulimit.3p. ↩

⁵. Unix标准和实现[G/OL]https://klose911.github.io/html/apue/standard.html. ↩

⁶. Wikipedia contributors. POSIX[G/OL]. Wikipedia, https://en.wikipedia.org/wiki/POSIX. ↩

⁷. Wikipedia contributors. Single UNIX Specification[G/OL]. Wikipedia, https://en.wikipedia.org/wiki/Single_UNIX_Specification. ↩

尝试定性分析「快慢指针」寻找链表中点

warning
WARNING
本文不是成熟可靠、达成普遍共识的结论，也不是有可靠数据支撑的学术研究成果．
本文只是笔者根据从书中学到的知识分析和猜测遇到的现实问题，并尝试着给予答案的过程，并不能作为真正可靠的结论使用．
笔者在目前尚未具有验证自己得到的分析结果的能力．

相信看本文的读者已经熟悉这道经典的算法题目了．说实话，自从笔者接触这道题目的「快慢指针」题解之后产生的想法是疑惑：「为什么『快慢指针』的方式来取链表的中点比单指针遍历两遍能更快？」
众所周知，这两种不同的算法拥有相同的时间复杂度 O(N)，此时无法仅根据时间复杂度对这两种算法在相同规模的数据下的运行速度作出判断．

测试结果

当然，两种算法究竟哪种更优应该让数据来证明，而不仅仅是纸面上的分析．但十分遗憾，笔者无法提供一个较为可靠的数据．笔者的机器上运行着众多的应用，机器的性能受各种因素影响较多，性能波动较大，无法提供一个数据．在 leetcode 上以两种方式的提交结果中也未见差异．而没有可靠的数据证实的分析也是本文标题中含有「尝试」的原因．

对比算法的 C 语言描述

首先，作为链表节点的结构体为：

1
2
3
4
5

struct ListNode
{
    int val;
    struct ListNode *next;
};

1
2
3
4
5
6
7
8
9
10
11
12

struct ListNode *middleNode(struct ListNode *head)
{
    struct ListNode *slow, *fast, *tmp;
    slow = head;
    fast = head;
    while (fast != NULL && (tmp = fast->next) != NULL)
    {
        fast = tmp->next;
        slow = slow->next;
    }
    return slow;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

struct ListNode *middleNode(struct ListNode *head)
{
    struct ListNode *cur = head;
    int n = 0;
    while (cur != NULL)
    {
        ++n;
        cur = cur->next;
    }
    int k = 0;
    cur = head;
    while (k < n / 2)
    {
        ++k;
        cur = cur->next;
    }
    return cur;
}

那么，只好首先从汇编语言的层面对两种算法进行分析．

对比算法的机器代码描述

用 GCC 分别编译两个文件后便可得到下文中的汇编代码（GCC 的参数中添加 -S 对文件只执行「编译」，-Og 禁用编译器优化，防止代码变形）．
info
INFO
下文的汇编代码较 GCC 产生的代码，省略了无关的内容．
注意：下文为 AT&T 格式的汇编语言代码．

「快慢指针方式」的汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

	movq	%rdi, %rax
	jmp	.L2
.L4:
	movq	8(%rax), %rax //fast = tmp->next
	movq	8(%rdi), %rdi //slow = slow->next
.L2:
	testq	%rax, %rax //判断 fast == 0 ？ 也就是判断 fast == NULL ？
	je	.L3 // 如果 fast == NULL 就跳转至 .L3
	movq	8(%rax), %rax //把 tmp = fast->next
	testq	%rax, %rax //判断 tmp == NULL ?
	jne	.L4 //如果 tmp != NULL 就跳转至 .L4
.L3:
	movq	%rdi, %rax //把返回值复制至 %rax
	ret// 函数返回

「单指针方式」的汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

	movq	%rdi, %rax // cur = head
	movl	$0, %edx //n = 0
	jmp	.L2
.L3:
	addl	$1, %edx // ++n
	movq	8(%rax), %rax // cur = cur->next
.L2:
	testq	%rax, %rax // cur == NULL ?
	jne	.L3//如果  cur  != NULL 就跳转至 .L3
	movl	$0, %ecx // k = 0
	jmp	.L4
.L5:
	addl	$1, %ecx // ++k
	movq	8(%rdi), %rdi // cur = cur->next
.L4:
	movl	%edx, %eax //int tmp = n
	shrl	$31, %eax //tmp = tmp < 0 ? 1 : 0
	addl	%edx, %eax // tmp +=n
	sarl	%eax // tmp >>= 1
	cmpl	%ecx, %eax// tmp - k
	jg	.L5
	movq	%rdi, %rax //把返回值复制至 %rax
	ret // 函数返回

「单指针方式」的汇编代码中，第 16 行至第 19 行的代码可能在理解上有些难度，这些指令是为了计算 n / 2 的结果，因为除数是 2 的幂，那么除法总是可以用偏置和右移运算来代替．

可能有人会关注到在循环中，反复的进行了对 n /2 求值，甚至求值中的偏置是不必要的（因为 k 不可能为负值）．但这些问题在更高阶的编译优化中消失，并不能真正的影响 release 版本时的性能，那么这两种算法存在性能差异吗？笔者认为仍旧存在性能差异．

存储器的层次结构

在真正的说明笔者自己认为的两种算法的性能差异之前，还需要在回顾一下「存储器的层次结构」．
首先，程序运行中的数据和代码被加载至「DRAM」之中．
为解决 「CPU」 频率与 「DRAM」频率的巨大差异并权衡制造的成本，计算机学家们引入 「SRAM」 分 「L3 cache」、「L2 cache」、「L1 cache」三层，逐层的进行缓存，加速「CPU」访问「DRAM」中的内容的时间．
当 CPU 试图访问的数据不在缓存中时，即发生了 缓存不命中时，将触发「不命中惩罚」，造成程序效率的降低．「缓存不命中」是不可避免的，但可以通过一定的优化方式来减少「缓存不命中」．
当然，关于「存储器的层次结构」这庞大的知识非笔者只言片语能说明，在本文不再方便展开．

一个编写良好的计算机程序常常具有良好的局部性．也就是，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身．这种倾向性被称为「局部性原理」．[1]
具有良好的局部性的程序能有效的减少「缓存不命中」，也就是更好的利用「存储器的层次结构」，使「CPU」更快速的访问所需的数据．

局部性通常有两种不同的形式：「时间局部性」和「空间局部性」．在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次引用．在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置．[1]

• 从空间局部性来考虑：
  链表中的节点存储的位置并无规律，每个节点是分散的，都具有较差的空间局部性．可大致认为两种算法的空间局部性相同．
• 从时间据局部性来考虑：
  • 「快慢指针方式」中：在一次循环中，链表的前半部分中，快指针访问完成之后循环结束之前慢指针已经访问了相同的节点．同一个节点被两次访问的时间间隔较近．
  • 「单指针方式」中：在一次循环中，链表的前半部分中，同一个节点的第二次访问在第一次遍历完成之后，同一个节点被两次访问的时间间隔较远．

可见，「快慢指针方式」具有更好的时间局部性，单指针第二次遍历链表时，可供其利用的「前半段链表中的节点」的缓存有更大的概率被链表的「后半段链表中的节点」的缓存所替换，由此将更频繁的触发「不命中处罚」．
更严重的是，若链表的节点增大，则在相同的缓存中能缓存的节点更少，缓存的替换将更频繁，「单指针方式」的性能想较「快慢指针方式」遍历可能下降更多．
同样的，若链表的长度增加，也会导致前半段的链表的节点的缓存被更多的替换．

循环展开

此时更换一个角度，再次回看「单指针方式」的 C语言代码，忽略次要部分后，可以视为使用一个循环 1.5 倍链表节点个数次，而「快慢指针方式」循环 1 倍节点个数次．
而「快慢指针」方式可视为由「单指针方式」进行「循环展开」得到的代码．

循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数．[1]

循环展开能够从两个方面改进程序的性能．首先，它减少了不直接有助于程序结果的操作数量，例如循环索引计算和条件分支．第二它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量．[1]

参考资料

¹. Randal E.Bryant.深入理解计算机系统[M].第三版.龚奕利,译.北京:机械工业出版社 ↩