关于c++:百度C工程师的那些极限优化内存篇

导读：在百度看似简简单单的界面前面，是遍布全国的各个数据中心里，运行着的海量 C ++ 服务。如何晋升性能，升高延时和老本就成了百度 C ++ 工程师的必修功课。随同着优化的深刻攻坚，诞生并积攒下来一系列的性能优化实践和计划，其中不乏一些冷门但精美实用的教训和技巧。本文从内存拜访角度，收集总结了一些具备通用意义的典型案例，分享进去和大家学习交换。

1  背景

在百度看似简简单单的界面前面，是遍布全国的各个数据中心里，运行着的海量 C ++ 服务。对 C ++ 的重度利用是百度的一把双刃剑，学习老本平缓，指针类谬误定位难、扩散性广另很多开发者望而生畏。然而在另一方面，语言层引入的额定开销低，对底层能力可操作性强，又可能为谋求极致性能提供优异的实际环境。

因而，对百度的 C ++ 工程师来说，把握底层个性并加以利用来领导利用的性能优化，就成了一门必要而且必须的技能。长此以往，百度工程师就将这种谋求极致的性能优化，逐步积淀成了习惯，甚至造成了对技术的信奉。上面咱们就来盘点和分享一些，在性能优化的征途上，百度 C ++ 工程师积攒下来的实践和实际，以及那些为了谋求极致，所挖掘的『奇技淫巧』。

2  重新认识性能优化

作为程序员，大家或多或少都会和性能打交道，尤其是以 C ++ 为主的后端服务工程师，然而每个工程师对性能优化概念的了解在细节上又是千差万别的。上面先从几个优化案例动手，建设一个性能优化相干的感性认识，之后再从原理角度，形容一下本文所讲的性能优化的切入角度和办法根据。

2.1  从字符串解决开始

2.1.1  string as a buffer

为了调用底层接口和集成一些第三方库能力，在调用界面层，会存在对 C ++ 字符串和 C 格调字符串的交互场景，典型是这样的：

size\_t some\_c\_style\_api(char\* buffer, size\_t size);
void some\_cxx\_style\_function(std::string& result) {
    // 首先扩大到短缺大小
    result.resize(estimate\_size);
    // 从 c ++17 开始，string 类型反对通过 data 获得十分量指针
    auto acture\_size = some\_c\_style\_api(result.data(), result.size());
    // 最终调整到理论大小
    result.resize(acture\_size);
}

这个办法存在一个问题，就是在首次 resize 时，string 对 estimate\_size 内的存储区域全副进行了 0 初始化。然而这个场景中，理论的无效数据其实是在 some\_c\_style\_api 外部被写入的，所以 resize 时的初始化动作其实是冗余的。在交互 buffer 的 size 较大的场景，例如典型的编码转换和压缩等操作，这次冗余的初始化引入的开销还是相当可观的。

为了解决这个问题，大概从 3 年前开始，曾经有人在继续尝试推动规范改良。

http://www.open-std.org/jtc1/…

注：在这个问题上应用 clang + libc++ 的同学有福，较新版本的 libc++ 中曾经非标实现了 resize\_default\_init 性能，能够开始尝鲜应用。

在规范落地前，为了可能在百度外部（目前宽泛应用 gcc8 和 gcc10 编译器）提前应用起来，咱们专门制作了实用于 gcc 的 resize\_uninitialized，相似于下面的性能，在百度，能够这样编码：

size\_t some\_c\_style\_api(char\* buffer, size\_t size);
void some\_cxx\_style\_function(std::string& result) {auto\* buffer = babylon::resize\_uninitialized(result, estimate\_size);
    auto acture\_size = some\_c\_style\_api(buffer, result.size());
    result.resize(acture\_size);
}

2.1.2  split string

理论业务中，有一个典型场景是一些轻 schema 数据的解析，比方一些规范分隔符，典型是 ’\_’ 或者 ’\t’，简略宰割的分列数据（这在日志等信息的粗加工解决中分外常见）。因为场景极其单纯，可能的算法层面优化空间个别认为较小，而理论实现中，这样的代码是广为存在的：

std::vector<std::string> tokens;
// boost::split
boost::split(token, str, \[\] (char c) {return c == '\\t';});
// absl::StrSplit
for (std::string\_view sv : absl::StrSplit(str, '\\t')) {tokens.emplace\_back(sv);
}
// absl::StrSplit no copy
for (std::string\_view sv : absl::StrSplit(str, '\\t')) {direct\_work\_on\_segment(sv);
}

