Meme of LinOnetwo

寇老师本来让我在数字集成电路课上简单讲一讲「不同指令实际运行的步骤」，不过我好久没看指令那部分了，怕讲得磕磕绊绊，于是我打算从我比较熟悉的浏览器开始，讲讲不同层次上的预测和浪费。

之前听到 Look Ahead Adder 的时候我就觉得它类似于预测，提前准备好数据

$C_{out,k}=G_k+P_k\times C_{out,k-1}$

$C_{out,k}=G_k+P_k\times (G_{k-1}+P_{k-1}\times C_{out,k-2})$

All the way:

$C_{out,k}=G_k+P_k\times (G_{k-1}+P_{k-1} (...+P_1 \times(G_0+C{i,0})))$

如果你预测一个数据未来会被程序使用到，那么就应该预加载、预编译、预运行它。

浏览器应用层

Google I/O 2019 提出，越来越多的网站开始做代码分块，延迟加载暂时用不到的块，因为

1. 单页面应用（Single Page App）越来越大
2. 加载同样大小的 JS 和图片，JS 消耗的时间更多（因为需要 gzip、unzip、解析等）

代码分割（Code Splitting）可以在你使用「创建新文章」表单时仅加载渲染这个表单所需的 JS：

但是在地铁里打开这样的 SPA 时，加载下一个页面就要加载下一个块，这会很卡：

我们习惯了打开一个 SPA 后就应该有丝滑体验，切换 route 不应该会卡。所以预加载。

风险：

1. 消耗大量网络资源来预加载用户并不会去访问的页面的 JS
2. 折腾了半天预测错了，该加载的 JS 却没有加载

降低风险：

1. 通过 Google Analytics 统计路由跳转概率，训练一个预测模型
2. 用户访问页面时，用马尔科夫链或训练好的 RNN 预测下几个要加载的 JS

JS JIT 层

JS 是一个很快的语言，金主 Google 将其速度提升到了 C++ 的二十分之一到二分之一。

到底是几分之一取决于 Just In Time 引擎有没有预测到下一个操作。

例如运行 for 循环时：

function arraySum(arrayToSum: Array<number>) {
  let sum: number = 0;
  for (let index = 0; index < arrayToSum.length; index++) {
    sum += arrayToSum[index];
  }
	return sum;
}

一开始是解释执行，解释结果跑完一次就丢掉

然后 JS 引擎中有一个 Monitor 会监控

1. 每段代码运行的次数
2. 代码中的变量的类型

如果相加这段代码运行次数足够多就会被标记为 Warn，允许它享受基本的缓存服务、生成优化的代码（比如使用 j 跳转回循环开头）：

但是 JS 是动态类型的，+ 可能会产生多种编译结果

在运行时，引擎会担心数组里可能有数字也可能有字符串，所以会把每种类型组合的相加操作都编译一组 operation 出来

这时每次循环都要检查类型组合是什么，然后取出对应的缓存好的指令，这仍然比重新解释要快

如果跑得足够多，Monitor 就会发现其实数组里都是 int 类型的数字，就可以抛弃掉其他组合的指令了，而且可以重新排列指令生成巨优化的代码

当然这假设了每个变量的类型就是我们猜的那样

如果我们猜错了，比如数组中间突然放了一个字符串…就会去优化 （deoptimization）

风险：

1. 可能会猜错，导致浪费很多内存去缓存指令、浪费 Monitor 的时间去打扫缓存
2. 优化了的代码没用几次就弃如敝履，浪费一片好心

解决风险：

1. 鼓励Web程序员使用TypeScript等带静态类型标注的语言
2. 如果 Monitor 翻错太多次，就让它冷静一会儿，先不要在这块代码上继续送人头了

Pipeline

指令级并行（ILP）指 CPU 流水线设计，使得多条指令可以并行执行，让每一块电路都不闲着。

单发射处理器的指令执行在一个时钟周期内只从存储器中取出一条指令，并且只对一条指令进行译码，只执行一条指令，只写一个运算结果。

如果在电路中放多个取指令部件，多个指令译码部件和多个写结果部件，就成了多发射处理器。

并行化是一种优化，有很多形式：

1. 循环的编译期展开
2. 用特殊的数字电路在运行时展开循环
3. 分支预测

以分支预测为例：

运行时会有一个叫分支预测器的数字电路，在分支指令执行前，猜测哪一个分支会被执行。

遇到 JMP 时，它通过一条信号线给出 1 （taken：执行JMP指令）或者 0 （not taken，跳过 JMP，继续往下执行）

风险：

1. 猜错了会浪费 20 个左右的时钟周期

解决风险：

1. 连续预测错两次就不要瞎预测了

每当一个branch taken，就 +1，branch没有taken则 -1；根据第一位的值来进行预测，例如 11 预测taken，01 预测 not taken

Branch Detection

之前提到预加载 JS，gzip

ALU

在这一层上没法像其它层那样根据运算的执行概率做缓存、优化等操作，因为它已经几乎是最底层的了。

但它同时计算多种运算的结果，几个选择器会根据 S （opcode）把所需的数据（结果、进位等）取到出口处。Result2 是乘法除得到的高位数据。