Content #

SIMD，中文叫作单指令多数据流（Single Instruction Multiple Data）。

我们先来体会一下 SIMD 的性能到底怎么样。下面是两段示例程序，一段呢，是通过循环的方式，给一个 list 里面的每一个数加 1。另一段呢，是实现相同的功能，但是直接调用 NumPy 这个库的 add 方法。在统计两段程序的性能的时候，我直接调用了 Python 里面的 timeit 的库。

$ python
>>> import numpy as np
>>> import timeit
>>> a = list(range(1000))
>>> b = np.array(range(1000))
>>> timeit.timeit("[i + 1 for i in a]", setup="from __main__ import a", number=1000000)
32.82800309999993
>>> timeit.timeit("np.add(1, b)", setup="from __main__ import np, b", number=1000000)
0.9787889999997788
>>>

从两段程序的输出结果来看，你会发现，两个功能相同的代码性能有着巨大的差异，足足差出了 30 多倍。也难怪所有用 Python 讲解数据科学的教程里，往往在一开始就告诉你不要使用循环，而要把所有的计算都向量化（Vectorize）。

有些同学可能会猜测，是不是因为 Python 是一门解释性的语言，所以这个性能差异会那么大。第一段程序的循环的每一次操作都需要 Python 解释器来执行，而第二段的函数调用是一次调用编译好的原生代码，所以才会那么快。如果你这么想，不妨试试直接用 C 语言实现一下 1000 个元素的数组里面的每个数加 1。你会发现，即使是 C 语言编译出来的代码，还是远远低于 NumPy。原因就是， NumPy 直接用到了 SIMD 指令，能够并行进行向量的操作。

Content #

超线程的 CPU，其实是把一个物理层面 CPU 核心，“伪装”成两个逻辑层面的 CPU 核心。这个 CPU，会在硬件层面增加很多电路，使得我们可以在一个 CPU 核心内部，维护两个不同线程的指令的状态信息。

比如，在一个物理 CPU 核心内部，会有双份的 PC 寄存器、指令寄存器乃至条件码寄存器。这样，这个 CPU 核心就可以维护两条并行的指令的状态。在外面看起来，似乎有两个逻辑层面的 CPU 在同时运行。所以，超线程技术一般也被叫作同时多线程（Simultaneous Multi-Threading，简称 SMT）技术。

不过，在 CPU 的其他功能组件上，Intel 可不会提供双份。无论是指令译码器还是 ALU，一个 CPU 核心仍然只有一份。因为超线程并不是真的去同时运行两个指令，那就真的变成物理多核了。超线程的目的，是在一个线程 A 的指令，在流水线里停顿的时候，让另外一个线程去执行指令。因为这个时候，CPU 的译码器和 ALU 就空出来了，那么另外一个线程 B，就可以拿来干自己需要的事情。这个线程 B 可没有对于线程 A 里面指令的关联和依赖。

这样，CPU 通过很小的代价，就能实现“同时”运行多个线程的效果。通常我们只要在 CPU 核心的添加 10% 左右的逻辑功能，增加可以忽略不计的晶体管数量，就能做到这一点。

不过，你也看到了，我们并没有增加真的功能单元。所以超线程只在特定的应用场景下效果比较好。一般是在那些各个线程“等待”时间比较长的应用场景下。比如，我们需要应对很多请求的数据库应用，就很适合使用超线程。各个指令都要等待访问内存数据，但是并不需要做太多计算。

于是，我们就可以利用好超线程。我们的 CPU 计算并没有跑满，但是往往当前的指令要停顿在流水线上，等待内存里面的数据返回。这个时候，让 CPU 里的各个功能单元，去处理另外一个数据库连接的查询请求就是一个很好的应用案例。

我这里放了一张我的电脑里运行 CPU-Z 的截图。你可以看到，在右下角里，我的 CPU 的 Cores，被标明了是 4，而 Threads，则是 8。这说明我手头的这个 CPU，只有 4 个物理的 CPU 核心，也就是所谓的 4 核 CPU。但是在逻辑层面，它“装作”有 8 个 CPU 核心，可以利用超线程技术，来同时运行 8 条指令。如果你用的是 Windows，可以去下载安装一个CPU-Z来看看你手头的 CPU 里面对应的参数。

Content #

代码优化技巧“循环展开”。让我们先来看一段代码：

#define LEN 4096
int data[LEN] = { ... };
int foo(void) {
  int acc = 1;
  for (int i = 0; i < LEN; ++i) {
    acc = acc * data[i];
  }
  return acc;
}

在这段代码中，我们定义了一个名为 data 的全局整型数组，并在其中存放了若干个值。而函数 foo 则主要用来计算该数组中所有数字的乘积之和。

此时，如果我们在 main 函数中调用函数 foo，CPU 在实际执行它的代码时， for 循环的每一轮都会产生两个数据相关：循环控制变量 i 的下一个值依赖于本次循环变量 i 在经过自增运算后得到的结果值。同样地，计数变量 acc 的下一个值也依赖于该变量在当前循环中经过乘积计算后的结果值。