boost 版本宽泛呈现在新工程师的代码中，接口灵便，流传度高，然而理论业务中效率其实并不优良，例如和 google 优化过的 absl 相比，其实有倍数级的差距。尤其如果工程师没有留神进行单字符优化的时候（间接应用了官网例子中的 is\_any\_of），甚至达到了数量级的差距。进一步地，如果联动思考业务状态，个别典型的宰割后处理是能够做到零拷贝的，这也能够进一步升高冗余拷贝和大量长期对象的创立开销。

最初，再思考到百度以后的外部硬件环境有多代不同型号的 CPU，进一步革新 spilt 显式应用 SIMD 优化，并自适应多代向量指令集，能够获得进一步的性能晋升。尤其是 bmi 指令减速后，对于一个 SIMD 步长内的间断分隔符探测，比方密集短串场景，甚至能够获得数量级的性能晋升。

最终在百度，咱们能够这样编码实现：

babylon::split(\[\] (std::string\_view sv) {direct\_work\_on\_segment(sv);
}, str, '\\t'};

2.1.3  magic of protobuf

随着 brpc 在百度外部的广泛应用，protobuf 成为了百度外部数据交换的支流形式，解析、改写、组装 protobuf 的代码在每个服务中简直都会有肯定的占比。尤其是近几年，进一步叠加了微服务化的发展趋势之后，这层数据交换边界就变得更加显著起来。

在有些场景下，例如传递并减少一个字段，或者从多个后端存储获取分列表白的数据合并后返回，利用规范的 C ++API 进行反序列化、批改、再序列化的老本，绝对于理论要执行的业务来说，额定带来的性能开销会显著体现进去。

举例来说，比方咱们定义了这样的 message：

message Field {

    bytes column = 1;
    bytes value = 2;
};
message Record {
    bytes key = 1;
    repeated Field field = 2;
};
message Response {
    repeated Record record = 1;
    bytes error\_message = 2;
};

咱们构想一个场景，一个逻辑的 record 扩散于多个子系统，那么咱们须要引入一个 proxy 层，实现多个 partial record 的 merge 操作，惯例意义上，这个 merge 动作个别是这样的：

one\_sub\_service.query(&one\_controller, &request, &one\_sub\_response, nullptr);
another\_sub\_service.query(&another\_controller, &request, &another\_sub\_response, nullptr);
...
for (size\_t i = 0; i < record\_size; ++i) {final\_response.mutable\_record(i).MergeFrom(one\_sub\_response.record(i));
    final\_response.mutable\_record(i).MergeFrom(another\_sub\_response.record(i));
    ...
}

对于一个轻量级 proxy 来说，这一层重复对后端的解析、合并、再序列化引入的老本，就会绝对凸现进去了。进一步的打消，就要先从 protobuf 的实质动手。

protobuf 的根基先是一套公开规范的 wire format，其上才是反对多语言结构和解析的 SDK，因而尝试升高对解析和合并等操作的进一步优化，绕过 c ++api，深刻 wire format 层来尝试是一种可行且无效的伎俩。那么咱们先来看一下一些 wire format 层的个性。

即 message 的形成间接由外部蕴含的 field 的序列化后果堆砌而成，field 之间不存在宰割点，在整个 message 内部，也不存在框架信息。基于这个个性，一些合并和批改操作能够在序列化的 bytes 后果上被低成本且平安地操作。而另一方面，message field 的格局和 string 又是完全一致的，也就是定义一个 message field，或者定义一个 string field 而把对应 message 序列化后存入，后果是等价的（而且这两个个性是被官网承诺的）。

https://developers.google.com…

联合这些个性，之前的合并操作在实现上咱们革新为：

message ProxyResponse {
    // 批改 proxy 侧的 message 定义，做到不深层解析
    repeated string record = 1;
    bytes error\_message = 2;
};

one\_sub\_service.query(&one\_controller, &request, &one\_sub\_response, nullptr);
another\_sub\_service.query(&another\_controller, &request, &another\_sub\_response, nullptr);
...
for (size\_t i = 0; i < record\_size; ++i) {
    // 利用 string 追加替换 message 操作
    final\_response.mutable\_record(i).append(one\_sub\_response.record(i));
    final\_response.mutable\_record(i).append(another\_sub\_response.record(i));
    ...
}

在微服务搭的环境下，相似的操作能够很好地管制额定老本的减少。

2.2  回头来再看看性能优化

一般来讲，一个程序的性能形成要件大略有三个，即算法复杂度、IO 开销和并发能力。

首要的影响因素是大家都相熟的算法复杂度。一次外围算法优化和调整，能够对利用性能产生的影响甚至是代差级别的。例如 LSM Tree 对 No-SQL 吞吐的晋升，又例如事件触发对 epoll 大并发能力的晋升。然而正因为关注度高，在理论工程实现层面，无论是犯错几率，还是留下的优化空间，反而会大为降落。甚至极其状况下，可能作为非科研主导的工程师，在进行性能优化时鲜少遇到改进算法的场景，剖析问题抉择适合算法会有肯定占比，然而可能范畴也无限。

