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

Question

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

我在Clojure意义上使用' persistent ' :持久列表是一个列表,其行为就像它具有值语义而不是引用语义,但不会产生复制大值类型的开销.持久性集合使用copy-on-write来共享内部结构.伪代码:

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以这种方式工作).如果引用计数为1,那么您将保留唯一的引用,因此破坏性地进行更新.如果refcount更高,其他人也持有对它的引用,它应该表现得像一个值类型,所以copy-on-write不会打扰其他引用者.

在这种数据结构的API中,可能会暴露引用计数,这会使API严重降低可用性,或者无法进行引用计数,如果每个操作都是COW,则会导致不必要的写时复制开销,或API丢失它的值类型行为,用户必须管理何时手动执行COW.

如果C#具有结构的复制构造函数,那么这是可能的.可以定义一个包含对实际数据结构的引用的结构,并在结构的复制构造函数和析构函数中执行所有increment()/ decref()调用.

有没有办法在C#中自动执行引用计数或结构复制构造函数,而不会打扰API用户？

编辑:

• 为了清楚起见,我只是询问API.Clojure已经有了用Java编写的实现.
• 通过使用带有对每个操作进行COW的真实集合的引用的结构,当然可以创建这样的接口.使用引用计数将是一种优化,以避免不必要的COWing,但显然不可能使用合理的API.

Answer 1

您可以使用Wea​​kReference类作为引用计数的替代方案，并实现引用计数为您带来的一些好处。当您在 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" ]