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

S>Всё правильно. Внутри ManualBox<T>.Foo лежит вполне себе невиртуальный вызов T.Foo().

Снаружи зато вызов уже виртуальный, через интерфейс или базовый абстрактный класс.
Именно это имелось ввиду.

Для виртуального вызова надо сделать три разыменования ссылки — сначала получить ссылку на VMT, затем у той получить указатель на метод, затем косвенно вызывать метод.
За ту же цену индирекции можно пройти три слоя узлов дерева. ))
Тем более, что верхний узел дерева с небольшой арностью можно хранить по-значению.
В иммутабельном варианте и само такое дерево может быть value-type, т.е. просто оберткой над корнем.


S>А при дальнейшем цепочка строится из наших ManualBox<T> примерно так:

Это я уже понял несколько сообщений назад.

Сравнить с моим примером логгирования, где запись на логгирование статическая, считай.
А у тебя вложенность типов будет зависеть от фактических данных.
Бедный джит. ))


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

Ну да, однажды скомпиллированный-заинлайненный по месту вызова this[i] потребует перекомпиляции после вставки.
Про спекулятивную оптимизацию тут и заикаться смысла нет, насколько я понял? ))

Тогда уж лучше рекурсия/виртуальность.
Причём, для this[i] можно приделать ручную виртальность.

Хранить индекс в узле-ветке можно так, грубо:

struct Cell {
   int _index;
   NodeBase _child;
   delegate * <NodeBase, ref T> _getItem;
}

А вставку-удаление протянуть виртуально для простоты, т.к. эффективность изменения иммутабельных структур и так тяжелая, там вирутальность особо не повлияет, тем более что для B+ деревьев кол-во слоёв выходит небольшим.

Бороться стоит лишь за эффективность доступа по чтению, ИМХО.


V>>В учебнике при балансировке B+ дерева можно копировать значения в родительские сегменты, если в тех есть незаполненные ячейки.
S>Не совсем так. Это вы про B-дерево пишете. В B+ все значения лежат только в листьях, поэтому в родителей ничего не копируется никогда.

В бинарных деревья априори не бывает незаполненных ячеек.
А в B+ бывают, зависит от реализации.
Например, когда балансировка допускает один уровень разницы высоты дерева по разным путям, как в красно-черных деревьях.

И еще в мутабельных структурах можно реализовать эффективное удаление за счёт образования "дырок" в хранилищах, в этих реализациях отдельно вводится операция компактификации.


V>>Сам алгоритм мутабельный.
S>Мутабельное дерево очень легко превратить в иммутабельное путём порождения копий узлов вместо модификаций.

Ну как легко...
В имутабельном дереве происходит изменение одной ссылки в родительском узле при повороте поддерева, а в имутабельном создаются копии родительских узлов до корня.
В этом месте и возникают эксперименты с подбором арности.

И эти эксперименты, таки, лучше провести.
Например, через сетку вложенных

struct BunchX2<TBunch> {
    internal TBunch _0, _1;
}

V>>Но в иммутабельных структурах принято полностью иниализировать объекты в конструкторе, а тут надо будет разделить создание узла, наполнение и последующую иммутабельную эксплуатацию.
S>Это всё тривиально реализуется в конструкторе, который принимает коллекцию, при помощи флагов заморозки на уровне узлов.

Вот, "флаги заморозки".


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

Странная формулировка задачи, ну да ладно.


S>Парни из TunnelVision пришли к той же идее, что и я, но их реализация недостаточно оптимизирована. Abstraction Penalty у них сожрало весь выигрыш от cache friendliness и уменьшения глубины дерева.

Ну, то смотря какие "веса" раздать операциям.
Повторюсь, если стоимость обновления и так большая, то за стоимостью обновления можно и не гнаться, а сосредоточиться на лучшем лейауте памяти, на эффективности чтения.


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

С тем замечанием, что дерево перестраивается до корня.


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

А вот тут непонятно.
Если была создана копия узла-ветки с обновлёнными индексами, родительский узел надо заставить ссылаться на новый экземпляр, т.е. сделать копию родительского узла и т.д. вверх.

Пока что навскидку кажется, что арность узлов стоит уменьшать при движению к корню.
Вернее, увеличивать при росте дерева.
Т.е., чем глубже уровень, тем больше стоит делать арность узлов.


V>>На каком-то уровне изменений для B+ дерева достаточно будет через lock-free цикл обновить ссылку на дочерний узел, например, при вставке в конец.
V>>Или при вставке в середину можно создавать копии только части узлов при провижении наверх.
S>Так и делается — клонируются ровно те узлы, которые входят в путь от изменяемой ячейки к корню.

Ага, ты ответил — путь к корню в любом случае клонируется.


S>Всего log(N) копий, что значительно дешевле, чем вставлять в середину copy-on-write массива.

Если массив сегментирован — не скажи.

Например, С++ дек исторически был выполнен как сегментированное хранилище.

As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one.

И приоритетные очереди отродясь на B+-деревьях строились.
(наконец попало в стандарт из Буста)

В условиях GC безблокировочные многопоточные реализации этих структур отличаются от однопоточных доп. циклом обновления сегментов на основе cas.


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

Ну ты там рассуждал о "cache friendliness" — это была основная причина, т.е. попытка уместить данные в один массив.

Давно не смотрел, сейчас вижу в исходниках, что они сделали отдельный массив индексов (размер которого только и должен быть простым числом), что позволяет складывать конфликтующие значения в общий массив данных.
Т.е. ввели доп. индирекцию в размен на более компактное хранение.
Тоже вариант...