更多状况下须要工程师解决的性能问题，借用一句算法比赛用语，用『卡常数』来形容可能更贴切。也就是采纳了正确的适合的算法，然而因为没有采纳体系结构下更优的实现计划，导致在 O(X)上附加了过大的常数项，进而造成的整体性能有余。尽管在算法比赛中，卡常数和常数优化是出题人和解题人都不违心大量呈现的烦扰项（因为毕竟是以外围算法自身为指标），然而转换到理论我的项目背景下，常数优化却往往是性能优化畛域的重要伎俩。

当初咱们再来回顾一下下面引出问题的三个优化案例。能够看到，其中都不蕴含算法逻辑自身的改良，然而通过深刻利用底层（比方依赖库或指令集）个性，仍然可能获得倍数甚至数量级的优化成果。这和近些年体系结构变得越发简单有很大关联，而这些变动，典型的体现场景就是 IO 和并发。并发的优化，对于工程教训比拟丰盛的同学应该曾经不生疏了，然而对于 IO，尤其是『内存 IO』可能须要特地阐明一下。

与代码中显示写出的 read/write/socket 等设施 IO 操作不同，存储系统的 IO 很容易被疏忽，因为这些 IO 通明地产生在一般 CPU 指令的背地。先列举 2009 年 Jeff Dean 的一个经典讲座中的一页数字。

https://www.cs.cornell.edu/pr…

尽管曾经是十多年前的数据，然而仍然能够看出，最疾速的 L1 cache 命中和 Main memory 拜访之间，曾经拉开了多个数量级的差距。这些操作并不是在代码中被显式管制的，而是 CPU 帮忙咱们通明实现的，在简化编程难度的同时，却也引入了问题。也就是，如果不能良好地适应体系结构的个性，那么看似同样的算法，在常数项上就可能产生数量级的差别。而这种差别因为隐蔽性，恰好是最容易被新工程师所疏忽的。上面，咱们就围绕内存拜访这个话题，来盘点一下百度 C ++ 工程师的一些『常数优化』。

3  从内存调配开始

要应用内存，首先就要进行内存调配。进入了 c ++ 时代后，随着生命周期治理的便捷化，以及基于 class 封装的各种便捷容器封装的诞生，运行时的内存申请和开释变得越来越频繁。然而因为地址空间是整个过程所共享的一种资源，在多外围零碎中就不得不思考竞争问题。有相干教训的工程师应该会很快联想到两个驰名的内存分配器，tcmalloc 和 jemalloc，别离来自 google 和 facebook。上面先来比照一下两者的大抵原理。

3.1  先 看看 tcmalloc 和 jemalloc

针对多线程竞争的角度，tcmalloc 和 jemalloc 独特的思路是引入了线程缓存机制。通过一次从后端获取大块内存，放入缓存供线程屡次申请，升高对后端的理论竞争强度。而典型的不同点是，当线程缓存被击穿后，tcmalloc 采纳了繁多的 page heap（简化了两头的 transfer cache 和 central cache，他们也是全局惟一的）来承载，而 jemalloc 采纳了多个 arena（默认甚至超过了服务器外围数）来承载。因而和网上流传的支流评测推导原理统一，在线程数较少，或开释强度较低的状况下，较为简洁的 tcmalloc 性能稍胜过 jemalloc。而在外围数较多、申请开释强度较高的状况下，jemalloc 因为锁竞争强度远小于 tcmalloc，会体现出较强的性能劣势。

个别的评测到这里大抵就完结了，不过咱们能够再想一步，如果咱们违心付出更多的内存到 cache 层，将后端竞争压力降下来，那么是否 tcmalloc 仍然能够回到更优的状态呢？如果从下面的剖析看，应该是能够有这样的推论的，而且近代服务端程序的瓶颈也往往并不在内存占用上，仿佛是一个可行的计划。

不过理论调整过后，工程师就会发现，大多数状况下，可能并不能达到预期成果。甚至明明从 perf 剖析体现上看曾经观测到竞争开销和申请开释动作占比很小了，然而整个程序体现仍然不尽如人意。

这实际上是内存调配 连续性 的对性能影响的体现，即线程缓存外围的减速点在于将 申请批量化 ，而非单纯的升高后端压力。缓存过大后，就会导致继续重复的申请和开释都由缓存承当，后果是缓存中寄存的内存块地址空间散布越来越零散，出现一种 洗牌 成果。

