一文解析数据结构是如何装入 CPU 寄存器的？

我们在之前很多文章的讲解中涉及了CPU与寄存器，然后有同学问了这样一个问题：既然CPU内部的寄存器数量有限，容量有限，那么我们使用的庞大的数据结构是怎样装入寄存器供CPU计算的呢？这篇文章就为你讲解一下这个问题。

内存与数据

真正有用的程序是离不开数据的，比如一个int、一个float等，这些都是非常简单的数据。当然也有非常复杂的数据，这样的数据通常在内存中以数据结构的形式组织起来，比如你创建了一个数组、一个链表、创建了一棵树、一张图，就像这样：

那么很显然这些数据存放在内存中，而且这些数据在不同的场景下有不同的大小，从数B、数KB到数百GB都有可能，与此同时，CPU内部的寄存器数量是固定的，容量也是极其有限的，那么CPU是如何利用有限的资源操作庞大的数据结构呢？

要回答这一问题，我们需要要认识一位农夫，因为他不生产数据，他只是数据的搬运工，这位农夫就是。。

搬运数据的机器指令

你没有看错，这位农夫就是我们之前多次提到的机器指令。机器指令中除了负责逻辑运算、执行流控制、函数调用等指令外，还有一类指令，这类执行只负责和内存打交道，典型的就是精简指令集架构中的Load/Store机器指令，即内存读写指令(复杂指令集没有单独的内存读写指令)。原来，从宏观上看的话，存放在内存中的数据，比如一个数组，可能会非常庞大，但是具体到代码，每一个步骤操作的数据又会非常简单，就像这样：

int* huge_arr = new int[1 * 1024* 1024 *1024];

我们创建了一个长度为1G的数组，每个int 4字节，则这个数组的大小就是4GB，这显然是一个很庞大的数组。对于这样的数据，我们通常都会怎么使用呢？最常见的情况可能是遍历一边，然后对每个字符进行一个简单操作，这里以计算数组之和为例：

long int sum = 0;
for (int i = 0; i < 1 * 1024* 1024 *1024; i++) {
    sum += huge_arr[i];
}

虽然整个数组多达4GB，但具体到每一步我们一次只能操作一个元素，就像这里的：

sum += huge_arr[i];

这行代码翻译成机器指令可能是这样的，我们假设此时i为100：

load $r0 100($r2)
add $r1 $r1 $r0

(注意，实际当中编译器不会傻傻的生成100这样的常数，这里代码仅用来方便讲解问题)。

第一行指令中数组首地址存放在寄存器r2中，100($r2)表示数组首地址+100，这样我们就能得到huge_arr[100]的地址了，然后将该地址中的值利用load指令加载到寄存器r0中。第二行就简单多了，r1寄存器中保存的是sum的值，该行指令执行过后r1中的值就已经加上了huge_arr[100]。现在你应该能看出来了吧，虽然我们不能把整个数组加载到寄存器供CPU计算，但这其实是没有必要的，因为我们一次只能操作数组中的一个元素，我们只需要把这一个元素加载到寄存器就足矣了。

对于其它复杂的数据结构也是同样的道理，无论多么复杂的数据，代码对其一次的操作都是很简单很微小的，这一微小的操作使用的基本元素都可以通过内存读写指令加载到寄存器，修改完后再写回内存。

编译器

现在你应该知道了为什么CPU内部那么少的寄存器能操作内存中庞大的数据结构，实际上由于内存中的数据要远大于CPU寄存器的容量，因此编译器必须精心挑选，好让那些经常使用的数据放到寄存器中的时间更长一点，这样可以减少内存读写次数。在上面的示例中，r2寄存器保存的是huge_arr这个数组在内存中的起始地址，那么这个数据应该放到寄存器中，因为后续遍历到的每一个元素都要用到该地址，这项工作就是编译器来完成的。编译器把那些经常使用的数据放到寄存器，剩下的放到内存中，然后利用内存读写指令在寄存器和内存之间来回搬运数据。