参考 Reflections on Trusting Trust，Running the “Reflections on Trusting Trust” Compiler。

The moral is obvious. You can’t trust code that you did not totally create yourself. (Especially code from companies that employ people like me.) No amount of source-level verification or scrutiny will protect you from using untrusted code.

步骤一

如何编写一个自我复制程序（Quine）？使用 Java 编写的代码如下，还是有点难的。最开始想直接打印，但是打印语句需要包含完整的程序，而完整的程序又包含打印语句，是一个循环依赖的过程。要把循环解开，就只能在字符串中包含基本的行，经过特殊处理得到正确的输出，最简单的方式是使用占位符。似乎不能使用转义字符，因为反斜杠在字符串中也需要转义，所以根本没办法打印出相同的行。更短的示例可以参考 Quine Programs。

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

public class Main {
    public static void main(String[] args) {
        char n = 10;
        String t = new String(new char[]{'"', '"', '"'});
        String s = """
public class Main {
    public static void main(String[] args) {
        char n = 10;
        String t = new String(new char[]{'"', '"', '"'});
        String s = %s;
        System.out.printf(s, t + n + s + t);
    }
}
""";
        System.out.printf(s, t + n + s + t);
    }
}

步骤二

如何构建一个自编译的编译器（即由要编译的语言编写的编译器），是一个先有鸡还是先有蛋的问题，解决方案是引导（Bootstrapping）。简单来说，首先使用机器支持的语言编写编译器 A 的源代码，编译器 A 可以编译目标语言的子集。然后使用目标语言的子集编写编译器 B 的源代码，经过编译器 A 编译得到编译器 B 的二进制文件。之后就可以不断重复，得到支持完整目标语言的编译器。

1
2

if (c == 'v') return 11; // 旧编译器可以识别
if (c == 'v') return '\v'; // 新编译器才能识别

论文提到的例子是，在目标语言中添加 \v 符号，表示垂直制表符。由于旧编译器不识别该符号，所以使用垂直制表符的 ASCII 码 11 扩展旧编译器的源代码，旧编译器编译扩展后的源代码得到新编译器，新编译器就能够识别 \v 符号。

步骤三

修改编译器，以匹配指定模式，如果匹配则错误地编译源代码，这是特洛伊木马（Trojan horse）。可以在编译器中插入指定的匹配模式（后门，backdoor），使其匹配 login 命令的源代码。如果用户使用该编译器编译 login 命令，则命令会被错误编译，从而可以使用指定的密码登录系统的任意用户。

最关键的是，如果再添加一个针对编译器自身的匹配模式，在识别到当前正在编译编译器时，将特洛伊木马插入到新编译器中，则可以实现类似步骤二中的“学习”过程。也就是说，即使编译器 B 的源代码是正确的，使用包含以上两个匹配模式的编译器 A 编译，得到的编译器 B 的二进制文件依然包含两个特洛伊木马。最终，编译器 B 仍会错误地编译 login 命令，而编译器 B 的源代码却是正确的。

论文提到，将特洛伊木马插入到新编译器中，使用的是步骤一的自我复制程序。我看半天才理解这句话，可以这么想，特洛伊木马需要获取自身的代码，然后插入到新编译器的特定位置，类似自我复制需要输出自身的代码。

参考 Reducible。

问题

如何求两个 \(n\) 次多项式 \(A(x)\) 和 \(B(x)\) 的乘积 \(C(x)\)？最简单的方式是使用乘法分配律对每个系数做乘积，时间复杂度为 \(O(n^{2})\)。

另一种想法是：① 在多项式 \(A(x)\) 和 \(B(x)\) 上取 \(2n+1\) 个点 \(x_{i}\)，其中 \(i=0,1,\cdots,2n\)，求出对应的函数值。② 根据 \(C({x_{i}})=A(x_{i})\cdot B(x_{i})\)，可以得到 \(C(x)\) 上的 \(2n+1\) 个点。③ 使用拉格朗日插值，化简得到 \(C(x)\) 的表达式。总时间复杂度为 \(O(n^{2})\)，如果能够将 ① 和 ③ 的时间复杂度优化为 \(O(n\log{n})\)，那么就能够降低总时间复杂度。

优化步骤 ①