体系结构的缓存优化，个别都是以局部性为规范，也就是说，程序近期拜访的内存左近，大概率是后续可能被拜访的热点。因而，如果程序间断申请和拜访的内存呈跳跃变动，那么底层就很难正确进行缓存优化。体现到程序性能上，就会发现，尽管调配和开释动作都变得开销很低了，然而程序整体性能却并未优化（因为真正运行的算法的访存操作常数项增大）。

3.2  那么现实的 malloc 模型是什么？

通过后面的剖析，咱们大略失去了两条对于 malloc 的外围因素，也就是竞争性和连续性。那么是否 jemalloc 是做到极致了呢？要答复这个问题，还是要先从理论的内存应用模型剖析开始。

这是一个很典型的程序，外围是一组继续运行的线程池，当工作到来后，每个线程各司其职，实现一个个的工作。在 malloc 看来，就是多个长生命周期的线程，随机的在各个时点发射 malloc 和 free 申请。如果只是基于这样的视图，其实 malloc 并没有方法做其余假设了，只能也依照根底局部性原理，给一个线程邻近的屡次 malloc，尽量调配间断的地址空间进去。同时利用线程这一概念，将内存分区隔离，缩小竞争。这也就是 tcmalloc 和 jemalloc 在做的事件了。

然而内存调配这件事和程序的边界就只能在这里了吗？没有更多的业务层输出，能够让 malloc 做的更好了吗？那么咱们再从业务视角来看一下内存调配。

微服务、流式计算、缓存，这几种业务模型简直涵盖了所有支流的后端服务场景。而这几种业务对内存的利用有一个重要的特色，就是领有边界明确的生命周期。回退到晚期的程序设计年代，其实 server 设计中每个申请独自一个启动线程解决，解决完整体销毁是一个典型的计划。即便是应用线程池，一个申请承受后从头到尾一个线程跟进实现也是继续了相当长时间的成熟设计。

而针对这种晚期的业务模型，其实 malloc 是能够利用到更多业务信息的，例如线程动静申请的内存，大概率后续某个时点会全副偿还，从 tcmalloc 的线程缓存调整算法中也能够看出对这样那个的额定信息其实是专门优化过的。

然而随着新型的子工作级线程池并发技术的广泛应用，即申请细分为多个子工作充分利用多核并发来晋升计算性能，到 malloc 可见界面，业务个性简直曾经不复存在。只能看到继续运行的线程在随机 malloc 和 free，以及大量内存的 malloc 和 free 漂移在多个线程之间。

那么在这样 job 化的背景下，怎么的内存调配和开释策略可能在竞争性和局部性角度工作的更好呢？上面咱们列举两个计划。

3.2.1  job arena

第一种是根底的 job arena 计划，也就是每个 job 有一个独立的内存分配器，job 中应用的动态内存注册到 job 的 arena 中。因为 job 生命周期明确，中途开释的动态内存被认为无需立刻回收，也不会显著增大内存占用。在无需思考回收的状况下，内存调配不必再思考分块对齐，每个线程内能够齐全间断。最终 job 完结后，整块内存间接全副开释掉，大幅缩小理论的竞争产生。

不言而喻，因为须要感知业务生命周期，malloc 接口是无奈取得这些信息并进行反对的，因而理论会依赖运行时应用的容器可能独自裸露内存调配接口进去。侥幸的是，在 STL 的带动下，事实的支流容器库个别都实现了 allocator 的概念，只管细节并不对立。

例如重度应用的容器之一 protobuf，从 protobuf 3.x 开始引入了 Arena 的概念，能够容许 Message 将内存构造调配通过 Arena 实现。惋惜直到最新的 3.15 版本，string field 的 arena 调配仍然没有被官网反对。

https://github.com/protocolbu…

然而，因为 string/bytes 是业务广为应用的类型，如果脱离 Arena 的话，理论对连续性的晋升就会大打折扣。因而在百度，咱们外部保护了一个 ArenaString 的 patch，重现了 issue 和正文中的表白，也就是在 Arena 上调配一个『看起来像』string 的构造。对于读接口，因为和 string 的内存表白统一，能够间接通过 const string& 出现。对于 mutable 接口，会返回一个代替的 ArenaString 包装类型，在应用了 auto 技术的状况下，简直能够放弃无缝切换。

另外一个重度应用的容器就是 STL 系列了，包含 STL 本身实现的容器，以及 boost/tbb/absl 中依照同类接口实现的高级容器。从 C ++17 开始，STL 尝试将之前混合在 allocator 中的内存调配和实例结构两大性能进行拆分，后果就是产生了 PMR（Polymorphic Memory Resouce）的概念。在解耦了结构器和分配器之后，程序就不再须要通过批改模板参数中的类型，来适应本人的内存调配办法了。其实 PMR 本身也给出了一种间断申请，整体开释的分配器实现，即 monotonic\_buffer\_resource，然而这个实现是非线程平安的。