而这两个数据相关会导致 CPU 无法提前计算下一轮循环中各个参与变量的值。而只有在寄存器写回，或内存访问阶段执行完毕，也就是变量 acc 和 i 的值被最终更新后，CPU 才会继续执行下一轮循环。

那么，应该如何优化这个过程呢？我们直接来看优化后的代码：

#define LEN 4096
int data[LEN] = { ... };
int foo(void) {
  int limit = LEN - 1;
  int i;
  int acc0 = 1;
  int acc1 = 1;
  for (i = 0; i < limit; i += 2) {  // 2x2 loop unrolling.
    acc0 = acc0 * data[i];
    acc1 = acc1 * data[i + 1];
  }
  for (; i < LEN; ++i) {  // Finish any remaining elements.
    acc0 = acc0 * data[i];
  }
  return acc0 * acc1;
}

可以直观地看到，参与到程序执行的局部变量变多了。而这里的主要改动是，我们为函数 foo 中的循环结构应用了 2x2 循环展开。

Content #

在某些情况下，可能只需要对程序的结构稍作调整，便能在很大程度上提升程序的运行性能。你可以先看看下面这段代码，思考下优化方式：

#define LEN 1024
int data[LEN] = { ... };
int foo(int* dest) {
  *dest = 1;
  for (int i = 0; i < LEN; i++) {
    *dest = *dest * data[i];
  }
}

在这段代码中，函数 foo 主要用来计算数组 data 中所有元素的乘积，并将计算结果值拷贝给指针 dest 所指向的整型变量。函数的逻辑很简单，但当仔细观察函数 foo 内部循环逻辑的实现时，便会发现问题所在。

在这个循环中，为了保存乘积在每一次循环时产生的累积值，函数直接将这个值更新到了指针 dest 指向的变量中。并且，在每次循环开始时，程序还需要再从该变量中将临时值读取出来。知道，从内存中读取数据的速度是慢于寄存器的。因此，这里可以快速想到一个优化方案。优化后的代码如下所示：

#define LEN 3
int data[LEN] = { 1,2,4 };
int foo(int* dest) {
  register int acc = 1;
  for (int i = 0; i < LEN; i++) {
    acc = acc * data[i];
  }
  *dest = acc;
}

在上面的代码中，一共做了两件事情：

1. 将循环中用于存放临时累积值的 “*dest” 替换为一个整型局部变量 “acc”；
2. 在定义时为该变量添加额外的 register 关键字，以建议编译器将该值存放在寄存器中，而非栈内存中。

通过消除不必要的内存引用，就能够减少程序访问内存的次数，进而提升一定的性能。

Content #

C99 标准新增了一个名为 restrict 的关键字，可以优化代码的执行。该关键字只能用于指针类型，用以表明该指针是访问对应数据的唯一方式。

在计算机领域，有一个名为 aliasing 的概念。这个概念是说内存中的某一个位置，可以通过程序中多于一个的变量来访问或修改其包含的数据。而这可能会导致一个潜在的问题：即当通过其中的某个变量修改数据时，便会导致所有与其他变量相关的数据访问发生改变。

因此，aliasing 使得编译器难以对程序进行过多的优化。而在 C 语言中， restrict 关键字便可以解决这个问题。当然，如果你学习过 Rust，这也是其所有权机制的核心内容。下面我们来看一个例子。

#include <stdio.h>
void foo(int* x, int* y, int* restrict z) {
  *x += *z;
  *y += *z;
}
int main(void) {
  int x = 10, y = 20, z = 30;
  foo(&x, &y, &z);
  printf("%d %d %d", x, y, z);
  return 0;
}

在这段代码中，函数 foo 共接收三个整型指针参数，它的功能是将第三个指针指向变量的值，累加到前两个指针指向的变量上。其中，第三个参数 z 被标记为了 restrict ，这表明我们向编译器做出了这样一个承诺：即在函数体 foo 内部，我们只会使用变量 z 来引用传入函数第三个指针参数对应的内存位置，而不会发生 aliasing。这样做使得编译器可以对函数的机器码生成做进一步优化。

来看下上面这段 C 代码对应的汇编代码：

foo:
        mov     eax, DWORD PTR [rdx]
        add     DWORD PTR [rdi], eax
        add     DWORD PTR [rsi], eax
        ret

在使用 restrict 关键字标注了 foo 函数的第三个参数后，在为指针 y 进行值累加前，编译器不会再重复性地从内存中读取指针 z 对应的值（对应上面第一行代码）。而这对程序的执行来说，无疑是一种性能上的优化。

Content #

默认情况下，编译器会采用自然对齐，来约束数据在内存中的起始位置。但实际 上，我们也可以使用 C11 提供的关键字 _Alignas ，来根据自身需求为数据指 定特殊的对齐要求。并且，头文件 stdalign.h 还为我们提供了与其对应的宏 alignas，可以简化关键字的使用过程。来看下面这段代码：

#include <stdio.h>
#include <stdalign.h>
int main(void) {
#if __alignas_is_defined == 1 && __alignof_is_defined == 1
  alignas(1024) int n = 1;
  printf("The alignment of n is \n", alignof(n));  // "The alignment of n is 1024".
  printf("The address of n is: %p\n", &n);  // "The address of n is: 0x7ffe80658c00".
#endif
  return 0;
}