可以发现，对于偶函数 \(f(x)=f(-x)\)，对于奇函数 \(f(x)=-f(-x)\)。如果将多项式分解为偶函数和奇函数两部分，则可以可以利用对称性快速求点值。不妨设 \(n\) 为偶数，将 \(n-1\) 次多项式 \(P(x)\) 划分为偶函数和奇函数两部分。

设 \(P_{e}(x)=p_{0}+p_{2}x^{1}+\cdots+p_{n-2}x^{\frac{n}{2}-2}\)，\(P_{o}(x)=p_{1}+p_{3}x^{2}+\cdots+p_{n-1}x^{\frac{n}{2}-2}\)，则 \(P(x)=P_{e}(x^{2})+xP_{o}(x^{2})\)。此时，如果取 \(n\) 个点 \(\pm x_{0},\pm x_{1},\cdots,\pm x_{\frac{n}{2}-1}\)，则只需要计算 \(P_{e}(x_{i}^{2})\) 和 \(P_{o}(x_{i}^{2})\)，就能够通过以下方式得到两个函数值。

所以，要求 \(P(x)\) 上的 \(n\) 个点值，等价于求 \(P_{e}(x^{2})\) 和 \(P_{o}(x^{2})\) 上的 \(\frac{n}{2}\) 个点值，即点 \(x_{0},x_{1},\cdots,x_{\frac{n}{2}-1}\) 的值。此时，原问题被分解为两个相同的子问题，并且子问题的大小只有原问题的一半，如果子问题能够按照原问题的方式继续分解，则可以得到时间复杂度为 \(O(n\log{n})\) 的算法。

但是，\(P_{e}(x^{2})\) 和 \(P_{o}(x^{2})\) 不能继续分解，因为定义域 \(x^{2}\geq 0\)，点 \(x_{0}^{2},x_{1}^{2},\cdots,x_{\frac{n}{2}-1}^{2}\) 不构成正负对，也就不能利用对称性求点值。如果能够取到一组构成正负对的点，在子问题中所有正点依然构成正负对，那么就可以继续递推。此时，需要引入复数，例如，取点 \(\pm 1,\pm i\) 构成正负对，子问题中 \(1^{2},i^{2}\) 等价于 \(1,-1\) 依然构成正负对。

那么对于 \(n-1\) 次多项式，如何取满足条件的 \(n\) 个点？假设取某个点 \(z\)，那么必然要取 \(-z\)，在子问题中 \(z\) 变为 \(z^{2}\)，那么必然要取 \(-z^{2}\)，以此类推，假设 \(n\) 为 \(2\) 的幂（总是可以通过对高次项补系数 \(0\) 取到），则最终得到 \(z^{n}\)。也就是说，所有取值的 \(n\) 次方都相等，不妨设 \(z^{n}=1\)，求解方程可以得到 \(n\) 个单位根，即为满足条件的 \(n\) 个点。

设复数 \(z=a+bi\)，则极坐标表示为 \(z=r(cos(\varphi)+isin(\varphi))\)，根据欧拉公式，有 \(z=re^{\varphi i}\)。要求 \(z^{n}=1\)，即求 \(r^{n}e^{\varphi ni}=e^{2k\pi i}\)，得出 \(r=1,\varphi =\frac{2k\pi}{n}\)，所以 \(z=e^{\frac{2k\pi}{n}i}\)，其中 \(k=0,1,\cdots,n-1\)。设 \(w_{n}=e^{\frac{2\pi}{n}i}\)，则 \(n\) 个单位根分别为 \(w_{n}^{0},w_{n}^{1},\cdots,w_{n}^{n-1}\)，它们将复平面中的单位圆 \(n\) 等分。

观察单位根的性质，有 \(w_{n}^{k}=-w_{n}^{k+\frac{n}{2}}\)，\(w_{n}^{k}=w_{\frac{n}{2}}^{\frac{k}2}\)，所以 \(w_{n}^{0},w_{n}^{1},\cdots,w_{n}^{\frac{n}{2}-1}\) 和 \(w_{n}^{\frac{n}{2}},w_{n}^{\frac{n}{2}+1},\cdots,w_{n}^{n-1}\) 构成正负对。在子问题中，\(w_{n}^{0},w_{n}^{1},\cdots,w_{n}^{\frac{n}{2}-1}\) 变为 \(w_{n}^{0},w_{n}^{2},\cdots,w_{n}^{n-2}\)，等价于 \(w_{\frac{n}{2}}^{0},w_{\frac{n}{2}}^{1},\cdots,w_{\frac{n}{2}}^{\frac{n}{2}-1}\)，前半和后半依然构成正负对，以此类推。从复平面的角度思考，更容易理解。