联合下面两个内存分配器的概念，在理论利用中，咱们利用线程缓存和无锁循环队列（升高竞争），整页获取零散供应（晋升间断）实现了一个 SwissMemoryResource，通过接口适配对立反对 STL 和 protobuf 的分配器接口。最终通过 protocol 插件集成到 brpc 中，在百度，咱们能够如下应用：

babylon::ReusableRPCProtocol::register\_protocol();
::baidu::rpc::ServerOptions options;
options.enabled\_protocols = "baidu\_std\_reuse";

class SomeServiceImpl : public SomeService {
public:
    // request 和 response 自身采纳了申请级别的 memory resource 来调配
    virtual void some\_method(google::protobuf::RpcController\* controller,
            const SomeRequest\* request,
            SomeResponse\* response,
            google::protobuf::Closure\* done) {baidu::rpc::ClosureGuard guard(done);
        // 通过转换到具体实现来获得 MemoryResource
        auto\* closure = static\_cast<babylon::ReusableRPCProtocol::Closure\*>(done);
        auto& resource = closure->memory\_resource();
        // 做一些申请级别的动静容器
        std::pmr::vector<std::pmr::string> tmp\_vector(&resource);
        google::protobuf::Arena::CreateMessage<SomeOtherMessage>(&(Arena&)resource);
        ...
        // done->Run 时申请级内存整体开释
    }
};

3.2.2  job reserve

更简单一些的是 job reserve 计划，在 job arena 的根底上，联合了 job 完结后不析构两头构造，也不开释内存，转而定期进行紧凑重整。这就进一步要求了两头构造是能够在保留内存的状况下实现重置动作的，并且可能进行容量提取，以及带容量从新构建的性能。这里用 vector<string> 为例解释一下：

和典型的 vector 解决次要不同点是，在 clear 或者 pop\_back 等操作缩减大小之后，内容对象并没有理论析构，只是清空重置。

因而，再一次用到这个槽位的时候，能够间接拿到曾经结构好的元素，而且其 capacity 之内的内存也仍然持有。能够看到重复应用同一个实例，容器内存和每个元素本身的 capacity 都会逐步趋向于饱和值，重复的调配和结构需要都被缩小了。理解过 protobuf 实现原理的工程师能够对照参考，这种保留实例的 clear 动作，也是 protobuf 的 message 锁采纳的办法。

不过关注到之前提过局部性的工程师可能会发现，只管调配需要升高了，然而最终饱和态的内存散布在连续性上仍不现实，毕竟中途的动态分配是按需进行，而未能参考局部性了。因而容器还须要反对一个动作，也就是重建。

也就是，当反复利用屡次，产生了较多长期申请之后，须要可能提取出以后的容量 schema，在新的间断空间中做一次原样重建，让内存块从新回归间断。

3.3  总结一下内存调配

通过剖析 malloc 的性能原理，引入这两种细粒度的内存调配和治理计划，能够在更小的竞争下，失去更好的内存连续性。

在实测中，简略利用做到 job arena 个别就能够获得大部分性能收益，个别可能达到倍数级晋升，在整体服务角度也可能产生可观测的性能节俭。而 job reserve，尽管能够取得进一步地性能晋升，但一方面是因为如果波及非 protobuf 容器，须要实现自定义的 schema 提取和重建接口，另一方面趋于饱和的 capacity 也会让内存应用增大一些。引入老本会进步不少，因而理论只会在性能更为紧要的环节进行应用。

4  再来看看内存拜访

内存调配实现后，就到了理论进行内存拜访的阶段了。个别咱们能够将访存需要拆解到两个维度，一个是单线程的间断拜访，另一个是多个线程的共享拜访。上面就分拆到两个局部来别离谈谈各个维度的性能优化办法。

4.1  程序访存优化

一般来说，当咱们要执行大段访存操作时，如果拜访地址间断，那么理论效率能够取得晋升。典型例如对于容器遍历拜访操作，数组组织的数据，相比于比链表组织的数据，个别会有显著的性能劣势。其实在内存调配的环节，咱们引入的让间断调配（根本也会是间断拜访）的空间地址连续性更强，也是出于这一目标。

那么上面咱们先来看一看，连续性的拜访产生性能差别的原理是什么。

这里以 Intel CPU 为例来简要形容一下预取过程。详见：

https://www.intel.com/content…

