如何为C#中的持久集合设计api？

Question

我正在考虑在C#中创建一个持久的集合(列表或其他集合)，但我无法找到一个好的API。

我在持久的中使用了“克罗氏”：持久化列表是一种列表，其行为方式好像它具有值语义而不是引用语义，但不需要复制大型值类型的开销。持久集合使用复制即写来共享内部结构。伪码：

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的可用性，或者无法进行重新计算，如果每个操作都是奶牛，或者API失去了它的值类型行为，用户必须管理何时手动操作，就会导致不必要的复制上写开销。

如果C#有用于结构的复制构造函数，这是可能的。可以定义包含对实际数据结构的引用的结构，并在结构的复制构造函数和析构函数中执行所有/decref()调用。

是否有一种方法可以在C#中自动执行引用计数或结构复制构造函数之类的操作，而不影响API用户？

编辑：

• 澄清一下，我只是问一下API的情况。Clojure已经有了一个用Java编写的实现。
• 当然，可以通过使用带有引用每个操作的实际集合的结构来创建这样的接口。重新计算的使用将是一个优化，以避免不必要的COWing，但显然是不可能的一个理智的API。

Answer 1

严格地说，你想做的事是不可能的。您可以通过使用执行引用计数的静态函数来接近，但我知道这不是一个很好的选择。

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

Answer 2

您可以使用WeakReference类作为重新计算的替代方法，并实现填充给您带来的一些好处。当您持有WeakReference中对象的唯一副本时，它将被垃圾收集。WeakReference有一些钩子可以让您检查是否存在这种情况。

编辑3:虽然这种方法确实有作用，但我建议您不要在C#集合上说服值语义。您的结构的用户不会期望在平台上出现这种行为。这些语义增加了混乱和出错的可能性。

编辑2:添加了一个例子。 @AdamRobinson:恐怕我不清楚WeakReference有什么用处。我必须警告这种性能，在大多数情况下，它甚至可能比在每个操作中做一个简单的复制还要糟糕。这是由于垃圾收集器调用。因此，这只是一个学术解决方案，我不能推荐它在生产系统中的使用。不过，它确实能做你想要的。

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" ]

Answer 3

我阅读了您所要求的内容，并且正在考虑一种“终端服务器”-type API结构。

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

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

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