dhb's Blog HomeArchivesTagsCategoriesSite Log
Cppcon 笔记
|C++
字数总计: 4k|阅读时长: 13 分钟

Cppcon是个著名的C++会议，由C++社区举办，每年有很多来自全球各地的演讲者分享C++语言相关的内容。其中的演讲大多数质量很高，不乏出自一些社区中知名的C++专家的精彩演讲。此外，也有很多C++在不同领域的相关实践，如游戏开发、嵌入式、HPC、高频交易等等，可以吸收到来自不同领域的经验。总的来说，Cppcon是一个十分难得的优质学习资源。

本文主要记录了一系列的观看Cppcon presentation时做的笔记，供后续参考使用。

（最后更新于2020.09.06）

目录（按主题分类）

2018

Concepts in 60: Everything you need to know and nothing you don’t - Andrew Sutton

概述：Concepts快速介绍

  • Concepts有助于提高泛型代码的两个方面：

    • 更好的泛型约束
    • 使用多余的约束提高代码性能

  • 泛型代码目前来说有2种，“泛用性”从低到高：

    1. 函数重载，如运算符重载，不同的sin、cos等等

      并不是“真正”的泛型，只是从用户角度的泛型。

    2. 模版（template <typename T>）

      真正的泛型，“所有具体的实现都可以看做是某个模版算法的示例”。

      然而模版的问题是其过度通用了，显然一个模版算法不能适用于所有的类型，然而在接口中却没有表达任何限制，导致一旦误用，就会出现很可怕的错误信息（如std::vector<int&>）

  • **Concepts（概念）**正是解决模版过度通用问题的良药，其能够让我们限制模版参数适用的范围，也带来了如下的好处：

    • 直接表达模版参数意图
    • 在使用点检查模版参数是否符合限制（而不是在模版实例化后）
    • 基于多余限制做特殊优化
    • 更好的编译器信息提示（相比使用一些别扭的语法规则如SFINAE时的编译器信息）

    Concepts本质上是表达对模版参数提出要求的具名谓词。

    要求一般可以分为3种：

    1. 语法要求：需要使用到哪些语法操作、哪些相关类型
    2. 语义要求：操作的行为应该是什么
    3. 复杂度要求：操作的性能应该达到什么

  • 一些Tips：

    • 要写出好的Concepts并不容易，需要不断地尝试与迭代。所以，在自己写之前，最好看看有没有库已经写过类似的了，如果有就直接拿来用吧~
    • 编译器只能检测类型是否满足Concepts的语法要求，而对于语义和复杂度要求则无能为力。
    • 一个Concept可以由几个不同限制的Concept组成，一个Concept可以限制多个模版参数类型。
    • 基本上所有模版代码中的模版参数均有一些前提条件的要求，也可以用某种Concept表示，只是你可能还没有发觉。也就是说，不要再有裸的typename T出现在模版参数里了！

  • 注意语法要求和语义要求的区别，某些操作的语法要求一般不要求其在所有值上适用，如

    • 浮点数满足TotallyOrdered，即使有NaNs值的存在
    • 定点整数满足Arithmetic，即使overflow时行为undefined

  • 限制表示了一个算法所使用的抽象，注意这种抽象并不是仅仅看使用到了什么语法，否则实际上就是在暴露实现的细节。

    过度限制并不是一件坏事：

    • 从比较强的要求开始抽象，在实现上有更高的自由度，也防止了偶然的模版误用
    • 限制在以后总是可以放宽，并保证向前兼容。

    反之，过松的限制容易导致不成熟的泛用：

    • 较弱的语义难以推断其行为，限制实现的自由度
    • 过于追求“泛用”只会导致“面向语法的Concept”（不要让Concept表达“可加”、“可减”之类的语法限制！）

  • Concept还可以利用特殊情况优化性能：对于更强要求的Concept，其多余的要求有时可以用于优化。

    可以衡量Concept的要求严格程度：如果Concept D的要求Concept C都能满足，且C相比D有更多的要求，就认为C相比D更严格，称C隐含D。（比如BidirectionalIterator隐含ForwardIterator）

    基于这种严格程度的比较，就可以定义Concept的特化了：如果对于一个算法，Concept P可以替换Concept Q，也就是Concept P隐含Concept Q，那么P就是Q的特化。

    这种Concept的特化和模版的特化类似，也是决定函数重载的规则，编译器会选择最特化的Concept限制的函数版本。

    比如下面这个例子就利用了RandomAccessIterator相比InputIterator多出的限制，将原本O(N)复杂度的算法降低到了O(1)：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    template <InputIterator Iter>
    int distance(Iter first, Iter last) {
    	int n = 0;
    	while (first++ != last) ++n;
    	return n;
    }

    template <RandomAccessIterator Iter>
    int distance(Iter first, Iter last) {
    	return last - first;
    }

    有些时候两个特化之间编译器无法决定哪一个更好的时候，就会导致ambiguous报错，这时可以用if constexpr在函数体内判断，同样可以实现类似的优化。

