Здравствуйте, vdimas, Вы писали:

V>Если у нас есть россыпь структур, которые реализуют некий интерфейс, то в любом случае потребуется адаптер для вызова методов интерфейса.
V>И таких адаптеров всего два — это встроенное боксирование, либо ручное:
V>

V>interface ISomeAPI {
V>   void Foo();
V>}

V>struct S1 : ISomeAPI { ... }
V>struct S2 : ISomeAPI { ... }

V>class ManualBox<T> : ISomeAPI 
V>    where T : struct, ISomeAPI
V>{ 
V>    internal T _boxed;
V>    public void Foo() { _boxed.Foo(); }
  V>}
V>

Всё правильно. Внутри ManualBox<T>.Foo лежит вполне себе невиртуальный вызов T.Foo().
А при дальнейшем цепочка строится из наших ManualBox<T> примерно так:

struct SM<T>: ISomeAPI
  where T: struct, ISomeAPI
{
...  
  private Children: ManualBox<T>[];
  public void Foo() { Children[0]._boxed.Foo(); }
}

В итоге, когда JIT строит код SM<S1>.Foo(), у него тоже нет ни одного виртуального вызова. И вообще, весь ManualBox нам нужен только для того, чтобы заставить SM<S1> хранить массив ссылок на S1, а не массив копий S1. И при этом продолжать обращаться к Foo детишек невиртуально.

И это работает, пока в цепочке не появляются одноимённые классы — к примеру, код this[] для BranchNode<LeafNode<int>, int> прекрасно инлайнится целиком — потому, что там внутри идут обращения к Box<LeafNode<int>>.Value, точный тип которого виден джиту.


V>В учебнике при балансировке B+ дерева можно копировать значения в родительские сегменты, если в тех есть незаполненные ячейки.
Не совсем так. Это вы про B-дерево пишете. В B+ все значения лежат только в листьях, поэтому в родителей ничего не копируется никогда.
V>Сам алгоритм мутабельный.
Мутабельное дерево очень легко превратить в иммутабельное путём порождения копий узлов вместо модификаций. Конкретно B-деревья прекрасно к этому адаптируются, т.к. там и так постоянно возникают ситуации типа "ой, давайте заменим этот 1 лист на 2 вот этих" и наоборот.
V>Но в иммутабельных структурах принято полностью иниализировать объекты в конструкторе, а тут надо будет разделить создание узла, наполнение и последующую иммутабельную эксплуатацию.
Это всё тривиально реализуется в конструкторе, который принимает коллекцию, при помощи флагов заморозки на уровне узлов.
То есть в процессе "наполнения" дерево мутабельное, но перед тем, как отдать ссылку на него наружу, все его узлы замораживаются.

V>Ага, тогда точно в конструкторе завершить инициализацию не выйдет.
В конструкторе дерева — выйдет. А конструктор узла никого не интересует — это подробность реализации.

V>И еще тебе иммутабельность нужна не сама по себе, а как ср-во межпоточной реализации контейнеров.
Ну не обязательно. У меня вообще не стояло никакой прикладной задачи, для которой нужна была бы иммутабельность. Стояла значительно более приземлённая задача — обыграть System.Collections.Immutable.ImmutableList.
Парни из TunnelVision пришли к той же идее, что и я, но их реализация недостаточно оптимизирована. Abstraction Penalty у них сожрало весь выигрыш от cache friendliness и уменьшения глубины дерева.

V>Например, взять сложные структуры, разбитые на сегменты (как B+ деревья или очереди с приоритетами, или простые двусторонние очереди с возможностями вставки-удалениях элементов из середины) — такие алгоритмы могут использовать copy-on-write "точечно", на уровне отдельных сегментов.
Так и делается.

V>Например, копирование узлов до вершины при балансировке иммутабельного дерева не нужно, если не происходит перемещение значений м/у уровнями или разбиениях и обновление индекса вверх.
Так и делается.

V>На каком-то уровне изменений для B+ дерева достаточно будет через lock-free цикл обновить ссылку на дочерний узел, например, при вставке в конец.
V>Или при вставке в середину можно создавать копии только части узлов при провижении наверх.
Так и делается — клонируются ровно те узлы, которые входят в путь от изменяемой ячейки к корню. Независимо от операции — вставка, удаление, изменение.
Всего log(N) копий, что значительно дешевле, чем вставлять в середину copy-on-write массива.

V>Но этот вариант имеет плохой лейаут в памяти, если не использовать кастомный пул-аллокатор.
V>Поэтому, дотнетный вариант реализован иначе.
Возможно, поэтому. Может, из-за других причин. Я свечку не держал, точно сказать не могу.