c++ - c++中的持久化数据结构

Question

c++ 中有没有类似于 clojure 的持久化数据结构实现？

Answer 1

我自己滚动，但有 immer library作为一个相当全面的例子，它特别受到 clojure 的启发。几年前，在听了约翰·卡马克 (John Carmack) 的演讲后，我感到非常兴奋，并推出了自己的演讲，他在函数式编程的潮流中跳跃。他似乎能够想象一个围绕不可变数据结构旋转的游戏引擎。虽然他没有详细说明，虽然这在他的脑海中似乎只是一个模糊的想法，但他正在认真考虑它并且似乎并不认为开销会急剧降低帧速率这一事实足以让我兴奋关于探索这个想法。

我实际上将它用作某种优化细节，这可能看起来很矛盾(不变性存在开销)，但我的意思是在特定的上下文中。如果我绝对想这样做:

// We only need to change a small part of this huge data structure.
HugeDataStructure transform(HugeDataStructure input);

...而且我绝对不希望该函数引起副作用，以便它可以是线程安全的并且永远不会被误用，那么我别无选择，只能复制巨大的数据结构(可能跨越一个千兆字节)。

我发现在这种情况下拥有一个不可变数据结构的小型库非常有用，因为它通过浅拷贝和引用未更改的部分使上述场景相对便宜。也就是说，我大多只使用一种不可变的数据结构，它基本上是一个随机访问序列，如下所示:

正如其他人所提到的，它确实需要一些小心和调整以及全面的测试以及许多 VTune session 才能使其线程安全和高效，但是在我投入了肘部油脂之后，它确实让事情变得非常简单.

每当我们使用这些结构来编写没有副作用的函数时，除了自动线程安全之外，您还可以获得诸如非破坏性编辑、简单的撤消系统、简单的异常安全(无需回滚副作用)之类的东西通过函数中的范围保护，导致异常路径中没有)，并让用户复制和粘贴数据并实例化它而不占用太多内存，直到/除非他们修改他们粘贴的内容作为奖励。实际上，我发现这些奖励每天比线程安全更有用。

我使用“ transient ”(又名“构建器”)来表达对数据结构的更改，如下所示:

Immutable transform(Immutable input)
{
    Transient transient(input);

    // make changes to mutable transient.
    ...

    // Commit the changes to get a new immutable
    // (this does not touch the input).
    return transient.commit();
}

我什至有一个不可变的图像库，用于图像编辑以简化非破坏性编辑。它使用与上述结构类似的策略，将图像视为图 block ，如下所示:

当一个 transient 被修改并且我们得到一个新的不可变时，只有被改变的部分是唯一的。其余的图 block 是浅拷贝的(只有 32 位索引):

我确实在网格和视频处理等性能相当关键的领域使用这些。对于每个 block 应该存储多少数据进行了一些微调(太多了，我们浪费了处理和内存深度复制了太多数据，太少了，我们浪费了处理和内存浅复制了太多带有更频繁线程锁的指针)。

我不将这些用于光线追踪，因为这是可以想象到的最极端的性能关键领域之一，并且用户可以注意到最微小的开销(他们实际上进行基准测试并注意到 2% 范围内的性能差异)，但是大多数时候，它们足够高效，当您可以将这些巨大的数据结构作为一个整体左右复制以简化线程安全、撤消系统、非破坏性编辑等时，这是一个非常棒的好处，而无需担心爆炸性的内存使用和明显的延迟用于深度复制所有内容。