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

V>>Снаружи зато вызов уже виртуальный, через интерфейс или базовый абстрактный класс.
S>Снаружи — ровно один виртуальный вызов.

Три пинг-понга понадобилось... ))


V>>Для виртуального вызова надо сделать три разыменования ссылки — сначала получить ссылку на VMT, затем у той получить указатель на метод, затем косвенно вызывать метод.
S>Вроде бы два — у нас же заранее известен слот.

Два косвенных чтения и один косвенный call.
Для сравнения, прямой call обслуживается механизмами предвыборки очереди инструкций процессора, т.е. фактически бесплатен.


S>Я полагал, что там идёт LEA EAX, [VMT+4*slotNo], и сразу после этого CALL EAX.

Ну вот у тебя уже две косвенные операции.
И предварительно требуется достать VMT из объекта.

Там происходит такое (в дебаге и релизе идентично).

            b.Foo();
00007FFCCD6A6962  mov         rcx,qword ptr [rbp-88h]  // rcx = b, это this для будущего вызова метода
00007FFCCD6A6969  mov         rax,qword ptr [rbp-88h]  // кошмар! надо было просто mov rax,qword ptr [rcx]
00007FFCCD6A6970  mov         rax,qword ptr [rax]      // rax = b.GetType()???
00007FFCCD6A6973  mov         rax,qword ptr [rax+40h]  // rax = typeinfo.VMT???
00007FFCCD6A6977  call        qword ptr [rax+20h]      // indirect call to [VMT+20h]
            b.Bar();
00007FFCCD6A697A  mov         rcx,qword ptr [rbp-88h]  
00007FFCCD6A6981  mov         rax,qword ptr [rbp-88h]  
00007FFCCD6A6988  mov         rax,qword ptr [rax]  
00007FFCCD6A698B  mov         rax,qword ptr [rax+40h]  
00007FFCCD6A698F  call        qword ptr [rax+28h]     // отличия только тут, другой слот

Т.е. даже 5 косвенных операций, хотя можно было сделать 4 — повторно из стека загружается ссылочная переменная b в rax.
Это гребанный баг! ))

Далее.
Колега Serginio1 как-то сказал рядом в этом же обсуждении, что ссылка на typeinfo находится по отрицательному смещению VMT (это так в плюсах, и я даже поверил насчёт дотнета, бо давно не всматриваюсь в виртуальные вызовы в дотнете, бо где гоняюсь за эффективностью, там их нет).

Но, наоборот, это указатель на VMT обитает в виде поля typeinfo, т.е. требуется два разыменования только чтобы достать адрес VMT.

И если подумать — это правильно, т.к. VMT у многих типов могут совпадать, а typeinfo уникальный.
(Например, совпадают у всех типов-классов без собственных виртуальных методов, в т.ч. у всех боксированных value-type — тогда VMT наследуют от Object)



V>>За ту же цену индирекции можно пройти три слоя узлов дерева. ))
S>Смотря какого дерева.

Простого двоичного.
Количество операций сравнения у тебя идентично в узлах-ветках, насколько я понимаю.
(особенно в оригинальной твоей версии с вручную заинлайненым двоичным поиском, в версии с линейным поиском чуть больше, но там может быть выигрыш за счёт специфики происходящего в проце)

А сразу по индексу ты смещаешься только в узлах-листьях.

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


V>>Тем более, что верхний узел дерева с небольшой арностью можно хранить по-значению.
V>>В иммутабельном варианте и само такое дерево может быть value-type, т.е. просто оберткой над корнем.
S>Это всё зависит от того, какой интерфейс мы отдаём клиенту.

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


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

Это когда однократно скомпилял и всё.
У тебя же динамически эти типы производятся по мере роста дерева.


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

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


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

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


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

Это понятно, потому что тип известен.


V>>Причём, для this[i] можно приделать ручную виртальность.

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

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

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

Почему?
При вызове метода this уже будет в RXC, тут одна косвенность получится.


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

Красно-черный алгоритм.
Преимущество в более дешевых изменениях дерева, т.к. балансировка красно-черных дешевле в мутабельной реализации.
В т.ч. по принципу copy-on-write, как оно есть в файловых системах.


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

Это перпендикулярные задачи.
Но твои "игры" с арностью помогли, согласно графикам.


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

))


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

Что-то я на скорую руку не увидел графики, а можно повторить ссылку?


V>>Пока что навскидку кажется, что арность узлов стоит уменьшать при движению к корню.
V>>Вернее, увеличивать при росте дерева.
V>>Т.е., чем глубже уровень, тем больше стоит делать арность узлов.
S>Теоретически можно; на практике смысла нет. Маленькая арность у корня означает низкое основание логарифма — увеличиваем глубину дерева на ровном месте.

Делаем дерево дешевым в изменениях для относительно небольшого кол-ва узлов.
При росте арности в геометрической прогрессии 2, уже на 4-м уровне арность сравняется с твоей, на следующем уровне общее кол-во узлов уже будет равным, а далее с каждым слоем в геометрической прогрессии будет уменьшаться от твоей реализации.


S>В принципе, имеет смысл рассматривать разную арность у листьев и у промежуточных узлов. Последние вообще устроены так, что memory layout у них фиксирован и не зависит от T.

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


S>Поэтому их можно вылизать достаточно хорошо; а вот количество элементов в листьях скорее всего стоит менять в зависимости от sizeof(T).

И это тоже.
Но и от кол-ва элементов тоже.


S>Но опять таки: это всё семечки по сравнению с call. Если честно, я не понимаю, почему. Родное бинарное дерево в дотнете не стесняясь использует банальный рекурсивный вызов, и до 512 элементов (то есть до глубин в 9) оно ведёт себя вполне приемлемо по производительности.

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