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

V>В двоичном дереве все узлы одинаковые, т.е. виртуальность не нужна.
Да. И, похоже, даже вызовы не нужны.

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

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

V>Попробуй ввести разные типы (одинаковые внутри) сугубо для эксперимента.
Это и была идея номер 2 в моём ответе.

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

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

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

V>Ну ты же обогнал имеющуюся реализацию?
Я обогнал на коде без вызовов.

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

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


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

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

V>Запутал.
V>Тут показывает, что у тебя доступ по this[index] хуже:
V>https://github.com/evilguest/atropos/blob/main/Atropos.Benchmarks/Atropos.Benchmarks.List.IndexInt.png
V>И в других сценариях тоже.
V>Ранее ты показывал график, где твой код эффективней.
Я же говорю — был прошлогодний код, который работал на гомогенном дереве. Но в нём были проблемы с выделением лишней памяти в листьях. График, который я показал — оттуда.
Сейчас я пытаюсь реализовать код, в котором нет лишних данных. Технически, это получилось, но вот лишние вызовы портят всю малину.