CppCon 2017: Juan Pedro Bolivar Puente “后现代不可变数据结构”

CppCon 2017: Juan Pedro Bolivar Puente “Postmodern immutable data structures”

频道:CppCon · 时长:1:05:59 · 发布:2017-10-27 · 播放:31439

在 YouTube 观看

简介

Juan Pedro Bolivar Puente解释了C++中的不可变和持久数据结构,以及它们如何支持值语义。他介绍了Immer库、rrb树,以及一个能瞬间打开巨大文件的原型文本编辑器。

HN 为什么推荐

HN的人指出它涉及rrb树、文本编辑器数据结构,并将Clojure风格的持久结构引入C++。

Immer [0][1]似乎是一个真正认真的尝试,将高质量的持久数据结构引入C++。 — HN, 2021

函数式编程 · C、C++、Rust、Go 与系统语言 · 算法与数据结构

中文字幕节选

大家好,欢迎各位。我叫 Juanpe。 我是一名独立软件工程师和顾问,目前常驻柏林。 今天我要讲的是不可变数据结构。 我的意思是,不可变数据结构的核心要义 就是让值语义能够规模化。 在座有多少人觉得值语义很棒? 好,几乎所有人。太好了。 有多少人主要在一个代码库中工作,其中大多数类型都是值类型, 并且大多数函数都是按值接收参数并返回结果? (笑声)哦,两个人,太棒了。 你们用的是 C++ 还是 Haskell? (笑声)问题就在这儿。 要让值语义规模化,实际上是很复杂的。 所以这就是为什么本次演讲的第一部分 叫做“基于值架构的悲剧”。 而这个悲剧始于许多良好的初衷。 在我们的架构中心,理想情况下有一个数据模型,它由 简单的值类型组成,比如结构体、STD 向量、 元组,简单的东西。现在,软件中的应用逻辑 将是纯函数。这些函数按值接收一个文档, 然后按值产生另一个文档,对吧? 这种架构经常被宣传的优点之一是, 比如实现撤销操作变得轻而易举。 我们只需把之前的状态保存在一个向量或某个集合中,就完成了。 我们现在可以撤销了。同时,我们还能非常简单地实现并发,因为 假设我们想要一个渲染线程 在单独的线程中渲染 UI,我们只需在那个单独的线程中循环, 通过某种神奇的消息 传递机制,把文档的值 传给另一个线程,它们就可以独立地 进行渲染,与所有逻辑发生的地方分开。 持久化也是同样的道理。 我想保存到磁盘,这可能很慢, 所以我只需启动一个异步任务。 我在 lambda 中按值捕获文档,然后对它进行操作。 同样地,我可以有文档的其他表示形式, 比如我在音乐软件行业工作了很多年, 那里你经常会有文档的音频表示, 某种能产生音频的东西。 我们可以在这类替代 UI 或表示形式中 遵循同样的模式。 但这里有个问题。 我们到处都在做拷贝,对吧? 除非我们处理的是非常简单的文档,否则这无法规模化。 所以一个聪明的 C++ 工程师会说: 好吧,我们不要按值接收文档 并返回一个新值,那样可能会产生拷贝, 我们就按引用接收它,然后原地更新。 但一旦这么做,我们就不再把数据模型 看作一个值,而是把它看作一个对象、一个位置。 它在内存中存储的位置变得重要, 因为这关系到这个函数的正确性。 当然,现在还有其他人也在访问这个文档。 他们需要用互斥锁等机制 来同步访问,所以我们可能还要添加 一些有状态的 UI 中间表示, 带有我们的控件树,当然我们需要保持这个控件树更新, 所以现在我们需要在文档中加入信号和槽, 这样当文档中的内容发生变化时,我们可以回调并更新。 当然,你知道,我们不再在撤销历史中保留拷贝了, 所以我们需要实现这个命令模式 众所周知这很难实现。 异步进行持久化将会 非常困难,因为我们不能简单地复制 文档,尤其是在我们添加了信号之后。 不管怎样,我们的用户已经习惯了界面上有这种旋转的时钟 但没有什么能拯救我们免受飞行面条

HN 上的讨论

嘿。看看 Juan Pedro Bolivar Puente 关于面向值设计的演讲。他曾在 Ableton 工作,这是一个大型应用程序。他特别谈到了撤销。他描述了一种比命令模式更好的模式。他还发布了他的面向值数据结构的源代码。Juan Pedro 是一位下一级程序员,我认为他通过将面向值设计引入 C++ 世界,推动了这门手艺的发展。演讲 I [VIDEO] 演讲 II [LINK] 数据结构:[LINK] 应用程序结构:[LINK] 文本编辑器:[LINK] 祝你好运。 — nightowl_games, 2020-12
> [...] 这对于任何面向性能的东西都是必须的。但这也并不完全正确。使用函数式数据结构可以编写高性能的软件。例如,看看“CppCon 2017: Juan Pedro Bolivar Puente - 后现代不可变数据结构”[1],这是一个令人印象深刻的演讲,其中有人展示了他们开发的编辑器,可以比当今任何主流编辑器更快地编辑巨大的文本文件而无延迟。这是由函数式数据结构实现的。在整个项目中使用函数式数据结构也确保了部分可以轻松并行化,这对于传统算法来说是不成立的,因此可以轻松地随着可用 CPU 的数量扩展。关于这个主题,你可能想看看 Joe Armstrong 的几个演讲。Rust 通过引入更多语言概念(如所有权、借用和生命周期)来实现类型安全,以形式化谁在何时以及如何访问。它还默认创建不可变的东西,除非你使用 `mut`。不幸的是,Rust 的理念是共享内存并使共享内存访问安全,而不… — zelphirkalt, 2025-10
你可能对 Juan Pedro Bolivar Puente 的 ewig 和 immer 感兴趣:[LINK] [LINK] 在演讲大约 27 分钟处,可以看到作者瞬间打开一个约 1GB 的文本文件,进行异步加载、分页浏览、复制/粘贴以及撤销/重做,使用的是他们的原型“ewig”文本编辑器:[VIDEO] 它由一个称为松弛基数平衡树的“向量的向量”数据结构支持:[LINK] 那篇原始论文受到了很多关注,并有许多性能改进的尝试,例如:[LINK] [LINK] — modernerd, 2023-06
Immer [0][1] 似乎是一个真正严肃的尝试,将高质量的持久数据结构引入 C++。[0]:[VIDEO] [1]:[LINK] — bertmuthalaly, 2021-09
嗯,美味。如果有人想要了解这种数据结构的背景故事,可以看看这个演讲:[VIDEO] 他构建了一个 rrb-tree,使用了与 ALEX 相同的基本概念,只是没有 ML 增强。 — proverbialbunny, 2020-06

相关视频