性能
C++，作为最艰涩、最难把握的支流编程语言，一贯是容易上手，却很难写好。而这难写好的局部中，除了代码格调等稍微形象的局部，最难也最容易忽略的局部则是性能了。依据经典的二八准则，通常 20% 左右的代码耗费了 80% 左右的性能。然而，用户日常接触到的性能、或者在日常应用的场景下，性能是能够满足的，因而这往往造成程序员的漠视并埋下了隐患。
通常状况下，一旦遇到性能问题，那将是比性能问题更辣手、更难解决的。
C++，作为常常和硬件间接打交道的高级语言，性能问题堪称是重灾区。 本系列文章，将联合实践和实际，深度分析典型的性能问题和陷阱。
在上一篇性能专题的文章（点击可跳转上期文章）中，咱们具体地介绍了 C ++ 代码中的性能杀手【拷贝】，并提供了几类具备针对性的应答措施。然而作为须要时刻思考硬件条件的编程语言，如果你认为防止了不必要的结构和拷贝，就能够领有极致的性能的话，那就大错特错了。
让咱们来看一个与拷贝无关，然而又存在显著性能问题的例子。
举例
CPU Cache
首先咱们须要介绍一下什么是 CPU Cache。
在咱们写代码的时候，有 3 个计算机硬件和咱们关系密切，别离是 CPU、内存和硬盘。为什么这样说呢？因为咱们敲的代码和编译进去的执行文件是存储在硬盘上的，每次程序启动，对应的数据和代码被加载进内存，而后各种各样的指令会在 CPU 中运行。
看似内存中的数据会被间接加载进 CPU 进行解决，而后这两头实际上还存在着一个至关重要的组件：缓存（CPU Cache）。缓存通常会存储着最近拜访过的内存中的数据（这就是大家相熟的 LRU、LFU 等缓存替换算法作用的中央），它领有远快于内存（RAM）的访问速度，然而容量也显著地小于内存，它能够被视作 CPU 和内存数据的桥梁。
同时，CPU Cache 也有不同的品种，次要有 D -Cache，I-Cache 和 TLB。
其实只有晓得全名，就很好了解了。D-Cache 全名 data cache，用来缓存数据。I-Cache 全名 instruction cache，用来缓存 CPU 指令。TLB 全名 translation lookaside buffer，用来缓存虚拟内存到物理内存的映射后果。
TLB 看似让人摸不着头脑，然而有一个好消息是：如果 D -Cache 和 I -Cache 可能被很好地利用，那么 TLB 的性能通常也能从中受害。
I-Cache 呢，在小片代码中区别不会太大，而且编译器会帮忙做肯定的优化，因而咱们最首要思考的就是 D -Cache，它和咱们写代码的形式具备最严密的分割。
以一个 6 核 12 线程 CPU 为例，Cache 的构造大抵如下：
能够看到，每个物理外围领有 2 个硬件线程，每个线程领有本人的 L1 Cache，每个外围领有本人的 L2 Cache，所有外围共享 L3 Cache 和内存。（请记住这个构造，前面的剖析都会基于此）
那么，这些 CPU Cache 具体是怎么影响咱们代码的性能的呢？
前文中咱们提到了，CPU Cache 是 CPU 和内存之间的桥梁并且领有多个档次，可能此时咱们曾经发现，如果每一级缓存领有不同的访问速度，是不是就会导致拜访同样的数据（这些雷同的数据可能因为之前的拜访形式坐落于不同级的缓存和内存中）耗费不同的工夫？答案是必定的，下图中能够看到一个典型的古代 CPU 各个硬件的访问速度。能够看到，L1 Cache 的访问速度根本是内存的 100 倍以上，L2 Cache 则是 10 倍以上。
因而，整体上来看，越高的缓存命中率意味着程序具备越高的性能。 所谓缓存命中率，直白地说，就是指原本要去内存中读取的数据，正好存在于缓存中的比例。
那么，是什么样的起因会导同样的数据在不同的拜访模式下会坐落于不同层级的缓存中呢？这就不得不提到缓存的存储形式和根本单元了。
CPU Cache 的根本单元叫做 cache line，这些 cache line 中存储的就是内存中的 hottest data。内存和 Cache 替换数据都是通过它。对于典型的古代处理器，cache line 的大小通常都是 64 bytes，意味着，每一条 cache line 能够存储 8 个 64 位的整型。到目前为止，所有看上去都那么失常。
然而，cache line 有一个十分非凡的性质，就是它的读写必须操作一整条！比方，你只想读前 8 个 bytes，对不起，不行，整条 cache line 都会被读取；你只想写最初 8 个 bytes，对不起，不行，整个 cache line 都须要更新。
缓存局部性（Cache locality）
有了下面对于 CPU Cache 的介绍，咱们能够剖析为什么例 1 中拜访二维数组的形式会对性能有如此大的影响了。以下剖析咱们思考冷启动的模式，意即缓存最开始是空的，外面没有任何数据。
留神到，咱们的二维数组中存储的数据类型为整型，每个元素的大小为 8 bytes，因而一条大小为 64 bytes 的 cache line 能够存储 8 个数据。
如果咱们一行一行地拜访二维数组数组，第一次读取缓存的某条 cache line 的时候，数据不在缓存上，须要从内存中读取，因而这次是一次 cache miss，CPU 读取这条数据的耗时是 t_memory + t_cache。然而请留神，因为 cache line 的个性，它的操作必须是整条的，因而在 t_memory 的这次耗费中，在内存上相邻的另外 7 个 int64 型的数据也被加载到了这条 cache line 中。因为咱们是按行读取，前面拜访的 7 个数据正好就是被加载进了 cache line 的数据，他们的读取工夫都只须要 t_cache，省去了 7 次 t_memory 的高额开销。
在这种状况下，每读取 8 个元素的总工夫开销就是 t_memory + 8 t_cache。以上图中的硬件为例，仅思考 L2 Cache，即 100 + 8 7 = 156ns。
反观一列一列地拜访二维数组，读取每一列第一个元素的时候，与上述情况雷同，内存上相邻的 7 个数据也被加载进了 cache line 中。然而可怜的是，这里是按列拜访的，同一列下一行的数据并不是被提前加载进 cache line 的，这就须要持续把内存中的数据加载进下一条 cache line 中，使得所有的操作都会产生 cache miss，从而耗时都是 t_memory + t_cache。
更蹩脚的是，当拜访到第 n（n>1）列的时候，如果此时缓存已耗尽，则须要将旧的数据从 cache 中踢出并加载进新的数据（同样地，新加载的数据会因为按列拜访的模式持续无用武之地）。
即便咱们疏忽缓存替换的工夫开销，着这种模式下，每读取 8 个元素的总工夫开销就是 8 (t_memory + t_cache)，以上图中的硬件为例，仅思考 L2 Cache，即 8 (100 + 7) = 856ns。这就是导致二维数组按列拜访性能差的根本原因。
侥幸的是，依据大多数人的习惯，如果没有非凡的需要，咱们很天然地就会依照行优先（一行一行地）的模式来拜访二维数组，因而这个问题在绝大多数状况下被天然而言地防止掉了。
然而，咱们这里不可一概而论地认为，二维数组按列拜访的性能就肯定比按行拜访差。
不错，一个更加精确的形容应该为， 对于按行存储的二维数组，应该应用按行拜访的形式；对于按列存储的二位数组，应该应用按列拜访的形式。而 Eigen 中的数据，正是按列存储的。
因而，咱们能够看到在 Eigen 中遍历二位数组的代码通常和遍历 std::vector 的行列先后顺序调换。
结语
C++ 作为一个谋求效率又和硬件严密关联的高级语言，想要纯熟掌控它的性能，必须对计算机体系架构领有足够的认知。
本文旨在抛砖引玉，与大家探讨处理器缓存带来的微小的性能差别。鉴于笔者程度无限，此文必然存在诸多值得商讨之处，欢送批评指正，共同进步。
对于 DeepRoute Lab
深圳元戎启行科技有限公司（DEEPROUTE.AI）是一家专一于研发 L4 级主动驾驶技术的科技公司，聚焦出行和同城货运两大场景，领有“元启行”（Robotaxi 主动驾驶乘用车）和“元启运”（Robotruck 主动驾驶轻卡）两大产品线。
【Deeproute Lab】是咱们开办的主动驾驶学术产业前沿常识共享平台。咱们将会把公司外部的 paper reading 分享在这里，让你轻松读懂 paper；咱们也会在这里分享咱们对行业的了解，期待越来越多的同学意识主动驾驶，退出这个行业！