当硬件监测到间断地址拜访模式呈现时，会激活多层预取器开始执行，参考以后负载等因素，将预测将要拜访的数据加载到适合的缓存层级当中。这样，当后续拜访实在到来的时候，可能从更近的缓存层级中获取到数据，从而减速访问速度。因为 L1 容量无限，L1 的硬件预取步长较短，减速指标次要为了晋升 L2 到 L1，而 L2 和 LLC 的预取步长绝对较长，用于将主存晋升到 cache。

在这里局部性概念其实充当了软硬件交互的某种约定，因为程序人造的拜访模式总有一些局部性，硬件厂商就通过预测程序设计的局部性，来尽力减速这种模式的拜访申请，力求做到通用晋升性能。而软件设计师，则通过尽力让设计出现更多的局部性，来激活硬件厂商设计的优化门路，使具体程序性能失去进一步优化。某种意义上讲，z 不失为一个相生相伴的循环促成。

这里通过一个样例来验证体现一下如何尊重局部性，以及局部性对程序的影响。

// 设计一块很大的存储区域用于存储固定维度的浮点向量
// vecs 中存储每个浮点向量的起始地址
std::vector<float> large\_memory\_buffer;
std::vector<float\*> vecs;

std::shuffle(vecs.begin(), vecs.end(), random\_engine);

for (size\_t i = 0; i < vecs.size(); ++i) {\_\_builtin\_prefetch(vecs\[i + step\]);
    dot\_product(vecs\[i\], input);
}

这是一个举荐 / 搜寻零碎中常见的内积打分场景，即通过向量计算来进行大规模打分。同样的代码，根据 shuffle 和 prefetch 存在与否，产生相似如下的体现：

1. shuffle & no prefetch：44ms
2. shuffle & prefetch：36ms
3. shuffle & no prefetch：13ms
4. shuffle & prefetch：12ms

从 1 和 3 的区别能够看出，完全相同的指令，在不同的访存程序下存在的性能差距能够达到倍数级。而从 1 和 2 的区别能够看出，手动增加预取操作后，对性能有肯定改善，预期更精密地领导预取步长和以及 L1 和 L2 的散布还有改善空间。不过指令执行周期和硬件效率很难齐备匹配，手动预取个别用在无奈革新成物理间断的场景，但调参往往是一门玄学。最初 3 和 4 能够看出，即便间断访存下，预取仍然有一些无限的收益，揣测和硬件预取无奈逾越页边界造成的屡次预测冷启动无关，然而影响曾经比拟强劲了。

最具备指导意义的可能就是相似这个内积打分的场景，有时为了节俭空间，工程师会将程序设计为，从零散的空间取到向量指针，并组成一个数组或链表零碎来治理。人造来讲，这样节俭了内存的冗余，都援用向一份数据。然而如果引入一些冗余，将所须要的向量数据一起拷贝形成间断空间，对于检索时的遍历计算会带来显著的性能晋升。

4.2  并发拜访优化

提到并发拜访，可能要先从一个概念，缓存行（cache line）说起。

为了防止频繁的主存交互，其实缓存体系采纳了相似 malloc 的办法，即划分一个最小单元，叫做缓存行（支流 CPU 上个别 64B），所有内存到缓存的操作，以缓存行为单位整块实现。

例如对于间断拜访来说第一个 B 的拜访就会触发全副 64B 数据都进入 L1，后续的 63B 拜访就能够间接由 L1 提供服务了。所以并发拜访中的第一个问题就是要思考缓存行隔离，也就是个别能够认为，位于不同的两个缓存行的数据，是能够被真正独立加载 / 淘汰和转移的（因为 cache 间流转的最小单位是一个 cache line）。

典型的问题个别叫做 false share 景象，也就是不慎将两个本无竞争的数据，搁置在一个缓存行内，导致因为体系结构的起因，引入了『本不存在的竞争』。这点在网上材料比拟短缺，例如 brpc 和 disruptor 的设计文档都比拟具体地解说了这一点，因而这里就不再做进一步的开展了。

4.3  那先来聊聊缓存一致性

排除了 false share 景象之后，其余就是真正的共享问题了，也就是的确须要位于同一个缓存行内的数据（往往就是同一个数据），多个外围都要批改的场景。因为在多外围零碎中 cache 存在多份，因而就须要思考这多个正本间一致性的问题。这个一致性个别由一套状态机协定保障（MESI 及其变体）。

大体是，当竞争写入产生时，须要竞争所有权，未取得所有权的外围，只能期待同步到批改的最新后果之后，能力持续本人的批改。这里要提一下的是有个流传甚广的说法是，因为缓存零碎的引入，带来了不统一，所以引发了各种多线程可见性问题。