根据上述讨论，单位根的正负对性质，在所有子问题中都成立，所以求 \(n-1\) 次多项式 \(P(x)\) 的 \(n\) 个点值，可以使用递归分治的方式求解。当 \(n=1\) 时，多项式是常数，\(P(w_{1}^{0})\) 就是该常数值。当 \(n>1\) 时，如果已知 \(P_{e}(x^{2})\) 和 \(P_{o}(x^{2})\) 在 \(w_{n}^{k}\) 的点值，其中 \(k<\frac{n}{2}\)，则利用之前推出的 \(P(x)=P_{e}(x^{2})+xP_{o}(x^{2})\) 公式可以得到以下两个函数值。

优化步骤 ③

步骤 ① 是已知系数，求 \(n-1\) 次多项式 \(P(x)\) 在 \(n\) 个 \(n\) 次单位根位置的值，可以看作矩阵相乘的形式。

步骤 ③ 是已知 \(n\) 个点值，求多项式的系数，可以看作上述变换的逆变换。

如果将步骤 ① 表示为 \(FFT(w_{n},p_{0},p_{1},\cdots,p_{n-1})\)，则步骤 ③ 为 \(IFFT(w_{n},P(w_{n}^{0}),P(w_{n}^{1}),\cdots,P(w_{n}^{n-1}))=\frac{1}{n}FFT(w_{n}^{-1},P(w_{n}^{0}),P(w_{n}^{1}),\cdots,P(w_{n}^{n-1}))\)。

参考 Coroutines for Go，Coroutine Wiki。

什么是协程（coroutine）？通常使用的函数（function）也被称为子例程（subroutine），一系列调用会形成一个调用栈（call stack），调用者（caller）和被调用者（callee）是父子关系。而协程不同，协程之间是对等关系，每个协程都有一个调用栈。协程有非对称和对称两种实现，非对称协程使用 resume 和 yield 关键字，调用者使用 resume 恢复某个协程，被调用者使用 yield 暂停当前协程，然后控制会转移到调用者。对称协程只使用 yield 关键字，但是需要指定将控制转移给哪个协程。经典的例子，比较两个二叉树是否包含相同的序列（中序遍历），代码。

协程的控制转移是主动的（非抢占式），不需要操作系统支持，也不需要使用锁和信号量等同步原语。线程的控制转移是被动的（抢占式），由操作系统调度，上下文切换更加昂贵，需要使用同步原语保护共享变量。协程只提供并发性，而线程可以利用多核 CPU 实现并行。切换的速度，协程最多 10 纳秒，线程几微秒，Goroutines 和 Virtual Threads（Java 21） 几百纳秒。

网络上各种术语的解释很混乱，根据多线程模型，我倾向于使用用户线程和内核线程的对应关系，来描述不同的实现。简单描述一下我的理解：平常使用的是一对一模型，Goroutines 和 Virtual Threads 使用的是多对多模型。协程不能简单的看作多对一模型，协程是非抢占式的用户线程，描述的是多个用户线程之间的协作关系，实际上可以在各个模型上实现协程。

关于 Goroutines 的实现，可以看 Dmitry Vyukov 的演讲 Go scheduler: Implementing language with lightweight concurrency。其他资源：Scalable Go Scheduler Design Doc，The Go scheduler，HACKING。

简单的设计，使用一对一模型 + 线程池，缺点是线程的内存占用较大，Goroutine 阻塞会导致线程阻塞，没有“无限数量”的栈。所以，使用多对多模型，Goroutine 占用内存更小，可以被 Go runtime 完全控制。如果 Goroutine 因为锁/通道/网络 IO/计时器而阻塞，Goroutine 将会进入阻塞队列，运行此 Goroutine 的内核线程不会阻塞，Go runtime 可以从 Run Queue 中调度 Runnable 的 Goroutine 到该内核线程上（复用，Multiplex）。

