title: 快速数无向图中的三角形个数的程序

程序代码在： https://github.com/jyi2ya/tc-lab

运行方式
========

依照 Rust 语言的传统和推荐做法，使用了 cargo 作为依赖管理工具和构建系统。程序使用了很多 Rust 的预览特性，请使用 nightly 工具链构建。

运行程序的机器的 CPU 必须支持 AVX512 指令集。

程序有 memmap2、rayon 和 rayon-k-way-merge 三个外部依赖。其中 memmmap2 是封装了跨平台的 mmap 调用的很好用的库，rayon 是 Rust 世界中最完善且通用的线程池，rayon-k-way-merge 是一个并行的多路归并算法，因为觉得它可能可以复用到更多程序中，所以我单独写了一个库。

程序运行时必须接收一个参数即输入文件路径。输入文件要求以 CRLF 为换行符，每行两个十进制表示的 32 位无符号整数，用制表符分隔，表示图中的一条边。两个整数分别为边的两点的编号，输入文件中允许存在重边。

编译程序只需要 `cargo build --release` 即可。编译出来的二进制程序会放在 `target/release/triangle-counting-lab` 这里。

一个运行程序的命令行示例：`./target/release/triangle-counting-lab /data/soc-LiveJournal1.txt`


运行结果
========

测试环境如下：

    CPU: 16-Core Intel Xeon Gold 5218 (-MCP-) speed: 2295 MHz
    Kernel: 5.15.0-107-generic x86_64 Up: 23h 18m Mem: 2518.9/15985.7 MiB (15.8%)
    Storage: 40.00 GiB (88.5% used) Procs: 504 Shell: bash 5.0.17 inxi: 3.0.38

程序可以在 1.28 秒内完成对 https://snap.stanford.edu/data/soc-LiveJournal1.html 数据集的读取和处理，能够正确计算出给定无向图中的三角形个数。数据集包含 4,847,571 个节点和 68,993,773 条边，输入大小约为 1.1 GB。

    test-KVM 15:36 (master) ~/tc/target/release
    0 ./triangle-counting-lab /data/soc-LiveJournal1.txt
    compute chunk size ratio: 8
    scan chunk size ratio: 2
    [ScopeTimer] 0.44753418 seconds | scanning and parsing
    [ScopeTimer] 0.13225858 seconds | merging thread results
    [ScopeTimer] 0.10247132 seconds | deduping edge list
    [ScopeTimer] 0.05148247 seconds | adjusting memory layout
    [ScopeTimer] 0.05831781 seconds | building adjacency list
    [ScopeTimer] 0.42185576 seconds | computation
    285730264
    [ScopeTimer] 1.27462609 seconds | totals


算法流程
========

定义：Lower(i) 为编号为 i 的节点的邻居中，编号小于 i 的节点所组成的集合。

1. 读取文件，获得边的列表。
2. 对边的列表排序去重，得到边的集合。
3. 根据边的集合建立邻接表。
4. 对每个节点 i，求 Lower(i)。Lower(i) 中的每个元素 j 对答案的贡献为 Lower(i) 与 Lower(j) 的交集的大小

这是一个 Vertex Ordering to List Triangles[1] 算法的简化版本。

[1]: https://github.com/lecfab/volt


为什么它能跑得比朴素实现快
==========================

~~当然是因为它是 Rust 写的！~~


读入文件的优化
--------------

* 并行读取文件，并且解析数据
* 使用了 mmap 系统调用来完成文件读写

首先明确：C 标准库的 fread 函数在我们的场景下并不适用。因为 fread 函数本质上是 read 系统调用套了个缓冲区，每次调用 fread 时如果缓冲区是空的，fread 函数就会调用 read 系统调用将缓冲区填满；如果缓冲区不空，fread 就直接将缓冲区中的数据作为结果返回。在少量多次顺序读写的场景下，这个策略可以通过减少系统调用次数的方式来降低所有读取操作的平均开销。

而我们操作数据的模式主要是大量的，次数很少的读写，每次可能读取几十几百 MB 的数据。这个时候，fread 函数所带的缓冲区没有任何意义，反而额外增加了内存拷贝的开销。数据要先从内核拷到 FILE 结构体内部的缓冲区，再拷到 fread 函数的参数所指向的内存，比直接使用 read 调用读反而更加耗时。

一般来说，Linux 系统下的文件 IO 都是有内核维护的缓冲机制的，这个缓冲机制主要就是 page cache。page cache 是内核中缓存磁盘文件的数据结构，单位为内存页（通常大小为 4 KB）。每个内存页与磁盘文件上的一段数据直接关联——即读写磁盘时会先读写 page cache，等因为被修改而与磁盘数据不一致的页面（即 “脏页”）占比达到一定程度时，再统一写回到磁盘。

我们最终选用的 IO 方式为 mmap。mmap 系统调用主要作用于页表，它会指定一块内存区域代表被映射的文件，读写这块内存时通过缺页中断来真正完成对文件的访问。

与 mmap 竞争的读入方式为基于 read 系统调用的读写方式，两者都和 page cache 紧密关联。

read 系统调用的读入流程如下：

1. 发起系统调用
2. （如果数据没在 page cache 中）从磁盘将数据读入 page cache 中
3. 将 page cache 中的数据拷贝到调用者提供的缓冲区中
4. 系统调用完成

使用 mmap 方法时读入流程如下：

1. 程序试图访问 mmap 所映射的内存
2. （如果之前没有访问过这个内存页）触发缺页中断
    1. （如果 page cache 中没有被访问的内存页所关联的磁盘文件的内容）从磁盘将数据读入 page cache 中
    2. 设置页表，将内存页映射到用户空间
    3. 缺页中断返回
3. 读取完成

可以发现，read 调用的优点是执行路径简单、可以在单次调用中读取大量数据，缺点是存在额外的数据拷贝；mmap 调用的优点是没有额外的数据拷贝、编程模型简单（访存即是读取文件），缺点是每次访问新页时都需要陷入缺页中断。对比两者优缺点之后，我们可以很粗略地认为，如果拷贝一个内存页的代价大于一次缺页中断的代价，那么 read 调用占优；否则，mmap 调用点优。

对于 read 来说，内核会通过 copy_to_user 函数来将数据拷贝到用户空间，copy_to_user 最后调用的还是 memcpy，内核的 memcpy 的实现是 4 个字节为一组拷贝的；对于 mmap 来说，我只找到了一个十年前的讨论[1]，里面提到了一次 page fault 需要 1000 cycles 的开销。

[1]: https://plus.google.com/app/basic/stream/z12fybdg3uqeh5nhu04cj1yx1py4xrsb1ps0k

懒得管了，脑测了一下觉得两者耗时应该会是差不多的，所以决定用写起来更方便的 mmap 做法来写。


读入文件的可能的进一步优化
--------------------------

在我们对 mmap 和 read 两种方案做评估时，我们认为在 page cache 未命中时，两者读盘的开销是相同的。实际上，虽然读盘开销不可变更，但是我们可以将磁盘读写放到后台进行，让数据处理（分行、将字符串解析成整数）和磁盘读写交叠进行，从而掩盖掉部分磁盘读写的开销。

以 read 调用为例，记磁盘 IO 的部分为 L，数据处理的部分为 A，那么现有的先读取再处理的方案是这么做：

    LLLLLLLLLLLLAAAA
    时间 --->

如果我们交替读取和数据处理，那么它执行时应该会是这样的结果：

    LLLALLLALLLALLLA
    时间 --->

而 read 调用实际上是有预读机制的，简单说就是在 read 调用会在读到所要求的字节数量后立刻返回，但是还是会向前多读几个页面，这几个页面便是预读页面，保存在 page cache 中。所以实际上，我们程序执行应该是这样的结果：

    LLLALLALLALLA      <-- 用户态的程序
       L  L  L         <-- 后台预读
    时间 --->

可以看出，这里数据处理和磁盘读写形成了交叠的结构，从而掩盖了部分磁盘读取的开销，让整个过程加速了一些。

在 Linux 下，可以用 readahead 系统调用控制 read 的预读行为；可以用 readaround 系统调用控制 mmap 的预读行为。


并行读取任务划分设计
--------------------

最简单的并行读取便是将文件大小分割成 N 块，每一块由一个线程来读来处理。遗憾地是这种方法在我们的问题里是行不通的，因为如果分块边界没有落在换行符上，就会让同一行被两个线程分别处理，产生两个错误的结果。

解决方案也很简单：首先根据文件大小平分成 N 块的做法求出大致的块边界，接着将每个块边界向右移动直到遇到换行符为止。这样便是一个合理合法的分块方案。

关于 N 的大小如何选取的问题：假设 CPU 的数量是 ncpu，一个简单的想法是取 N = ncpu。然而这相当坏，因为并不能保证数据大小相近的块计算量也相近。一般我们会采用的做法是取 N = M * ncpu，总共划分出 M * ncpu 个任务。负载均衡通过线程池的任务窃取机制来实现。

M 的要求是，既不能大到增加数据合并和任务调度的开销，又不能小到保证负载均衡的效果。这里我们按照经验取了 M = 2。实际最佳值是多少需要消耗大量核时依靠枚举或者优选法试出来。



