CppCon 2016: Chandler Carruth “高性能代码201:混合数据结构”
CppCon 2016: Chandler Carruth “High Performance Code 201: Hybrid Data Structures"
频道:CppCon · 时长:55:49 · 发布:2016-10-01 · 播放:119167
简介
Chandler Carruth在CppCon 2016上关于为性能设计混合数据结构的演讲。他涵盖了缓存局部性、工作集大小和分配开销,以及为什么标准C++容器不够好。
HN 为什么推荐
被引用作为对std::deque和移动构造函数陷阱批评的来源,以及编写自定义数据结构的动机。
我建议观看这个演讲 — HN, 2021
C、C++、Rust、Go 与系统语言 · 软件性能与优化 · 算法与数据结构
中文字幕节选
好的。我叫 Chandler Kut。 我在这里要和大家聊聊高性能代码。 在座有多少人是第一次来 CppCon? 哇。天哪,人真多。 好。那么,有多少人看过两年前 YouTube 上的那个演讲? 好。好。那还好,因为我不会重复那个演讲。 所以,这算是系列的第二部分,对吧? 我的想法是,第一次我讲了很多关于真正限制高性能代码的因素, 你需要培养的模式,以及那些你想反复使用的基本方法。 你需要反复去做的基本事情。 但那个演讲让我因为一个原因感到遗憾。 呃,一个原因是它非常消极,对吧? 它实际上不是一个很有建设性的演讲。 我没有告诉你们很多你们可以做、应该做的事情,或者一些新的、 令人兴奋的工具来帮助你们编写真正快速的代码。 所以这个演讲会试着更积极一些。 它会试着更多地帮助大家。 我们会试着实际介绍一些混合数据结构, 这些结构在编写真正快速的代码时,希望对你们非常有用。 呃,作为一点背景,如果大家不知道的话,我在 谷歌工作。我从事 LLVM 编译器的工作,特别是,我今天实际上要讲 LLVM 的内部数据结构。 呃,事实证明 LLVM 是一个很好的例子,展示了真正高性能的 代码,因为你有一群编译器极客,我的意思是一群非常非常 糟糕级别的编译器极客。 他们都是性能狂人。 我可能就是一个很好的例子,而且他们都在开发这个编译器, 我们实际上非常关心编译器本身是否非常快,对吧? 而且你知道,我们都在思考现代计算机架构以及 当我们试图让编译器运行得非常快时所面临的挑战, 所以我们最终编写了一堆很棒的数据结构,编写了一堆 算法,并花费大量时间真正调优、检查各种东西,试图获得 绝对最佳的性能,所以我实际上认为这是一个很好的地方 来了解高性能数据结构,所以这个演讲 我将在我们开始之前就透露这个演讲的所有秘密。 只是让你们知道,没有,我袖子里没有任何东西。 好的,那么 vector、set 和 map。 就这些。我们整个小时就只讲这些,但它会 很棒。好的,那么第一个数据结构当然是 vector。 好的,这就是 LLVM 的 vector 大概的样子。 现在,我本可以给你们看 LLVM 的真实代码,但如果那样的话,你们 都得站在屏幕前,使劲眯着眼睛看, 那会非常令人困惑。 所以我将所有这些提炼到了最基本的要素,以 传达 LLVM 如何使这些数据结构变快的精髓。 所以这是一个非常直接的小尺寸优化 vector。 这就是关键思想。 它是一个小尺寸优化的 vector。 这并不意味着我们期望整个编译器中的所有 vector 都是 小的。实际上这不是重点。 重点是节省早期的小分配,因为事实证明这些 最终成为 vector 成本的一个非常大的组成部分。 通过进行小尺寸优化,我们不必在自由存储区分配这些。 我们可以非常快速地使用内部缓冲区来处理这些。 我们只有在增长时,当增长到某个相当大的尺寸时, 才真正向堆请求分配。
HN 上的讨论
我建议看看这个演讲:[VIDEO] 或者Chandler的几乎任何其他演讲,来理解为什么STL很烂,以及为什么你应该为自己的用例写更好的数据结构。 — typon, 2021-08
在CppCon 2016:Chandler Carruth的“High Performance Code 201: Hybrid Data Structures”[1]中,他说:“但标准的deque数据类型真的很糟糕。我不建议任何人用它做任何事。如果你看看它的实现约束、对其迭代器的约束以及失效约束,它被逼到了一个非常难受的角落,几乎没有机会成为高效的数据结构。”[1] [VIDEO] — 04091948, 2020-04
楼上问的是那个“金发姑娘”问题——有没有那么一个时刻,C++既不像现代C++那么复杂(比如这个{}问题),又有足够的功能(对比C,C对很多应用来说功能不够)。我认为不存在这样的时刻。显然,move构造函数在std::vector的情况下反而成了去优化。据我所知,这和迭代器失效以及move语义让小型优化变得不可能有关(比如把小vector内联到对象本身,而不是再搞一个指针和堆分配)。我很确定就在这个视频里:[VIDEO] 虽然这有多重要可以争论,但这是个很好的例子。人们喜欢“带类的C”,因为他们能读源码,大致搞明白会生成什么代码。他们能推理局部性。虽然我不认为自己是C++专家,但如果我无法推理move构造函数对std::vector这个基础且相对简单的数据结构的影响,那这门语言就已经进入“令人意外”的领域了。要不是在视频里听到,我根本不会想到那是去优化。相关地,我希望返回值优化能有更好的语… — chubot, 2016-11
相关视频
- Python如何被泄漏的内部机制塑造,Armin Ronacher,Flask框架 · Видео с мероприятий {speach! · 49:55
- CppCon 2015:Andrei Alexandrescu “std::allocator...” · CppCon · 1:12:27
- Go 中的词法扫描 - Rob Pike · GoogleFOSSSydney · 51:17
- 防止文明崩溃 / Jonathan Blow (Thekla, Inc) · DevGAMM · 1:02:41
- Emery Berger 的“性能至关重要” · Strange Loop Conference · 42:15
- 三千万行代码问题 · Molly Rocket · 1:48:55
- CppCon 2017: Matt Kulukundis “逐步设计一个快速、高效、缓存友好的哈希表” · CppCon · 59:33
- RustConf 2018 - 闭幕主题演讲 - 使用 Rust 进行游戏开发 by Catherine West · Rust Programming Language · 42:29
- Erlang Factory 2014 - 那是带 'B' 的 'Billion':在 WhatsApp 扩展到下一个级别 · Erlang Solutions · 49:15
- 古惑狼如何黑掉原版PlayStation | 战争故事 | Ars Technica · Ars Technica · 31:37
- Gil Tene 的 "如何不测量延迟" · Strange Loop Conference · 42:59
- CppCon 2016: Jason Turner “为微型计算机编写丰富代码:用C++17实现一个简单的Commodore 64游戏” · CppCon · 1:19:52
- 关于游戏新编程语言的想法。 · Jonathan Blow · 1:55:24
- 快速傅里叶变换(FFT):史上最巧妙的算法? · Reducible · 28:23
- 现代字典 by Raymond Hettinger · SF Python · 1:07:41
- Refterm讲座第一部分 - 优化哲学 · Molly Rocket · 18:41