Здравствуйте, Ночной Смотрящий, Вы писали:
I>> I>Именно. И с наследованием ровно так же. НС> Да, так же. И что?
Мы пришли к тому, что все твои утверждения про наследование применимы к интерфейсам. Это говорит, что ты не можешь внятно продемонстрировать свой пример. Как то так.
I>>>>Это нарушение всех принципиов вместе взятых НС>>>Нет. I>>Тут стоит посмотреть Skott Meyers, Herb Sutter, Bertrand Meyer, начало 90х. Чем больше методов — тем сильнее нарушается инкупсуляция.
НС>Нет там такого.
Это смотря как смотреть
I>>И никакого обоснования, как будто это и так ясно. Аргументы будут?
НС>О, заметил наконец. Теперь можно посмотреть на свои утверждения и задать себе тот же вопрос.
То есть, пример показать не можешь, показать ошибку в утверждениях тоже не можешь
I>>Возьми любое другое свойство, например тот самый метод add. НС>Нет, надо взять то, что таки ОО контракты гарантируют. Только смысл сего действа непонятен.
Так ты возьми да покажи, что они гарантируют и что за проблему это создает.
I>>Тебе интерфейсы для чего нужны? НС>А мне они нужны?
Покажи, как ты обеспечиваешь гарантии для полиморфизма теми самыми интерфейсами. Ты же сказал, что интерфейсов для полиморфизма более чем достаточно. Вот покажи, где там чего более чем достаточно.
I>> Всё проще фича extends это плохое решение, которое плохо решает три задачи — subtype, переиспользование и композицию. А нужны раздельные языковые конструкции для каждого аспекта.
НС>И ровно это я с самого начала и написал. Ты с чем споришь то?
Ты утверждаешь что для интерфейсов наследование работает нормально. А я тебе показал, что для интерфейсов тоже не палит.
Ты разницу видишь?
Re[70]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Ты просто неверно меня понял. Я тебе говорил не про то что есть какая то магия, а про то что в ФП от необходимости использовать словари явно уходят в пользу замены их использования на паттерн Memoize. Т.е. то что ты хранишь в словаре в ФП вычисляется каждый раз при обращении, а чтобы не вычислять каждый раз одно и тоже используют memoize.
А, вот теперь всё встало на свои места.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[78]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Здравствуйте, Serginio1, Вы писали:
НС>>>Это какой то бред. SQL сервер это отдельная машина, иначе смысла нет. S>>Отдельная машина это еще бОльшие тормоза.
НС>Разумеется. Важнее то, что никакие сингулярити тебя от этих тормозов не спасут.
Именно спасут. Если бы ты посмотрел заголовок, то смысл в том, что файловая база на интерпретаторе быстрее в 3 раза
компилируемого SQL S>> Вот если всю эту беду делать в пространстве сервера, домене или аля сингулярити скорость резко возрастет.
НС>Ну так попытки засунуть жабу или дотнет вовнутрь сиквела были, чего тебя в них не устраивает?
Ну я не видел примеров ни на EF ни на Linq2DB S>>И может убивца 1С можно сделать
НС>Нельзя. 1С такой популярный не из-за его технологий.
Как раз в технологиях,языке и готовые конфигурации которые легко можно заточить под себя.
В начале там вообще были dbf. Народ быстро еще прикрутил терминальные сессии с цитриксом.
Потом начали прикручивать и SQL но опять же с терминальными сессиями.
Потом 1С сделала 8 ку с сервером приложений.
Здесь то как раз идет разговор о том, как проще взаимодействовать с нативными данными. Да можно делать обертки над записями с использованием MemoryMarshal для доступа к массивам.
Без лишнего копирования и передач между процессами.
Конечно надо смотреть, но хотелось бы посмотреть примеры с доступом аля Linq к данным.
Ну и ограничения Ограничения модели программирования
и солнце б утром не вставало, когда бы не было меня
Re[60]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, vdimas, Вы писали:
V>Причём, ввиду того, что там всё-равно lock-free цикл и в массиве null может считаться как пустая ячайка, не обязательно каждый раз пересоздавать массив на точное кол-во элементов, можно увеличивать его, например, вдвое при добавлении элементов, если пустых ячеек уже нет.
Делегаты не проектировались для случая "у нас будет миллион подписчиков на событие". Полагаю, что их бенчмарки для такого сценария будут разочаровывать.
V>Но в "обычных случаях", например, когда кешируются справочные данные, должные быть доступными из разных потоков, там другие подходы эффективнее кратно.
Ну это и так понятно, что иммутабельность сама по себе не может быть бесплатной (кроме случая immutable stack).
Они дают преимущества в определённых сценариях — и в первую очередь это преимущества удобства, в виде различных гарантий корректности.
У меня нет задачи заменить List<int> на ImmutableTreeList<int>. Есть задача сделать так, чтобы ImmutableList<int> работал быстрее, чем он это делает сейчас.
V>Размером линейки кеша, ты хотел сказать? V>Самые ходовые 64 байта, у продвинутых 128 байт. V>Оба раза всё-равно меньше размера твоего узла.
Там самое главное — это индексы. Их размер как раз 64 байта. V>И в этих делах не только размер играет роль, но и выравнивание.
Выравнивание можно подправить после того, как будут задавлены лишние вызовы. V>Например, часть памяти твоей иммутабельной структуры залезло на линейку кеша, где живёт мутабельная переменная — получи трафик когерентности и тормоза даже для иммутабельных данных. V>Необходимо для классов верхнего уровня, в которых хранятся структуры, расставлять выравнивание через [StructLayout)], дополнительно указывать размеры структур-классов кратными размеру линейки кеша в этом же аттрибуте.
Это всё понятно. Тем не менее, двоичные деревья слишком сильно прыгают по кэшу, по сравнению с деревьями большего размера.
Вообще, я изначально пилил дерево с бранч-фактором 8, потом заменил на 16, да так и оставил. Меня устроило, т.к. двоичное дерево удалось объехать и на нём.
V>Ну, изначально B+ деревья разрабатывались под куда как большие размеры блоков, чем 64 байта.
Исключительно из-за того, какими блоками оперировали конечные устройства. Никакой отдельной магии в числах 8к или 16к нету.
B-деревья прекрасно работают для бранч-фактора, скажем, 7.
V>Тю, там придётся весь механизм тасков переделывать, включая реализацию work stealing и учитывая тот факт, что пул IO-потоков, поток таймеров — это отдельные потоки, не пересекающиеся с пулом потоков для тасков.
А то. Языком-то легко, а как начинаешь погружаться в тему — ойойой.
V>Во сколько раз и какие операции у тебя получились быстрее?
this[]. Где-то в 2-2.5 раза:
На графике видно, как дотнетный код начинает встревать на объёмах выше 256 элементов. А B+-дерево сохраняет логарифмическую асимптотику до 64к (там, афаик, и до миллиона — я не стал бенчмаркать на таких количествах).
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[71]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, vdimas, Вы писали:
V>Таки, если в where используется простейшая лямбда-предикат, то её стоит инлайнить.
Так-то я не против. Я вообще бы хотел, чтобы JIT умел инлайнить известные делегаты. Но пока что все обсуждения подобной функциональности в соответствующих группах заканчиваются на том, что это hell lot of a job.
Была также мысль напилить хелперную библиотеку, которая бы умела делать constant propagation для всего, включая делегаты.
Ну, то есть берём метод типа add, и скармливаем его в Specialize:
При этом этот add2 — это вовсе не вызов того же add с b=2, а по честному проинлайненный код делегата, соответствующий a=>a+2.
Для Expression это, понятное дало, тривиальное упражнение. А интересно, конечно, делать это для готовых делегатов.
И точно также для Where(IEnumerable<int> e, Predicate<int> p) делаем Specialize(Where, a => a%2==0), и получаем на выходе Func<IEnumerable<int>, IEnumerable<int>>, внутри которой уже нет никаких вызовов делегатов, а только итерирование по аргументу и вызовы a%2==0.
А уже потом поверх такой библиотеки можно делать различные прикольные плюшки типа "а давайте оптимизируем нашу цепочку цепочек делегатов".
Но это всё тоже требует больших затрат; в проекте linq2d мне оно не пригодилось, а пока что больше применить мне некуда — поэтому идея лежит на полке.
V>Спасибо. V>И почему до сих пор нет в дотнете, если разница такая впечатляющая?
Я не вдавался. Так-то есть и всякие интересные реализации расширений к самим Expression, которые пока что в дотнет не вошли.
Например, хорошо известная штука — в Expressions до сих пор нет поддержки Tuple Initializer или как он там называется.
То есть нельзя сделать
Expression<Func<int, (int, int)>> t = a=>(a, a);
Можно только
Expression<Func<int, (int, int)>> t = a=>Tuple.Create(a, a);
Хотя казалось бы — чего такого-то?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[60]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, Sinclair, Вы писали:
S>Всё правильно. Внутри ManualBox<T>.Foo лежит вполне себе невиртуальный вызов T.Foo().
Снаружи зато вызов уже виртуальный, через интерфейс или базовый абстрактный класс.
Именно это имелось ввиду.
Для виртуального вызова надо сделать три разыменования ссылки — сначала получить ссылку на VMT, затем у той получить указатель на метод, затем косвенно вызывать метод.
За ту же цену индирекции можно пройти три слоя узлов дерева. ))
Тем более, что верхний узел дерева с небольшой арностью можно хранить по-значению.
В иммутабельном варианте и само такое дерево может быть value-type, т.е. просто оберткой над корнем.
S>А при дальнейшем цепочка строится из наших ManualBox<T> примерно так:
Это я уже понял несколько сообщений назад.
Сравнить с моим примером логгирования, где запись на логгирование статическая, считай.
А у тебя вложенность типов будет зависеть от фактических данных.
Бедный джит. ))
S>В итоге, когда JIT строит код SM<S1>.Foo(), у него тоже нет ни одного виртуального вызова. И вообще, весь ManualBox нам нужен только для того, чтобы заставить SM<S1> хранить массив ссылок на S1, а не массив копий S1. И при этом продолжать обращаться к Foo детишек невиртуально.
Ну да, однажды скомпиллированный-заинлайненный по месту вызова this[i] потребует перекомпиляции после вставки.
Про спекулятивную оптимизацию тут и заикаться смысла нет, насколько я понял? ))
Тогда уж лучше рекурсия/виртуальность.
Причём, для this[i] можно приделать ручную виртальность.
А вставку-удаление протянуть виртуально для простоты, т.к. эффективность изменения иммутабельных структур и так тяжелая, там вирутальность особо не повлияет, тем более что для B+ деревьев кол-во слоёв выходит небольшим.
Бороться стоит лишь за эффективность доступа по чтению, ИМХО.
V>>В учебнике при балансировке B+ дерева можно копировать значения в родительские сегменты, если в тех есть незаполненные ячейки. S>Не совсем так. Это вы про B-дерево пишете. В B+ все значения лежат только в листьях, поэтому в родителей ничего не копируется никогда.
В бинарных деревья априори не бывает незаполненных ячеек.
А в B+ бывают, зависит от реализации.
Например, когда балансировка допускает один уровень разницы высоты дерева по разным путям, как в красно-черных деревьях.
И еще в мутабельных структурах можно реализовать эффективное удаление за счёт образования "дырок" в хранилищах, в этих реализациях отдельно вводится операция компактификации.
V>>Сам алгоритм мутабельный. S>Мутабельное дерево очень легко превратить в иммутабельное путём порождения копий узлов вместо модификаций.
Ну как легко...
В имутабельном дереве происходит изменение одной ссылки в родительском узле при повороте поддерева, а в имутабельном создаются копии родительских узлов до корня.
В этом месте и возникают эксперименты с подбором арности.
И эти эксперименты, таки, лучше провести.
Например, через сетку вложенных
V>>Но в иммутабельных структурах принято полностью иниализировать объекты в конструкторе, а тут надо будет разделить создание узла, наполнение и последующую иммутабельную эксплуатацию. S>Это всё тривиально реализуется в конструкторе, который принимает коллекцию, при помощи флагов заморозки на уровне узлов.
Вот, "флаги заморозки".
V>>И еще тебе иммутабельность нужна не сама по себе, а как ср-во межпоточной реализации контейнеров. S>Ну не обязательно. У меня вообще не стояло никакой прикладной задачи, для которой нужна была бы иммутабельность. Стояла значительно более приземлённая задача — обыграть System.Collections.Immutable.ImmutableList.
Странная формулировка задачи, ну да ладно.
S>Парни из TunnelVision пришли к той же идее, что и я, но их реализация недостаточно оптимизирована. Abstraction Penalty у них сожрало весь выигрыш от cache friendliness и уменьшения глубины дерева.
Ну, то смотря какие "веса" раздать операциям.
Повторюсь, если стоимость обновления и так большая, то за стоимостью обновления можно и не гнаться, а сосредоточиться на лучшем лейауте памяти, на эффективности чтения.
V>>Например, взять сложные структуры, разбитые на сегменты (как B+ деревья или очереди с приоритетами, или простые двусторонние очереди с возможностями вставки-удалениях элементов из середины) — такие алгоритмы могут использовать copy-on-write "точечно", на уровне отдельных сегментов. S>Так и делается.
С тем замечанием, что дерево перестраивается до корня.
V>>Например, копирование узлов до вершины при балансировке иммутабельного дерева не нужно, если не происходит перемещение значений м/у уровнями или разбиениях и обновление индекса вверх. S>Так и делается.
А вот тут непонятно.
Если была создана копия узла-ветки с обновлёнными индексами, родительский узел надо заставить ссылаться на новый экземпляр, т.е. сделать копию родительского узла и т.д. вверх.
Пока что навскидку кажется, что арность узлов стоит уменьшать при движению к корню.
Вернее, увеличивать при росте дерева.
Т.е., чем глубже уровень, тем больше стоит делать арность узлов.
V>>На каком-то уровне изменений для B+ дерева достаточно будет через lock-free цикл обновить ссылку на дочерний узел, например, при вставке в конец. V>>Или при вставке в середину можно создавать копии только части узлов при провижении наверх. S>Так и делается — клонируются ровно те узлы, которые входят в путь от изменяемой ячейки к корню.
Ага, ты ответил — путь к корню в любом случае клонируется.
S>Всего log(N) копий, что значительно дешевле, чем вставлять в середину copy-on-write массива.
Если массив сегментирован — не скажи.
Например, С++ дек исторически был выполнен как сегментированное хранилище.
As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one.
И приоритетные очереди отродясь на B+-деревьях строились.
(наконец попало в стандарт из Буста)
В условиях GC безблокировочные многопоточные реализации этих структур отличаются от однопоточных доп. циклом обновления сегментов на основе cas.
V>>Но этот вариант имеет плохой лейаут в памяти, если не использовать кастомный пул-аллокатор. V>>Поэтому, дотнетный вариант реализован иначе. S>Возможно, поэтому. Может, из-за других причин. Я свечку не держал, точно сказать не могу.
Ну ты там рассуждал о "cache friendliness" — это была основная причина, т.е. попытка уместить данные в один массив.
Давно не смотрел, сейчас вижу в исходниках, что они сделали отдельный массив индексов (размер которого только и должен быть простым числом), что позволяет складывать конфликтующие значения в общий массив данных.
Т.е. ввели доп. индирекцию в размен на более компактное хранение.
Тоже вариант...
Re[62]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, Sinclair, Вы писали:
НС>>Ты просто неверно меня понял. Я тебе говорил не про то что есть какая то магия, а про то что в ФП от необходимости использовать словари явно уходят в пользу замены их использования на паттерн Memoize. Т.е. то что ты хранишь в словаре в ФП вычисляется каждый раз при обращении, а чтобы не вычислять каждый раз одно и тоже используют memoize. S>А, вот теперь всё встало на свои места.
=============
Кстате, интересная идея.
Например, при обновлении той самописной сегментированной хеш-таблицы не обновлять сразу сегмент, а создавать некие lazy-данные для будущего обновления при первом чтении сегмента...
Re[61]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, 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>Бороться стоит лишь за эффективность доступа по чтению, ИМХО.
Этот вопрос уже решён. Сейчас хочется добиться того, чтобы вставки и модификации создавали меньше мусора.
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) оно ведёт себя вполне приемлемо по производительности.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[61]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Ты пока без тасков, просто лучший вариант ConcurrentQueue попробуй сделать.
Речь о тасках + IO.
Всю систему можно расписать на очередях другой дисциплины — many producers, single consumer.
Очередь такой дисциплины проще и эффективнее в разы на стороне чтения, особенно при нагрузке, т.к. практически исключаются interlocked-операции.
В этой системе есть очереди задач к конкретным потокам и общая очередь задач.
И есть пул элементов, привязанный к конкретному потоку.
Элементы возвращаются в пул по очереди той же дисциплины, т.е. из разных потоков.
У нас этот вариант уже расписан, там примерно в 5-6 раз больше throughput задач, и это на тестах, где массив тасков создан предварительно.
Если же создавать таски по месту — там в 20-30 раз разница, а у нас пул.
В связке с IO тоже труба, сейчас в дотнете по готовности IO таск-продолжение отправляется для исполнения в "общий" пул тасков — это самый тяжелый сценарий в том самом месте, где требуется самая эффективность.
Для сравнения, запустить task из worker-потока относительно дешево, т.к. task по-умолчанию закидывается в очередь тому же потоку.
(особенно эффективно, если экземпляр task был предварительно создан ранее)
У нас код вызывает колбэк прямо из потока IO (там всё-равно пул потоков), всё по классике.
Задержки IO примерно нулевые.
Исходники распространяются с Visual Studio, т.е. можно посмотреть.
Правда, PPL вышла примерно на 5 лет позже, чем мы уже расписали подобную систему в своих продуктах.
Но меня где-то образовало, что реализация их lock-free очереди совпадает с моей (с точностью до идентификаторов, ес-но).
Это был самопридуманный механизм, я его исследовал вдоль и поперек на ABBA-проблему и всё-равно, где-то сомнения таились, бо там не всё так просто — возвращённая в кучу память может в конкурентных поток опять быть выделена, получить тот же адрес, т.е. сравнения на CAS недостаточно, требуется вводить некие куки для защиты, но любые куки не защищают, а лишь уменьшают вероятность возникновенния ABBA в разы или даже на порядки.
Лишь уменьшают, да...
Я же поставил себе целью разработать алгоритм, который исключает ABBA на принципиальном уровне, и у меня получилось когда-то.
Причём, решение вышло забавным — после всех исследований пришёл к выводу, что полностью исключить ABBA невозможно без нарушения Lock-free гарантий.
Поэтому, стал пытаться разрабатывать алгоритм, который сохраняет целостность данных даже в случае возникновения ABBA.
Алгоритм вышел простой и офигенно эффективный, даже interlocked-операции стали не нужны на стороне чтения в 99% случаев.
И вот, после выхода PPL я увидел в их исходниках такой же алгоритм и вздохнул, наконец, с облегчением. ))
Просто хороший совет — берите.
В дотнет я уже давно портировал плюсовый вариант — летает как ковёр-самолёт.
Re[61]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, Sinclair, Вы писали:
V>>Тю, там придётся весь механизм тасков переделывать, включая реализацию work stealing и учитывая тот факт, что пул IO-потоков, поток таймеров — это отдельные потоки, не пересекающиеся с пулом потоков для тасков. S>А то. Языком-то легко, а как начинаешь погружаться в тему — ойойой.
S>На графике видно, как дотнетный код начинает встревать на объёмах выше 256 элементов.
Но хорош еще на 128 элементах, как я примерно и предполагал для относительно небольшого размера данных.
S>А B+-дерево сохраняет логарифмическую асимптотику до 64к (там, афаик, и до миллиона — я не стал бенчмаркать на таких количествах).
Для дотнета вообще странный график — скачок на тех самых примерно 256, потом опять линейное нарастание в логарифмической шкале.
O(log(N)) не соблюдается?
А стоимость вставки-удаления в/из середины графики есть?
Re[72]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, Sinclair, Вы писали:
S>При этом этот add2 — это вовсе не вызов того же add с b=2, а по честному проинлайненный код делегата, соответствующий a=>a+2. S>Для Expression это, понятное дало, тривиальное упражнение. А интересно, конечно, делать это для готовых делегатов.
Восстанавливать из тела делегата Expression, как это делает Reflector и другие подобные тулзы. ))
S>А уже потом поверх такой библиотеки можно делать различные прикольные плюшки типа "а давайте оптимизируем нашу цепочку цепочек делегатов".
Ес-но.
S>Но это всё тоже требует больших затрат
Ну вот, задача сформулирована — восстанавливать Expression из CIL.
S>Например, хорошо известная штука — в Expressions до сих пор нет поддержки Tuple Initializer или как он там называется. S>То есть нельзя сделать S>
S>Expression<Func<int, (int, int)>> t = a=>(a, a);
S>
S>Можно только S>
S>Expression<Func<int, (int, int)>> t = a=>Tuple.Create(a, a);
S>
S>Хотя казалось бы — чего такого-то?
У меня вот так ругается:
Expression<Func<int, (int, int)>> t = a => Tuple.Create(a, a);
Вот так нет:
Expression<Func<int, Tuple<int, int>>> t2 = a => Tuple.Create(a, a);
А как вообще сюда напишешь расширение, если Expression порождает сам компилятор?
Я еще понимаю написать расширения к уже готовым экземплярам Expression...
Ниже вообще для меня новости.
Вот так ОК:
Func<int, int> f = a => {
return a;
};
Вот так нельзя:
Expression<Func<int, int>> t3 = a => {
return a;
};
Т.е. блоки для Expression нельзя.
Можно так:
Expression<Func<int, int>> t4 = a => a;
=================
Кароч, там еще пилить и пилить...
Здравствуйте, 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>>
Почему?
При вызове метода 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) оно ведёт себя вполне приемлемо по производительности.
Может, потому что в дотнетной вызывается тот же метод, а у тебя на каждом уровне разный, даже если их тела в железе совпадают (с точностью до адреса псевдорекурсивного вызова).
Здравствуйте, vdimas, Вы писали: V>А стоимость вставки-удаления в/из середины графики есть?
Все графики — https://github.com/evilguest/atropos/tree/main/Atropos.Benchmarks
Но там надо смотреть на прошлогоднюю версию, до того, как я попробовал перейти на цепочку генериков.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[73]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, vdimas, Вы писали: V>Вот так нет: V>
V>Expression<Func<int, Tuple<int, int>>> t2 = a => Tuple.Create(a, a);
V>
Да это непринципиально. Принципиально, что нельзя написать a=>(a, a).
Это сильно портит, к примеру, синтаксис возврата нескольких массивов в linq2d. V>А как вообще сюда напишешь расширение, если Expression порождает сам компилятор?
Вот так: https://github.com/bartdesmet/ExpressionFutures/tree/master/CSharpExpressions
То есть сами Expression есть, а вот компилятор их порождать не умеет. V>Т.е. блоки для Expression нельзя.
Да, это хорошо известный факт. Мы это обсуждали в прошлый раз в ветке про linq2d.
С точки зрения применения Expression Trees для разнообразной работы вроде "Давайте пользователь соберёт абстрактный pipeline обработки каких-то данных, а я из него сделаю монолитный эффективный метод без лишних аллокаций" это плохо.
С точки зрения "я хочу писать Queryable Provider" это хорошо. Потому, что мне не нужно писать код для обработки случаев вроде
from p in Person where {var s = new StringBuilder(); foreach(var ch in p.Name} if (p.IsLetterOrDigit) s.Append(ch); return s.ToString()=="John";} select p
V>Кароч, там еще пилить и пилить...
Коротко, там есть два основных класса проблем:
1. Не все языковые конструкции имеют аналог в виде Expression. Решается, к примеру, кодом Барта де Смета.
2. Не все типы Expression (даже из стандартной библиотеки) можно породить компилятором из лямбда-синтаксиса. Вот это решается только коммитом в компилятор шарпа.
Актуальность каждой из проблем зависит от решаемой задачи.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[63]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, vdimas, Вы писали:
V>Но, наоборот, это указатель на VMT обитает в виде поля typeinfo, т.е. требуется два разыменования только чтобы достать адрес VMT.
Конечно. Там же ещё может быть и доступ через интерфейс — тогда надо сначала пойти в таблицу интерфейсов, чтобы узнать адрес нужной VMT.
V>Простого двоичного.
Смотря как организовано это простое двоичное дерево. Если в нём известны точные типы, то да.
А если там опять виртуальный вызов — то всё грустно. V>Количество операций сравнения у тебя идентично в узлах-ветках, насколько я понимаю. V>(особенно в оригинальной твоей версии с вручную заинлайненым двоичным поиском, в версии с линейным поиском чуть больше, но там может быть выигрыш за счёт специфики происходящего в проце)
В версии с двоичным поиском мы выигрываем за счёт гарантий локальности кэша. То есть весь поиск с четырьмя ветвлениями происходит без какого-либо обмена с памятью; для случайно организованного двоичного дерева это не так.
V>Это еще один пункт к той моей идее, что арность узлов может расти (например, геометрически) при росте дерева вглубину, т.е. при большом кол-ве данных арность узлов-листьев будет расти. V>Это даст что-то O(log(log(N))
Нет, это не даст O(log(log(N)).
V>Например, арность корня может быть небольшой в той моей идее. V>Допустим даже 2. V>И всегда представлять из себя узел-ветку.
Это как раз будет убивать производительность на маленьких коллекциях.
S>>Дотнет прекрасно работает с генерик типами в пару десятков уровней вложенности.
V>Это когда однократно скомпилял и всё. V>У тебя же динамически эти типы производятся по мере роста дерева.
Это тоже происходит однократно. То есть как только мы хотя бы раз в приложении достигли глубины дерева 4, у нас есть готовый для этого код. Все последующие деревья глубиной до 4х обходятся без компиляции.
V>Вот тот "моноблочный" будет разный для разных глубин, если тебе удастся всё заинлайнить.
Совершенно верно. Это именно то, чего я хочу добиться.
V>Только не "мы", а джит будет иметь дело с разными типами при изменении данных в дереве.
А то.
V>Это понятно, потому что тип известен.
Да. И это не помогает — см. график.
V>>>Хранить индекс в узле-ветке можно так, грубо: V>>>
S>>Вот не запуская бенчмарки вижу — не взлетит.
V>Почему?
Потому что не взлетает даже когда у нас "рекурсивный" вызов делается напрямую, по call CONST. А вы предлагаете добавить косвенный вызов — который не будет предсказываться процессором.
Плюс к этомк добавляем мелочи типа разрушения локальности индексов. Cell занимает 20 байт на x64, и наши index разбросаны в 320 байтах (если branchfactor == 16).
V>Красно-черный алгоритм.
Он же только для бинарных деревьев, разве нет?
V>Но твои "игры" с арностью помогли, согласно графикам.
Нет. Хорошие графики получены на гомогенных деревьях. Там код this[] не выполнял вообще никаких вызовов: https://github.com/evilguest/atropos/blob/c5d59b008e6da8dc202e816f5c9d3863c78e8b44/Atropos/ListNode.cs#L118-L126
V>Что-то я на скорую руку не увидел графики, а можно повторить ссылку? https://github.com/evilguest/atropos/blob/main/Atropos.Benchmarks/README.md
V>Делаем дерево дешевым в изменениях для относительно небольшого кол-ва узлов. V>При росте арности в геометрической прогрессии 2, уже на 4-м уровне арность сравняется с твоей, на следующем уровне общее кол-во узлов уже будет равным, а далее с каждым слоем в геометрической прогрессии будет уменьшаться от твоей реализации.
Как по мне, так это сочетание недостатков обоих подходов: на "дне" у нас "длинные" листья, у которых дороги любые модификации. Плюс у нас растёт длина пути к корню, т.к. арность веток уменьшена.
Но я могу неверно считать в уме — можно либо сесть и внимательно расписать O-оценки, либо закодировать и бенчмаркнуть.
V>Отож. V>И тогда переход вглубь к ветке или листу можно сделать через проверку типа, которая в дотнете дешевая.
Вот надо попробовать.
V>Может, потому что в дотнетной вызывается тот же метод, а у тебя на каждом уровне разный, даже если их тела в железе совпадают (с точностью до адреса псевдорекурсивного вызова).
Возможно, там срабатывает tailcall.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[63]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, vdimas, Вы писали:
V>Колега Serginio1 как-то сказал рядом в этом же обсуждении, что ссылка на typeinfo находится по отрицательному смещению VMT (это так в плюсах, и я даже поверил насчёт дотнета, бо давно не всматриваюсь в виртуальные вызовы в дотнете, бо где гоняюсь за эффективностью, там их нет).
Ага, значит TypeHandle может быть как указателем на MethodTable, так и указателем на TypeDesc, в зависимости от типа объекта. Для массивов он указывает на TypeDesc. Тип object[][] — это массив, элементами которого являются object[], для которых TypeHandle=TypeDesc. Эта информация объясняет наш пример, но всё ещё остаются некоторые вопросы. Например: а как же отличить, на что именно указывает TypeHandle? Поможет нам в этом дальнейшее изучение исходников CLI:
Всё зависит от второго бита в адресе: нулевое значение определяет MethodTable, а единичное — TypeDesc. Если мы работаем с шестнадцатеричными адресами, то можно легко определить вид TypeHandle по последней цифре:
MethodTable: 0, 1, 4, 5, 8, 9, C, D
TypeDesc : 2, 3, 6, 7, A, B, E, F
А теперь взглянем ещё раз на дамп памяти нашего примера. Можно видеть, что для System.Object[] в дампе присутствуют указатели как на его TypeDesc, так и на MethodTable. Не смотря на то, что под TypeHandle в данном случае подразумевается TypeDesc, заголовочный указатель для a[0] всё-таки указывает на MethodTable. Поэтому некорректно говорить о том, что в заголовке каждого объекта хранится TypeHandle: там хранится указатель на MethodTable, а это далеко не всегда одно и то же.
Пример 4
Последний пример проиллюстрирует недавно полученное правило про последнюю цифру адреса. Мы можем получить TypeHandle прямо из управляемого кода, а по этому значению мы можем определить, что именно под ним подразумевается:
Int32 : 65C4C480 => MethodTable
Object : 65C4B060 => MethodTable
Stream : 65C4D954 => MethodTable
Int32[] : 65854C8A => TypeDesc
Int32[][] : 658F6BD6 => TypeDesc
Object[] : 65854D7A => TypeDesc
Выводы
В ходе нашего маленького исследования были получены следующие выводы:
TypeHandle является указателем либо на MethodTable, либо на TypeDesc (зависит от типа объекта)
В заголовке каждого объекта для идентификации его типа всегда хранится указатель на MethodTable (это не всегда TypeHandle)
Для массивов, чьи элементы должны представлять ссылочный тип, хранится дополнительное поле, которое представляет собой TypeHandle для типа элементов.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Serginio1, Вы писали:
S> Именно спасут. Если бы ты посмотрел заголовок, то смысл в том, что файловая база на интерпретаторе быстрее в 3 раза S>компилируемого SQL
Что ты (неверно) безосновательно интепретировал как затраты на маршаллинг.
НС>>Нельзя. 1С такой популярный не из-за его технологий. S>Как раз в технологиях,языке и готовые конфигурации которые легко можно заточить под себя.
Это есть у нескольких продуктов на рынке.
S> Здесь то как раз идет разговор о том, как проще взаимодействовать с нативными данными.
Тебе уже сказали, что внутренние структуры сиквела тебе все равно никто не отдаст, так что маршалинг из внутренних типов в публичные все равно будет.
S> Да можно делать обертки над записями с использованием MemoryMarshal для доступа к массивам. S>Без лишнего копирования и передач между процессами.
Сперва нужно убедиться, что проблема именно в копировании между процессами. Кроме того, локально сиквел умеет через shared mem общаться, да и namep pipes локально через него же работают.
... << RSDN@Home 1.3.17 alpha 5 rev. 62>>
Re[74]: MS забило на дотнет. Питону - да, сишарпу - нет?
Здравствуйте, Ikemefula, Вы писали:
I>Мы пришли к тому, что все твои утверждения про наследование применимы к интерфейсам.
Нет.
НС>>Нет там такого. I>Это смотря как смотреть
О да, умеючи между строк столько всего можно прочесть.
I>>>Возьми любое другое свойство, например тот самый метод add. НС>>Нет, надо взять то, что таки ОО контракты гарантируют. Только смысл сего действа непонятен. I>Так ты возьми да покажи
И опять полетели чайники.
НС>>И ровно это я с самого начала и написал. Ты с чем споришь то? I>Ты утверждаешь что для интерфейсов наследование работает нормально.
Ссылку на подобное утверждение мое не затруднит?
... << RSDN@Home 1.3.17 alpha 5 rev. 62>>
Re[63]: MS забило на дотнет. Питону - да, сишарпу - нет?