SIMD 加速的分行算法
-------------------

考虑一行最多可能出现多少个字符：32 位无符号整数不会超过 10 个字符，中间用制表符隔开，行末是 \r\n 换行符，也就是说单行不会超过 10 + 1 + 10 + 2 = 23 个字符。

avx512 指令集能够同时处理 512 位的向量，也就是 64 个 8 位整数，即 64 个字符。

64 > 23，所以，我们有这个重要结论：将行首及其后 64 个字节读入一个 512 位向量寄存器后，要么行尾也在同一个寄存器里，要么这是一个无关紧要的注释行。

这个结论提示我们分割出一行甚至不用读两次，可以大大减少我们需要考虑的边界情况数量，也彻底消除了分行过程的循环。

分行算法的过程如下：

1. 将行首及其后 64 个字节读入 u8x64 的向量 data 中
2. 将 data 和 '\n' 比较，得到一个 64 位的结果 result，如果 data 某个位置上的值是 '\n'，则结果对应的位会是 1；否则为 0
3. 数 result 的前导零数量，将其作为本次处理的行的长度


SIMD 加速的字符串转整数算法
---------------------------

考虑将 512 位向量看作 u32x16 的向量。32 位无符号整数不会超过 10 个字符，10 < 16。

也就是说，如果我们让 32 位无符号整数的十进制字符串中的每一个字符占用 4 byte，这个字符串仍然可以放进一个 512 位向量中。这启发我们直接将十进制字符串中的每个字符当作 32 位整数，放进 512 位向量中后乘上对应的系数（指 1、10、100、1000 等等）后，求归约和即可得到结果。

算法过程如下：

1. 将字符串读入 u8x16 的向量中
2. 将向量中每个 u8 减去 '0'
3. 调整向量中字符串所在的位置，由头对头调整为尾对尾，方便后续乘上系数
4. 将 u8x16 转换成 u32x16
5. 将 u32x16 的向量乘上 [1, 10, 100, 1000, 10000 ... ] 的系数
6. 求 u32x16 的归约和作为结果

相比逐位乘系数求和的朴素算法，SIMD 加速的方法会比原方法快约 1/3。


并行多路归并算法
----------------

每个磁盘读取任务完成后，会对自己读取到的所有数据排序。在所有磁盘读取任务完成后，只要对所有结果做多路归并就可以得到一个完整的排好序的边表。

为什么需要对所有的边排序呢？

1. 我们需要处理的是无向图，而输入文件给的是有向图。需要将边去重以避免出现错误的结果
2. 排序后可以让源点相同的边排在相邻的位置，在后面建立邻接表时可以获得更好的 cache 亲和性
3. 我们需要知道节点编号的最大值，提前分配内存以减少数据扩容的开销。排序后正好可以从数组末尾获取这一信息

普通的串行多路归并算法是一个迭代的过程，它会给每一路的最小值建一个小根堆，每次从堆顶取出下一个值。这个算法因为用到了共用的数据结构（堆），并且所有求出的最小值需要按照顺序写入内存，导致它根本不适合做并行化。

如果要获得很高的并行度，就势必要抛弃共享的数据结构，转而思考数据并行的可能性。所以，我们需要考察原问题是否存在一些特质，使它可以被划分成若干个之间不需要相互依赖的子任务，且子任务与原问题性质相似但是规模较小。

考虑到我们是在做和有序的序列相关的问题，按照经验，我们可以先取一个结果序列的中间值 pivot 来看看它会不会对我们的问题有所帮助。观察选取了 pivot 后的结果序列，发现 pivot 左侧的所有元素均小于 pivot，而右侧均大于等于 pivot。如果能够把原始的待归并的 K 个数组，每个数组根据 “是否小于 pivot” 拆成两个部分，那么拆分之后获得的 2K 个数组要么所有元素大于 pivot，要么所有元素小于 pivot。我们可以发现，pivot 左右的内存操作互不干扰，这是一个适合并行的结构。可以让所有元素小于 pivot 的数组归并后写入结果数组中 pivot 左侧的部分，让所有元素大于等于 pivot 的数组归并后写入结果数组中 pivot 右侧的部分，这样两个子任务的结构也与我们正在处理的问题相似了。

这是个递归的过程，递归的终止条件很好设置：K 个数组中只有 1 个长度不为零，此时直接使用内存拷贝将数组内容拷贝到结果数组中即可；或者 K 个数组中的元素数量的总和小于某个阈值，继续划分任务的话并行度增加获得的收益无法抵消划分过程及任务调度产生的损耗。

最后是 pivot 选取的过程。最佳的方案肯定是每次都准确地选中结果序列的中点，这样可以稳定地使每次递归之后任务量变成原来的一半。这是可以做到的，只要二分 pivot 的值即可。设所有数组中的元素数量之和为 N，数组中所有数的最大值为 M，则二分的次数为 log(M)，二分过程中每次判定需要用二分过程的中点值 mid 在所有数组中二分查找，求出所有 K 个数组中小于 mid 的元素的数量，复杂度为 K log(N)，总复杂度为 K log(M) log(N)。对于划分这种简单的任务来说，K log(M) log(N) 的开销还是有些不能接受。

我用的 pivot 选择方案为选择待归并的 K 个数组中最大的那个数组的中点。复杂度为 O(K)，至少能够保证每次划分过后最大的那个数组将会变成均匀的两半。

这个算法的性能相当不错，测试的时候并行的 K 路归并算法仅比 K 个并行的 memcpy 操作慢了 40% 。细心做一些剪枝和边界条件的优化，有望使这个算法吃满内存带宽，达到 memcpy 同等水平。


并行去重
--------

相比归并，去重操作的并行化实现起来非常简单。只需要将数据分块，块内去重，对块边缘的元素重复情况做一些处理后合并就可以了。没有什么值得一提的优化点。


边表从 AOS 到 SOA 的转换
------------------------

简而言之，就是把这样的东西：

    struct Edge {
        unsigned src, dst;
    } edges[100];

转换成这样的东西：

    unsigned src[100];
    unsigned dst[100];

前者的排布就是 AOS（Array Of Struct）；后者的排布就是 SOA（Struct Of Array）。之前由于需要对边做排序和去重，所以我们采用了 AOS 的排布。之后因为关注点由边变成了各个节点的邻居，源点不再重要了，为了提高 cache 的亲和性以及让 SIMD 指令一次能处理更多元素，我们将其转换成 SOA 的模式，使一个源点的所有邻居在内存上连续排布。

这个过程是很好并行的，也很适合 SIMD。可惜我太懒了，看到它并行后跑得挺快的就没管它了。


并行建立邻接表
--------------

这个问题抽象出来就是：给出长为 N 的数组 src[]，对每个 i，求出 lbound[i] 和 ubound[i]，使 src[] 中下标为 lbound[i] 到 ubound[i] 的所有数都等于 i。很显而易见的二分查找问题。

这个显然是可以并行的，算得上是并行计算 hello world 级别的问题，如果要做数据并行的话，也很适合 SIMD。相信受过并行算法训练的同学心里已经有 100 种方法来把它用多核实现，这儿就懒得讲了。

如果你真不会并行二分：<https://github.com/rarocat/recruitment-2024-spring/>


SIMD 加速的 bitset
------------------

回顾我们的算法：

    对每个节点 i，求 Lower(i)。Lower(i) 中的每个元素 j 对答案的贡献为 Lower(i) 与 Lower(j) 的交集的大小

按照我们算法的流程，我们求出 Lower(i) 后，会用它和多个 Lower(j) 相交，并对交集的大小求和。我一开始是用 HashSet 来存 Lower(i) 和 Lower(j) 的，但是很快我就发现这超级慢。

去偷看了一眼 volt[1] 的代码后发现，他的做法是用 bitset 表示 Lower(i)，接着用每个 Lower(j) 的元素来访问 bitset，最后对结果求和。这下连交集也不用求了，整个算法变成了很纯的访存数数过程。

[1]: https://github.com/lecfab/volt

bitset 可以用 SIMD 加速吗？一般来说是没有这个必要的，但是我们的场景有其特殊性：Lower(j) 是一些下标，这些下标在内存中的位置是连续的。我们需要用这些下标寻址 bitset，对结果求和。

内存连续——可以读入向量寄存器里；对所有下标做相同操作——可以用向量操作；对结果求和——最后需要一个归约过程。好了，我们发现用 SIMD 来做批量的下标访问其实是有利可图的！

bitset 的 SIMD 向量化实现相当简单，就是把普通的寻址工作用 SIMD 写了一遍而已。但是有个值得考虑的问题：我们能用 SIMD 批量访问 bitset 中的元素，我们能批量设置或者翻转它们吗？

答案是不行。大部分 CPU 是不支持直接对 bit 寻址的。如果我们需要修改某个 bit 的值，我们至少需要把它所在的那个字节读出来，修改 bit 的值，再写回去。如果我们用 SIMD 来批量操作，那么会遇到一种情况：两个需要修改的 bit 刚好在同一个字节中，那么后写回的结果将会掩盖先写回的结果，我们会发现我们丢失了一次写入或者翻转操作。

