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

V>>Тогда на верхнем уровне в любом случае виртуальность.
S>Нет конечно, не в любом. Все эти типы — struct, так что в коде нет ни одного виртуального вызова.

Перечитай фразу на которую отвечаешь внимательно, плиз.

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

interface ISomeAPI {
   void Foo();
}

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

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

V>>Попробую найти время, посмотреть на балансировку.
S>Да она там совершенно обычная, как в учебнике.

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

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


V>>Точная балансировка тем дороже, чем больше арность, потому что приходится создавать более дорогие копии при каждом изменении дерева.
S>Да, одиночные вставки могут подтормаживать; зато на AddRange можно немножко наиграть за счёт повторного использования.

Ага, тогда точно в конструкторе завершить инициализацию не выйдет.


V>>Ну вот как раз ради случая хеш-таблицы в хеш-таблицах всё и затевалось.
V>>Capacity каждой хеш-таблицы относительно невелик (23, 19, 17, 13, 11), пересоздавать при изменении достаточно одну таблицу, а не всю цепочку их до корневого узла, как оно есть в иммутабельных деревьях при балансировке.
S>Да, мысль хорошая. У меня задачи делать IDictionary<,> не стояло, а для IList<> B-дерево выглядит самой эффективной реализацией.

Только у тебя B+.
И еще тебе иммутабельность нужна не сама по себе, а как ср-во межпоточной реализации контейнеров.

Например, copy-on-write тоже пляшет от иммутабельных структур.

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

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

Потому что для перечисленного набора ограничений чистая иммутабельность не диктуется, а разве что выбирается как ср-во решения задачи.
А диктуется лишь атомарность/транзакционность при внесении изменений, т.е. согласованность данных при чтении.

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


V>>Самый простой вариант — складывать конфликты в упорядоченный список (массив конфликтующих значений).
S>Да, именно этот вариант первым приведён у Кнута, емнип.

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