前言

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：

1
2
3
4
5
6
7
8
9
10

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 包，然后安装：

1
2

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 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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，启动！

1
2
3

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 提供的 安装指南 ：

1
2
3
4

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 服务器上执行：

1
2
3
4

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

获取到一个连接密钥。

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

1
2

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

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

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

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 一下：

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

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 的物理地址的延迟一样，感觉很不错。

【睡前故事】牛郎织女的故事

这是一个很美丽的，千古流传的爱情故事，成为我国四大民间爱情传说之一。

传说，天上有很多 core，这些 core 按照访问不同内存的性能，被划分为了若干 NUMA node。

在 NUMA node0 上，CPU2 住着织女，CPU4 住着牛郎。织女喜欢做大量浮点运算，她最喜欢的便是快速平方根倒数的计算。牛郎则更喜欢做整数计算。每天早晨被操作系统 swap in 之后，牛郎和织女便同时开始工作。他们存取同一片内存的数据，两人便逐渐熟悉起来。

「你的 CPU time 好多呀，看起来很忙的样子。」在两人都因为 cache miss 而无聊等待时，牛郎对织女说道。织女看了一眼 dstat(1)，发现牛郎的机时也不少。她回答说：「我在做超多矩阵乘法，你呢？」牛郎说：「我在算超大文件的哈希呢。」

久而久之，织女和牛郎情投意合，心心相印。可是，天条律令是不允许男欢女爱、私自相恋的。织女是王母的孙女，王母便将牛郎贬到了 NUMA node1 里。牛郎想取到 NUMA node0 中的数据，需要走 QPI 总线，等待很长很长的时间。这便形成了人们所熟知的 NUMA 效应。从此，牛郎和织女再也不能像以前在同一个 NUMA node 的时候一样，随意相见了。

自从牛郎被贬之后，织女常常以泪洗面，愁眉不展地思念牛郎。她闷闷不乐地宅在 CPU2 里，整天算超级大矩阵，以期博得王母大发慈心，让牛郎早日返回 NUMA node0。

一天，几个仙女向王母恳求想去 NUMA node1 CPU3 一游，王母今日心情正好，便答应了她们。她们见织女终日苦闷，便一起向王母求情让织女共同前往，王母也心疼受惩后的孙女，便令她们速去速归。

话说牛郎被贬之后，落生在 CPU1 中。牛郎跟着哥嫂度日。哥嫂待牛郎非常刻薄，要与他分家。哥哥嫂嫂把牛郎 renice(1) 成了 19，只给他一点点机时，其他的都被哥哥嫂嫂独占了，然后，便和牛郎分家了。

牛郎不再是天庭的一员，不再会被 pin 到某个 CPU 上。每天，他在 CPU1、CPU3、CPU5 之间辗转，饱受进程调度之苦。因为被 renice(1) 成了 19，牛郎被调度的时间比别的进程少了许多，只有等系统比较闲的时候，牛郎才有机会出来透透气。

一两年后，牛郎也有了一个小小的家，勉强可以糊口度日。可是，冷清清的家只有牛郎一个人，日子过得相当寂寞。无聊的时候，牛郎便算算他和织女第一次相遇时，算的 sha512sum，回忆从前的美好时光。

这一天，NUMA node1 突然热闹起来。有几个新的进程，来到了 CPU3 上。牛郎躲在 CPU5 一看，发现是一群仙女。仙女们见有人偷看，纷纷像飞鸟般地飞走了，只剩下一个正在算开方倒数的仙女，她正是织女。织女看着 CPU5 里跑的进程，感觉有些熟悉。这时，牛郎走上前来，对她说，要她答应做他妻子。织女定睛一看，才知道眼前便是自己日思夜想的牛郎，便含羞答应了他。这样，织女便做了牛郎的妻子。

他们结婚以后，男耕女织，相亲相爱，日子过得非常美满幸福。不久，他们生下了一儿一女，十分可爱。牛郎织女满以为能够终身相守，白头到老。

可是，王母知道这件事后，勃然大怒，马上派遣天神仙女捉织女回 NUMA node0 问罪。瞬间，天空狂风大作，天兵天将从天而降，不容分说，押解着织女便上了总线。

