5

我正在考虑在 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 是不可能的。
4

4 回答 4

3

严格来说，你想要做的事情是不可能的。您可以通过使用执行引用计数的静态函数来接近，但我知道这不是一个糟糕的可口选项。

即使有可能，我也会远离这个。虽然您描述的语义在 Clojure 中可能很有用，但值类型和引用类型语义之间的这种交叉会使大多数 C# 开发人员感到困惑（可变值类型——或具有可变值类型语义的类型——通常也被认为是邪恶的）。

于 2010-11-16T00:13:15.670 回答
1

您可以使用Wea​​kReference类作为引用计数的替代方法，并获得引用计数给您带来的一些好处。当您在 WeakReference 中保存对象的唯一副本时，它将被垃圾收集。WeakReference 有一些钩子供您检查是否是这种情况。

编辑 3：虽然这种方法确实起到了作用，但我敦促您不要在 C# 集合上使用值语义。您的结构的用户不希望在平台上出现这种行为。这些语义增加了混乱和错误的可能性。

编辑 2：添加了一个示例。@AdamRobinson：恐怕我不清楚如何WeakReference使用。我必须警告说，在性能方面，大多数时候它可能比在每次操作中都执行一个简单的 Copy-On-Write 更糟糕。这是由于垃圾收集器调用。因此，这只是一个学术解决方案，我不建议将其用于生产系统。但是，它确实可以满足您的要求。

class Program
{

  static void Main(string[] args)
  {
    var l1 = default(COWList);
    l1.Add("foo"); // initialize
    l1.Add("bar"); // no copy
    l1.Add("baz"); // no copy
    var l2 = l1;
    l1.RemoveAt(0); // copy
    l2.Add("foobar"); // no copy
    l1.Add("barfoo"); // no copy
    l2.RemoveAt(1); // no copy
    var l3 = l2;
    l3.RemoveAt(1); // copy
    Trace.WriteLine(l1.ToString()); //  bar baz barfoo
    Trace.WriteLine(l2.ToString()); // foo baz foobar
    Trace.WriteLine(l3.ToString()); // foo foobar
  }
}

struct COWList
{
  List<string> theList; // Contains the actual data
  object dummy; // helper variable to facilitate detection of copies of this struct instance.
  WeakReference weakDummy; // helper variable to facilitate detection of copies of this struct instance.

  /// <summary>
  /// Check whether this COWList has already been constructed properly.  
  /// </summary>
  /// <returns>true when this COWList has already been initialized.</returns>
  bool EnsureInitialization()
  {
    if (theList == null)
    {
      theList = new List<string>();
      dummy = new object();
      weakDummy = new WeakReference(dummy);
      return false;
    }
    else
    {
      return true;
    }
  }

  void EnsureUniqueness()
  {
    if (EnsureInitialization())
    {

      // If the COWList has been copied, removing the 'dummy' reference will not kill weakDummy because the copy retains a reference.
      dummy = new object();

      GC.Collect(2); // OUCH! This is expensive. You may replace it with GC.Collect(0), but that will cause spurious Copy-On-Write behaviour.
      if (weakDummy.IsAlive) // I don't know if the GC guarantees detection of all GC'able objects, so there might be cases in which the weakDummy is still considered to be alive.
      {
        // At this point there is probably a copy.
        // To be safe, do the expensive Copy-On-Write
        theList = new List<string>(theList);
        // Prepare for the next modification
        weakDummy = new WeakReference(dummy);
        Trace.WriteLine("Made copy.");

      }
      else
      {
        // At this point it is guaranteed there is no copy.
        weakDummy.Target = dummy;
        Trace.WriteLine("No copy made.");

      }
    }
    else
    {

      Trace.WriteLine("Initialized an instance.");

    }
  }

  public void Add(string val)
  {
    EnsureUniqueness();
    theList.Add(val);
  }

  public void RemoveAt(int index)
  {
    EnsureUniqueness();
    theList.RemoveAt(index);
  }

  public override string ToString()
  {
    if (theList == null)
    {
      return "Uninitialized COWList";
    }
    else
    {
      var sb = new StringBuilder("[ ");
      foreach (var item in theList)
      {
        sb.Append("\"").Append(item).Append("\" ");
      }
      sb.Append("]");
      return sb.ToString();
    }
  }
}

这输出：

Initialized an instance.
No copy made.
No copy made.
Made copy.
No copy made.
No copy made.
No copy made.
Made copy.
[ "bar" "baz" "barfoo" ]
[ "foo" "baz" "foobar" ]
[ "foo" "foobar" ]
于 2010-11-16T00:09:55.867 回答
0

我想在我的一个灵活的树集合对象上有这样的东西，虽然它不是通过使用值类型语义（这在.net中基本上是不可能的），而是通过让克隆生成一个“虚拟”深度克隆，而不是实际克隆集合中的每个节点。每个内部节点都没有尝试保持准确的引用计数，而是具有三种状态：

  1. 灵活的
  2. 共享不可变
  3. 非共享可变

在 sharedImmutable 节点上调用 Clone() 只会产生原始对象；在 Flexible 节点上调用 Clone 会将其变成 SharedImmutable 节点。在非共享的可变节点上调用 Clone 将创建一个新节点，其中包含其所有后代的克隆；新对象将是灵活的。

在写入对象之前，必须将其设为 UnsharedMutable。如果对象还不是 UnsharedMutable，则要使其成为 UnsharedMutable，请将其父级（访问它的节点）设为 UnsharedMutable（递归）。然后，如果对象是 SharedImmutable，则克隆它（使用 ForceClone 方法）并更新父对象的链接以指向新对象。最后，将新对象的状态设置为 UnsharedMutable。

这种技术的一个重要方面是拥有单独的类来保存数据并为其提供接口。像这样的声明

MyCollection["this"]["that"]["theOther"].Add("George")
需要通过让索引操作返回一个索引器类来评估，该类包含对 MyCollection 的引用。那时，“添加”方法就可以对它必须执行的任何中间节点进行操作，以执行任何必要的写时复制操作。

于 2011-01-27T20:02:39.820 回答
0

我阅读了您的要求，并且正在考虑“终端服务器”类型的 API 结构。

首先，定义一个内部的、线程安全的单例类作为你的“服务器”；它实际上包含您正在查看的数据。它将公开一个 Get 和 Set 方法，该方法将获取正在设置或获取的值的字符串，由 ReaderWriterLock 控制以确保任何人都可以读取该值，但不能在任何人写入时读取，并且一次只有一个人可以写入.

然后，为您的“终端”类提供一个工厂；此类将是公共的，并且包含对内部单例的引用（否则无法看到）。它将包含实际上只是单例实例的传递的属性。通过这种方式，您可以提供大量“终端”，它们都将从“服务器”看到相同的数据，并且能够以线程安全的方式修改该数据。

您可以使用复制构造函数和每个实例访问的值列表来提供复制类型知识。您还可以将值名称与对象的句柄混搭，以支持 L1 和 L2 共享 A，但 L3 具有不同的 A，因为它是单独声明的。或者，L3 可以得到与 L1 和 L2 相同的 A。无论您如何构建它，我都会非常清楚地记录它应该如何表现，因为这不是基本 .NET 中的行为方式。

于 2010-11-16T00:16:19.393 回答