Здравствуйте, Sinclair, Вы писали:
V>>Простого двоичного.
S>Смотря как организовано это простое двоичное дерево. Если в нём известны точные типы, то да.
S>А если там опять виртуальный вызов — то всё грустно.
В двоичном дереве все узлы одинаковые, т.е. виртуальность не нужна.
S>В версии с двоичным поиском мы выигрываем за счёт гарантий локальности кэша. То есть весь поиск с четырьмя ветвлениями происходит без какого-либо обмена с памятью; для случайно организованного двоичного дерева это не так.
Ну вот как раз джависты показывали, что после уплотнения GC узлы подобных объектов располагаются в памяти рядом, т.к. доступны по ссылкам только из родительских узлов, т.е. по мере естественного обхода ссылок выстроились в правильный порядок в памяти.
V>>Это еще один пункт к той моей идее, что арность узлов может расти (например, геометрически) при росте дерева вглубину, т.е. при большом кол-ве данных арность узлов-листьев будет расти.
V>>Это даст что-то O(log(log(N))
S>Нет, это не даст O(log(log(N)).
Да, наврал, независимо от арности узлов-веток по ним сложность сохраняется, выигрыш только в узлах-листьях.
V>>Например, арность корня может быть небольшой в той моей идее.
V>>Допустим даже 2.
V>>И всегда представлять из себя узел-ветку.
S>Это как раз будет убивать производительность на маленьких коллекциях.
Твои графики имеющейся дотнетной реализации показывают, что не будет.
V>>Вот тот "моноблочный" будет разный для разных глубин, если тебе удастся всё заинлайнить.
S>Совершенно верно. Это именно то, чего я хочу добиться.
Попробуй ввести разные типы (одинаковые внутри) сугубо для эксперимента.
Т.е. тип Node0 порождает Node1, далее Node2 и т.д., чтобы не было псевдорекурсии.
Т.е. рост дерева будет дороже, но можно будет замерить доступ по чтению (если успешно заинлайнится), т.е. чтобы понять — стоит ли вообще копать в эту сторону.
V>>Это понятно, потому что тип известен.
S>Да. И это не помогает — см. график.
Так непонятен график.
Он должен быть линейным в логарифмической шкале для имеющейся реализации.
Что такого может произойти на 256 элементах, что до него рост линейный, потом скачок, потом опять линейный рост?
Может, стоит внимательней взглянуть на происходящее в имеющемся коде?
V>>>>Хранить индекс в узле-ветке можно так, грубо:
V>>>>V>>>>struct Cell {
V>>>> int _index;
V>>>> NodeBase _child;
V>>>> delegate * <NodeBase, ref T> _getItem;
V>>>>}
V>>>>
S>>>Вот не запуская бенчмарки вижу — не взлетит.
V>>Почему?
S>Потому что не взлетает даже когда у нас "рекурсивный" вызов делается напрямую, по call CONST.
Ну ты же обогнал имеющуюся реализацию?
S>А вы предлагаете добавить косвенный вызов — который не будет предсказываться процессором.
Один косвенный вызов, в отличие от 5-ти для случая виртуального.
Косвенные вызовы тоже умеют обрабатываться предвыборкой до какой-то степени.
S>Плюс к этомк добавляем мелочи типа разрушения локальности индексов. Cell занимает 20 байт на x64, и наши index разбросаны в 320 байтах (если branchfactor == 16).
Ну, в твоей реализации индексы вынесены в отдельный bunch, что можно повторить и в этом случае.
Двоичное ветвление или линейный поиск происходит на индексах, которые в памяти рядом, а доступ к Cell (убрать оттуда поле index) происходит просто по смещению.
И там лишние 8 байт на Cell особой роли играть не будут.
V>>Красно-черный алгоритм.
S>Он же только для бинарных деревьев, разве нет?
Алгоритм можно расширить на n-арное дерево.
Считай, что твой 16-арный узел — это 8 по 2, но не принципиально, пусть там было бы не 16, а 17.
Алгоритм выявляет место, где требуется произвести поворот дерева.
V>>Но твои "игры" с арностью помогли, согласно графикам.
S>Нет. Хорошие графики получены на гомогенных деревьях. Там код this[] не выполнял вообще никаких вызовов:
S>https://github.com/evilguest/atropos/blob/c5d59b008e6da8dc202e816f5c9d3863c78e8b44/Atropos/ListNode.cs#L118-L126
Речь про арность.
V>>Что-то я на скорую руку не увидел графики, а можно повторить ссылку?
S>https://github.com/evilguest/atropos/blob/main/Atropos.Benchmarks/README.md
Запутал.
Тут показывает, что у тебя доступ по this[index] хуже:
https://github.com/evilguest/atropos/blob/main/Atropos.Benchmarks/Atropos.Benchmarks.List.IndexInt.png
И в других сценариях тоже.
Ранее ты показывал график, где твой код эффективней.