这么说其实有失偏颇，MESI 实质上是一个『一致性』协定，也就是恪守协定的缓存零碎，其实对下层 CPU 多个外围做到了程序一致性。比方比照一下就能发现，缓存在竞争时体现进去的解决动作，其实和只有主存时是统一的。

只是阻塞点从竞争一个物理主存单元的写入，转移到了尽管是多个缓存物理单元，然而通过协定竞争独占上。不过正因为竞争阻塞状况并没有缓解，所以 cache 的引入其实搭配了另一个部件也就是写缓冲（store buffer）。

注：写缓存自身引入其实同时收到乱序执行的驱动，在《并发篇》会再次提到。

写缓冲的引入，真正开始带来的可见性问题。

以 x86 为例，当多核产生写竞争时，未获得所有权的写操作尽管无奈失效到缓存层，然而能够在改为期待在写缓冲中。而 CPU 在个别状况下能够防止期待而先开始后续指令的执行，也就是尽管 CPU 看来是先进行了写指令，后进行读指令，然而对缓存而言，先进行的是读指令，而写指令被阻塞到缓存从新同步之后能力进行。要留神，如果聚焦到缓存交互界面，整体仍然是保障了程序统一，然而在指令交互界面，程序产生了颠倒。这就是典型的 StoreLoad 乱序成了 LoadStore，也是 x86 上惟一的一个乱序场景。而针对典型的 RISC 零碎来说（arm/power），为了流水线并行度更高，个别不承诺写缓冲 FIFO，当一个写操作卡在写缓冲之后，后续的写操作也可能被先解决，进一步造成 StoreStore 乱序。

写缓冲的引入，让竞争呈现后不会立刻阻塞指令流，能够容忍直到缓冲写满。但因为缓存写入实现须要周知所有 L1 执行作废操作实现，随着外围增多，会呈现局部 L1 作废长尾阻塞写缓冲的状况。因而一些 RISC 零碎引入了进一步的缓冲机制。

进一步的缓冲机制个别叫做生效队列，也就是当一个写操作只有将生效音讯投递到每个 L1 的生效队列即视为实现，生效操作长尾不再影响写入。这一步改变甚至的确地局部毁坏了缓存一致性，也就是除非一个外围期待以后生效音讯排空，否则可能读取到过期数据。

到这里曾经能够感触到，为了对大量惯例操作进行优化，近代体系结构设计中引入了多个影响一致性的机制。然而为了可能构建正确的跨线程同步，某些要害节点上的一致性又是必不可少的。

因而，配套的性能指令应运而生，例如 x86 下 mfence 用于领导后续 load 期待写缓冲全副失效，armv8 的 lda 用于确保后续 load 期待 invalid 失效实现等。这一层因为和机型与指令设计强相干，而且指令的配套应用又能带来多种不同的内存可见性成果。这就大幅减少了工程师编写正确一致性程序的老本，而且难以保障跨平台可移植。于是就到了标准化发挥作用的时候了，这个对于内存一致性畛域的标准化标准，就是内存序（memory order）。

4.4  再谈一谈 memory order

作为一种协定机制，内存序和其余协定相似，次要承当了明确定义接口层性能的作用。体系结构专家从物理层面的优化伎俩中，形象总结出了多个不同层级的逻辑一致性等级来进行刻画表白。这种形象成为了专用边界规范之后，硬件和软件研发者就能够独立发展各自的优化工作，而最终造成跨平台通用解决方案。

对于硬件研发者来说，只有可能最终设计一些特定的指令或指令组合，反对可能实现这些内存序标准的性能，那么任意的设计扩大原理上都是可行的，不必思考有软件兼容性危险。同样，对于软件研发者来说，只有依照规范的逻辑层来了解一致性，并应用正确的内存序，就能够不必关注底层平台细节，写出跨平台兼容的多线程程序。

内存序在官网定义里，是洋洋洒洒一大篇内容，为了便于了解，上面从开发程序须知角度，抽出一些简洁精炼的概念（虽不是实践齐备的）来辅助记忆和了解。

首先来看看，内存序背地到底产生了啥。

int payload = 0;
int flag = 0;
void normal\_writer(int i) {
  payload = flag + i;
  flag = 1;
}
int normal\_reader() {while (flag == 0) { }
  return payload;
}

在这个样例中能够看到，在编译层，默认对于无关指令，会进行肯定水平的程序调整（不影响正确性的前提下）。另一方面，编译器默认能够假设不受其余线程影响，因而同一个数据间断的屡次内存拜访能够省略。

上面看一下最根底的内存序等级，relaxed。

int payload = 0;
std::atomic<int> flag {0};
void relaxed\_writer(int i) {payload = flag.load(std::memory\_order\_relaxed) + i;
    flag.store(1, std::memory\_order\_relaxed);
}
int relaxed\_reader() {while (flag.load(std::memory\_order\_relaxed) == 0) { }
    return payload;
}

