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

V>Но, наоборот, это указатель на VMT обитает в виде поля typeinfo, т.е. требуется два разыменования только чтобы достать адрес VMT.
Конечно. Там же ещё может быть и доступ через интерфейс — тогда надо сначала пойти в таблицу интерфейсов, чтобы узнать адрес нужной VMT.

V>Простого двоичного.
Смотря как организовано это простое двоичное дерево. Если в нём известны точные типы, то да.
А если там опять виртуальный вызов — то всё грустно.
V>Количество операций сравнения у тебя идентично в узлах-ветках, насколько я понимаю.
V>(особенно в оригинальной твоей версии с вручную заинлайненым двоичным поиском, в версии с линейным поиском чуть больше, но там может быть выигрыш за счёт специфики происходящего в проце)
В версии с двоичным поиском мы выигрываем за счёт гарантий локальности кэша. То есть весь поиск с четырьмя ветвлениями происходит без какого-либо обмена с памятью; для случайно организованного двоичного дерева это не так.

V>Это еще один пункт к той моей идее, что арность узлов может расти (например, геометрически) при росте дерева вглубину, т.е. при большом кол-ве данных арность узлов-листьев будет расти.
V>Это даст что-то O(log(log(N))
Нет, это не даст O(log(log(N)).

V>Например, арность корня может быть небольшой в той моей идее.
V>Допустим даже 2.
V>И всегда представлять из себя узел-ветку.
Это как раз будет убивать производительность на маленьких коллекциях.

S>>Дотнет прекрасно работает с генерик типами в пару десятков уровней вложенности.

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

V>Вот тот "моноблочный" будет разный для разных глубин, если тебе удастся всё заинлайнить.
Совершенно верно. Это именно то, чего я хочу добиться.

V>Только не "мы", а джит будет иметь дело с разными типами при изменении данных в дереве.
А то.

V>Это понятно, потому что тип известен.
Да. И это не помогает — см. график.

V>>>Хранить индекс в узле-ветке можно так, грубо:
V>>>

V>>>struct Cell {
V>>>   int _index;
V>>>   NodeBase _child;
V>>>   delegate * <NodeBase, ref T> _getItem;
V>>>}
V>>>

S>>Вот не запуская бенчмарки вижу — не взлетит.

V>Почему?
Потому что не взлетает даже когда у нас "рекурсивный" вызов делается напрямую, по call CONST. А вы предлагаете добавить косвенный вызов — который не будет предсказываться процессором.
Плюс к этомк добавляем мелочи типа разрушения локальности индексов. Cell занимает 20 байт на x64, и наши index разбросаны в 320 байтах (если branchfactor == 16).

V>Красно-черный алгоритм.
Он же только для бинарных деревьев, разве нет?

V>Но твои "игры" с арностью помогли, согласно графикам.
Нет. Хорошие графики получены на гомогенных деревьях. Там код this[] не выполнял вообще никаких вызовов:
https://github.com/evilguest/atropos/blob/c5d59b008e6da8dc202e816f5c9d3863c78e8b44/Atropos/ListNode.cs#L118-L126

V>Что-то я на скорую руку не увидел графики, а можно повторить ссылку?
https://github.com/evilguest/atropos/blob/main/Atropos.Benchmarks/README.md

V>Делаем дерево дешевым в изменениях для относительно небольшого кол-ва узлов.
V>При росте арности в геометрической прогрессии 2, уже на 4-м уровне арность сравняется с твоей, на следующем уровне общее кол-во узлов уже будет равным, а далее с каждым слоем в геометрической прогрессии будет уменьшаться от твоей реализации.
Как по мне, так это сочетание недостатков обоих подходов: на "дне" у нас "длинные" листья, у которых дороги любые модификации. Плюс у нас растёт длина пути к корню, т.к. арность веток уменьшена.
Но я могу неверно считать в уме — можно либо сесть и внимательно расписать O-оценки, либо закодировать и бенчмаркнуть.

V>Отож.
V>И тогда переход вглубь к ветке или листу можно сделать через проверку типа, которая в дотнете дешевая.
Вот надо попробовать.

V>Может, потому что в дотнетной вызывается тот же метод, а у тебя на каждом уровне разный, даже если их тела в железе совпадают (с точностью до адреса псевдорекурсивного вызова).
Возможно, там срабатывает tailcall.