事先扫描所有下标，通过重新排序来避免写入冲突是可以保证算法的正确性的，但是既然都在扫描下标了，那么在扫描的时候直接访问 bitset，把结果算出来肯定是一个更快的方法。

也就是说 SIMD 加速的批量 bitset 翻转要么有正确性问题，要么打不过串行访问。总之无利可图。


Rust 是好的
===========


零开销的迭代器
--------------

Rust 的迭代器实现是惰性求值的，这就保证了一般迭代器连接时不会需要申请新的内存，被过滤掉的元素也不会参与后续计算。

迭代器写起来很好玩。

如果用迭代器来对标循环的话，那么 rayon 提供的并行迭代器就是类似 C 中 OpenMP 一类的东西。它可以在一定程度上完成对数组的数据并行操作。同时，迭代器提供了 map filter 等方法用于转换和过滤元素，也提供了 collect 和 sum 等方法用于归约，这让我们在使用迭代器时能够更自然地以比较函数式的方式思考问题，从而自然地写出类似 map-reduce 的适合并行的结构。


好用的数组切片
--------------

Rust 里面数组切片能够像只读数组一样使用，切片支持迭代器访问，还能再切出小小切片，非常适合用来做数据划分。同时切片的标准库支持也很丰富，让人感觉到了家的温暖。


无畏并发
--------

首先不管 Rust 的 Send 和 Sync 标记机制，单说一个变量不会有两个可变引用就已经能够避免相当大的一部分数据竞争问题了。堆了这么多屎山竟然连一次并发问题都没有遇到过。

并发是这样的，编译器只要把好像有问题的代码拒掉就可以了，工程师想战斗爽要考虑的问题就多了。


Unsafe
------

Rust 提供了很好用的标准库，标准库里有很多有益的假设和保证：比如，保证所有 String 类型都是合法的 UTF-8 串，保证所有的内存都被妥善初始化，运行时执行下标检查等等。

这些检查能避免很多问题。然而我们现在在做的是即使方向盘掉了也得等跑完再捡起来修的 “我不管总之结果对了就是对了” 的超级高性能优化项目，有时这些标准库的检查甚至会成为性能热点。好在 Rust 提供了 unsafe 机制，标准库也有一些低开销但是标记了 unsafe 的函数，让我们可以直接油门踩死——至于跑着跑着会不会突然爆掉那就是人的水平问题了。


结论
----

Rust 确实比 C++ 好写。

---

title: 从 zerotier 迁移到 headscale date: 2024-02-25 19:28:48+08:00

tags:

前言

zerotier 是我正在用的虚拟局域网设施。它的主要特性就是能用 UDP 打洞 技术，在没有公网 IP 地址的情况下实现 P2P 连接。tailscale 是它的类似物。

今天从网上看到了一份 评测 ，里面提到：

• Tailscale: Download speed: 796.48 Mbps, Upload speed: 685.29 Mbps
• ZeroTier: Download speed: 584.17 Mbps, Upload speed: 406.12 Mbps

看起来 tailscale 比 zerotier 快不少。于是决定把现有的 zerotier 网络迁移到 tailscale 上面去。

中继服务器 headscale 架设

想了想，现在的 zerotier 网络由于大陆没有中继服务器，打洞偶尔会非常不顺利。tailscale 和 zerotier 一样在大陆没有中继服务器，估计也会遇到一样的问题。最好的解决方案也许就是使用 tailscale 的开源实现，headscale 自建一个中继服务器。

所以，决定自建 headscale 服务！

因为 headscale 服务需要在节点建立 P2P 连接时提供帮助，所以需要所有节点即使在没有 tailscale 网络时，也能连接到 headscale 服务。也就是说，headscale 服务需要一个公网 IP。因此，我只能在我的 VPS 上搭建服务。

为了保持现在依赖 zerotier 网络的服务依然能够运行，我需要保证新的 tailscale 网络里设备依然有它们原本在 zerotier 网络里时 的 IP。为了避免 IP 地址冲突，首先，删掉原来就有的 zerotier：

0 apt autoremove zerotier-one
[sudo] password for jyi:
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
The following packages will be REMOVED:
  zerotier-one
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
After this operation, 11.3 MB disk space will be freed.
Do you want to continue? [Y/n] Y

接着，参考 headscale 的 Linux 安装指南。我们的 VPS 是 Debian bookworm 发行版，amd64 架构。因此，我们先下载对应的 deb 包，然后安装：

wget https://github.com/juanfont/headscale/releases/download/v0.22.3/headscale_0.22.3_linux_amd64.deb
apt install ./headscale_0.22.3_linux_amd64.deb

接着来配置 headscale。因为端口很难记，所以我们先用 nginx 给它反向代理一下，让它可以使用酷炫的维尔薇爱好者特供域名和 SSL ：

map $http_upgrade $connection_upgrade {
    default      keep-alive;
    'websocket'  upgrade;
    ''           close;
}

server {
        listen 443 ssl http2;
        listen [::]:443 ssl http2;

        ssl_certificate  XXXXXXXXXXXXXXXXX;
        ssl_certificate_key XXXXXXXXXXX;
        ssl_protocols TLSv1.2 TLSv1.3;

        server_name headscale.villv.tech;

        location / {
                proxy_pass http://127.0.0.1:18002;
                proxy_http_version 1.1;
                proxy_set_header Upgrade $http_upgrade;
                proxy_set_header Connection $connection_upgrade;
                proxy_set_header Host $server_name;
                proxy_redirect http:// https://;
                proxy_buffering off;
                proxy_set_header X-Real-IP $remote_addr;
                proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
                proxy_set_header X-Forwarded-Proto $http_x_forwarded_proto;
                add_header Strict-Transport-Security "max-age=15552000; includeSubDomains" always;
        }
}

这样配好了以后，就可以用 headscale.villv.tech 访问我们监听 18002 端口的 headscale 服务了。我们再编辑 /etc/headscale/config.yaml 把 headscale 服务配好（配置文件中有详细的注释，不再给出示例）。

写 headscale 配置时发现它只支持 110.64.0.0/10 这一个网段，和原来 zerotier 的 172.27.0.0/16 完全不在一个段。它还不支持改网段，这下 zerotier 白删了。tailscale 给了个 解释 说明为什么用这个段（ 但是没说为什么不支持改）。其中有句话特别好玩：

The addresses are supposed to be used by Internet Service Providers (ISPs) rather than private networks. Philosophically, Tailscale is a service provider creating a shared network on top of the regular Internet. When packets leave the Tailscale network, different addresses are always used.

好耶，我现在也是个 ISP 了！

不管怎么样，总之 headscale，启动！

root:/etc/nginx/sites-enabled# systemctl enable --now headscale.service
Created symlink /etc/systemd/system/multi-user.target.wants/headscale.service → /lib/systemd/system/headscale.service.
root:/etc/nginx/sites-enabled#

客户端 tailscale 安装

首先，VPS 作为网关，肯定得加入我们的 headscale 网络，这样才能把流量转发到我们在 headscale 网络里的服务中。所以，先试着在 VPS 上安装。

注意，你可以需要辗转两个组织（headscale 和 tailscale）提供的文档，才能把它玩起来。

依照 tailscale 提供的 安装指南 ：

curl -fsSL https://pkgs.tailscale.com/stable/debian/bookworm.noarmor.gpg | sudo tee /usr/share/keyrings/tailscale-archive-keyring.gpg >/dev/null
curl -fsSL https://pkgs.tailscale.com/stable/debian/bookworm.tailscale-keyring.list | sudo tee /etc/apt/sources.list.d/tailscale.list
apt update
apt install tailscale

接着，再依照 headscale 提供的 接入指南

在 headscale 服务器上执行：

root:~# headscale users create jyi
User created
root:~# headscale --user jyi preauthkeys create --reusable --expiration 24h
XXXXXXXXXXXXXXXXX980f40768460b1025aXXXXXXXXXXXXX

获取到一个连接密钥。

接着在需要连接到 headscale 服务的 tailscale 客户端上执行，并且带上刚刚获取的连接密钥：

root:~# tailscale up --login-server https://headscale.villv.tech --authkey XXXXXXXXXXXXXce90980f4XXXXXXXXXXXXXXXXXXXXXXXXXX
root:~#

搞定！接下来检查一下自己是否已经拿到了 tailscale 的 IP 地址：

root:~# ip a
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
    inet 127.0.0.1/8 scope host lo
       valid_lft forever preferred_lft forever
    inet6 ::1/128 scope host noprefixroute
       valid_lft forever preferred_lft forever
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc fq_codel state UP group default qlen 1000
    link/ether 00:16:3e:03:0b:6e brd ff:ff:ff:ff:ff:ff
    altname enp0s5
    altname ens5
    inet 172.20.113.58/20 metric 100 brd 172.20.127.255 scope global dynamic eth0
       valid_lft 314157516sec preferred_lft 314157516sec
    inet6 fe80::216:3eff:fe03:b6e/64 scope link
       valid_lft forever preferred_lft forever
