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

V>>Я не вижу на графиках объезжания на малых объемах данных, но ты утверждаешь обратное.
S>Надо внимательно смотреть:
S>Image: 2021_08_05_17_40_39_SmallSize.png

И под каким графиком площадь меньше?


V>>Это с большой копипастой.
V>>Я бы для простоты сделал на виртуальных методах или if-ах с последующим разбоксированием.
S>Не понимаю смысл.

Узел типа вложенности 1 должен породить тип узла вложености 2 при разбиении, для сохранения статичности типа и т.д.


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

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

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

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


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

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

Это как альтернатива проверки типа или флага дочернего узла:

internal static unsafe class NodeHelper<T> {
    private static readonly delegate*<BranchNode<T>, int, T> s_branchGetItem = &BranchNode<T>.GetItem;
    private static readonly delegate*<LeafNode<T>, int, T> s_leafGetItem = &LeafNode<T>.GetItem;

    public static delegate*<object, int, T> GetItemFun(bool isLeaf)
        => isLeaf ? (delegate*<object, int, T>)s_leafGetItem : (delegate*<object, int, T>)s_branchGetItem;
}

internal class LeafNode<T> {
    private Bunch<T> _values;

    public static T GetItem(LeafNode<T> @this, int index) => @this._values[index];
}

internal unsafe class BranchNode<T> {
#region do not reorde
    private struct Indicies { private fixed int _data[16];}
    private Indicies _indicies;

    private Bunch<object> _children;
    private readonly delegate*<object, int, T> _childGetItem;
#endregion
        
    internal BranchNode(bool childIsLeaf) => _childGetItem = NodeHelper<T>.GetItemFun(childIsLeaf);

    // agressive-optimization
    // no-locals-init
    public static T GetItem(BranchNode<T> @this, int index) {
        object child;
        (child, index) = @this.FindChild(index);
        return @this._childGetItem(child, index);
    }

    private (object child, int index) FindChild(int index) => (0, 0);
}

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

Здесь в коде тоже хак — типы указателей на ф-ии приводятся к друг другу без проверки, т.е. корректность должна обеспечиваться самим кодом, бо в рантайме тоже проверок нет.
Это дыра в привычной безопасности, поэтому delegate*<> может жить только в unsafe-блоках кода.


V>>При повороте дочерний узел заменяет собой родительский узел.
S>Какой именно из дочерних узлов?

Где происходит сбой разметки красное-черное.
В худшем случае (при упорядоченной вставке) происходит, если склероз не изменяет, одна балансировка на две вставки.


V>>А у тебя при росте вложенности потребуется перестроить всё дерево, насколько я сейчас понял.
S>Нет конечно. Рост вложенности — это split, он очень простой. порождаются ровно три узла, независимо от глубины дерева. Это же B-tree, они все работают одинаково.

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


V>>В мутабельном B+ дереве легко последовательно обойти хранящиеся значения (один из основных кейзов для списка), т.к. все листья соеденены в связанный список.
V>>В иммутабельном виде этой функциональности нет, насколько я понимаю, поэтому обход достаточно дорогой.
S>Обход я ещё не оптимизировал; но там скорее всего тоже всё будет не намного дороже. Прямо сейчас итератор сделан тупо через _list[_position], то есть шаг итерации ~ O(log(N)). Можно сделать на immutable stack за O(1).

Зачем для итератора immutable stack?
Обычно это локальная переменная.
Можно приделать ему Сlone() при надобности.
(хотя, от сценариев надо плясать)

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

V>>Я не вижу на графиках объезжания на малых объемах данных, но ты утверждаешь обратное.
S>Надо внимательно смотреть:
S>Image: 2021_08_05_17_40_39_SmallSize.png

И под каким графиком площадь меньше?


V>>Это с большой копипастой.
V>>Я бы для простоты сделал на виртуальных методах или if-ах с последующим разбоксированием.
S>Не понимаю смысл.

Узел типа вложенности 1 должен породить тип узла вложености 2 при разбиении, для сохранения статичности типа и т.д.


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

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

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

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


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

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

Это как альтернатива проверки типа или флага дочернего узла:

internal static unsafe class NodeHelper<T> {
    private static readonly delegate*<BranchNode<T>, int, T> s_branchGetItem = &BranchNode<T>.GetItem;
    private static readonly delegate*<LeafNode<T>, int, T> s_leafGetItem = &LeafNode<T>.GetItem;

    public static delegate*<object, int, T> GetItemFun(bool isLeaf)
        => isLeaf ? (delegate*<object, int, T>)s_leafGetItem : (delegate*<object, int, T>)s_branchGetItem;
}

internal class LeafNode<T> {
    private Bunch<T> _values;

    public static T GetItem(LeafNode<T> @this, int index) => @this._values[index];
}

internal unsafe class BranchNode<T> {
#region do not reorder
    private struct Indicies { private fixed int _data[16];}
    private Indicies _indicies;

    private Bunch<object> _children;
    private readonly delegate*<object, int, T> _childGetItem;
#endregion
        
    internal BranchNode(bool childIsLeaf) => _childGetItem = NodeHelper<T>.GetItemFun(childIsLeaf);

    // agressive-optimization
    // no-locals-init
    public static T GetItem(BranchNode<T> @this, int index) {
        object child;
        (child, index) = @this.FindChild(index);
        return @this._childGetItem(child, index);
    }

    private (object child, int index) FindChild(int index) => (0, 0);
}

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

Здесь в коде тоже хак — типы указателей на ф-ии приводятся к друг другу без проверки, т.е. корректность должна обеспечиваться самим кодом, бо в рантайме тоже проверок нет.
Это дыра в привычной безопасности, поэтому delegate*<> может жить только в unsafe-блоках кода.


V>>При повороте дочерний узел заменяет собой родительский узел.
S>Какой именно из дочерних узлов?

Где происходит сбой разметки красное-черное.
В худшем случае (при упорядоченной вставке) происходит, если склероз не изменяет, одна балансировка на две вставки.


V>>А у тебя при росте вложенности потребуется перестроить всё дерево, насколько я сейчас понял.
S>Нет конечно. Рост вложенности — это split, он очень простой. порождаются ровно три узла, независимо от глубины дерева. Это же B-tree, они все работают одинаково.

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


V>>В мутабельном B+ дереве легко последовательно обойти хранящиеся значения (один из основных кейзов для списка), т.к. все листья соеденены в связанный список.
V>>В иммутабельном виде этой функциональности нет, насколько я понимаю, поэтому обход достаточно дорогой.
S>Обход я ещё не оптимизировал; но там скорее всего тоже всё будет не намного дороже. Прямо сейчас итератор сделан тупо через _list[_position], то есть шаг итерации ~ O(log(N)). Можно сделать на immutable stack за O(1).

Зачем для итератора immutable stack?
Обычно это локальная переменная.
Можно приделать ему Сlone() при надобности.
(хотя, от сценариев надо плясать)