Здравствуйте, vdimas, Вы писали:
V>Снаружи зато вызов уже виртуальный, через интерфейс или базовый абстрактный класс.
Снаружи — ровно один виртуальный вызов.
V>Для виртуального вызова надо сделать три разыменования ссылки — сначала получить ссылку на VMT, затем у той получить указатель на метод, затем косвенно вызывать метод.
Вроде бы два — у нас же заранее известен слот. Я полагал, что там идёт LEA EAX, [VMT+4*slotNo], и сразу после этого CALL EAX.
V>За ту же цену индирекции можно пройти три слоя узлов дерева. ))
Смотря какого дерева.
V>Тем более, что верхний узел дерева с небольшой арностью можно хранить по-значению.
V>В иммутабельном варианте и само такое дерево может быть value-type, т.е. просто оберткой над корнем.
Это всё зависит от того, какой интерфейс мы отдаём клиенту.

V>А у тебя вложенность типов будет зависеть от фактических данных.
V>Бедный джит. ))
Дотнет прекрасно работает с генерик типами в пару десятков уровней вложенности.

V>Ну да, однажды скомпиллированный-заинлайненный по месту вызова this[i] потребует перекомпиляции после вставки.
Нет, тут идея в том, что в корне мы делаем один виртуальный вызов через интерфейс, но он стреляет сразу в моноблочный метод.
То есть для коротких коллекций мы попадаем в LeafNode<T>, у которой this[] работает с той же производительностью, что и для int[].

V>Про спекулятивную оптимизацию тут и заикаться смысла нет, насколько я понял? ))
Нет никакого смысла делать спекулятивную оптимизацию, если нет данных о том, какие реальные типы будут использоваться.
В нашем случае — если мы не знаем, какой размер коллекций будет типовым (и будет ли вообще какой-то размер доминировать).

V>Тогда уж лучше рекурсия/виртуальность.
Рекурсия адски тормозит даже без виртуальности. Вы же заметили, что в ассемблерном выхлопе стоит прямой вызов, безо всякой VMT?
V>Причём, для this[i] можно приделать ручную виртальность.

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

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

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

V>Бороться стоит лишь за эффективность доступа по чтению, ИМХО.
Этот вопрос уже решён. Сейчас хочется добиться того, чтобы вставки и модификации создавали меньше мусора.

V>А в B+ бывают, зависит от реализации.
Бывает, независимо от реализации. Все варианты B-деревьев (B, B+, B*, и прочие) подразумевают наличие неполных узлов.

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

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

V>В этом месте и возникают эксперименты с подбором арности.

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

V>Странная формулировка задачи, ну да ладно.
Нормальная формулировка. Не хуже других. Ну, то есть оригинальная формулировка была "реализовать ImmutableList". Но когда выяснилось, что в платформе такой уже есть, чувство профессиональной гордости потребовало сделать лучше.

V>Ну, то смотря какие "веса" раздать операциям.
Реализация TunnelVision проиграла на всех операциях. Я разве не давал ссылку на полный набор бенчмарков?

V>А вот тут непонятно.
V>Если была создана копия узла-ветки с обновлёнными индексами, родительский узел надо заставить ссылаться на новый экземпляр, т.е. сделать копию родительского узла и т.д. вверх.
А, тогда я неверно прочитал. Да, нужно всегда обновлять родителя, и родителя родителя, и т.п. Но это на практике не слишком дорого.

V>Пока что навскидку кажется, что арность узлов стоит уменьшать при движению к корню.
V>Вернее, увеличивать при росте дерева.
V>Т.е., чем глубже уровень, тем больше стоит делать арность узлов.
Теоретически можно; на практике смысла нет. Маленькая арность у корня означает низкое основание логарифма — увеличиваем глубину дерева на ровном месте.
В принципе, имеет смысл рассматривать разную арность у листьев и у промежуточных узлов. Последние вообще устроены так, что memory layout у них фиксирован и не зависит от T. Поэтому их можно вылизать достаточно хорошо; а вот количество элементов в листьях скорее всего стоит менять в зависимости от sizeof(T).
Но опять таки: это всё семечки по сравнению с call. Если честно, я не понимаю, почему. Родное бинарное дерево в дотнете не стесняясь использует банальный рекурсивный вызов, и до 512 элементов (то есть до глубин в 9) оно ведёт себя вполне приемлемо по производительности.