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


V>Т.е., тебе пока требуется "просто локальность", а в ней разница в 64 байта или 1кб практически отсутствует в разогретом кеше.
Нужен эксперимент.

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


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

V>Та граница должна будет пересечься и у тебя в каком-то месте.
Ну, вот другое расположение данных. Более кучное.

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


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


V>Но в дотнетной реализации именно это?
Повторюсь: есть подозрение, что в дотнетной реализации срабатывает tailcall. Я её не дизассемблировал — может там вообще вызова нет.
Ну, то есть руками-то я и её могу переписать в такой же цикл, который был у меня в декабре прошлого года.


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

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

V>Не только...
V>В мутабельном B+ дереве легко последовательно обойти хранящиеся значения (один из основных кейзов для списка), т.к. все листья соеденены в связанный список.

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

V>Попробуй опять с гомогенными узлами.
V>Там никакая рекурсия не нужна, вирутальность на верхнем уровне тоже, просто сдвигаешься в цикле до листового узла.
Ещё раз: этот код уже есть. Можно посмотреть на версию от 28 декабря 2020.

V>Причём, твой узел заведомо "знает", ссылается ли он на листья или ветки, это один флаг.
V>Затем можно приводить ссылку на дочерний узел через Unsafe.As<T>(Object).
Ну разве что.