7: tailscale0: <POINTOPOINT,MULTICAST,NOARP,UP,LOWER_UP> mtu 1280 qdisc fq_codel state UNKNOWN group default qlen 500
    link/none
    inet 100.64.0.1/32 scope global tailscale0
       valid_lft forever preferred_lft forever
    inet6 fd7a:115c:a1e0::1/128 scope global
       valid_lft forever preferred_lft forever
    inet6 fe80::84bd:1f32:8594:e3b/64 scope link stable-privacy
       valid_lft forever preferred_lft forever

发现，大功告成！

然后，我们再在另一台机器（我的 homelab）上做类似的事情，在上面配置好 tailscale 的客户端。

最后，试着 ping 一下：

warmhome 21:01 ~
0 tailscale ip
fd7a:115c:a1e0::2
100.64.0.2
warmhome 21:01 ~
0 ping 100.64.0.1
PING 100.64.0.1 (100.64.0.1) 56(84) bytes of data.
64 bytes from 100.64.0.1: icmp_seq=1 ttl=64 time=27.3 ms
64 bytes from 100.64.0.1: icmp_seq=2 ttl=64 time=26.9 ms
^C
--- 100.64.0.1 ping statistics ---
2 packets transmitted, 2 received, 0% packet loss, time 1001ms
rtt min/avg/max/mdev = 26.926/27.125/27.324/0.199 ms

好耶，ping 通了！而且通过 tailscale 网络 ping VPS 的延迟基本上和直接 ping VPS 的物理地址的延迟一样，感觉很不错。

---

title: Page/Buffer Cache 是什么？ date: 2023-10-01 17:48:39

tags:

Page/Buffer Cache 是什么？

简介

Page Cache

• 试图最小化磁盘 IO

• 本质上是一堆内存页面

内存页面（Page）：一小段连续内存，是操作系统管理内存的最小单位

• 包含了很多最近访问过的文件的内容
  • 意思是不包括 inode、目录等东西！

对于 inode 和目录来说，他们的 page cache 的类似物分别叫做 inode cache 和 directory entry cache。其中 directory entry cache 又由 inode cache 组织而来。

• 用途广泛，用于 file-backed mmap、buffered io，甚至 swap。

• 需要文件系统支持

Buffer Cache

• 试图最小化磁盘 IO

• 本质上是内存里的一堆块

块：操作系统对磁盘操作的基本单位，在 Linux 中要求大小为 2 的整数次幂，且比 sector 大，比 page 小

sector：磁盘读写数据的最小单位，由磁盘决定。

• 包含了最近访问过的块

• 用途不多，基本上只用来加速块设备

块设备（Block Device）：支持随机读写的设备。典型的比如磁盘。

• 不需要文件系统

比如，文件系统的 superblock 一般会躺在 buffer cache 里面

两者的关系

可以参考下图（从 usenix 上面偷的）：

考古时间

为什么 page cache 是一堆内存页面，而 buffer cache 是一堆块呢？

最开始 Linux 上面只有 buffer cache，此时 buffer cache 仅仅用于加速 buffered io 操作，向上与 read/write 交互，向下与磁盘交互。所以 buffer cache 设计成一堆块是很合适的。

page cache 则是为了支持 mmap，在 2.2 版本中引入的。由于它和内存关系比较紧密，所以设计成一堆内存页的形式。不过此时 buffered io 仍然只与 buffer cache 交互，不与 page cache 交互。要等两个 cache 合并之后才会出现大家所熟知的「调用 read/write 之后会写 page cache，过一会儿由操作系统把脏页写回磁盘」这种模式。

一些比较复杂的东西

page cache 和 buffer cache 其实是一个东西？

虽然逻辑上还是可以将他们分为两个东西，但是其实两者只是同一套数据的不同组织方式。

+---------------------------------------+
| page                                  |
|+-------+ +--------+ +--------++------+|
||buffer1| | buffer2| |buffer3 ||buffer||
||       | |        | |        ||  4   ||
|+-------+ +--------+ +--------++------+|
+---------------------------------------+

（没找到合适的图所以画了个）

每个 buffer 可以通过 buffer_head 结构体中的 b_page 字段获取自己对应的 page，同时 page 也可以通过 page 结构体中的 buffers 字段来得到自己所拥有的一组 buffer。

既然 page cache 与 buffer cache 合并了……

那如果我在 A 进程对 /dev/sda1 上的一个文件 F 的一个连续区域做 shared mmap，再在 B 进程对 /dev/sda 本身做 shared mmap，两个进程映射的实际磁盘空间一致，那 A 进程与 B 进程能映射到同一个 page 吗？

答案是不行 :3。因为 A 进程的 page 是文件系统给的，而 B 进程得到的东西更像是一堆 buffer 组合成的 page。

此时数据组织大概是这样的：

+---------------------------------------+  +---------------------------------------+
| A page                                |  | B page                                |
|                                       |  |                                       |
|                                       |  |                                       |
|    o         o          o           o |  |   o       o          o         o      |
|    |         |          |           | |  |   |       |          |         |      |
+----|---------|----------|-----------|-+  +---|-------+----------+---------+------+
     v         v          v           v        |       |          |         |
 +-------+ +--------+ +--------+   +------+    |       |          |         |
