我正在考虑在 C# 中创建一个持久性集合(列表或其他),但我想不出一个好的 API。
我在Clojure 意义上使用“持久” :持久列表是一个表现得好像它具有值语义而不是引用语义的列表,但不会产生复制大值类型的开销。持久集合使用写时复制来共享内部结构。伪代码:
l1 = PersistentList()
l1.add("foo")
l1.add("bar")
l2 = l1
l1.add("baz")
print(l1) # ==> ["foo", "bar", "baz"]
print(l2) # ==> ["foo", "bar"]
# l1 and l2 share a common structure of ["foo", "bar"] to save memory
Clojure 使用这样的数据结构,但在 Clojure 中,所有数据结构都是不可变的。执行所有写时复制的工作都会产生一些开销,因此 Clojure 提供了一种临时数据结构形式的解决方法,如果您确定不与其他任何人共享数据结构,您可以使用该解决方法。如果您只有对数据结构的引用,为什么不直接对其进行变异,而不是经历所有的写时复制开销。
获得这种效率增益的一种方法是在您的数据结构上保持引用计数(尽管我不认为 Clojure 以这种方式工作)。如果 refcount 为 1,那么您将持有唯一的引用,因此会破坏性地进行更新。如果引用计数较高,则其他人也持有对它的引用,该引用应该表现得像值类型,因此请执行写时复制以免打扰其他引用者。
在这种数据结构的 API 中,可能会暴露引用计数,这会严重降低 API 的可用性,或者不能进行引用计数,如果每个操作都是 COW,则会导致不必要的写时复制开销,或者 API失去它的价值类型行为,用户必须管理何时手动执行 COW。
如果 C# 有结构的复制构造函数,这将是可能的。可以定义一个包含对真实数据结构的引用的结构,并在结构的复制构造函数和析构函数中执行所有 incref()/decref() 调用。
有没有办法在 C# 中自动执行引用计数或结构复制构造函数之类的操作,而不会打扰 API 用户?
编辑:
- 为了清楚起见,我只是在询问 API。Clojure 已经有一个用 Java 编写的实现。
- 当然可以通过使用一个结构来创建这样一个接口,该结构引用了在每个操作中都被 COW 处理的真实集合。引用计数的使用将是避免不必要的 COWing 的优化,但显然对于理智的 API 是不可能的。