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

V>>Ну вот как раз джависты показывали, что после уплотнения GC узлы подобных объектов располагаются в памяти рядом, т.к. доступны по ссылкам только из родительских узлов, т.е. по мере естественного обхода ссылок выстроились в правильный порядок в памяти.
S>Это всё ещё значительно менее плотно, чем int[].

На быстродействие влияет не только кеш нулевого уровня, который у каждого ядра личный.
Кеш нулевого уровня влияет на быстродействие я уже напоминал где — это когда иммутабельные типы заползают на ту линейку кеша, в которых расположены активно изменяемые данные. В этом случае иммутабельность профанируется с т.ч. железа. И эта задача всё-равно еще не решена у тебя.

Т.е., тебе пока требуется "просто локальность", а в ней разница в 64 байта или 1кб практически отсутствует в разогретом кеше.


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

Я не вижу на графиках объезжания на малых объемах данных, но ты утверждаешь обратное.


V>>Т.е. рост дерева будет дороже, но можно будет замерить доступ по чтению (если успешно заинлайнится), т.е. чтобы понять — стоит ли вообще копать в эту сторону.
S>Рост будет стоить ровно столько же.

Это с большой копипастой.
Я бы для простоты сделал на виртуальных методах или if-ах с последующим разбоксированием.
Это же все-равно лишь эксперимент для замера эффективности другой функциональности.


V>>Так непонятен график.
V>>Он должен быть линейным в логарифмической шкале для имеющейся реализации.
V>>Что такого может произойти на 256 элементах, что до него рост линейный, потом скачок, потом опять линейный рост?
S>Я полагаю — пересечение границы какого-то из кэшей.

Когда просто по чтению?
Та граница должна будет пересечься и у тебя в каком-то месте.

Можно было бы повторить замеры с предварительным full GC после наполнения дерева.


S>>>Потому что не взлетает даже когда у нас "рекурсивный" вызов делается напрямую, по call CONST.
V>>Ну ты же обогнал имеющуюся реализацию?
S>Я обогнал на коде без вызовов.

Код без вызовов не объясняет отклонение от log(N).


V>>Косвенные вызовы тоже умеют обрабатываться предвыборкой до какой-то степени.
S>Вряд ли.

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


V>>И там лишние 8 байт на Cell особой роли играть не будут.
S>Да там не нужен этот Cell вообще. Это же B+ дерево — тип у всех детей любой ноды одинаков. Поэтому достаточно хранить ровно одну ссылку на getItem.

А да, в твоей релизации одинаковы.
Тем более.


S>Но это всё ещё не поможет — даже когда вместо косвенного вызова внутри getItem стоит прямой вызов на getItem вложенного класса, производительность падает на дно.

Но в дотнетной реализации именно это?



V>>Алгоритм можно расширить на n-арное дерево.
V>>Считай, что твой 16-арный узел — это 8 по 2, но не принципиально, пусть там было бы не 16, а 17.
V>>Алгоритм выявляет место, где требуется произвести поворот дерева.
S>Хм. Сходу не очень понимаю, как будет работать поворот небинарного дерева.

При повороте дочерний узел заменяет собой родительский узел.
В иммутабельном виде как таковой "замены" нет, есть перестроение подиерархии.
Красно-черные позволяют при перестроении перестраивать ограниченное кол-во узлов, т.к. допускается разница в уровнях в 1 по разным веткам.

А у тебя при росте вложенности потребуется перестроить всё дерево, насколько я сейчас понял.


V>>Речь про арность.
S>Речь про лишние вызовы. Они доминируют над арностью.

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

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


S>Я же говорю — был прошлогодний код, который работал на гомогенном дереве. Но в нём были проблемы с выделением лишней памяти в листьях. График, который я показал — оттуда.
S>Сейчас я пытаюсь реализовать код, в котором нет лишних данных. Технически, это получилось, но вот лишние вызовы портят всю малину.

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

Причём, твой узел заведомо "знает", ссылается ли он на листья или ветки, это один флаг.
Затем можно приводить ссылку на дочерний узел через Unsafe.As<T>(Object).

Смотри какие фокусы выдаёт:

class Box<T>
    where T : struct 
{
    public readonly T Value;

    public Box(T value) => Value = value;
}

class Box {
    public static Box<T> From<T>(T value) where T : struct => new(value);
}

private static void Main() {
    object boxedDouble = Box.From(1.0);
    var boxedLong = Unsafe.As<Box<long>>(boxedDouble);
    var doubleBits = boxedLong.Value;
    var isPositive = (doubleBits & 1L << 63) == 0;
}