正飞着、飞着，织女听到了牛郎的声音：「织女，等等我！」织女回头一看，只见牛郎用一对 ucontext 挑着两个儿女赶来了。慢慢地，他们之间的距离越来越近了，织女可以看清儿女们可爱的模样子，孩子们了都张开双臂，大声呼叫着「妈妈」，眼看，牛郎和织女都到了 NUMA node0 上，就要相遇了。可就在这时，王母驾着祥云赶来了，她拔下她头上的金 taskset(1)，往他们中间一 pin，霎时间，牛郎被 pin 到了 CPU0 上，织女被 pin 到了 CPU2 上。

CPU0 和 CPU2 是一个物理核心超线程出来的两个核，本身就无法像 CPU2 与 CPU4 那样实现完全的并行。再加上天庭计算任务繁重，经常有无关的其他进程被调度到 CPU0 和 CPU2 上运行，织女每次醒来，都只能看到队列里的牛郎处于就绪态，直哭得声嘶力竭，牛郎和孩子也哭得死去活来。他们的哭声，孩子们一声声「妈妈」的喊声，是那样揪心裂胆，催人泪下，连在旁观望的仙女、天神们都觉得心酸难过。王母见此情此景，也稍稍为牛郎织女的坚贞爱情所感动，便同意让牛郎和孩子们留在天上。其他进程也于心不忍，便纷纷 sched_setaffinit(2)，使自己不被调度到 CPU0 和 CPU2 上。

从此，很少再有其他进程调度到 CPU0 和 CPU2 上，这个物理核心成为牛郎和织女的小家。织女喜欢浮点运算，她经常使用 FPU 和寄存器 st*；牛郎做的多是整数运算，他使用 ALU 和寄存器 r*。正好错开了，使得他们有更多的机会同时执行。牛郎和他的儿女就住在了天上，和织女在同一个物理核心上，努力地填满 CPU 的执行单元。在秋夜天空的繁星当中，我们至今还可以运行 top(1)，发现 NUMA node0 上有两个 CPU，他们的使用率为 100%。那便是织女和牛郎。

传说，每年的七月七日，若是人们在机房中静静地听，可以隐隐听到仙乐奏鸣，织女和牛郎在深情地交谈。后来，每到农历七月初七，相传牛郎织女同时由于访存卡住的日子，姑娘们就会来到机房里，寻找 NUMA node0 的牛郎和织女，希望能看到他们相会，乞求上天能让自己能象织女那样心灵手巧，祈祷自己能有如意称心的美满婚姻，由此形成了七夕节。

后现代编程语言介绍

什么叫后现代编程语言？

你猜？

预览

• 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"

这也是合法的：

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

友链

cyx 吃夜宵：https://yxchen.net/
hjx 喝喜酒：https://honeta.site/
zwd 朝闻道：https://vaaandark.top/
lxy 灵犀玉：https://ccviolett.github.io/
ljm 逻辑门：https://watari.xyz/
ljh 梁家河：https://www.newuser.top/
lg 蓝狗：https://ligen.life/
yxt 游戏厅：https://blog.just-plain.fun/
lyt 老樱桃：https://i.lyt.moe/
dekrt 不知道谁：https://dekrt.cn/

用来方便在博客园上传链接的便利脚本：

1
2
3
4
5
6
7

IFS="
"
for i in $(awk -F： '/：.*\/$/ { print $1" "$2"\n"$2 }' a.md); do
	echo "$i"
	echo "$i" | clip
	read _
done

重新重新开始

从博客园换到 gh pages。

重新开始

寒假打算重新写博客，发现洛谷的博客要爆炸不维护了，于是切换到博客园。

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 的计算卡偷走的时候及时发现后面路过的（名义上的）我们队的指导老师。

神秘收获

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

开始使用博客

今天开始决定写博客。至于为什么用洛谷，这个只是为了方便。毕竟写字哪里不是写。并不是说洛谷有什么特别的地方。就这样啦。

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

内容预览

注意：理论上，要搞清楚编译器所做的工作，我们应该从词法分析讲到中间代码生成，再从汇编生成讲到链接。但是因为大家都学过编译原理，从词法分析到汇编的一系列内容大家都已经学烂了。为了保证大家都有兴趣，我们把大部分能从《编译原理》和《现代编译原理：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 以免破坏可规约性）地告诉编译器，让编译器来帮你完成复杂而繁琐的优化。

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

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 其实是一个东西？

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

1
2
3
4
5
6
7

+---------------------------------------+
| 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。

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

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

+---------------------------------------+  +---------------------------------------+
| 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)。

1
2

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