在应用了根底的内存序等级 relaxed 之后，编译器不再假如不受其余线程影响，每个循环都会从新加载 flag。另外能够观测到 flag 和 payload 的乱序被复原了，不过原理上 relaxed 并不保障程序，也就是这个程序并不是一个编译器的保障承诺。总体来说，relaxed 等级和一般的读写操作区别不大，只是保障了对应的内存拜访不可省略。

更进一步的内存序等级是 consume-release，不过以后没有对应的实现案例，个别都被默认晋升到了下一个等级，也就是第一个实在有意义的内存序等级 acquire-release。先从原理上讲，个别能够依照满足条件 / 给出承诺的形式来简化了解，即：

• 要求：对同一变量 M 别离进行写（release）A 和读（acquire）B，B 读到了 A 写入的值。
• 承诺： A 之前的所有其余写操作，对 B 之后的读操作可见。
• 理论影响：

1. 波及到的操作不会产生穿梭 A / B 操作的重排；
2. X86：无额定指令；
3. ARMv8：A 之前排空 store buffer，B 之后排空 invalid queue，A/ B 保序；
4. ARMv7&Power：A 之前全屏障，B 之后全屏障。

int payload = 0;
std::atomic<int> flag {0};
void release\_writer(int i) {payload = flag.load(std::memory\_order\_relaxed) + i;
    flag.store(1, std::memory\_order\_release);
}
int acquire\_reader() {while (flag.load(std::memory\_order\_acquire) == 0) { }
    return payload;
}

因为 x86 默认内存序不低于 acquire-release，这里用 ARMv8 汇编来演示成果。能够看出对应指令产生了替换，从 st/ld 变更到了 stl/lda，从而利用 armv8 的体系结构实现了相应的内存序语义。

再进一步的内存序，就是最强的一级 sequentially-consistent，其实就是复原到了 MESI 的承诺等级，即程序统一。同样能够依照满足条件 / 给出承诺的形式来简化了解，即：

• 要求：对两个变量 M，N 的（Sequentially Consistent）写操作 Am，An。在任意线程中，通过（Sequentially Consistent）的读操作观测到 Am 先于 An。
• 承诺：在其余线程通过（Sequentially Consistent）的读操作 B 也会观测到 Am 先于 An。
• 理论影响：

1. X86：Am 和 An 之后清空 store buffer，读操作 B 无额定指令；
2. ARMv8：Am 和 An 之前排空 store buffer，B 之后排空 invalid queue，A/ B 保序；
3. ARMv7：Am 和 An 前后全屏障，B 之后全屏障；
4. POWER：Am 和 An 前全屏障，B 前后全屏障。

值得注意的是，ARMv8 开始，特意优化了 sequentially-consistent 等级，省略了全屏障老本。揣测是因为程序统一在 std::atomic 实现中作为默认等级提供，为了通用意义上晋升性能做了专门的优化。

4.5  了解 memory order 如何帮忙咱们

先给出一个根本测试的论断，看一下一组比照数据：

1. 多线程竞争写入近邻地址 sequentially-consistent：0.71 单位工夫
2. 多线程竞争写入近邻地址 release：0.006 单位工夫
3. 多线程竞争写入 cache line 隔离地址 sequentially-consistent：0.38 单位工夫
4. 多线程竞争写入 cache line 隔离地址 release：0.02 单位工夫

这里能够看出，做 cache line 隔离，对于 sequentially-consistent 内存序下，有肯定的收益，然而对 release 内存序，反而有负成果。这是因为 release 内存序下，因为没有强内存屏障，写缓冲起到了竞争缓解的作用。而在充沛缓解了竞争之后，因为 cache line 隔离引入了雷同吞吐下更多 cache line 的传输交互，反而开销变大。

在这个信息领导下，咱们在实现无锁队列时，采纳了循环数组 + 分槽位版本号的模式来实现。因为队列操作只须要 acquire-release 等级，分槽位版本号间无需采纳 cache line 隔离模式设计，整体达到了比拟高的并发性能。

浏览原文
https://mp.weixin.qq.com/s/wF…

举荐浏览

|前端工程化之 H5 性能优化篇

|趣谈哈希表优化：从躲避 Hash 抵触到利⽤ Hash 抵触

|百度智能小程序框架性能优化实际

———-  END  ———-

百度 Geek 说

百度官网技术公众号上线啦！

技术干货 · 行业资讯 · 线上沙龙 · 行业大会

招聘信息 · 内推信息 · 技术书籍 · 百度周边

欢送各位同学关注！