性能
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；咱们也会在这里分享咱们对行业的了解，期待越来越多的同学意识主动驾驶，退出这个行业！