但是，当 Goroutine 进行系统调用，控制将从 Goroutine 转移到系统调用处理程序，Go runtime 是无法感知该处理流程的，直到系统调用返回，所以此时运行 Goroutine 的内核线程是无法被复用的。有可能所有内核线程都阻塞在系统调用上，而该系统调用所需的资源被某个 Runnable 的 Goroutine 持有，从而发生死锁。所以在系统调用发生时总是会创建/唤醒一个内核线程，执行 Run Queue 中的 Goroutine。当内核线程从系统调用返回，Go runtime 将内核线程上的 Goroutine 放入 Run Queue，使该内核线程空闲从而保证指定的并行度（由 GOMAXPROCS 指定）。

关于 GOMAXPROCS，runtime 文档的描述如下：The GOMAXPROCS variable limits the number of operating system threads that can execute user-level Go code simultaneously. There is no limit to the number of threads that can be blocked in system calls on behalf of Go code; those do not count against the GOMAXPROCS limit.

该实现的瓶颈在全局的互斥锁（MUTEX），内核线程创建 Goroutine 以及获取 Goroutine 都需要操作共享的 Run Queue。解决方案很容易想到，就是为每个内核线程创建本地变量，从而避免频繁访问全局的共享变量。该方案会增加获取下一个 Goroutine 的复杂性，Go 调度器实现的获取顺序是， Local Run Queue、Global Run Queue、Network Poller、Work Stealing。

由于发生系统调用时会创建/唤醒内核线程，也就是说内核线程的数量会多于 CPU 的核心数量。新的调度器为每个内核线程分配本地资源，但是实际上执行 Go 代码的内核线程的数量是固定的（由 GOMAXPROCS 指定），所以空闲线程不应该持有资源，会造成资源浪费以及降低 Work Stealing 的效率。所以，设计上引入一个新的实体，也就是处理器（Processor），从而调度模型从 GM 变为 GMP。Go runtime 不会为每个内核线程分配资源，而是为 Processor 分配资源，Processor 的数量就是 CPU 的核心数量。在新的模型中，当 Goroutine 发生系统调用时，Goroutine 会创建/唤醒新的内核线程，然后将 Processor 对象交给新的内核线程。

目前，调度器已经足够好，不过可以更好。公平性（Fairness）和性能的权衡：设计者想要以最小的性能开销获得最小的公平性。FIFO 队列可以一定程度上保证公平性，但是如果当前 Goroutine 陷入无限循环，队列中的 Goroutine 将会饥饿，所以设计者使用 10 ms 的时间片轮转调度（时分共享，抢占式）。另一方面，FIFO 队列缺少局部性（影响性能），最后进入队列的 Goroutine 会在最后运行。常见的场景，当前 Goroutine 创建另一个 Goroutine，然后自身被阻塞等待另一个 Goroutine 执行。缺少局部性的 FIFO 会产生很大延迟，所以设计者在 Local Run Queue 的尾部添加一个单元素的 LIFO 缓冲区，每次获取 Goroutine 都会首先从缓冲区中获取（Direct Switch）。

该设计引入额外两个问题，一个是其他内核线程从当前内核线程 Work Stealing 时，将 LIFO 中的 Goroutine 窃取，影响 Direct Switch 的执行。解决方案是只有 Goroutine 被放入 LIFO 超过 3 μs 才能被窃取。另一个问题是，不断创建 Goroutine 会导致 LIFO 缓冲区总是有元素，从而 FIFO 队列中的 Goroutine 会饥饿，解决方案是当前 Goroutine 和 LIFO 中的 Goroutine 共享同一个 10 ms 的时间片。

如果 Local Run Queue 一直不为空，Global Run Queue 会饥饿。所以，假设当前是第 schedTick 次获取，设计者设置当 schedTick % 61 == 0 时，优先从 Global Run Queue 获取 Goroutine。为什么使用 61，因为 61 不大不小，太大会饥饿，太小会因为 Global Run Queue 的 MUTEX 限制性能，并且参考哈希表的设计，使用质数而不是 2 的幂会更随机/公平。

最后，Network Poller 可能会饥饿，解决方案是使用后台线程从中定期获取 Goroutine。之所以不像处理 Global Run Queue 饥饿一样在当前线程中获取，是因为从 Network Poller 获取 Goroutine 涉及到 epoll_wait() 系统调用（很慢）。