Информация об изменениях

Сообщение Re[68]: MS забило на дотнет. Питону - да, сишарпу - нет? от 17.09.2021 17:41

Изменено 17.09.2021 17:47 vdimas

Старый текст
Новый текст
Разница

Re[68]: MS забило на дотнет. Питону - да, сишарпу - нет?

Здравствуйте, 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() при надобности.
(хотя, от сценариев надо плясать)

Re[68]: MS забило на дотнет. Питону - да, сишарпу - нет?

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);
}