旭穹の陋室

指令级并行 当程序员听到并行（parallelism）这个词时，他们主要想到的是多核并行（multi-core parallelism），即将计算过程明确地拆分为协同工作的半独立的线程（threads），以此解决常见问题。 这种并行主要是为了减少延迟（latency）和实现可扩展性（scalability），而不是为了提高效率（efficiency）。你可以用并行算法解决十倍大的问题，但它需要至少十倍的计算资源。尽管并行硬件越来越丰富，并行算法设计也越来越重要，但目前，我们先只考虑单个CPU内核的情况。 还有其他类型的并行，已经存在于CPU内核中，可以免费（不需要额外计算资源）使用。 指令流水线 要执行任何指令，处理器首先需要做大量的准备工作，包括： 从内存获取（fetch）机器代码块； 对其进行解码（decode）并分割成指令； 执行（execute）这些指令，其中可能涉及一些访存（memory）操作； 将结果写（write）回寄存器。 整个操作序列很长。即使是像将两个寄存器中的值相加这样简单的操作，也需要15-20个CPU周期。为了隐藏这种延迟，现代CPU使用了 ...

机器码布局 计算机工程师习惯将CPU流水线分为两个部分：前端（front-end），从内存获取指令并进行解码；后端，对指令进行调度并最终执行。通常，性能会受到执行阶段的限制，因此，我们在本书中的大部分工作都将用于后端优化。 但有时，当前端没有以足够快的速度向后端提供指令以使其饱和时，可能会发生相反的情况。这种情况可能有很多原因，所有这些最终都与机器码在内存中的布局有关，并以奇奇怪怪的方式影响性能，例如删除未使用的代码、交换if分支，甚至更改函数声明的顺序，都可能导致性能提升或恶化。 CPU 前端 在机器码被转换为指令，并且CPU理解程序员想要做什么之前，它首先需要经历两个我们感兴趣的重要阶段：取指（fetch）和译码（decode）。 在取值阶段，CPU只需从主存中加载一个固定大小的字节块，其中包含一些指令的二进制编码。这个块大小在x86上通常是32字节，在不同的机器上可能会有所不同。一个重要的细节就是这个内存块必须对齐：内存块的地址必须是其大小的倍数（在我们的例子中是32字节）。 接下来是译码阶段：CPU查看这个字节块，丢弃指令指针之前的所有字节，并将其余字节拆分为指令。机器指令使用 ...