Talk

2016

Want fast C++? Know your hardware! - Timur Doumler

概述：通过实际测量的数据说明现代处理器不同方面对性能的影响

  • 2D数组遍历：

    • 行主序（Row major）和列主序（Column major），后者比前者慢30倍

      不同数组大小的测试中可以看出，两者在很小的数组时有一个基础的性能差异，而数组大小超过L2 Cache和L3 Cache时差距有显著提高。

      如果在循环中加入一点计算，基础性能差异就消失了，只剩在超过L3 Cache时的差距。可以认为左侧速度受限于计算，右侧受限于数据访问。

    • 访问每N个int元素：N>16时速度明显下降，因为一个Cacheline为64bytes，刚好为16个int。

    • 数组的遍历顺序很重要，比如一个图像处理程序，需要经常访问局部一个范围内的数据，可以进行分块遍历，甚至可以用希博尔特曲线…

      核心思想是用好数据局部性，让访问的数据尽量都在Cache中。

    • 当比较列主序遍历和随机遍历时，随机遍历比前者还要慢几倍。这可能是由于CPU中**预取器（Prefetcher）**的作用导致的，它能够识别出数据访问分模式，并对固定步长的访问做数据预取以降低cache miss带来的影响。

  • 每隔N个元素访问一次，循环进行，得到了如下的图。

    在N=256、N=512、1024时访问时间一下变为了几十倍。出现这种现象的原因是Cache相联性，事实上现代CPU Cahce采用了组相联的方式，而每组内又是直接相联，导致在特殊步长（如2的指数）下可能经常发生碰撞，相当于很多数据在竞争Cache中的几个位置。

  • 数据对齐很重要，在某些机器上未对齐的数据访问比对齐的要慢几倍。

  • 避免随机分支。分支预测失败导致流水线被清空，造成显著的性能损失。有模式的分支如循环、判空指针、可预测的虚函数访问等经过CPU分支预测器，开销被降到很低，而分支预测器对随机分支无能为力。

    注：较新的CPU可以在分支预测失败时“快速恢复”，不必清空流水线。参考

  • 避免原子变量的核间共享访问。不同核对同一个原子变量的竞争，导致其他核的Cache经常被失效，导致性能随线程数的提高而显著下降。

    另一个相关概念是伪共享（false sharing）：虽然不同核访问的变量不一样，但由于它们在同一Cacheline内，出现同样的问题。解决办法是将变量显式对齐到一个Cacheline。

    1
    2
    3
    struct alignas(64) aligned_type {
    	std::atomic<int> a;
    };

  • 避免循环的不同迭代间的数据依赖，改写为同一迭代间的依赖可以有助于编译器进行自动SIMD向量化。

  • SIMD数据的对齐在某些机器上很重要。

  • 浮点数乘法需要注意**次正规数（denormal）**对性能的影响：其运算速度比一般的乘法慢30倍。

    如果它们对计算结果影响不大，可以考虑之前将次正规数变为0（一般在编译选项中开启-ffast-math即可）。

    相关讨论可以参考这篇文章

总结性能问题的着手处：

  • 了解程序速度是受限于计算，还是受限于数据访问。
  • 数据在内存中的排布：连续 > 常数步长 > 完全随机（注重数据访问在时间与空间上的局部性）
  • 避免连续计算之间、循环的不同迭代之间的数据依赖
  • 避免难以预测的分支
  • 了解Cacheline和对齐，避免线程间Cacheline的共享
  • 不要惊讶于硬件古怪的地方（Cache相联性、浮点denormal…）

Talk

Garbage In, Garbage Out: Arguing about Undefined Behavior… - Chandler Carruth

