Как создать API для постоянной коллекции в C #?

Question

Я думаю о создании постоянной коллекции (списков или других) в C #, но я не могу найти хороший API.

Я использую ' persistent ' в смысле 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, вы держите единственную ссылку, поэтому делайте обновления деструктивно.Если refcount выше, кто-то другой также имеет ссылку на него, которая должна вести себя как тип значения, поэтому копируйте при записи, чтобы не мешать другим ссылкам.

В API для такой структуры данных можно выставить пересчет, что делает API менее пригодным для использования, или невозможно выполнить пересчет, что приведет к ненужным издержкам копирования при записи, если каждая операция является COW', или API теряет свое поведение типа значения, и пользователь должен решить, когда делать COW вручную.

Если бы в C # имелись конструкторы копирования для структур, это было бы возможно.Можно определить структуру, содержащую ссылку на реальную структуру данных, и выполнить все вызовы incref () / decf () в конструкторе копирования и деструкторе структуры.

Есть ли способ сделать что-то вроде подсчета ссылок или конструктора структурного копирования автоматически в C #, не беспокоя пользователей API?

Редактировать:

• Просто чтобы прояснить, я просто спрашиваю об API.У Clojure уже есть реализация этого, написанная на Java.
• Такой интерфейс, безусловно, можно создать, используя структуру со ссылкой на реальную коллекцию, которая используется COW в каждой операции.Использование пересчёта было бы оптимизацией, чтобы избежать ненужного 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

Я хотел бы иметь что-то подобное на моем гибком объекте коллекции деревьев, хотя это было бы не с использованием семантики типа значения (что было бы по существу невозможно в .net), а с помощью клона, генерирующего«виртуальный» глубокий клон вместо того, чтобы фактически клонировать каждый узел в коллекции.Вместо точного подсчета ссылок каждый внутренний узел будет иметь три состояния:

1. Гибкий
2. SharedImmutable
3. UnsharedMutable

Вызов Clone () для узла sharedImmutableпросто даст исходный объект;вызов Clone на узле Flexible превратил бы его в SharedImmutable.Вызов Clone на неразделенном изменяемом узле создаст новый узел, содержащий клоны всех его потомков;новый объект будет гибким.

Прежде чем объект может быть написан, его необходимо сделать UnsharedMutable.Чтобы сделать объект UnsharedMutable, если он еще не создан, сделать его родительским (узел, через который он был доступен) UnsharedMutable (рекурсивно).Затем, если объект был SharedImmutable, клонируйте его (используя метод ForceClone) и обновите ссылку родителя, чтобы он указывал на новый объект.Наконец, установите состояние нового объекта в UnsharedMutable.

Существенным аспектом этого метода будет наличие отдельных классов для хранения данных и предоставления интерфейса к ним.Оператор, подобный

MyCollection["this"]["that"]["theOther"].Add("George")

, должен оцениваться, если операции индексирования возвращают класс индексатора, который содержит ссылку на MyCollection.На этом этапе метод «Добавить» мог бы затем воздействовать на любые промежуточные узлы, необходимые для выполнения любых необходимых операций копирования при записи.

Answer 4

Я прочитал то, что вы просите, и я думаю о структуре API типа "терминал-сервер".

Сначала определите внутренний потокобезопасный одноэлементный класс, который будет вашим "сервером"; на самом деле он содержит данные, которые вы смотрите. Он предоставит метод Get and Set, который будет принимать строку устанавливаемого или получаемого значения, управляемую ReaderWriterLock, чтобы гарантировать, что значение может быть прочитано кем угодно, но не тогда, когда кто-либо пишет, и только один человек может писать одновременно .

Затем предоставьте фабрику для класса, который является вашим "терминалом"; этот класс будет общедоступным и содержит ссылку на внутренний синглтон (который иначе не будет виден). Он будет содержать свойства, которые на самом деле являются просто переходами для экземпляра синглтона. Таким образом, вы можете предоставить большое количество «терминалов», которые будут видеть одни и те же данные с «сервера» и смогут изменять эти данные потокобезопасным способом.

Вы можете использовать конструкторы копирования и список значений, к которым обращается каждый экземпляр, для предоставления знаний о типе копирования. Вы также можете смешивать имена значений с дескриптором объекта для поддержки случаев, когда L1 и L2 совместно используют A, но L3 имеет другой A, потому что он был объявлен отдельно. Или, L3 может получить тот же, что и L1 и L2. Как бы вы это ни структурировали, я бы очень четко задокументировал, как он должен себя вести, потому что это НЕ так, как ведут себя вещи в базовом .NET.