间接分支 在汇编过程中，所有标签（labels）都将转换为（绝对或相对）地址，然后编码到跳转指令中。 你还可以通过存储在寄存器中的变量值进行跳转，称为计算跳转（computed jump）： jmp rax 这里有一些与动态语言和实现更复杂的控制流有关的有趣例子。 多路分支 如果你已经忘记了switch语句的用法，这里有一个美国评分系统中计算GPA的小程序： switch (grade) { case 'A': return 4.0; break; case 'B': return 3.0; break; case 'C': return 2.0; break; case 'D': return 1.0; break; case 'E': case 'F': return 0.0; b ...

函数与递归 要在汇编中“调用函数”，你需要跳转到函数的开头，执行完毕后再跳转回来。这引出了两个重要问题： 如果调用者将数据存储在与被调用者相同的寄存器中，该怎么办？ 跳转回那个地方？ 这两个问题都可以通过在内存中设置一个专用位置来解决，在调用函数之前，我们可以往该位置写入从函数返回时需要的所有信息。这个位置被称为栈（stack）。 栈 硬件栈的工作方式与软件栈相同，并且类似地仅用两个指针进行实现： 栈底指针（base pointer）标记栈的开始，通常存储在rbp寄存器中； 栈顶指针（stack pointer）标记栈中最后一个元素，通常存储在rsp寄存器中。 当你需要调用一个函数时，你可以将所有本地变量压进栈中（在其他情况下也可以这样做；例如，当寄存器用完时），当前指令指针压栈，然后跳转到函数的开头。从函数中退出时，查看存储在栈顶的指针，跳转到那里，然后仔细地将存储在栈中的所有变量读取回对应的寄存器。 你可以通过一般的内存操作和跳转指令来实现压栈出栈操作，但由于使用频率的不同，有4条专用指令来实现： push在栈顶指针处写入数据并令其递减； pop从栈顶指针处读取数 ...

循环与条件 让我们考虑一个稍微复杂一点的例子： loop: add edx, DWORD PTR [rax] add rax, 4 cmp rax, rcx jne loop 它会对32位整数数组进行求和，就像简单的for循环一样。 循环体是add edx, DWORD PTR [rax]：该指令根据迭代器rax加载数据，并将其累加到累加器edx。接下来，我们通过add rax, 4将迭代器向前移动4个字节。然后，一件稍微复杂一些的事情发生了。 跳转 汇编语言没有高级语言所具有的if-s、for-s、函数或其他流控制结构。它所拥有的是goto，在低级编程世界中，它的另一个名字跳转（Jump）更为出名。 跳转将指令指针移动到由其操作数指定的位置。这个位置可以是内存中的绝对地址，相对于当前地址的相对地址，甚至可以是在运行时计算的地址。为了避免直接管理这些地址的麻烦，你可以用后面跟着:的字符串来标记任何指令，然后将此字符串用作标签，当转换为机器代码时，该标签将被该指令的相对地址所取代。 标签可以是任何字符串，但编译器没有创造性，在为标签选择名称时，通常只使用 ...

汇编语言 CPUs由机器语言（machine language）控制，机器语言只是一个二进制编码指令流，用于指定 指令号（称为操作码（opcode）） 它的操作数（operands）是什么（如果有的话） 以及将结果存储在哪里（如果产生了结果） 一种更人性化的机器语言，称为汇编语言（assembly language），使用助记码来指代机器码指令，使用符号名来指代寄存器和其他存储位置。 让我们直接开始，下面是使用Arm汇编进行两数相加*c = *a + *b的操作： ; *a = x0, *b = x1, *c = x2ldr w0, [x0] ; load 4 bytes from wherever x0 points into w0ldr w1, [x1] ; load 4 bytes from wherever x1 points into w1add w0, w0, w1 ; add w0 with w1 and save the result to w0str w0, [x2] ; write contents of w0 to wherev ...

指令集架构 作为软件工程师，我们绝对喜欢构造和使用抽象。 想象一下当你加载一个URL时会发生多少事情。你在键盘上打字；按键动作被操作系统以某种方式检测到并发送到浏览器；浏览器解析URL并要求操作系统进行网络请求；然后是DNS、路由、TCP、HTTP和所有其他OSI层；浏览器解析HTML；JavaScript发挥其魔力；页面的一些表示被发送到GPU以进行渲染；图像帧被发送到监视器……这每一个步骤中可能还会涉及到做几十件更具体的事情。 抽象有助于我们将所有这些复杂性降低到一个单一接口，该接口描述了某个模块可以做什么事情，而不需要关心具体实现。这提供了双重好处： 从事顶层模块开发的工程师只需要知道接口。 只要接口固定，从事模块本身开发的工程师就可以自由地优化和重构其实现。 硬件工程师也喜欢抽象。CPU的抽象被称为指令集架构（instruction set architecture，ISA），它从程序员的角度定义了计算机应该如何工作。与软件接口类似，它让计算机工程师有能力改进现有的CPU设计，同时也让用户——我们程序员——相信以前行之有效的东西不会在新的芯片上不适用。 ISA本质上 ...

前言 分配器（Allocator）是对堆内存管理的方法进行封装的类，在整个C++标准库，尤其是STL容器中被广泛使用。绝大数情况下，我们都是使用默认的分配器std::allocator，但其实我们可以自定义分配器，并将其应用到容器中。自定义分配器的理由可能有以下几种： 有些嵌入式平台没有提供默认的malloc、free等底层堆内存管理函数，你需要继承std::allocator，并封装自定义版本的malloc、free等底层堆内存管理函数； std::allocator的性能表现不能满足具体场景的需求； 类型别名 定义类型别名，可以根据需要自行定义： using value_type = T;using pointer = T *;using const_pointer = const T *;using reference = T &;using const_reference = const T&;using size_type = size_t;using difference_type = ptrdiff_t;using const_void_pointer ...

线程和数据竞争 当一个表达式（expression）的求值（evaluation）写入一个内存地址，而另一个求值读取或修改同一内存地址时，这些表达式被称为冲突（conflict）。具有两个冲突求值的程序具有数据竞争（data race），除非： 两个求值操作都在同一线程或同一信号处理程序（signal handler）中执行； 两个冲突的求值操作都是原子操作； 其中一个冲突的求值操作发生在另一个之前（引入内存顺序（std::memory_order）概念，另外也可通过加锁解决）； 当出现数据竞争时，程序的表现是未定义的。 概述 内存顺序究竟解决了什么问题？ 首先上个暴论：即便目前大多数资料（包括官方文档）中给出的示例都是关于多线程的，但是内存顺序其实不是限制多线程之间的指令的执行顺序。而是规定单个线程内的指令如何排序的。 是的，内存排序模型本身与多线程无关，而是限制单一线程中的指令执行顺序。但是指令执行顺序的（合理地）重排在单线程环境下不会造成逻辑错误，而在多线程环境下（可能）会，所以需要对重排进行限制。 让我从一个实际的例子逐步展开： int x = 0;// thread 1: ...

计算机体系结构 在我刚开始学习如何自己优化程序时，犯了一个很大的错误就是主要依赖经验主义方法。由于不了解计算机真正的工作原理，我会半随机地使用交换循环嵌套方式、重新排列算术、组合分支条件、显示使用内联函数等操作，或者遵循我从别人那里道听途说的各种其他性能优化技巧，盲目地希望性能有所提升。 不幸的是，大多数程序员都是这样做性能优化的。大多数关于性能的文本并不教你如何定性地思考软件性能。相反，它们会给你一些关于特定实现方法的一般性建议，而一般性的性能直觉显然是不够的。 如果我在学习算法编程之前学习了计算机体系结构，那么可能会为我节省数十甚至数百个小时。因此，即使大多数人对此不感兴趣，我们也将花费前几章学习CPU的工作原理，并开始学习汇编语言。