Сообщение Re[62]: MS забило на дотнет. Питону - да, сишарпу - нет? от 13.09.2021 22:06
Изменено 13.09.2021 22:08 vdimas
Re[62]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, Sinclair, Вы писали:
V>>Снаружи зато вызов уже виртуальный, через интерфейс или базовый абстрактный класс.
S>Снаружи — ровно один виртуальный вызов.
Три пинг-понга понадобилось... ))
V>>Для виртуального вызова надо сделать три разыменования ссылки — сначала получить ссылку на VMT, затем у той получить указатель на метод, затем косвенно вызывать метод.
S>Вроде бы два — у нас же заранее известен слот.
Два косвенных чтения и один косвенный call.
Для сравнения, прямой call обслуживается механизмами предвыборки очереди инструкций процессора, т.е. фактически бесплатен.
S>Я полагал, что там идёт LEA EAX, [VMT+4*slotNo], и сразу после этого CALL EAX.
Ну вот у тебя уже две косвенные операции.
И предварительно требуется достать VMT из объекта.
Там происходит такое (в дебаге и релизе идентично).
Т.е. даже 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>>
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) оно ведёт себя вполне приемлемо по производительности.
Может, потому что в дотнетной вызывается тот же метод, а у тебя на каждом уровне разный, даже если их тела в железе совпадают (с точностью до адреса псевдорекурсивного вызова).
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) оно ведёт себя вполне приемлемо по производительности.
Может, потому что в дотнетной вызывается тот же метод, а у тебя на каждом уровне разный, даже если их тела в железе совпадают (с точностью до адреса псевдорекурсивного вызова).
Re[62]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, Sinclair, Вы писали:
V>>Снаружи зато вызов уже виртуальный, через интерфейс или базовый абстрактный класс.
S>Снаружи — ровно один виртуальный вызов.
Три пинг-понга понадобилось... ))
V>>Для виртуального вызова надо сделать три разыменования ссылки — сначала получить ссылку на VMT, затем у той получить указатель на метод, затем косвенно вызывать метод.
S>Вроде бы два — у нас же заранее известен слот.
Два косвенных чтения и один косвенный call.
Для сравнения, прямой call обслуживается механизмами предвыборки очереди инструкций процессора, т.е. фактически бесплатен.
S>Я полагал, что там идёт LEA EAX, [VMT+4*slotNo], и сразу после этого CALL EAX.
Ну вот у тебя уже две косвенные операции.
И предварительно требуется достать VMT из объекта.
Там происходит такое (в дебаге и релизе идентично).
Т.е. даже 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>>
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) оно ведёт себя вполне приемлемо по производительности.
Может, потому что в дотнетной вызывается тот же метод, а у тебя на каждом уровне разный, даже если их тела в железе совпадают (с точностью до адреса псевдорекурсивного вызова).
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) оно ведёт себя вполне приемлемо по производительности.
Может, потому что в дотнетной вызывается тот же метод, а у тебя на каждом уровне разный, даже если их тела в железе совпадают (с точностью до адреса псевдорекурсивного вызова).