在代码的第 4 行，我们首先通过验证宏常量 __alignas_is_defined 与 __alignof_is_defined 的值是否为 1，来判断当前编译环境是否支持 alignas 与 alignof 这两个宏。

在代码第 5 行，通过在变量 n 的定义中添加 alignas(1024) 标识符，我们可 以限定，变量 n 的值被存放在内存中时，其起始地址必须为 1024 的倍数。而 在接下来代码的第 6~7 行，我们分别通过使用 alignof 宏函数和直接查看地址 这两种方式，来验证我们对变量 n 指定的对齐方式是否生效。

Content #

#include <stdio.h>
int main() {
    int sum3 = (3 + 999 / 3 * 3) * (999 / 3) / 2;
    int sum5 = (5 + 999 / 5 * 5) * (999 / 5) / 2;
    int sum15 = (15 + 999 / 15 * 15) * (999 / 15) / 2;
    printf("%d\n", sum3 + sum5 - sum15);
    return 0;
}

假设，我们现在手上有两个集合，第一个集合中装的是所有 3 的倍数，第二个集合中装的是所有 5 的倍数，想想两个集合的交集是什么？是不是就是所有 15 的倍数。那么当我们用第一个集合的所有元素和，加上第二个集合中的所有元素和的时候，两个集合交集中的元素，被重复加了一次。所以，最后再减去两个集合交集中的元素和即可。

sum3, sum5, sum15的计算用到了“等差数列求和公式”。

From #

Links #

Content #

Employee本身实现了Comparable<Employee>接口。现有Java代码如下：

class Manager extends Employee
{
    public int compareTo(Employee other)
    {
        Manager otherManager = (Manager) other; // NO
        . . .
    }
    . . .
}

为什么这种实现方法是错误的？应如何解决？

Java语言对Comparable接口的实现有如下规定：

The implementor must ensure

sgn(x.compareTo(y)) = -sgn(y.compareTo(x))

for all x and y . (This implies that x.compareTo(y) must throw an exception if y.compareTo(x) throws an exception.)

如果x为Employee，而y是Manager，x.compareTo(y)不会抛出异常，而 y.compareTo(x)则会抛出异常，从而违反了这条规定。

解决的方案有两种：

• 认定两个不同类的对象不能比较，直接抛出异常：

if (getClass() != other.getClass()) throw new ClassCastException();

• 在超类中将compareTo声明为final，为所有自身或子类的对象制订统一的比

较规则。如，以Employee中的rank字段作为比较的依据。

Content #

我们对照 Top 运行界面，"%Cpu(s)“开头的这一行，你会看到一串数值，也就是 “0.0 us, 0.0 sy, 0.0 ni, 99.9 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st”，那么这里的每一项值都是什么含义呢？

下面这张图里最长的带箭头横轴，我们可以把它看成一个时间轴。同时，它的上半部分代表 Linux 用户态（User space），下半部分代表内核态（Kernel space）。这里为了方便你理解，我们先假设只有一个 CPU 吧。

1. “us"框，“us"是"user"的缩写，代表 Linux 的用户态 CPU Usage。
2. “sy"是 “system"的缩写，代表内核态 CPU 使用。
3. “wa"是"iowait"的缩写，代表等待 I/O 的时间，这里的 I/O 是指 Disk I/O。
4. 当磁盘返回数据时，进程在内核态拿到数据，这里仍旧是内核态的 CPU 使用中的"sy”，也就是图中的第四个框。
5. 进程再从内核态切换回用户态，在用户态得到文件数据，这里进程又回到用户态的 CPU 使用，“us”，对应图中第五个框。
6. 这时在这个 CPU 上也没有其他需要运行的进程了，那么系统就会进入"id"这个步骤，也就是第六个框。“id"是"idle"的缩写，代表系统处于空闲状态。
7. 如果这时这台机器在网络收到一个网络数据包，网卡就会发出一个中断（interrupt）。CPU 会响应中断，然后进入中断服务程序。这时，CPU 就会进入"hi”，也就是第七个框。“hi"是"hardware irq"的缩写，代表 CPU 处理硬中断的开销。
8. 从网卡收到数据包的大部分工作，都是通过软中断来处理的。CPU 就会进入到第八个框，“si”。这里"si"是"softirq"的缩写，代表 CPU 处理软中断的开销。

Viewpoints #

From #

05｜容器CPU（1）：怎么限制容器的CPU使用？

Content #

基于 Linux Namespace 的隔离机制相比于虚拟化技术也有很多不足之处，其中最主要的问题就是：隔离得不彻底。隔离不彻底主要体现在哪两个方面？

1. 既然容器只是运行在宿主机上的一种特殊的进程，那么多个容器之间使用的就还是同一个宿主机的操作系统内核。

2. 在 Linux 内核中，有很多资源和对象是不能被 Namespace 化的，最典型的例子就是：时间。这就意味着，如果你的容器中的程序使用 settimeofday(2) 系统调用修改了时间，整个宿主机的时间都会被随之修改，这显然不符合用户的预期。

From #

Links #