概述：Undefined Behaviour的背后是约定

  • 未定义行为（Undefined Behaviour）实质上是程序编写错误所引发的综合征，与调用API时没有准守约定一样。

    很多时候，我们难以定义错误程序的行为，因为它们和实现密切相关，这个时候，只能指定其为未定义行为。

  • 正如API对参数的要求一样，部分语言操作也对操作数有要求（典型的如*解引用运算符）。

    这里就涉及到两个关于约定的概念：

    1. 宽约定（Wide contract）：一个函数或操作对于所有的输入都有效
    2. 窄约定（Narrow）：一个函数或操作只对满足特定前提条件的输入有效

    比如对于std::vector的size()成员函数就是一个宽约定函数，因为其对于任何的std::vector实例都有效；而operator[](size_t index)就是一个窄约定函数，因为其只对于满足index < size()的输入有效，而对于其他输入为未定义行为。

  • 怎样解决UB带来的问题？

    • 定义所有行为？显然不行，一些行为只在特定平台上适合实现，而其他平台则难以实现；在语言层面上定义所有的行为也不是C++的风格。
    • 限制UB的行为？然而限制UB的行为实际上偏离了正确的道路；不同的用户想要的行为也是不同的。

    唯一合理的选择依然是，在合适的地方引入窄约定（当然，违反了约定的行为还是UB）。

  • 何时是引入窄约定的好时机呢？

    窄约定是一种更简单的语义模型，只不过某些时候不符合人们的预期。

    引入窄约定的原则有：

    1. 在运行时（可能）可以检测
    2. 提供显著的价值：发现bug、简化实现、优化
    3. 易于解释
    4. 没有被现有代码大量违背

  • 几个例子：

    • 位移量超过字长

      1
      2
      3
      4
      5
      int main() {
      	volatile unsigned x = 1;
      	volatile unsigned y = 33;
      	volatile unsigned result = x << y;
      }

      该操作是UB的原因：为了达到最大的可移植性，不同的平台（x86、arm、powerPC）对其均有不同的实现。如果定义了某种行为，就一定意味着某些平台上的性能下降。至于为什么不能定义其为平台定义的呢？因为这样就不能提醒潜在的程序错误了。

    • 有符号整数溢出

      这里举了一个比较特殊的地址，用32位无符号整数作为数组下标索引。相同的程序，修改为32位有符号整数下标后生成的汇编代码少了很多。原因是64位x86平台下，为了实现32位无符号整数的溢出模运算，需要生成更多的汇编代码；然而32位有符号数本身的溢出是UB，实际实现时转换为了64为整数计算，生成的汇编代码反而更少。

      这里就体现了窄约定带来的好处：实现可以利用额外的自由度实现特定的优化。

Talk

2015

std::allocator… - Andrei Alexandrescu

概述：吐槽现有的内存分配设计，讲述如何设计可组合的内存分配器

  • malloc分配时需要提供size，而free却不用 -> 说明allocator需要想办法记住这个信息。显然这个接口设计是不合理的

    改进：分配器不是返回指针，而是一个struct，如

    1
    struct blk { void* ptr; size_t size; };

    好在C++14之后operator new/delete新增了带size的版本 ; )

  • operator new加入了类型信息，但是语法有些奇怪：即使是fixed-size的数组（如int[100]），也是调用的动态分配的数组operator new，而语义上fixed-sized数组应该看做一个类型。

    还提到不要使用class operator new…

    此外delete和delete[]完全没区别，应该统一…

  • std::allocator原本并不是为了分配内存而生的，是为了解决“near/far pointer”的问题。目前标准中已经把这一部分完全移除了。

    Allocator设计奇烂无比，设计后的20年还在思考如何使其work… 可以看Alisdair Meredith的"Making Allocators Work"演讲。体现在：

    • Allocator应该完全不知道类型信息，只需要size和alignment
    • Allocator不是factory，不应该管构造/析构
    • rebind<U>::other太恶心了
    • 假定Allocator是stateless的（C++14后终于支持了Allocator有state）

  • Allocator的关键是“组合”：有针对特定大小的Allocator、有不同实现的Allocator、有hook其他Allocator的Allocator（以实现debug、stat等）

    讲到了一下的可组合Allocator：

    • Fallback Allocator：连接两个Allocator，分别为Primary和Fallback，如果前者失败则尝试后者。

      分配很简单，free就…需要知道指针来自哪个allocator。显然当前的接口是无法知道的，可以增加一个owns接口，查询一个指针是否来自此分配器

    • Stack Allocator：在栈空间上用后进先出思想分配。

      优点是栈空间为hot内存区域，访问很快。缺点自然也是对free的顺序要求很严格。

      后进先出可搭配SCOPE_EXIT辅助使用。

    • Freelist Allocator：在空闲块内维护一个intrusive list管理空闲块。据说freelist的cache friendly不好。

      可改进的点：加入适用块大小范围、成批分配、加入块数上限。

    • Affix Allocator：可在在分配块上加入prefix和suffix。可用于调试、统计等信息，或访问越界检查。

    • Allocator With Stats：专门收集分配信息的Allocator，如call count、failures、byte count、high water、caller file/line/function/time。

    • Bitmapped Block：用bitmap管理固定大小块的分配信息。

      优点：meta信息可以fit进cache，分配很快，额外空间开销小。

    • Cascading Allocator：维持一个allocator list，当allocator不够用时就产生一个新的。

    • Segregator：size < threshold的走small allocator，否则走large allocator。通过组合可以实现一个二叉搜索树。

    • Bucketizer：分配大小从min到max以指数方式递增分成桶。

Talk [Slide]([https://github.com/CppCon/CppCon2015/blob/master/Presentations/allocator Is to Allocation what vector Is to Vexation/allocator Is to Allocation what vector Is to Vexation - Andrei Alexandrescu - CppCon 2015.pdf](https://github.com/CppCon/CppCon2015/blob/master/Presentations/allocator Is to Allocation what vector Is to Vexation/allocator Is to Allocation what vector Is to Vexation - Andrei Alexandrescu - CppCon 2015.pdf))

文章作者: dhbloo
文章链接: https://dhbloo.github.io/2020/09/06/Cppcon-Notes/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 dhb's Blog！
C++Cppcon