`|buffer1| | buffer2| |buffer3 |   |buffer|    |       |          |         |
 |       | |        | |        |   |  4   |    |       |          |         |
 +---^---+ +---^----+ +---^----+   +--^---+    |       |          |         |
     +---------+----------|-----------+--------+       |          |         |
               +----------|-----------+----------------+          |         |
                          +-----------+---------------------------+         |
                                      +---------------------------+---------+

一些好玩的接口

来点文件预读

除了缓存已经读过/写过的数据之外，猜测程序要读什么从而提前把它们读进 page cache 中，也能加快程序！

• posix_fadvise(2): POSIX_FADV_SEQUENTIAL 参数可以暗示内核自己将要顺序读文件。

• madvise(2): MADV_SEQUENTIAL 参数可以暗示内核自己将顺序使用一些内存，配合 mmap(2) 使用。

• readahead(2)：简单直接地告诉内核，偷偷多读一些东西（感觉这是个没用的屑调用……）。

掉落擦车

可以通过 /proc/sys/vm/drop_caches 来告知内核扔掉一些 cache 数据。可以通过 echo X > /proc/sys/vm/drop_caches 来使用。其中 X 的取值可以为 1, 2 或 3。当 X 为 1 时意思是让内核扔掉所有 page cache 里面的数据。2 和 3 代表什么，不知道 :3。

在测试一些 io-bounded 的程序时，为了防止 page cache 对测量结果造成干扰，可以在测试前运行一下。

未解之谜

发现自己还是不太看得懂 free(1)。

               total        used        free      shared  buff/cache   available
Mem:            13Gi       4.4Gi       3.2Gi       135Mi       6.5Gi       9.1Gi

---

title: CPC 2023 简明总结 date: 2023-10-01 17:48:39

tags:

CPC 2023 简明总结

记录我印象里的 CPC 2023 的大概流程。想着 BBHust 上面的大家不一定都对并行编程很感兴趣，所以省略了大部分纠结与调试的故事，只留下了好玩的部分。

比赛要和其他选手比拼技术，所以算是 “竞技”。因为经常睡不好，考验身体素质，所以也是某种很新的 “体育”。四舍五入 CPC 也是竞技体育。

比赛简介

CPC 是 “国产 CPU 并行应用挑战赛” 的简称。赛制大概是，主办方给出一个程序，让选手在特定架构的机器上优化，最后谁的程序跑得快谁就赢了。

今年主办方给的机器是一台名叫 “神威·问海一号” 的超级计算机，它是 “神威·太湖之光” 的后继者，国产超级计算机的明星之一。关于超级计算机，大家简单地理解成 “在上面用某些华丽的技巧编程，写出来的程序可以跑得很快” 的奇特电脑就可以了。

遗憾地是，这个国产超级计算机的硬件设计有很多不足。整个问海一号的架构被我们称为 “硬件设计友好型架构” —— 硬件工程师设计时自己怎么偷懒怎么来，给软件工程师（嗨呀，这是我）造成了诸多限制，使得我们在这个架构上编程难度颇大。同时，问海一号的现象还比较反常识，许多指令的加速效果远远不如它们在 x86 上的等价物。

我愿称其为 超算原神 。

初赛

初赛的任务是优化一个大程序中的小部分，和我们平时做的东西挺像。

我负责的部分是数据划分。就是把一个巨大的矩阵，切成很多个小小矩阵，让我的队友们写的代码来做后续处理。它只要满足划分出的任务量尽可能负载均衡、队友使用我的划分结果足够方便、缓存十分友好、能够适应不同的数据规模大小、不带来额外的数据转换开销等等条件的基础上跑得足够快就好了。最后我就写了这么一个东西。

“我什么都做得到！” —— 我，于七边形活动室，写完这部分代码之后

初赛的代码全是用 C 和 C++ 写的，很友好。我能很轻松地把一部分模块抽出来放到 x86 的架构上优化，再把优化后的代码给缝到原来的项目里面。这样原来自己熟悉的 perf 等等工具链就都可以用了。相比性能分析工具都要自己写的神威架构，x86 简直是天堂。

比赛后期队友 P 同学发挥奇思妙想，参考 OpenGL 的双缓冲技术，设计了一组面向 DMA 操作的双缓冲数据结构与 API，成功地将数据传输的开销掩盖在了计算下面，获得了巨量的性能提升。堪称最有想象力的一集。

还有个非常欢乐的事情是，神威架构上的 512 位浮点 SIMD 加速比仅有 1.8x 左右。经过我的仔细思考，我觉得可能神威在实现 SIMD 的时候就是单纯地给前端解码加了条指令，后端实际还是逐个逐个元素计算的……相当于仅省略了解码开销。不知道是不是真的但是很符合我对神威的想像。

很遗憾，初赛到现在已经过了两个多月了，期间经历了期末考试、构造动画片电视台、升级重构 bot、研究跨平台包管理器、无聊的并行计算课、学 vscode、学习怎么逛街、配置全新网络文件系统、研究 AMD ROCm、打工以及最终暑假结束了也没找到女朋友等诸多好玩的事情，具体初赛时发生了什么我已经几乎忘光了（其实暑假做了什么我也几乎忘掉了，这个列表是参考 bash history 和 bot 聊天记录写出来的），只留下了印象最深的一点点事情。也许应该发展一下写日记的习惯……或者用 bot 代劳写日记的习惯。

决赛

决赛的任务是优化一个巨大的 Fortran 项目，和我们平时做的东西一点也不像。

决赛刚刚开始的几天我恰好开始实习，就拿到了一份任务列表。拿着做了两三天发现自己要是想跟上任务表的进度，每天都会很累，回到酒店后根本就没啥精力和心情来搓 CPC 的傻逼 Fortran 代码。于是研究了一下换人的可能性。但是就在换人讨论的后一天上班时，无意间发现自己拿到的好像是一个月量的任务表，但是自己把它当成一周的量来做了。本来还以为是什么万恶扒皮公司压榨实习生的剧情，结果现在直接做上了做一休三的悠闲生活。因为突然多出了不少空闲时间，我就接着打 CPC 比赛了。

实习公司的网络管制很严格，要和它的防火墙斗智斗勇才能成功打洞连上比赛的集群。比赛开打的前几天，网络相关的知识猛增……

决赛集齐了 Fortran、神威、大项目 等多种我们的短板，所以游戏体验并不良好。大量时间被花在了无意义的代码调试上，欢乐的事情很少很少……每天最快乐的事情就是骂骂神威。

之前大家还是一直认为 “Machine is always right” 的，但是在神威上编了几个月程，遇到了一堆问题后，最后几天调试代码我都有点开始相信风水了。总之，在神威机器上编程的时候，遇到问题除了排查自己的代码中出现的问题外，还要排查编译器本身的选项、从核同步性等一系列本应由编译器开发人员和硬件设计人员给我们弄好的问题。烦烦烦。

决赛现场

决赛的前一天半夜，队友突然发现比赛集群上的环境疑似被主办方重置了，导致大家的 git 被回滚到了旧版本，某些功能没法用。作为成熟稳重可靠万能的超算队前辈（嗨呀，突然发现参赛小队里只有一个勉强能算后辈，怎么回事呢），我就连夜给它重新装了一个。

现场照片：

决赛比较无聊，到后面有点垃圾时间的意味。于是……

原神，启动！ —— 某不知名 P 同学

星铁，启动！ —— 某不知名 H 同学

以及畅想讨论怎么把比赛现场的 NVidia 的计算卡偷走的时候及时发现后面路过的（名义上的）我们队的指导老师。

神秘收获

感觉这次算是第一次遇到自己没法单刷的比赛，确定了自己并不是什么都做得到。之前因为比赛的工程量都比较小，想了想反正可以单刷就几乎没管过团队合作的事情。但是这次比赛拿到题时就知道这不太是一个人可以搞定的东西，再加上队长和队友都很积极，于是点了一些协作方面的技能。通过交流让四个人达成共识，并一起完成同一件事，感觉是某种很新的体验。

---

title: 一些书上不怎么讲的编译器优化方法 date: 2023-10-01 17:48:39

tags:

一些书上不怎么讲的编译器优化方法

内容预览

注意：理论上，要搞清楚编译器所做的工作，我们应该从词法分析讲到中间代码生成，再从汇编生成讲到链接。但是因为大家都学过编译原理，从词法分析到汇编的一系列内容大家都已经学烂了。为了保证大家都有兴趣，我们把大部分能从《编译原理》和《现代编译原理：C语言描述》里面找到的内容都删掉了（其实是根本没写）！

整个分享将会讲述一些书上没有的优化点和优化方法。还会介绍大家平时写的语言用得很少，但是 Jvavavava 和别的一些脚本语言用得很多神奇玩意 —— JIT。

一些名词在 LLVM 和 MSVC 中有不同的称呼，会在标题使用 LLVM 的叫法，并且在正文给出 MSVC 的叫法，方便大家 RTFM。

JIT - Just In Time Compilation

即时编译器。作用大概是把代码一边执行一边翻译成机器语言，从而用一些编译的代价，换取之后相关代码执行更快的利益。工作量主要在于确定何时进行翻译，优化到什么程度，以及优化 JIT 本身的速度。

本来按照历史的进程，应该先讲 AOT 部分的，但是有些重要概念在 JIT 里面讲比较方便，所以就调换了一下顺序。

单层编译器

没有解释器，所有代码执行之前都会被编译一次，然后直接执行二进制代码。

可以类比一下 Tiny C Compiler 的 tcc -run 命令。这个命令声称能直接执行 C 语言代码。但是实际上是先把 C 编译一遍，存到内存里再执行的。因为现在单层结构的 JIT 实际上几乎没有了，所以也没找到什么好玩的例子。

优点：

• 好写。要求不高的话，造一个飞快的编译器就可以了

缺点：

• 不优化会很慢。如果你的编译器真的一点也不优化的话，你会发现你编译到二进制的语言会和 Java 打得 有来有回
• 更糟的是，因为每次执行代码时 JIT 编译器都要运行一遍，就注定这个编译器不可能牺牲编译时间来换取更多的优化。

解释器 + 编译器

典型的是 Java 的虚拟机 —— HotSpot VM。听名字就知道，HotSpot VM 和性能热点有关。事实也是如此。

HotSpot VM 运行时会首先对程序解释执行，接着分析程序性能热点。并将热点部分编译。

通常，编译器分为很多层，对应不同的优化等级。一段代码在执行过程中会被反复编译，程序越热的部分，得到的优化会越多。

这么看来，我们自己也是某种神秘 JIT。写代码时先用 perf/vtune 之类的东西查出性能热点，然后再优化跑得多的部分……

为什么针对热点优化：阿姆达尔定律

FDO - Feadback-Directed Optimization

之前我们已经知道了多层的 JIT 会分析运行的代码执行的情况，以确定何时对代码进行优化。

我们只收集 “代码在过去一段时间内运行次数” 这一个信息，就可以较好地确定代码需要的优化程度。但是我们在运行时对程序进行分析时，往往能得到更多的信息。比如，程序在某个分支失败的概率等等。而这些信息往往是无法在源代码中体现出来的。我们能不能利用这些信息来对代码做进一步的优化呢？

这就是 FDO 的思路：利用代码运行时的收集的数据来优化代码。

在微软的文档里通常叫 PGO，Profile-Guided Optimization

很容易想到，借助 FDO 我们可以实现这几个神奇优化：

• 内联高频执行的函数
• 寄存器分配优化
• 条件跳转优化

还有一些不那么容易想到的优化：

• 虚函数调用优化：发现某个 virtual call 总是调一个函数，就加一组条件判断 + 直接调用来优化

同时，由于 FDO 是根据代码运行的实际数据来优化，所以它会更加容易适应实际数据的模式。这比 AOT 编译对着源代码瞎猜好多了……

JIT 中的 FDO 通常也分为两种，分别是：

• Sample-Based FDO：工作方式类似 perf(1)，原理是采样
• Instrumentation-based FDO：工作方式类似 gprof(1)，原理是插桩

因为平时没写什么带 JIT 的脚本语言，所以这部分暂时没有例子。如果有人知道的话欢迎补充一些。

AOT - Ahead Of Time Compilation

AOT，即 Aheaed Of Time。顾名思义，就是把程序提前编译好，整成二进制/字节码啥的，然后需要用的时候直接执行。在这期间，编译器 通常 会消耗大量计算资源对代码进行大量优化。不同 pass 的优化贯穿了整个代码生成的过程。

LTO - Link-Time Optimization

微软把这个叫 LTCG，怪。

链接时优化，发生在汇编器之后，生成可执行文件之前。

大致思想是，在链接时把目标文件都读进内存里，接着把这些东西看成一个整体，进行激进的优化。

优点：

• 跨文件的函数内联、常量传播、死代码消除等等
• 跨编程语言优化，比如，可以优化 C 和 Rust 混写的代码。
• 可实现相同代码的折叠与消除（听起来有点像 zip 压缩的感觉？）

缺点：

• 冲浪时发现 有个文章 说相同函数的折叠在涉及到函数指针的比较操作时可能不安全，至于为什么我暂且蒙在鼓里……
• 非常慢。我在编译 rust 代码时如果开了 lto = "fat"，要在链接那里等好久。

对策：

• 将内存中的巨大二进制代码分块，并行进行 LTO。不过并行度越高，同一个优化线程所看到的代码就越少，优化机会也就越少。所以这里还是涉及到编译速度和编译质量折衷的问题……

具体到实现上的话，GCC 和 LLVM 不约而同（约了也说不定，反正大家都你偷我的我偷你的……）地选择了 bitcode 的形式。也就是说，开启 LTO 相关的编译选项后，生成的目标文件中将不再是机器码，而是编译器自己的 bitcode。至于为什么这样设计，官方文档说如果换用其他方案会产生工程复杂性等诸多问题，因为我没写过链接器，不太知道咋回事，所以也暂且蒙在鼓里。

同时，GCC 和 LLVM 各自又把 LTO 的过程划分成了好几个阶段，并不是一趟跑完的（所以才这么慢啊）。

FDO - Feadback-Directed Optimization

上面讲 JIT 的时候就已经提到了 FDO，我们知道 FDO 是需要依靠代码运行时的信息来决定优化方式。这种优化似乎天生是适合 JIT 的，因为 JIT 在解释执行代码的时候就能自然地拿到很多关于程序运行情况的信息。

如果我们说，在 AOT 编译里面也能做 FDO 呢？

以 MSVC 为例（他们会把这个操作叫 PGO），它的大概流程是：

1. 先用一些魔法参数编译出一个可执行文件
2. 运行这个可执行文件几次（称为 train run），它会自动收集运行信息并且写到某个文件里
3. 另一些魔法参数，使编译器参考之前收集到的信息来编译出最终的可执行文件

LLVM 好像也有类似物，叫做 autofdo，由 Google 开发，有几页 简单介绍。但是我还没看完，懒狗程度令人感叹。

之前我们提到，JIT 里面的 FDO 有很多优化，比如：

• 内联高频执行的函数
• 寄存器分配优化
• 条件跳转优化

相比之下， AOT 的 FDO 还能做出更多神奇的优化，比如：

• 基本块优化：可以把经常执行的一些基本块放到同一个 page 里面
• 死代码隔离：把多次 train run 都没有使用的代码放一个独立的 section 里面，如果它们没真的没被运行，就不用给它们分配 page 了！
• 错误处理代码隔离：同死代码隔离。

然而，在 AOT 上应用 FDO 还会有很多不可忽略的缺点：

• 编译模型十分复杂
• 大大增加编译时间
• 如果 train run 时使用的数据不够典型，甚至可能做出负优化

所以，目前 FDO 技术暂时还没有在 AOT 里面被广泛使用。

BOLT - Binary Optimization and Layout Tool

似乎是 LLVM 专属的，目前还没有在别的地方找到类似物。仓库在 这里。

和 FDO 很像，也是基于运行时的信息来优化代码。不过和 FDO 不同之处在于，FDO 在产出可执行文件时需要根据收集到信息重新链接程序，而 BOLT 则是直接基于已有的可执行程序重建控制流等信息，接着调整整个程序布局。

由于不需要重新链接，BOLT 甚至可以对没有源码的库或者可执行程序优化。

非常科技。

吔我 AI 啦

能不能用 AI 来帮我优化代码啊妈的

结束

快过年了，不要再讨论什么 AOT JIT 之类了。你写的各种离谱的 pass 和不知道怎么优化出来的代码回到家并不能给你带来任何实质性作用，朋友们兜里掏出一大把钱吃喝玩乐，你默默的在家里用各种晦涩难懂的语言和各种奇奇怪怪的技术优化出来的代码压根不对。亲戚朋友吃饭问你收获了什么你说我差点把图着色 RA 写出来了，亲戚们懵逼了，你还在心里默默嘲笑他们，笑他们不懂 Register Allocation，不懂 Local 和 Global 的区别，不懂 IR 除了 SSA 还能做 SoN，不懂一个 SSA 可以被你们玩出Hashed SSA，formal SSA，也笑他们根本不知道你的编译器的diagnosis都弄了个 TTY 真彩色 但实际上根本没人在意。你父母的同事都在说自己的子女一年的收获，儿子买了个房，女儿买了个车，姑娘升职加薪了，你的父母默默无言，说我的儿子整了个小电脑，天天黑框敲个烂代码天天对着笑，一天折腾那个 Lit 和 GTEST，破电脑开起来嗡嗡响，家里的电表转的是越来越快了，头上的头发越来越少了，人也越来越魔怔了

编译器越来越强了，以往很多的技巧（比如著名的 Duff's Device）正在随着编译技术的发展而成为历史。

任何编译器做优化都需要足够的信息，比如，有了控制流图就可以做可达性分析，多了运行时得到的信息又可以做 FDO。

而人对自己正在面对的问题，知道的信息总会是比编译器多的。所以，你要把你知道的东西或显式（比如，likely() 和 unlikely）或隐式（比如，不用向后跳的 goto 以免破坏可规约性）地告诉编译器，让编译器来帮你完成复杂而繁琐的优化。

快进到和编译器双向奔赴然后结婚😋😋

---

title: urxvt 跑得比 alacritty 还快，为什么呢？ date: 2023-10-01 17:48:39

tags:

urxvt 跑得比 alacritty 还快，为什么呢？

答案

答案是 urxvt 并没有老老实实地绘制其内程序输出的每一个字符，而是通过一些非常取巧的方法，减少了屏幕渲染的内容数量。

具体来说，是用了以下两个优化：

• jump scroll：如果短时间内需要渲染很多行，那么 urxvt 仅会在收到的行能充满一屏时尝试刷新。
• skip scroll：在 jump scroll 的基础上，限制刷新率为 60 Hz。

开启这两个优化之后，urxvt 收到的很多内容实际上都被直接扔进历史记录里了，根本没在屏幕上出现过。同时，因为人的眼睛是非常低速的设备，所以即使这些内容没有在屏幕上出现，也不会影响使用体验。

如果禁用掉这些小优化，urxvt 的速度大概仅是 alacritty 的 1/2 到 1/3。

alacritty 与 urxvt 的简介

urxvt 本身是个二十多年前的老东西，使用了很多奇怪的 X 特性。配置文件和 xterm 一样非常奇怪，可能是 Xorg 给世界留下的遗产之一……使用 C 和 C++ 编写，用 Perl 扩展。rxvt 的可扩展性很强，对标准支持也很好，各种 corner case 处理相对比较完善。

alacritty 是个很新的项目，号称要成为最快的终端。使用超级炒作语言 rust 开发，并且实现了 GPU 加速。他们一度声称自己是 “Fastest Terminal Emulator in Existence（现存最快终端）”。但是在 2020 年末的 一次提交 中不知道为什么他们换了说法，甚至连大家炒作时最爱的 “Blazing Fast” 也干没了。可能是开发者开发地表最速终端的梦想在现实里撞车了。非常快乐，大家快去围观。总之，相比项目早期的自述，现在的自述温和了很多。

两个都是非常好的终端。我之前是在 Windows 下用 alacritty，在 Linux 下用 urxvt。

为什么需要关注终端速度

……其实意义也不是很大，因为大家在输出内容太长的时候都会 | less 一下，用 pager 分页来看，终端速度对使用体验的影响很小。

但是既然速度是个能比的项目，那总会有人抱着一种宝可梦对决的心态来研究两个终端谁快谁慢，这也促进了这篇水帖的诞生！

urxvt 的小优化相关代码

摘自 urxvt 代码仓库 src/command.C 的第 2267 行。

if (ecb_unlikely (ch == C0_LF || str >= eol))
  {
    if (ch == C0_LF)
      nlines++;

    refresh_count++;

    if (!option (Opt_jumpScroll) || refresh_count >= nrow - 1)
      {
        refresh_count = 0;

        if (!option (Opt_skipScroll) || ev_time () > ev::now () + 1. / 60.)
          {
            refreshnow = true;
            ch = NOCHAR;
            break;
          }
      }

大概就是它用一堆错综复杂的条件变量实现了上面提到的小优化，整段代码唯一的注释的是这样的：

/*
 * If there have been a lot of new lines, then update the screen
 * What the heck we'll cheat and only refresh less than every page-full.
 * if skipScroll is enabled.
 */

摆了。这啥 GNU-style 的神秘老代码看得我头疼……

---

title: 后现代编程语言介绍 date: 2023-10-01 17:48:39

tags:

后现代编程语言介绍

什么叫后现代编程语言？

你猜？

预览

• Perl 历史
• Perl 设计理念：TIMTOWTDI
  • TIMTOWTDI 的范式
  • TIMTOWTDI 的语法
• Perl 很方便
  • You GUESS？
  • PCRE
  • Perl 的不知道多少个操作符
• Perl 的缺点
• 鬼畜代码大赏
  • JAPH
  • Golf
  • Poetry
  • 我的作品

Perl 历史

应该没人会对 Perl 的历史感兴趣……所以这里就列举几个比较有趣的东西好了。

• Perl 1 发布于 1987 年，比 ANSI-C 还早。这就导致 1998 年发布 Perl 5.005 时提到了一句 “Source code now in ANSI C”。
• Perl 在 1987-1991 四年中发布了 Perl 1 到 Perl 4 四个版本。但是 1993 年发布了 Perl 5 之后，大版本号就再也没变过了。基本上可以认为，Perl 已经 29 年没发生过大的 breaking change 了。
• Perl 社区几年前试着设计了 Perl 6。结果发现设计出来的东西和 Perl 5 完全是两个东西，于是给它改了个名字叫 “Raku”。
• Perl 7 正在开发！它将会与 Perl 5 兼容。

Perl 设计理念：TIMTOWTDI

There Is More Than One Way To Do It

做一件事不仅有一种方法。

TIMTOWTDI 的范式

有些坏比语言，会限制你 “只能面向对象” 或者 “不要副作用” 之类的，非常不人道！代码一下子就变得难写了！

但是 Perl 非常包容，以下将展示一些合法并且有用的 Perl 代码。

---

假装我们在写 C

my $acc = 0;
for (my $i = 0; $i < 100; $i++) {
    $acc += $i;
}
printf("%d\n", $acc);

---

假装我们在写 shell script

if ( -d '/var/log/v2ray' ) {
    chdir '/var/log/v2ray';
    for $file (<*.log>) {
        $size = `stat -c %s $file`;
        say "size of $file is $size";
    }
}

---

我一天不 new 浑身难受。

use JSON;

my $ds = {
    perl => 'yes',
};

sub main {
    my $json = new JSON;

    my $text = $json->encode($ds);
    my $pretty = $json->pretty->encode($ds);

    printf("%s\n", $text);
}

main;

---

我一直是链式调用的粉丝啊

my $say = sub { say join ",", @_ };
my $length = sub { length shift };
my $double = sub { shift() * 2 };
my $add = sub { shift() + shift() };

"hello,world"->$length()->$double()->$add(42)->$say();

---

我一直是 S-expression 的粉丝啊

use List::Util qw/sum min max first shuffle/;
say
(sum
(min 1, 2, 3, 4, ),
2,
(first
  { $_ > 3 }
  (shuffle 4, 5, 6, 8, 2)));

---

函数要是一等公民

sub compose ($f, $g) {
    sub { $f->($g->(@_)) }
}

my $h = compose(
    sub ($x) { $x ** 2 },
    sub ($x) { $x + 3 },
);

$h->(2)

---

谁说 sed 和 awk 不是语言？

#!/usr/bin/perl -n
s/^\s+//;s/\s+$//;s/android/harmonyos/g;

#!/usr/bin/perl -a
if ($NR > 10) { print $F[2] }

---

TIMTOWTDI 的语法

Perl 的语法很灵活的。

---

一般我们会把 if 写成这样：

if ($ok) { say 'hello'; }

但是这样也是可以的

say 'hello' if $ok;

再邪恶一点

say 'hello' unless not $ok;

---

一般我们会把函数调用写成这样：

printf("hello, world\n");

但是这样也是可以的，就像 shell 一样

printf "hello, world\n";

也可以不加空格，只要解释器认得出来

printf"hello, world\n";

极大地减少了 typo 数量！

---

Perl 很方便

除了灵活的语法，Perl 还有一些内置功能，以及约定来简化代码编写

You GUESS？

while (<>) {
    chomp;
    s/open\s*ai/csdn/gi;
    say join "\n", split /\s+/;
}

很多 Perl 函数会把默认的参数与结果放到特殊变量 $_ 里面。所以写 Perl 代码经常写出 “把那什么拿过来，处理一下放到那里” 这样的东西，任务竟然还完成了（

PCRE

大家都爱用的超级正则表达式。

PCRE 全称是 “Perl Compatible Regular Expression”。PCRE 是 BRE/ERE 的超集，而 Perl 本身的正则表达式又是 PCRE 的超集。

Perl 的不知道多少个操作符

捡两个比较好玩的说说

flip-flop 操作符

while (<>) {
    next if /^begin/ .. /^end/;
    next if /^begin/ ... /^end/;
    say if 1 .. 100
}

可以想象每个 flip-flop 操作符内部维护了一个布尔变量，它会在匹配到左边或右边的表达式时翻转。这个布尔变量的取值就是 flip-flop 操作符的取值。

yada-yada 操作符

...

表示代码尚未完成。

其他魔法

• 运行时操作解释器符号表的程度的能力
• 变量绑定的程度的能力
• 各种逆天 pragma
• 还有很多……

Perl 的缺点

• 设计老旧
• 过于灵活

鬼畜代码大赏

Perl 有各种神奇比赛，比谁更能玩弄 Perl 的语法规则。比如……

JAPH 大赛

JAPH（有时是 YAPH）全称是 “Just Another Perl Hacker”。规则是在标准输出中输出 “Just Another Perl Hacker” 这句话。

这是最简单的：

say"Just Another Perl Hacker"

这也是合法的：

`$=`;$_=\%!;($_)=/(.)/;$==++$|;($.,
$/,$,,$\,$",$;,$^,$#,$~,$*,$:,@%)=(
$!=~/(.)(.).(.)(.)(.)(.)..(.)(.)(.)
..(.)......(.)/,$"),$=++;$.++;$.++;
$_++;$_++;($_,$\,$,)=($~.$"."$;$/$%
[$?]$_$\$,$:$%[$?]",$"&$~,$#,);$,++
;$,++;$^|=$";`$_$\$,$/$:$;$~$*$%[$?
]$.$~$*${#}$%[$?]$;$\$"$^$~$*.>&$=`

文学创作

这是一个合法的 Perl 代码：

listen me, please;
my $dear;

please:
`touch my heart`. read the, $message, in;
sort my @feelings, and pop my @feelings;

please:
open your, heart;
join us, together.

let us tell world,
that we are in love until time;

我的缝缝作品

---

title: hyperfine 使用指南 date: 2023-10-01 17:48:39

tags:

hyperfine 使用指南

简介

测量程序运行耗时是一个常见的需求。

我们经常会调整自己编写的程序，来给程序加速。但是自己提出的加速计划，不一定会被 机器认可。比如，你觉得 ++i 比 i++ 更快并且花了两天时间把程序里所有的后缀全 改成了前缀，但是机器不管，她编译的时候直接把你的写法给扬掉了。这个时候再在 git 的提交信息里写 perf: 优化 XX 部分性能 就会显得非常滑稽。所以，我们经常需要对 程序性能测试来保证自己的优化是有效的。对程序性能测试的最常用的方法就是计时。

小时候幼儿园的老师经常教育我们，在 bash 里面用 time 的命令就可以测量程序 运行的时间。这也是大家最常用的方法。但是我们都知道，time 是一个非常粗糙的工 具。用它测量程序性能时，总会遇到这么几个问题：

• 测量出来的时间真的是准的吗？会不会受到系统波动的影响？
• 测量出来的时间有多可靠？该怎么知道测量误差？
• 我能比较轻松地对比两个或多个程序的性能吗？

我们可以通过写一堆土制脚本来解决上述问题，但是与其费心写功能不全、漏洞百出的脚 本，还不如直接使用已有的趁手工具。

hyperfine 就是一个优秀的性能测试工具。

优势

根据 hyperfine 自己的 介绍 ，hyperfine 拥有如下功能：

• 多次测量并统计均值方差
• 支持任意 shell 命令
• 进度条和预估剩余时间
• 预热：正式测试之前先运行几次
• 测试之前执行指定命令（可用于清除缓存）
• 自动发现 cache 影响和系统性能波动影响
• 多种输出格式，支持 CSV、JSON、Markdown 等等
• 跨平台

（注：hyperfine 的介绍是有 中文翻译 的，但是我看的时候它略微有些过时了。 希望有好心人来更新一下翻译）

它的使用截图如下：

个人评测：life-changing 的好东西，我现在没有 hyperfine 都不会测程序了。

基本使用

hyperfine 的使用方式非常符合直觉，命令行结构和选项设计得很好。

安装

hyperfine 是用 rust 写的（不打算去学一下？）。如果机器上有 rust 开发环境， 直接运行 cargo install hyperfine 即可完成安装。cargo 是 rust 的编译系统 和依赖管理工具。

如果机器上没有 rust 开发环境，可以求助你的包管理器，或者从 hyperfine 在 Github 上的发布页面 中，下载与自己的机器架构对应的二进制 文件。

测试单个程序

命令：

hyperfine 'hexdump file'

结果：

11:17 jyi-station ~/tmp/bgifile
0 hyperfine 'hexdump test13.c'
Benchmark 1: hexdump test13.c
  Time (mean ± σ):     385.0 ms ±   5.1 ms    [User: 383.0 ms, System: 2.1 ms]
  Range (min … max):   381.6 ms … 398.9 ms    10 runs

从结果可以看出，hyperfine 把程序运行了 10 次。测量出来平均耗时是 385 ms，误差 是 5.1 ms。运行的时候，hyperfine 把程序的所有输出重定向到了 /dev/null 里，所 以终端上没有多余的内容。

你看，我几乎什么都没做，只是把命令提供给 hyperfine，她就自动帮忙把所有东西都测 好了！

我们甚至无需检查误差是否过大，因为 hyperfine 会自动检测误差过大的情况，并且根 据程序运行时间的特征来猜测可能发生了什么问题，并给出一些建议。非常贴心。后面会 详细讨论这些细节。

对比测试多个程序

命令：

hyperfine 'hexdump test13.c' 'xxd test13.c' 'xxd test14.c'

结果：

11:24 jyi-station ~/tmp/bgifile
0 hyperfine 'hexdump test13.c' 'xxd test13.c' 'xxd test14.c'
Benchmark 1: hexdump test13.c
  Time (mean ± σ):     383.6 ms ±   1.9 ms    [User: 381.8 ms, System: 1.6 ms]
  Range (min … max):   381.6 ms … 387.7 ms    10 runs

Benchmark 2: xxd test13.c
  Time (mean ± σ):      90.2 ms ±   1.0 ms    [User: 88.4 ms, System: 1.9 ms]
  Range (min … max):    88.7 ms …  93.4 ms    32 runs

Benchmark 3: xxd test14.c
  Time (mean ± σ):     180.2 ms ±   2.8 ms    [User: 176.8 ms, System: 3.2 ms]
  Range (min … max):   177.1 ms … 186.6 ms    16 runs

Summary
  'xxd test13.c' ran
    2.00 ± 0.04 times faster than 'xxd test14.c'
    4.25 ± 0.05 times faster than 'hexdump test13.c'

在这个例子里，我们给了 hyperfine 三个参数，让她测量三个程序的耗时。hyperfine 首先输出了三个程序各自的运行结果，这部分和测试单个程序时的结果差不多。但是在报 告的最后，hyperfine 还额外给出了一些信息。她指出了跑的最快的程序（港记程序 :P） ，并且显示了其相对其他程序的加速比和误差。

我们一般测试程序时只需要关注最后的 “Summary” 一栏，知道哪个更快、快多少就可以 了。前面几行是和别人吵架时，给他们看测试结果让他们闭嘴时用的。

运行原理

对每个程序，hyperfine 会把它运行 10 次（运行次数有选项可以配置）。hyperfine 会 对运行时间计时，并且求出均值和标准差。

每次运行的时候，hyperfine 会运行一个 shell 来执行这些程序。比如，假定程序 是 sleep 1，那么 hyperfine 实际运行的是 sh -c 'sleep 1'。这种用 shell 来运 行程序的行为，会导致程序运行时间测量结果偏大；但是如果不用 shell 来运行程序， 大家平时习惯的 ~/ 和 *.txt 这些便利缩写就不能用了，非常麻烦。

总之，这种使用 shell 来执行参数的设计，算是便利与准确之间的一种折衷。

为了使测量结果更精确，你可以手动禁止 hyperfine 使用 shell 来执行程序的行为。 hyperfine 本身也会检测 shell 对测量结果的影响，并且在她觉得 shell 对测量结果的 影响已经大到不可忽略时提出警告。判定规则与细节将在之后描述。

使用进阶

现在，你已经基本学会用 hyperfine 了！让我们来看看一些更好玩的东西吧。

测试 IO 密集型程序

假设我们要运行一个大量读写磁盘文件的程序 10 次，我们会发现什么怪现象呢？我们 会发现，第一次或前几次运行所花费的时间会显著大于后面几次。这是由于 Linux 系统 有 Page Cache 的机制，它会尽可能努力地把最近使用过的文件缓存在内存里。

在第一次运行的时候，程序试图读文件。操作系统发现内存里没有相关文件，只好老老实 实地从磁盘上把文件读出来再交给程序。但是紧接着程序运行第二三四次，程序试图读文 件时，操作系统发现文件刚刚才被读过，还被缓存在内存里，于是直接把内存中的内容交 给程序，直接省略掉了读盘的过程。众所周知，内存的读写速度一般远大于硬盘。这导致 了第二三四次运行程序时，程序用时会显著少于第一次。

类似的情况还会出现在很多具有缓存机制的系统（没有特指操作系统！）里。在对于这些 系统打交道的程序计时时，我们需要给 hyperfine 加一些参数。

预热

我们可以使用 --warmup N 的参数让程序被真正计时之前，先运行 N 次，其中 N 是一 个整数。比如，hyperfine --warmup 2 sleep 3 这个命令实际上会运行 sleep 3 这 个命令 12 次，其中最后 10 次会被计时。

这种方式有利于将程序需要用到的东西提前装到缓存里。可以测量程序在缓存工作良好时 的运行效率。

提前执行指令

我们可以使用 --prepare X 的参数让 hyperfine 每次运行程序之前，先运行一下 X， 其中 X 是一条 shell 命令。比如， hyperfine --prepare 'echo 3 | sudo tee /proc/sys/vm/drop_caches' sleep 3 这个命令，会运行 sleep 3 10 次，但是每次运行前，会运行 echo 3 | sudo tee /proc/sys/vm/drop_caches 一次，来清除 Linux 的 Page Cache。

这种方式直接让缓存没用了。可以测量程序冷启动的速度。

测试运行时间过短的程序

之前说到，hyperfine 会用一个 shell 来执行待计时的程序。但是如果程序跑得很快， 导致 shell 启动、解析、执行的时间已经占总用时不小的一部分了，那么测量误差就会 变得不可接受。

这个时候我们就可以使用 -N 参数来制止 hyperfine 使用 shell。此时，她会用一个 内置的简陋的解析器来把命令的可执行文件和参数给分开。这个简陋的解析器主要使用 空白字符来分割参数，但是也支持基础的转义字符和引号。

比如：

hyperfine -N 'touch x'

不知道自己的程序属于哪种类型？

有笨比……

如果你不知道你的程序要跑多久，也不知道它是不是要用到某种缓存系统，直接把它当成 纯计算的程序来测就行了。hyperfine 会在发现不对劲时来提醒你。

下面是几个例子：

奇怪的测量结果

20:21 jyi-station ~/tmp/bgifile
0 hyperfine 'cat test18.c'
Benchmark 1: cat test18.c
  Time (mean ± σ):      16.9 ms ±   1.0 ms    [User: 1.1 ms, System: 15.9 ms]
  Range (min … max):    15.7 ms …  22.1 ms    154 runs

  Warning: Statistical outliers were detected. Consider re-running this
  benchmark on a quiet system without any interferences from other programs.
  It might help to use the '--warmup' or '--prepare' options.

hyperfine 发现测试的时候，有些数据与别的明显不在一个等级。所以她警告你并且建议 你在系统闲的时候重跑。

初次测量很慢

20:21 jyi-station ~/tmp/bgifile
0 hyperfine 'cat test19.c'
Benchmark 1: cat test19.c
  Time (mean ± σ):      34.3 ms ±  14.1 ms    [User: 2.2 ms, System: 31.8 ms]
  Range (min … max):    30.4 ms … 105.4 ms    28 runs

  Warning: The first benchmarking run for this command was significantly slower
  than the rest (105.4 ms). This could be caused by (filesystem) caches that
  were not filled until after the first run. You should consider using the
  '--warmup' option to fill those caches before the actual benchmark.
  Alternatively, use the '--prepare' option to clear the caches before each
  timing run.

这次 hyperfine 不仅发现数据异常，还发现是第一次跑的时候数据异常。于是她猜测是 某种神秘的缓存系统起了作用，并且建议你用 --warmup 参数或 --prepare 参数来 消除缓存的影响。

程序跑得很快

20:21 jyi-station ~/tmp/bgifile
0 hyperfine 'cat test1.c'
Benchmark 1: cat test1.c
  Time (mean ± σ):       0.9 ms ±   0.1 ms    [User: 0.7 ms, System: 0.4 ms]
  Range (min … max):     0.7 ms …   1.3 ms    1340 runs

  Warning: Command took less than 5 ms to complete. Note that the results
  might be inaccurate because hyperfine can not calibrate the shell startup
  time much more precise than this limit. You can try to use the
  `-N`/`--shell=none` option to disable the shell completely.

这次，hyperfine 发现程序跑得很快，误差会比较大，并且建议你用 -N 参数来直接运行程序， 绕过启动 shell 的步骤。

额外的功能

除此之外，hyperfine 还有一些别的功能，比如参数化测试之类的东西。不过我感觉要参 数化的话与其用这一坨命令行参数，不如去写一个小小脚本……所以我没用过。如果有人感 兴趣的话可以试试。

改变输出格式以便与其他软件协作

hyperfine 的命令行界面很好看，有进度条还有颜色。在除命令行之外的地方，她也做得 很好。比如，hyperfine 可以直接用 --export-markdown 参数生成 markdown 表格， 接着你就可以直接把结果插进 README 里面。她还可以导出 json 格式的测试结果，方便 之后再用脚本处理，做些可视化什么的（hyperfine 的仓库就附带了许多可视化脚本，很 好玩）。

总结

测量程序性能的方式有很多。相比那些在函数调用上插桩（gprof）或读 PMC 寄存器 （perf）的东西来说，单纯的计时也许太简陋了一些。但是第一次参观 profiler，却并 不觉得震撼。因为我早已遇见，独属于我的 benchmarking tool。初遇你的那天起，齿轮 便开始转动，却无法阻止丧失的预感。尽管已经拥有了很多，但让我们再多加一个吧。 可以给我最后一个加速比吗？我不愿遗忘