Под катом предлагается расшифровка доклада Стефана Карпински, одного из ключевых разработчиков языка Julia. В докладе он рассуждает о том, к каким неожиданным результатам привела удобная и эффективная множественная диспетчеризация, взятая за основную парадигму Julia.
От переводчика: название доклада отсылает к статье Юджина Вигнера "Непостижимая эффективность математики в естественных науках".
Множественная диспетчеризация — ключевая парадигма языка Julia, и за время его существования мы, разработчики языка, заметили нечто ожидаемое, но в то же время озадачивающее. По крайней мере, мы не ожидали этого в той степени, в которой увидели. Это нечто — ошеломительный уровень переиспользования кода в экосистеме Julia, который гораздо выше чем в любом другом известном мне языке.
Мы постоянно видим, что одни люди пишут обобщённый код, кто-то другой определяет новый тип данных, эти люди между собой не знакомы, а затем кто-то применяет этот код к этому необычному типу данных… И всё просто работает. И так происходит на удивление часто.
Я всегда думал, что такого поведения следует ожидать от объектно-ориентированного программирования, но я пользовался многими объектно-ориентированными языками, и оказывается, что в них обычно всё так просто не работает. Поэтому в какой-то момент я задумался: почему же Julia столь эффективный язык в этом плане? Почему там настолько высок уровень переиспользования кода? А также — какие уроки можно из этого извлечь, что другие языки могли бы позаимствовать из Julia, чтобы стать лучше?
Иногда, когда я это говорю, публика мне не верит, но вы уже на JuliaCon, так что вы в курсе происходящего, так что я сфокусируюсь на том, почему, по моему представлению, так происходит.
Но для начала — один из моих любимых примеров.
На слайде — результат работы Криса Ракаукаса. Он пишет всякие очень обобщённые пакеты для решения дифференциальных уравнений. Вы можете скормить туда дуальные числа, или BigFloat, — да что хотите. И как-то он решил, что хочет видеть погрешность результата интегрирования. И нашёлся пакет Measurements, который может отслеживать как значение какой-либо физической величины, так и распространение ошибки через последовательность формул. Также этот пакет поддерживает элегантный синтаксис для величины с неопределённостью, используя символ Юникода ±. Здесь на слайде показано, что ускорение свободного падения, длина маятника, начальная скорость, угол отклонения — все известны с какой-то погрешностью. Так, вы определяете простенький маятник, пропускаете его уравнения движения через солвер ОДУ и — бам! — всё работает. И вы видите график с усами погрешностями. И это я ещё не показываю, что код для рисования графика — тоже обобщённый, и вы просто пускаете туда величину с погрешностью из Measurements.jl и получаете график с погрешностями.
Уровень совместимости разных пакетов и обобщения кода просто мозговыносящий. Как, оно просто работает? Оказывается, да.
Ну ладно, не то чтобы мы совсем этого не ожидали. Как-никак, концепцию множественной диспетчеризации мы включили в язык именно потому, что она позволяет выразить обобщённые алгоритмы. Так что всё вышесказанное не так уж и безумно. Но одно дело — знать это в теории, и другое — увидеть на практике, что подход и впрямь работает. Ведь одиночная диспетчеризация и перегрузка операторов в C++ тоже должны давать похожий результат — но на деле часто не работают так, как хотелось.
Кроме того, мы наблюдаем нечто большее, чем мы предвидели, разрабатывая язык: пишется не просто обобщённый код. Дальше я постараюсь рассказать, в чём, на мой взгляд, это большее заключается.
Итак, есть два вида переиспользования кода, и они довольно сильно отличаются. Один — это обобщённые алгоритмы, и это первое, о чём вспоминают. Второй, менее очевидный, но, похоже, более важный аспект — это простота, с которой в Julia одни и те же типы данных используются в самых разных пакетах. В какой-то степени так происходит потому, что методы типа не становятся препятствием для его использования: вам не нужно соглашаться с автором типа по поводу интерфейсов и методов, которые он наследует; можно просто сказать: "О, мне нравится вот этот тип RGB. Операции над ним я придумаю свои, но структура его мне нравится".
Предисловие. Множественная диспетчеризация против перегрузки функций
Теперь я обязан упомянуть перегрузку функций в C++ или Java, поскольку мне всё время задают о них вопросы. На первый взгляд, она ничем не отличается от множественной диспетчеризации. В чём тут отличие и чем перегрузка функций хуже?
Начну с примера на Julia:
abstract type Pet end
struct Dog <: Pet; name::String end
struct Cat <: Pet; name::String end
function encounter(a::Pet, b::Pet)
verb = meets(a, b)
println("$(a.name) meets $(b.name) and $verb")
end
meets(a::Dog, b::Dog) = "sniffs"
meets(a::Dog, b::Cat) = "chases"
meets(a::Cat, b::Dog) = "hisses"
meets(a::Cat, b::Cat) = "slinks"Мы определяем абстрактный тип Pet, вводим для него подтипы Dog и Cat, у них есть поле имени (код немного повторяется, но терпимо) и определяем обобщённую функцию "встречи", которая принимает аргументами два объекта типа Pet. В ней мы сначала вычисляем "действие", определяемое результатом вызова обобщённой функции meet(), а потом печатаем предложение, описывающее встречу. В функции meets() мы используем множественную диспетчеризацию, чтобы определить действие, которое совершает одно животное при встрече с другим.
Добавим пару собак и пару кошек и посмотрим результаты встречи:
fido = Dog("Fido")
rex = Dog("Rex")
whiskers = Cat("Whiskers")
spots = Cat("Spots")
encounter(fido, rex)
encounter(rex, whiskers)
encounter(spots, fido)
encounter(whiskers, spots)Теперь то же самое "переведём" на C++ как можно более буквально. Определим класс Pet с полем name — в C++ мы это можем сделать (кстати, одно из преимуществ C++ — поля данных можно добавлять даже в абстрактные типы. Затем определим базовую функцию meets(), определим функцию encounter() для двух объектов типа Pet и, наконец, определим производные классы Dog и Cat и сделаем перегрузим meets() для них:
class Pet {
public:
string name;
};
string meets(Pet a, Pet b) { return "FALLBACK"; }
void encounter(Pet a, Pet b) {
string verb = meets(a, b);
cout << a.name << " meets "
<< b. name << " and " << verb << endl;
}
class Cat : public Pet {};
class Dog : public Pet {};
string meets(Dog a, Dog b) { return "sniffs"; }
string meets(Dog a, Cat b) { return "chases"; }
string meets(Cat a, Dog b) { return "hisses"; }
string meets(Cat a, Cat b) { return "slinks"; }Функция main(), как и в коде на Julia, создаёт собак и кошек и заставляет их встретиться:
int main() {
Dog fido; fido.name = "Fido";
Dog rex; rex.name = "Rex";
Cat whiskers; whiskers.name = "Whiskers";
Cat spots; spots.name = "Spots";
encounter(fido, rex);
encounter(rex, whiskers);
encounter(spots, fido);
encounter(whiskers, spots);
return 0;
}Итак, множественная диспетчеризация против перегрузки функций. Гонг!
Что, по-вашему, вернёт код с множественной диспетчеризацией?
Fido meets Rex and sniffs
Rex meets Whiskers and chases
Spots meets Fido and hisses
Whiskers meets Spots and slinksЗверушки встречаются, обнюхиваются, шипят и играют в догонялки — как и было задумано.
Fido meets Rex and FALLBACK
Rex meets Whiskers and FALLBACK
Spots meets Fido and FALLBACK
Whiskers meets Spots and FALLBACKВо всех случаях возвращается "запасной" вариант.
Почему? Потому что так работает перегрузка функций. Если бы работала множественная диспетчеризация, то meets(a, b) внутри encounter() вызывалась бы с конкретными типами, которые a и b имеют на момент вызова. Но применяется перегрузка, поэтому meets() вызывается для статических типов a и b, которые оба в этом случае — Pet.
Итак, в подходе C++ прямой "перевод" обобщённого кода Julia не даёт желаемого поведения из-за того, что компилятор пользуется типами, выведенными статически на этапе компиляции. А вся суть в том, что мы хотим вызывать функцию на основе реальных конкретных типов, которые переменные имеют в рантайме. Шаблонные функции, хотя и несколько улучшают ситуацию, всё равно требуют знания всех входящих в выражение типов статически во время компиляции, и несложно придумать такой пример, где это будет невозможно.
Для меня подобные примеры показывают, что множественная диспетчеризация делает правильно, а все остальные подходы — лишь не очень хорошее приближение к верному результату.
Теперь посмотрим такую таблицу. Надеюсь, вы найдёте её осмысленной:
| Тип диспетчеризации | Синтаксис | Аргументы диспетчеризации | Степень выразительности | Выразительная возможность |
|---|---|---|---|---|
| нет | f(x1, x2, ...) | {} | O(1) | постоянная |
| одиночная | x1.f(x2, ...) | {x1} | O(|X1|) | линейная |
| множественная | f(x1, x2, ...) | {x1, x2, ...} | O(|X1| |X2| ...) | экспоненциальная |
В языках без диспетчеризации вы просто пишете f(x, y, ...), типы всех аргументов фиксированы, т.е. вызов f() — это вызов единственной функции f(), которая может быть в программе. Степень выразительности постоянная: вызов f() всегда делает одну и только одну вещь. Одиночная диспетчеризация была большим прорывом при переходе к ООП в 1990-х и 2000-х. Обычно используется синтаксис с точкой, что людям очень нравится. И появляется дополнительная выразительная возможность: вызов диспетчеризуется по типу объекта x1. Выразительная возможность характеризуется мощностью множества |X1| типов, имеющих метод f(). Во множественной же диспетчеризации количество потенциально возможных вариантов для функции f() равно мощности декартова произведения множеств типов, к которым могут принадлежать аргументы. В реальности, конечно, вряд ли кому-то нужно столько разных функций в одной программе. Но ключевой момент тут в том, что программисту даётся простой и естественный способ использовать любой элемент этого многообразия, и это приводит к экспоненциальному росту возможностей.
Часть 1. Обобщённое программирование
Поговорим теперь об обобщённом коде — главной фишке множественной диспетчеризации.
Вот (абсолютно искусственный) пример обобщённого кода:
using LinearAlgebra
function inner_sum(A, vs)
t = zero(eltype(A))
for v in vs
t += inner(v, A, v) # множественная диспетчеризация!
end
return t
end
inner(v, A, w) = dot(v, A * w) # очень обобщённое определениеЗдесь A — это что-то матрицеподобное (хотя я не указал типы, и угадать что-то можно разве что по названию), vs — это вектор каких-то векторо-подобных элементов, и затем через эту "матрицу" считается скалярное произведение, для которого приведено обобщённое определение без указания каких-либо типов. Обобщённое программирование тут заключается в этом самом вызове функции inner() в цикле (совет от профессионала: хотите писать обобщённый код — просто уберите любые ограничения на типы).
Итак, "гляди, мама, оно работает":
julia> A = rand(3, 3)
3?3 Array{Float64,2}:
0.934255 0.712883 0.734033
0.145575 0.148775 0.131786
0.631839 0.688701 0.632088
julia> vs = [rand(3) for _ in 1:4]
4-element Array{Array{Float64,1},1}:
[0.424535, 0.536761, 0.854301]
[0.715483, 0.986452, 0.82681]
[0.487955, 0.43354, 0.634452]
[0.100029, 0.448316, 0.603441]
julia> inner_sum(A, vs)
6.825340887556694Ничего особенного, оно вычисляет какое-то значение. Но — код написан в обобщённом стиле и будет работать для любых A и vs, лишь бы над ними можно было произвести соответствующие операции.
Насчёт эффективности на конкретных типах данных — как повезёт. Я имею в виду, что для плотных векторов и матриц этот код будет делать "как надо" — сгенерирует машинный код с вызовом операций BLAS и т.д. и т.п. Если передать статические массивы — то компилятор и это учтёт, развернёт циклы, применит векторизацию — всё как надо.
Но что более важно — код будет работать и для новых типов, и можно его сделать не просто супер-эффективным, а супер-пупер-эффективным! Давайте доопределим новый тип (это реальный тип данных, который используется в машинном обучении), унитарный вектор (one-hot vector). Это вектор, у которого один из компонентов равен 1, а все остальные нулю. Представить его можно очень компактно: всё, что нужно хранить, — это длина вектора и номер ненулевого компонента.
import Base: size, getindex, *
struct OneHotVector <: AbstractVector{Int}
len :: Int
ind :: Int
end
size(v::OneHotVector) = (v.len,)
getindex(v::OneHotVector, i::Integer) = Int(i == v.ind)На самом деле, это реально всё определение типа, из пакета, который его добавляет. И с этим определением inner_sum() также работает:
julia> vs = [OneHotVector(3, rand(1:3)) for _ in 1:4]
4-element Array{OneHotVector,1}:
[0, 1, 0]
[0, 0, 1]
[1, 0, 0]
[1, 0, 0]
julia> inner_sum(A, vs)
2.6493739294755123Но для скалярного произведения тут используется общее определение — для такого типа данных это медленно, не круто!
Итак, общие определения работают, но не всегда оптимальным образом, и с этим при использовании Julia можно периодически столкнуться: "а, тут вызывается общее определение, вот почему этот GPU-код работает уже пятый час..."
В inner() по умолчанию вызывается общее определение произведения матрицы на вектор, что при умножении на унитарный вектор возвращает копию одного из столбцов с типом Vector{Float64}. Потом вызывается общее определение скалярного произведения dot() с унитарным вектором и этим столбцом, которое делает много ненужной работы. По сути, для каждого компонента проверяется "ты равен единице? а ты?" и т.д.
Мы можем сильно оптимизировать эту процедуру. Например, заменить умножение матрицы на OneHotVector просто выбором столбца. Прекрасно, определим этот метод, да и всё.
*(A::AbstractMatrix, v::OneHotVector) = A[:, v.ind]И вот она, мощь: мы говорим "хотим диспетчеризацию по второму аргументу", неважно что там в первом. Такое определение просто вытащит строку из матрицы и будет гораздо быстрее общего метода — убирается итерирование и суммирование по столбцам.
Но можно пойти и дальше и напрямую оптимизировать inner(), потому что перемножение двух унитарных векторов через матрицу просто вытаскивает элемент этой матрицы:
inner(v::OneHotVector, A, w::OneHotVector) = A[v.ind, w.ind]Вот и обещанная супер-пупер-эффективность. И всё что надо — это определить этот метод inner().
Этот пример показывает одно из применений множественной диспетчеризации: есть общее определение функции, но для каких-то типов данных оно работает неоптимально. И тогда мы точечно добавляем метод, который сохраняет поведение функции для этих типов, но работает значительно эффективнее.
Но есть и другая область — когда общего определения функции нет, а хочется добавить функциональность для каких-то типов. Тогда можно с минимальными усилиями её добавить.
И третий вариант — просто хочется иметь то же имя функции, но с разным поведением для разных типов данных — например, чтобы функция вела себя по-разному при работе со словарями и с массивами.
Как получить аналогичное поведение в языках с одиночной диспетчеризацией? Можно, но сложно. Проблема: при перегрузке функции * нужно было делать диспетчеризацию по второму аргументу, а не по первому. Можно сделать двойную диспетчеризацию: сначала диспетчеризуем по первому аргументу и вызываем метод AbstractMatrix.*(v). А этот метод, в свою очередь, вызывает что-то вроде v.__rmul__(A), т.е. второй аргумент в исходном вызове теперь стал объектом, чей метод реально вызывается. __rmul__ тут взято из Python, где такое поведение — стандартный паттерн, но работает, кажется, только для сложения и умножения. Т.е. проблема двойной диспетчеризации решена, если мы хотим вызывать функцию под названием + или *, в ином случае — увы, не наш день. В C++ и других языках — надо строить свой велосипед.
ОК, а что с inner()? Теперь тут три аргумента, и диспетчеризация идёт по первому и третьему. Что делать в языках с одиночной диспетчеризацией — непонятно. "Тройную диспетчеризацию" я вживую никогда не встречал. Хороших решений нет. Обычно, когда появляется подобная необходимость (а в численных кодах она появляется весьма часто), люди в конце концов реализуют свою систему множественной диспетчеризации. Если вы посмотрите большие проекты для численных расчетов на Python, вы будете поражены, сколько из них идут по этому пути. Естественно, подобные реализации работают ситуативно, плохо проработаны, полны багов и медленные (отсылка к десятому правилу Гринспена — прим. перев.), потому что ни над одним из этих проектов не работал Джеф Безансон (автор и главный разработчик системы диспетчеризации типов в Julia — прим. перев.).
Часть 2. Общие типы
Перейду к обратной стороне парадигмы Julia — общим типам. Это, на мой взгляд, главная "рабочая лошадка" языка, потому что именно в этой области я наблюдаю высокий уровень переиспользования кода.
Для примера, пусть у вас есть тип RGB, вроде того, что имеется в ColorTypes.jl. В нём нет ничего сложного, просто собраны вместе три значения. Ради простоты, будем считать, что тип не параметрический (но мог бы быть), и автор определил для него несколько базовых операций, которые счёл полезными. Вы берёте этот тип и думаете: "Хм, мне бы хотелось добавить ещё операции над этим типом". Например, представить RGB как векторное пространство (что, строго говоря, неверно, но в первом приближении сойдёт). В Julia вы просто берёте и добавляете в своём коде все операции, которых не хватает.
Возникает вопрос — и чо? Почему я на этом так акцентирую внимание? Оказывается, что в объектно-ориентированных языках, основанных на классах такой подход на удивление сложно реализуем. Поскольку в этих языках определения методов находятся внутри определения класса, добавить метод можно лишь двумя способами — либо отредактировать код класса, добавив нужное поведение, либо создать класс-наследник с нужными методами.
Первый вариант раздувает определение базового класса, а также заставляет разработчика базового класса заботиться о поддержке всех добавленных методов при изменениях кода. Что может в один прекрасный момент сделать такой класс неподдерживаемым.
Наследование — классический "рекомендованный" вариант, но тоже не лишён недостатков. Во-первых, нужно поменять имя класса — пусть оно теперь будет не RGB, а MyRGB. Кроме того, новые методы теперь не будут работать для исходного класса RGB; если я хочу применить мой новый метод к объекту RGB, созданному в чужом коде — нужно делать конвертацию или обёртку в MyRGB. Но это не самое плохое. Если я сделал класс MyRGB с какой-то добавленной функциональностью, кто-то ещё OurRGB и т.д. — то если кто-то хочет класс, у которого есть вся новая функциональность, нужно использовать множественное наследование (и это только если язык программирования его вообще позволяет!).
Итак, оба варианта оказываются так себе. Есть, правда, другие решения:
- Вынести функционал во внешнюю функцию вместо метода класса — перейти к
f(x, y)вместоx.f(y). Но тогда теряется обобщённое поведение. - Плюнуть на переиспользование кода (и, мне кажется, во многих случаях так и происходит). Просто скопировать себе чужой класс
RGBи добавить то, чего не хватает.
Ключевая особенность Julia в плане переиспользования кода практически полностью сводится лишь к тому, что метод определяется вне типа. Всё. Сделать то же самое в языках с одиночной диспетчеризацией — и типы можно будет переиспользовать с такой же лёгкостью. Вся эта история с "давайте сделаем методы частью класса" — так себе идея, на поверку. Есть там, правда, хороший момент — использование классов как пространств имён. Если я пишу x.f(y) — f() не обязана быть в текущем пространстве имён, её надо искать в пространстве имён x. Да, это хорошая штука — но стоит она всех остальных неприятностей? Не знаю. По-моему, нет (хотя моё мнение, как можете догадаться, слегка предвзято).
Эпилог. Проблема выражения
Есть такая проблема в программировании, которая была замечена в 70-е. Она во многом связана со статической проверкой типов, потому что в таких языках она появилась. Я, правда, думаю, что она не имеет отношения к статической проверке типов. Суть проблемы в следующем: можно ли изменить модель данных и набор операций над данными одновременно, не прибегая к сомнительным методикам.
Проблему более-менее можно свести к следующему:
- можно ли легко и без ошибок добавить новые типы данных, к которым применимы имеющиеся методы и
- можно ли добавить новые операции над уже существующими типами.
(1) легко делается в объектно-ориентированных языках и сложно в функциональных, (2) — наоборот. В этом смысле как раз можно говорить о дуализме ООП и ФП подходов.
В языках с множественной диспетчеризацией обе операции делаются легко. (1) решается добавлением методов к существующим функциям для новых типов, (2) — определением новых функций на существующих типах. И это не ново, не мы это придумали. Если зайти на страницу Википедии о проблеме выражения (https://en.wikipedia.org/wiki/Expression_problem), множественная диспетчеризация просто идёт под номером один в списке возможных решений. Почему его никто не использует? Такое ощущение, что большинство считает, что вся проблема очень нишевая. Но если подумать, "добавление новых типов, для которых работают существующие операции" — это же "обобщённое программирование работает как должно" другими словами. А "добавление новых операций, которые работают для существующих типов" возможно, потому что методы можно добавить после того, как определены типы.
И эти две стороны проблемы выражения в точности соответствуют типам переиспользования кода, которые мы наблюдаем. И эта, казалось бы, теоретическая проблема — ключ к высокой степени переиспользования кода.
Таким образом, избавившись в Julia от проблемы выражения (простейшим и старейшим из предлагаемых способов), мы имеем невероятную степень переиспользования кода. Кто бы мог подумать.
Комментарии (44)
Alex_ME
27.09.2019 03:02Тем не менее, есть неточность:
Возникает вопрос — и чо? Почему я на этом так акцентирую внимание? Оказывается, что в объектно-ориентированных языках, основанных на классах такой подход на удивление сложно реализуем. Поскольку в этих языках определения методов находятся внутри определения класса, добавить метод можно лишь двумя способами — либо отредактировать код класса, добавив нужное поведение, либо создать класс-наследник с нужными методами.
Например, в C# есть Extension Methods, которые позволяют определить функцию для какого угодна типа (класса, интерфейса) вне этого типа.
Pand5461 Автор
27.09.2019 10:02Тоже, когда дошёл до перевода этого момента, вспомнил — в C# же было что-то такое. Но, похоже, до этого только в C# и дошли.
andreyverbin
28.09.2019 13:31Extension method это далеко не мультиметоды, даже не близко. Мультиметоды они в runtime определяют конкретный метод, а extension method в compile time. Вот пример
`
void Copy(object a, object b); //сигнатура операции, копируем что угодно, куда угодно. Лежит в библиотеке Commons.
var a = new Folder();
var b = new File();
var c = new Folder();
var d = new ZipFile();
Copy(a, b); // копируем файл в папку
Copy(a, c); // копируем папку в папку, мержим деревья директорий.
Copy(d, a); //копируем папку в zip архив.
// библиотека FileSystem от компании MacroHard
void Copy(Folder a, Folder b) {}
void Copy(Folder a, File b) {}
//библиотека ZipArchive в open source
void Copy(ZipFile a, File b) {}
void Copy(ZipFile a, Folder b) {}
//библиотека Dropbox
void Copy(DropboxFolder, File);
void Copy(DropboxFolder, Folder);
// мой прикладной код
// шах и мат extension methods
void MyCopy(object target, object source1, object source2)
{
Copy(target, source1);
Copy(target, source2);
}
`
vintage
27.09.2019 09:59Перегрузка функций — такая же множественная диспетчеризация. Разница лишь в том, что в C++ диспетчеризация функций статическая, а в Julia — динамическая. И как как любая динамика, она имеет накладные расходы в рантайме.
Pand5461 Автор
27.09.2019 10:15+1В Julia не всегда динамическая диспетчеризация, на самом деле, и это одна из фишек.
Если типы можно вывести при компиляции функции — они и диспетчеризуются статически, без каких-либо накладных расходов (кроме времени на JIT-компиляцию, конечно). Динамика применяется только тогда, когда статических гарантий сделать нельзя, но тут уже от накладных расходов в принципе никуда не деться.
В этом отличие мультиметодов Julia от мультиметодов CLOS, в которых всегда диспетчеризация в рантайме.seslomayer
27.09.2019 20:35У julia есть аналог -S от gcc? Можно как-то посмотреть сгенерированный код?
Pand5461 Автор
27.09.2019 20:43+1Можно, причём на разных этапах работы транслятора. Но только для отдельной функции:
code_lowered(func, argtypes)— АСДcode_warntype(func, argtypes)— АСД с пометками о выведенных типахcode_llvm(func, argtypes)— байткод LLVMcode_native(func, argtypes)— ассемблерный код.
seslomayer
27.09.2019 21:19Посмотрел я выхлоп — у меня получилось добиться адекватного результата. Но в целом вопрос остаётся открытый — на более сложных примерах он генерирует какую-то муть. Что там вызывается и откуда — решительно непонятно.
По поводу же самого результата — это выхлоп уже после мидла, а что там нагенерил фронт — неясно. llvm в базовых случаях может всё ненужно свернуть. Вопрос заключается именно в этом — фича ли это языка, либо llvm свернул.Pand5461 Автор
27.09.2019 22:14Что-то я не понял.
Все оптимизации, которые есть вcode_lowered,code_typed,code_warntypeиcode_llvm— это до LLVM.code_native— это то, что LLVM сделал из поданного ему байткода.
То, что язык в плане низкоуровневой оптимизации опирается на LLVM — это особо не скрывается. Но сам компилятор в байткод уже достаточно умный, чтобы можно было провернуть Tim Holy's trait trick, например.seslomayer
27.09.2019 23:26code_llvm — это до LLVM.
Сомнительно. Очень похоже на после.
что LLVM сделал из поданного ему байткода.
Это тоже крайне сомнительно. llvm сам генерирует свой ir. llvm-ir очень сложен и непереносим, поэтому в llvm есть специальное api для его генерации. Я очень сомневаюсь, что вообще какой-то фронт умеет его генерировать сам, если только это не какой-то «приветмир».
То, что язык в плане низкоуровневой оптимизации опирается на LLVM — это особо не скрывается.
Дело не в этом. Дело в том, что в случае с реализацией на уровне языка — это ещё как-то предсказуемо(хотя и неявно). В случае с тем, когда это делает llvm — это совсем мало предсказуемо и это явно не:
Если типы можно вывести при компиляции функции — они и диспетчеризуются статически
т.к. llvm ни про какие типы жулии не знает.
Но сам компилятор в байткод уже достаточно умный, чтобы можно было провернуть Tim Holy's trait trick, например.
Вот динамический диспатч с тем же результатом: godbolt.org/z/qOI5Cp
Нужно показывать не llvm на выходе в бек, а прям с фронта до оптимизаций. Хотя вроде как оно там что-то сворачивает в показанных примерах, но опять же. Всё это такие примитивные случае, которые работают и так(я выше показывал).
Слишком простые случаи, слишком мало примеров для того, что-бы действительно говорить о каком-то «работает всегда, когда явно известны типы».Pand5461 Автор
28.09.2019 02:09Да, ошибся, со стандартными аргументами
code_llvm()даёт код после оптимизаций. Полная документация к функции: https://docs.julialang.org/en/v1/stdlib/InteractiveUtils/#InteractiveUtils.code_llvm (также на странице и документация по другим функциям вывода промежуточных представлений).
По поводу совместимости LLVM — в документации по сборке так и написано, что версия LLVM прибита гвоздями.
Слишком простые случаи, слишком мало примеров для того, что-бы действительно говорить о каком-то «работает всегда, когда явно известны типы».
Ну установите какой-нибудь пакет, например, упомянутый в докладе DifferentialEquations.jl, посмотрите, во что в тамошние функции компилируются (мне тоже интересно узнать). Люди же не будут в статьи для новичков выкладывать код проекта на тысячи строк.
seslomayer
28.09.2019 05:17По поводу совместимости LLVM — в документации по сборке так и написано, что версия LLVM прибита гвоздями.
Из этого ничего не следует. Версия никак не связана с тем, о чём я говорил. У llvm постоянно меняется api — он развивается. Там что угодно не соберётся.
Я же говорю о непереносимости(т.е. под каждую платформу он свой) ir и сложности его генерации. Поэтому он везде и всюду генерируется специальным инструментарием, предоставленным llvm.
Ну установите какой-нибудь пакет, например, упомянутый в докладе DifferentialEquations.jl, посмотрите, во что в тамошние функции компилируются (мне тоже интересно узнать).
Нету нормального инструментария. То, во что там компилируются эти функции — это не показать — нужно видеть картину в целом.
В целом, я уже видел несколько бенчмарков. Особенно та победа на си, которую лучше не вспоминать. Не заметил там ничего, да и нету предпосылок к тому, что-бы что-то заметить.
Люди же не будут в статьи для новичков выкладывать код проекта на тысячи строк.
Ну почему же. Это не для новичков — это пруф. Пруфы всем интересны.
sairus777
28.09.2019 18:12В целом, я уже видел несколько бенчмарков. Особенно та победа на си, которую лучше не вспоминать.
А можно поподробнее? Есть какие-то проблемы с оптимизациями на Julia? (помимо первого вызова для jit)seslomayer
28.09.2019 19:08+1Вот ссылка на ту эпичную победу. Таких примеров уже много было — я все не записываю.
По поводу самих проблем. Оптимизации — это не халява. Да, какие-то базовые вещи llvm даёт на халяву, но далеко на этом не уедешь. Оптимизация — это, прежде всего, предсказуемость. Да, в некоторых случаях можно забить и это даже будет работать, но это капля в море. Автовекторизация нигде нормально не работает. Алгоритмические оптимизации компилятор в принципе делать не умеет. Учитывать нюансы работы ОС/железа/рантайма — тоже.
Общее развитие уже дошло до того, что практический любой язык может быстро посчитать факториал. Когда задача не оптимизируема в принципе, когда используются базовые value-типы, когда не используется сложная и вообще хоть какая-то работа с памятью — различий нет и не будет. И между си и между жулией и межу жаваскриптом.
Обычно акцент делается именно на описанном выше. Но это не показатель. Да, таким образом удобно продвигать языки/идеи, но это скользкая дорожка. Которая не приведёт к правильной конкуренции и к правильной оценки и себя и других.
Так же реальность в которой действительно пребывает что-то похожее на «оптимизации» — это возможности, которые даёт программисту язык и используя которые он может создать нечто удовлетворяющие критериям вида «оптимальный», «быстрый» и прочие.
И именно в это плоскости, насколько я могу судить, всё плохо и всё плохо везде. Выше пусть и в шутку — был высказан лозунг «мы делаем как хочешь — что там дальше — это не наша проблема». И это тупик.
Тот кто использует либу — использовать её оптимально — не его задача. Пусть этот делает создатель либы. Тот, кто создаёт либу — реализовывать её оптимальное — не его задача. Пусть это делают создатели языка. А за создателей языка пусть трудятся создатели llvm и так далее.
Причём на каждом этапе информация теряется и оптимизация даётся всё сложнее и сложнее. Программист может без проблем использовать другую структуру данных, более оптимальную. На уровне llvm сделать подобное практически невозможно.
Именно это и есть проблема и жулии и множества других языков. Даже в какой-то мере и С/С++. Точно так же проблема — неадекватность оценки себя/конкурентов.sairus777
28.09.2019 19:56Вот ссылка на ту эпичную победу. Таких примеров уже много было — я все не записываю.
Чья-то поверхностная оценка / недостаток профессионализма — это, конечно, печально, но хотелось бы увидеть какие-то объективные недостатки языка.
И именно в это плоскости, насколько я могу судить, всё плохо и всё плохо везде. Выше пусть и в шутку — был высказан лозунг «мы делаем как хочешь — что там дальше — это не наша проблема». И это тупик.
Я не понял, каким образом критика, связанная с разделением ответственности, специфична именно для Julia.
Если я добавляю или переопределяю функции для конкретных типов на Julia, то я могу быть уверен, что код будет себя вести вполне ожидаемо. Если я хочу динамизма, то могу рискнуть и не объявлять типы в сигнатурах функций. Если хочу обобщенный код — пишу функции от абстрактных типов, и перекладываю специализацию функций на компилятор. То есть, я не вижу здесь какой-то опасности, которой нельзя избежать, зато я вижу, что многие вещи можно сделать более лаконично/выразительно, и при этом иметь приличную скорость.
Что касается оценки с конкурентами, то в первую очередь надо сравнивать с матлабом и питоном, у которых намного больше геморроя с оптимизацией.seslomayer
28.09.2019 20:26Чья-то поверхностная оценка / недостаток профессионализма
Не чья-то. Это попытка манипулировать. Это именно показатель того, что комьюнити жулии то самое. Если бы не то самое, то подобную оплошность бы заметили.
но хотелось бы увидеть какие-то объективные недостатки языка.
Нету предмета — не о чём говорить. В этом проблема. Я ведь не должен за авторов/последователей пруфцевать состоятельность их кода. Это их задача.
Я же вижу в очередной раз ту же самую проблему — неадекватное сравнение. И для подобных языков — это норма. Они не обладают какой-то уникальностью, что-бы имело смысл выделять что-то. На llvm наплодилось десятки, если не сотни подобных языков. Повторюсь — не моя задача заниматься обоснованием их состоятельности/несостоятельности.
Я не понял, каким образом критика, связанная с разделением ответственности, специфична именно для Julia.
Повторю ещё раз. Для того, что-бы что-то оценивать «специфично» — это что-то должно выделяться. Лично я не замечаю подобного, но вы можете мне помочь с этим. Поэтому лично для себя я не вижу проблем в обобщении.
Если я добавляю или переопределяю функции для конкретных типов на Julia, то я могу быть уверен, что код будет себя вести вполне ожидаемо.
Неверно. Здесь нет диспатча — это не имеет отношения к теме. Такими свойствами обладает любая функция, если она конечного типа.
В данном случае я виду речь о другим. У меня есть затирание типа, у меня есть семантически динамаческий диспатч. Что там будет вызвано — я не знаю. Как мне эти управлять — я не знаю. И будет ли оно вызвано статически — я не знаю. Какой код будет сгенерирован — я тоже не знаю.
Если я хочу динамизма, то могу рискнуть и не объявлять типы в сигнатурах функций.
Они и так не объявлены. Объявлены общие тип.
Если хочу обобщенный код — пишу функции от абстрактных типов.
Это тоже динамика. То, что потом где-то на уровне компилятора что-то изменится — это не меняет семантики наблюдаемого поведения. Типы потерян — предсказать что-то нельзя.
К тому же — это не обобщённый код в контексте профита, который даёт обобщённый код в том же С++. Раз сравнивается с С++ и заявляется о статическом диспатче — имеется ввиду это.
Сам по себе статически диспачт без должной семантики ничего не даёт. Это нужно понимать. Ну уберёт он косвенность в вызове — это не то ради чего используются подобные методички в С++.
То есть, я не вижу здесь какой-то опасности, которой нельзя избежать, зато я вижу, что многие вещи можно сделать более лаконично/выразительно, и при этом иметь приличную скорость.
Скорость уже потеряна. Управление потеряно. Возможности к оптимизации — тоже. В ситуации с наличием jit — это позор. Попросту позор. В ситуации с jit и семантически статическим диспатчем — можно сделать много всего. И ключевая задача тут в не том, что-бы убрать какие-то косвенные вызовы. Ключевая задача в том, что-бы получить семантику компилтайма в рантайме.
Если в С++ я знаю, что случае со статическим диспачем и проставкой нужных флагов — я могу получить оптимальный код. Всё будет заинлайнено, все типы будут выведены, всё будет оптимизировано. Точно так же если я хочу посчитать что-то в коплтайме — узнать какие-то свойства из типа — я всё это сделаю до вычислений. Один раз и тогда когда нужно.
В ситуации же это — никто ничего не знает. И не будет знать, ведь нету даже инструментария адекватного для обратной связи. О какой производительности может идти речь?
По поводу выразительности я так же поспорю. Именно семантический статический диспатч позволяет раскрыть всё выразительность типизации, ведь он позволяет организовывать логику на типах и получать сразу же обратную связь от языка.
Жулия же пошла по пути репла. По-сути это скриптуха с частицами типизации. Да — перегрузка это круто. За это и любят С++ и молодцы, что сделали подобное. И я не хаю и ничего не говорю против.
Я лишь говорю о том, что ненужно сравнивать мягкое и холодное. Ненужно вбрасывать несостоятельные тезисы и занимать подобной нечестной игрой.
Что касается оценки с конкурентами, то в первую очередь надо сравнивать с матлабом и питоном, у которых намного больше геморроя с оптимизацией.
Судя по ленте — комьюнити жулии считает иначе.
sairus777
28.09.2019 20:42Судя по ленте — комьюнити жулии считает иначе.
Комьюнити Julia — оно вообще не русскоязычное.)
Сам по себе статически диспачт без должной семантики ничего не даёт. Это нужно понимать.
Я не понимаю. Можете на конкретном примере / куске кода пояснить, что вы имеете в виду? Либо прислать минимальный пример для сравнения производительности, чтобы я повторил его на Julia и сравнил?
Вот тут, например, нормальный тип выводится — Int64:
function foo(x::Number) print(typeof(x)) end foo(1) # output: Int64 foo(1.0) # output: Float64seslomayer
28.09.2019 22:23Комьюнити Julia — оно вообще не русскоязычное.)
Почти вся эта лента — переводы.
Вот тут, например, нормальный тип выводится — Int64:
Это не тип — это рантайм-тип. В целом в скриптухе слишком сложно разделить рантайм/компилтайм. От этого происходит много путаницы. Тоже самое можно написать на том же жаваскрипте 1в1. Правда там нет подобных типов, но bignum/number оно выведет. И да, возможно, это так же будет оптимизировано.
Если кратко — это не тип. Это не получение типа. Это всё рантайм логика. Её ключевая особенность в том, что она однофазна по-сути. Никакой логики над этими типами реализовать нельзя.
Разделении логики на две фазы — даёт чёткое представление о том, что будет посчитано до, а что после. Что попадёт в оптимизатор, а что нет. Можно заранее предсказать семантику каждой операции.
Т.е. мы отделяем то, что можно посчитать и вывести до — от того, что можно посчитать/вывести после. Причём до — можно сделать и не оптимально.
В ситуации же вашей — вы будите вынуждены разделять логику так же на две фазы. Это будет неявно, это будет неуправляемо. Шансы ваш на успех крайне малы.
И даже если мы сделаете это — далее вам нужно уповать на то, что всё посчитается заранее и jit создаст нужные функции. А он их не создаст, потому что он крайне примитивен, а не-примитивный он только в сказке.
Можете на конкретном примере / куске кода пояснить, что вы имеете в виду? Либо прислать минимальный пример для сравнения производительности, чтобы я повторил его на Julia и сравнил?
Напишите список тем удобных вам/жулии. Ну самое такое простое связанное с вычислениями — поумножать мелкие вектора/матрицы.sairus777
28.09.2019 22:37Да, хорошо, давайте пример на матрицах/векторах.
Ну или вообще с чем угодно, где у джулии начинаются описанные вами проблемы — лишь бы можно было повторить максимально похожий код.seslomayer
28.09.2019 23:02+1Хорошо, я напишу базовую реализацию и нормальную, где проявляются все преимущества семантической статики. Сможете ли вы повторить вторую — не знаю. Но вот первую точно — там ведь не ничего сложного.
Я не могу обещать прям скоро, я уже трачу достаточное ко-во своего времени на ресёрч на тему одного материала на хабре. Но меня тоже интересует реальное сравнение жулии(а возможно и не только) и условного C++.
Кстати, здесь задет ещё один важный аспект. Ведь возможности и правильные подходы важные не только тем, что они такие хорошие. Они важны и тем, что они тренируют правильное мышление, постоянно генерируют практику и не входят в диссонанс с тем самым лоулевел миром. А жить пребывая в вечном диссонансе крайне неудобно. И рано или поздно что-то одно победит.
andreyverbin
28.09.2019 13:36Она динамическая и во много выразительнее перегрузки. Их даже сравнивать нельзя, это все равно что сравнивать
`
void MyFunc(SomeSpecificType1 t) {}
void MyFunc(SomeSpecificType2 t) {}
//и
interface SomeSpecificType
{
virtual void MyFunc() {}
}
`
seslomayer
27.09.2019 21:29По поводу C++ — это неправильный код. Правильный вот: godbolt.org/z/5_hw9C
Если типы можно вывести при компиляции функции — они и диспетчеризуются статически, без каких-либо накладных расходов
Это неправда. Я уже выше писал, что накладных расходов может и не быть в случае динамического диспатча, если компилятор сможет свернуть. Но дело не в этом.
Дело в том, что на уровне языка — это всё равно будет динамический диспатч. Что там ниже произойдёт — неважно. И именно из-за этого и проистекают накладные расходы. Ведь в случае С++ я могу получить эти типы в любой момент, что угодно с ними сделать. Как угодно их преобразовать. Всё это возможности, которые позволят написать более эффективный код, либо написать его вообще.
К тому же — это даёт самое важное. Это даёт предсказуемость.Pand5461 Автор
28.09.2019 01:51По поводу C++ — это неправильный код.
Ну если уж пошла такая пьянка — то интересен-то случай, когда конкретный наследуемый тип определяется в рантайме: https://godbolt.org/z/nitocL
На Julia неважно, диспетчеризовать можно через статический вывод типов или только динамически в рантайме — результат будет одинаковый.
Дальше какой-то сумбур, ЯННП.
Могу только согласиться, что в рамках стандарта поведение C++ кода должно быть предсказуемым, и если это прям важно для задачи — нестандартизованный язык в принципе не подойдёт.
seslomayer
28.09.2019 05:05Ну если уж пошла такая пьянка — то интересен-то случай, когда конкретный наследуемый тип определяется в рантайме: godbolt.org/z/nitocL
Это вообще неверно, фундаментально. Код ничего не делает и работать не может. godbolt.org/z/Q1pRu3 — всё работает. Правда кейс крайне сомнительный.
Проблема тут в том, что такой подход типичный для любых генериков. Он крайне популярный, потому что самый простой для реализации и более-менее универсальный. Но проблема его в том, что семантически это динамика. Причём крайне куцая. Таким образом оно слишком слабо для статики и слишком строго для динамики.
Я так полистал ещё раз пост — там все примеры уровня виртуальных методов. Да, в целом оно может конкурировать с витуальными методами в С++, и даже лучше. Но виртуальные методы — это лишь вершина айсберга в мире С++.
На Julia неважно, диспетчеризовать можно через статический вывод типов или только динамически в рантайме — результат будет одинаковый.
Как я уже говорил — никаких пруфов этому тезису нет, но не это самое важное. Самое важное то, что семантически это будет динамический диспатч со всеми вытекающими. Оно никогда не будет даже близко настолько же эффективно как семантический статический диспатч.
Могу только согласиться, что в рамках стандарта поведение C++ кода должно быть предсказуемым, и если это прям важно для задачи — нестандартизованный язык в принципе не подойдёт.
Дело не в стандарте. Поведение virtual так же непредсказуемо в данном контексте. Дело в том, что я всегда могу глянув на код узнать — где там динамический диспатч. И знать, что где его нет — его нет. И там же я получаю фичи, которые обусловлены статическим диспатчем. А в случае с динамическим — наоборот.
Tiendil
28.09.2019 11:19Дело в том, что я всегда могу глянув на код узнать — где там динамический диспатч. И знать, что где его нет — его нет. И там же я получаю фичи, которые обусловлены статическим диспатчем. А в случае с динамическим — наоборот.
Плюсую.
В статье этот вопрос не раскрыт, а он является очень интересным и важным. В каких-то областях можно забить на это знание (если априори код не станет узким местом и важна гибкость), а в каких-то это может стать источником критических проблем.Pand5461 Автор
28.09.2019 17:26Сама идея о том, как совместить статические гарантии с правильной динамической диспетчеризацией — она важная и нужная, спору нет.
Утверждение, что в C++ (и в Julia) этот вопрос решён — глубоко ошибочно.
Судя по форуму Julia и по докладам с CppCon — проблема живо интересует оба сообщества, только, по очевидным причинам, с разных концов.
Pand5461 Автор
28.09.2019 15:10Это вообще неверно, фундаментально. Код ничего не делает и работать не может.
Так об этом и речь — статическая перегрузка функций не даёт полноценной диспетчеризации. Ну и да, вы опять привели код, который не делает динамическую диспетчеризацию.
Речь банально о том, что переменная типа
Subtypeи разыменованная ссылка наSupertype, по которой в данный момент в рантайме находится значение типаSubtypeимеют разную семантику.
Кейс для численных расчётов ни разу не сомнительный. Петы — это аллегория. А так для численных методов практически всегда надо выполнять операцию
A * B, гдеAможеть быть вектором (плотным, разреженным, состоящим только из 0 и 1), матрицей (плотной общего вида, разреженной, симметричной, диагональной, ленточной, единичной, представленной в виде LU-разложения, QR-разложения, разложения Холецкого и т.д.), всё это умножить на то, что тип элементов может быть Float32, Float64, Float128, Complex (ну и там в Julia есть несколько пакетов с кастомными числовыми типами) и то же самое дляB. С мультидиспатчем в библиотеке, реализующей численный метод, будет написаноA * B. Какие именно там будут матрицы и как это умножение эффективно на машине реализовать — забота того, кто придумал соответствующие типы. Когда пишется свой тип матрицы (пусть будетLUMatrixдля определённости) — достаточно определить базовые вещи типа получения элемента по индексу, конвертации в обычную матрицу и обратно, умножения на матрицу или вектор и backsolve (решения системы A*x = b). Кому надо добавить операции типаLUMatrix * MyMatrixType— может это сделать, не влезая в код классаLUMatrix(потому что классов нет).
Как я уже говорил — никаких пруфов этому тезису нет
Что значит — пруфов нет? Весь язык именно об этом. Я не говорю, что время выполнения будет одинаковым, я говорю — результат выполнения функции будет одинаковым.
Дело в том, что я всегда могу глянув на код узнать — где там динамический диспатч. И знать, что где его нет — его нет.
А, это уже понятный тезис. Но это на практике не имеет никакого значения, как говорят питонисты (сарказм).
seslomayer
28.09.2019 16:23Так об этом и речь — статическая перегрузка функций не даёт полноценной диспетчеризации. Ну и да, вы опять привели код, который не делает динамическую диспетчеризацию.
На этом можно закончить, но я продолжу — он делает динамическую диспетчеризацию, но, скорее всего, вы не поняли как. Но поверьте мне — он делает. Проблема тут в том, что ваш догмат несостоятелен и вы не хотите признать это.
К тому же речь не об этом. В моём ответе не было «не даёт» — там было о том, что вы не понимаете как использовать С++ и делаете неверные выводы, приводя некорректный код.
Кейс для численных расчётов ни разу не сомнительный.
Я видел уровень этих расчётов — не удивляет. К тому же говорить о каких-то расчётах реализуя их на непредсказуемом языке — это достаточно наивно, на мой взгляд, да.
А так для численных методов практически всегда надо выполнять операцию A * B, где A можеть быть вектором (плотным, разреженным, состоящим только из 0 и 1), матрицей (плотной общего вида, разреженной, симметричной, диагональной, ленточной, единичной, представленной в виде LU-разложения, QR-разложения, разложения Холецкого и т.д.), всё это умножить на то, что тип элементов может быть Float32, Float64, Float128, Complex (ну и там в Julia есть несколько пакетов с кастомными числовыми типами) и то же самое для B.
И? Для этого ненужен и даже вреден динамический диспатч.
С мультидиспатчем в библиотеке, реализующей численный метод, будет написано A * B.
Эта капля в море, да и это крайне примитивно. Нужно ещё и написать оптимальны реализации этих методов, а вот тут С++ поможет семантический статический диспатч, а жулии нет. Хотя у неё есть jit и это позволяет использовать статический(семантический) диспатч почти везде.
Какие именно там будут матрицы и как это умножение эффективно на машине реализовать — забота того, кто придумал соответствующие типы.
Ну в этом и проблема, что он не может получить необходимые данные при реализации. От того весь его код превращается в тыкву.
Когда пишется свой тип матрицы (пусть будет LUMatrix для определённости) — достаточно определить базовые вещи типа получения элемента по индексу, конвертации в обычную матрицу и обратно, умножения на матрицу или вектор и backsolve (решения системы A*x = b). Кому надо добавить операции типа LUMatrix * MyMatrixType — может это сделать, не влезая в код класса LUMatrix (потому что классов нет).
Это не новость. C++ — передовая подобных разработок. К тому же, даже в контексте пользователя — непредсказуемость является проблемой. Когда становится без разницы — это превращается в скриптуху со всеми вытекающими. Производительность не возьмётся на пустом месте — пользователь должен осознавать что используется и только тогда он сможет адекватно использовать предоставленный ему api.
Что значит — пруфов нет? Весь язык именно об этом. Я не говорю, что время выполнения будет одинаковым, я говорю — результат выполнения функции будет одинаковым.
Про результат никто не спорит. Я говорю о той семантике, которая присуща С++. При сравнении нужно это учитывать.
Pand5461 Автор
28.09.2019 22:18Но поверьте мне — он делает.
Он не работает как ожидается, когда туда даются разыменованные ссылки на
Pet. Т.е. это может не быть для вас проблемой — вы так не собираетесь писать. Но интерпретация ссылки на подтип как ссылки на родительский тип — это законное дело, кто-то решит пойти по такому пути, и тут начинаются те самые проблемы с переиспользованием кода, о чём в исходном докладе, в общем-то и речь.
Смысл примера в докладе был вообще не в том, что "в плюсах нет динамического диспатча", а именно "если вы думаете, что вот это в плюсах всегда сделает диспатч, то вы ошибаетесь".
И давайте всё-таки вернёмся к теме статьи — вопрос не в динамической диспетчеризации, а в мультиметодах как парадигме.
И непонятен, опять же, тезис о том, что "написать абстрактно" — в обязательном порядке неэффективно в Julia и эффективно в C++.
То, что разработчик, скажем, солвера для дифура не может знать заранее любой тип дифура, который туда попадёт — языком программирования не решается. Но это вовсе не значит, что на Julia разработчик махнёт рукой и скажет "оптимизируйте всё сами". Можно сделать какие-то разумные допущения, что, например, там будут часто попадаться произведение плотной матрицы на плотный вектор, и под этот случай написать отдельно оптимизированную версию, для остальных случаев оставить что-то абстрактное, чтобы просто работало.
Про результат никто не спорит. Я говорю о той семантике, которая присуща С++. При сравнении нужно это учитывать.
Тьфу, опять-двадцать пять. С чего вы решили, что я спорю насчёт семантики? О том и речь с самого начала, что код похожий, но у C++ другая семантика.
Про стандарт в том же ключе — что в нём прописано, для каких выражений диспатч статический, для каких динамический.
Насчёт того, что лучше по производительности, когда компиляция не статическая — сейчас горячо обсуждается тема "Time to first plot". Там по анализу времени компиляции оказалось, что плохие аннотации типов хуже никаких, потому что компилятор пытается из них что-то выводить, но в конце концов без толку, а время тратится. Теперь вот обсуждают, как сделать, чтобы компилятор угадывал, где пошла "скриптуха", и бросал затею для неё что-то эффективное генерить.
seslomayer
28.09.2019 22:54Он не работает как ожидается, когда туда даются разыменованные ссылки на Pet. Т.е. это может не быть для вас проблемой — вы так не собираетесь писать. Но интерпретация ссылки на подтип как ссылки на родительский тип — это законное дело, кто-то решит пойти по такому пути, и тут начинаются те самые проблемы с переиспользованием кода, о чём в исходном докладе, в общем-то и речь.
Я не понимаю того, что здесь написано. Кем ожидается? Вами? Ну дак вы не понимаете как работает и должен работать С++. Проблемы вашего восприятия — проблема вашего восприятия. Рассуждать о каких-то ссылках и прочих сущностях в контексте скриптухи — это, опять же, сильно. К тому же меняете показания. До этого диспатча не было, а теперь он уже вам неугоден. Угодность вам — не есть состоятельный критерий и я его игнорирую.
Смысл примера в докладе был вообще не в том, что «в плюсах нет динамического диспатча», а именно «если вы думаете, что вот это в плюсах всегда сделает диспатч, то вы ошибаетесь».
Я не знаю кто так думает, но это какая-то чушь. Можете обосновать эти версию — как мы можем её однозначно вывести из повествования выше. По-моему я вижу там обман/манипуляцию, а далее вижу какую-то не очень обоснованную попытку придумать задним числом объяснение.
И давайте всё-таки вернёмся к теме статьи — вопрос не в динамической диспетчеризации, а в мультиметодах как парадигме.
Это пародия на возможности С++. Сравнивать их не имеет смысла. Но автор попытался все обмануть, придумав какую-то новую(непонятно кому нужную фичу) и на базе неё начал «побежать» С++. Это глупо, это подло, это нелепо.
И непонятен, опять же, тезис о том, что «написать абстрактно» — в обязательном порядке неэффективно в Julia и эффективно в C++.
Это базовое свойство этой реальности. Другой у нас нет. И вы здесь так же пытаетесь манипулировать. Ключевое тут то, что это непредсказуемо и немощно. Очевидно, что будут существовать такие кейсы, в которых разницы может не быть. Но это ничего не будет значить. Тоже самое может получится и при использовании динамической типизации. И вообще без какой-либо типизации.
Получается из этого следует, что типизация ненужна? Нет. Типизация нужна не потому, что она ВСЕГДА лучше. А потому, что она в больших случаях приводит к лучшему результату. А в некоторых может приводить и к худшим, а может быть и к таким же.
Это ключевое. Здесь идёт борьба за шансы на успех, шансы выиграть оптимальность.
То, что разработчик, скажем, солвера для дифура не может знать заранее любой тип дифура, который туда попадёт — языком программирования не решается. Но это вовсе не значит, что на Julia разработчик махнёт рукой и скажет «оптимизируйте всё сами». Можно сделать какие-то разумные допущения, что, например, там будут часто попадаться произведение плотной матрицы на плотный вектор, и под этот случай написать отдельно оптимизированную версию, для остальных случаев оставить что-то абстрактное, чтобы просто работало.
Правильно, а типизация и семантический статический диспатч даст этому автору больше возможностей, а пользователю больше контроля.
Тьфу, опять-двадцать пять. С чего вы решили, что я спорю насчёт семантики? О том и речь с самого начала, что код похожий, но у C++ другая семантика.
Давайте посмотрим:
Ведь одиночная диспетчеризация и перегрузка операторов в C++ тоже должны давать похожий результат — но на деле часто не работают так, как хотелось.
Кому должны, что значит не работают? Кому хотелось? Тому, кто не знает С++? Не дак это не проблема С++ — это попросту манипуляция. Ведь читатель не будут думать, что это значит то, что значит. Он подумает, что? «такое сделать нельзя». Потому что очевидно, что критика вида «не работает потому, что не работает так как хочу я» — глупа и никто не поверит, что это действительно имеет ввиду.
Итак, в подходе C++ прямой «перевод» обобщённого кода Julia не даёт желаемого поведения из-за того, что компилятор пользуется типами, выведенными статически на этапе компиляции.
Мне лень слушать доклад и искать там месте, к тому же я не уверен, что там изначально была подобная формулировка. Здесь нету лога правок статей. Но опять же, даже в таком виде. Это не прямой, а неверный «перевод». Как минимум формулировка крайне сомнительна и манипулятивна.
А вся суть в том, что мы хотим вызывать функцию на основе реальных конкретных типов, которые переменные имеют в рантайме.
С чего вдруг мы этого хотим? К тому же мы знаем типы всех переменных в рантайме, если это статический код. Зачем нам терять эти типы? Потеря типов — следствие слабой системы типов.
Шаблонные функции, хотя и несколько улучшают ситуацию, всё равно требуют знания всех входящих в выражение типов статически во время компиляции, и несложно придумать такой пример, где это будет невозможно.
Опять же, я не помню было ли это изначально в том же виде. Но в любом случае всё опять неверно. Шаблоны не улучшают ситуацию — они работают, причём так, как нужно. И для этого ненужно создавать никакие базовые классы и прочий мусор.
К тому же, что следует из «где это будет невозможно»? Я могу так же придумать обратное. Что из этого следует? А ничего.
Вообщем всё так, как я и говорил. Смысл тот же, формулировки крайне сомнительны. Очень сильно походит на манипуляцию.
Про стандарт в том же ключе — что в нём прописано, для каких выражений диспатч статический, для каких динамический.
Не прописано. Там прописана семантика — а что там под — неважно.
Насчёт того, что лучше по производительности, когда компиляция не статическая — сейчас горячо обсуждается тема «Time to first plot». Там по анализу времени компиляции оказалось, что плохие аннотации типов хуже никаких, потому что компилятор пытается из них что-то выводить, но в конце концов без толку, а время тратится. Теперь вот обсуждают, как сделать, чтобы компилятор угадывал, где пошла «скриптуха», и бросал затею для неё что-то эффективное генерить.
Правильно — потому что система типов слабая. Тип и их отношения не могут адекватно представить необходимые требования. От того типы постоянно теряются. Кстати, а почему же они теряются? Наверное потому, что язык поощряет такое поведение.
Я выше там показывал подход С++, где даже для динамического диспатча типы не теряются. И именно поэтому то, о чём я говорю важно. Ведь по-сути именно на С++ пишут так как на скриптухе. И чем более сильная система типов — тем больше код становится похожим на скриптуху.
Pand5461 Автор
29.09.2019 13:14Так, давайте разберёмся с диспатчем на C++ и Julia.
Когда я пишу
abstract type Pet end, я ожидаю, что типPet— открытый, т.е. туда библиотека может добавить подтип.std::variant<Dog, Cat>имеет семантикуUnion{Dog, Cat}— но это не то, что подразумевается в контексте Julia.
Когда я пишу на Julia
encounter(Pet a, Pet b) = ..., я ожидаю две вещи:
- для всех типов, объявленных как подтипы
Petбудет выполняться тело функции - для всех остальных типов будет выдана ошибка о несоответствии типа.
Вы пишетеencounter(auto a, auto b)— это семантически соответствуетencounter(a, b)в Julia. Но в этом случае, если добавитьstruct Crocodile {string name;}с перегрузкойmeets()для него — функция будет пропускать крокодилов. А это мне не надо.
seslomayer
29.09.2019 16:08Когда я пишу abstract type Pet end, я ожидаю,
Я до сих пор не понимаю — зачем вы используете «я ожидаю»? У вас то кто-то ожидал, тем вы. Какая разница кто там и что ожидает? Вы ожидаете то, что вам привычно и это ничего не значит. Каждый ожидает своё — это не является чем-то состоятельным.
открытый, т.е. туда библиотека может добавить подтип.
Это допущение слабой системы типов скриптухи. Иначе ваша скриптуха работать не будет — это очевидно.
std::variant<Dog, Cat> имеет семантику Union{Dog, Cat} — но это не то, что подразумевается в контексте Julia.
Я, опять же, не понимаю к чему вы это пишите? Зачем вы задним числом придумываете новые обстоятельства? Про семантику юниона написал вам я, причём ещё давно и сразу. Почему эти откровения не случались до тезисов «нельзя»? К тому же, почему вы утверждали, что там динамического диспатча нет? Зачем вы игнорируете это обстоятельство.
для всех типов, объявленных как подтипы Pet будет выполняться тело функции
Повторю ещё раз. Ваши ожидания ничего не значат, как и мои. Про подтипы я уже говорил — это следствия слабой системы типов в этой скриптухе.
для всех остальных типов будет выдана ошибка о несоответствии типа.
Она и так будет выдана, если тип не соответствует необходимым инвариантам описанным в коде. Если что-то выглядит как пет — это пет. Если нужен явный пет — это так же можно указать.
Вы пишете encounter(auto a, auto b) — это семантически соответствует encounter(a, b) в Julia.
Очевидно, что нет. Попробуйте так написать.
Но в этом случае, если добавить struct Crocodile {string name;} с перегрузкой meets() для него — функция будет пропускать крокодилов. А это мне не надо.
А мне ненужно ваше поведение. Дальше что? Это ничего не значит.
В С++ используются куда более мощные и фундаментальные подходы. Всё это создано для обобщённого программирования, где почти всегда нужна структурная типизация и автоматический вывод типов. С этими аннотациями вы далеко не уедете.
Если же нужны ограничения — они так же описываются. Можно явно указать, что типы должны наследовать Pet, либо что угодно. В С++ это работает так. Полная свобода, а если нужны ограничения — они описываются.
Но из этого никак не следует то, что этого нет, либо это как-то плохо. Оно сделано иначе и очевидно, что вам может быть это непривычно. Но это базовая реакция на другое, но другое не значит непонятно/не может/хуже, повторюсь.
К тому же, ваш тезис про «будет пропускать крокодилов» крайне слаб. Ведь мне ничего не мешает сделать крокодила подтипом. Это сомнительный путь к критике структурной типизации, вернее в нём конечно что-то есть, но всё это крайне спорно. Здесь можно прийти к каким-то — действительно могут быть две разные иерархии объектов примерно одинаковым интерфейсом.
Но если интерфейс одинаковый, то и использование, наверное, будет одинаковым/похожим? И можно много кода общего написать, а у вас это сделать не получится. Надо будет добавлять ещё один уровень наследования, а там и недалеко запутаться.Pand5461 Автор
29.09.2019 19:26Ох. Да, ваш код правильный для конкретного юзкейса.
Я подразумевал под "правильным" поведением "так, как в Julia" с учётом расширяемости типа, ограничения по аргументам и т.д. (не уверен, что полностью могу сформулировать) и писал выше, что код "неправильный" имея в виду именно неполное соответствие этой семантике.
Логично предположить, что разработчик Julia, выступая на JuliaCon, мог иметь в виду примерно такие же умолчания. И продемонстрировать намеренно неправильным кодом хотел только лишь что "поведение в C++ как в Julia" не значит "код на C++ похож на код на Julia".
Единственное, что утверждается о C++ — что мультиметоды там не абстрагированы.
Если вы считаете, что они не нужны или что нужны, но в Julia реализованы неправильно — давайте это обсудим.
Это сомнительный путь к критике структурной типизации
Вы опять куда-то не в ту степь. Я критиковал исключительно то, что вы написали, потому что подразумевал, что, как и приведённый код на Julia, код на C++ не должен пропускать крокодилов, если крокодилы не объявлены петами.
Но если интерфейс одинаковый, то и использование, наверное, будет одинаковым/похожим? И можно много кода общего написать, а у вас это сделать не получится.
Тут есть два варианта. Один — ввести юнион типов, которые реализуют интерфейс. Тривиально, имеет определённые преимущества с точки зрения статических гарантий, но не расширяемо. Второй — Tim Holy's trait trick, который, на мой взгляд, лучше, хоть всё равно закат солнца вручную.
# вспомогательные типы abstract type HasInterface end abstract type DoesntHaveInterface end # a_function(x) нужно определить только для типов, реализующих интерфейс X a_function(x::T) where T = _a_function(has_interface_x(T), x) _a_function(::HasInterface, x::T) where T = <function body> # для SomeType пусть интерфейс реализован has_interface_x(::SomeType) = HasInterface() # для произвольного типа считаем, что интерфейс не реализован has_interface_x(::T) where T = DoesntHaveInterface()
Здесь
а)has_interface_x(T)вычисляется при компиляцииa_function()под конкретный тип, поэтому в рантайме просто вызывается одна из конкретных реализаций_a_function()
б) если вводится тип, реализующий интерфейс, то его можно добавить к списку, определив для негоhas_interface_x(::NewType) = HasInterface()
в) в иерархию типов это вообще никак не вмешивается; т.е. если вдруг обнаружилось, что для типовRavenиWritingDeskможно абстрактно записать какой-то алгоритм — под них можно сделать трейт и написать этот алгоритм (ну или записать его дляUnion{Raven, WritingDesk}, если есть разумные ожидания, что других типов с таким трейтом не предвидится).seslomayer
30.09.2019 08:19Единственное, что утверждается о C++ — что мультиметоды там не абстрагированы.
Проблема не в этом. Я не вижу от вас какого-либо иного объяснения подобным тезисам. Очевидно, что разные языки работают по-разному — подобные сравнения и утверждения либо глупость, либо манипуляция. Я не вижу третьего варианта, похоже и вы тоже.
Вы опять куда-то не в ту степь. Я критиковал исключительно то, что вы написали, потому что подразумевал, что, как и приведённый код на Julia, код на C++ не должен пропускать крокодилов, если крокодилы не объявлены петами.
Ну вы ведь понимаете, что эта критика крайне субъективна? И это моя основная претензия. Очевидно, что можно взять любой подход и надёргать примеров удобных, а потом называть это критикой. Это не особо конструктивно.
Второй — Tim Holy's trait trick, который, на мой взгляд, лучше, хоть всё равно закат солнца вручную.
В конечном итоге всё придёт туда, куда практически пришел С++ — godbolt.org/z/T-qBZz
Действительно, организовывать ограничения на базовых типах в некоторых случаях может быть удобно, но в ещё больших случаях это одни проблемы.
И данная проблема — не одна. Все типы с общей базой должны быть доступны через один интерфейс. Семантический статический диспатч не накладывает таких ограничений. Про затирание типов я уже писал. Там целый букет.
И перегрузка, которая работает в данном случае — это действительно сильно и она решает много проблем. Я нигде не отрицал полезность данной фичи, но она полезна только для динамического диспатча.
Если вы считаете, что они не нужны или что нужны, но в Julia реализованы неправильно — давайте это обсудим.
Да, я считаю. В большинстве случае можно не терять типы, а в ситуации с жулией — этих мест ещё больше, чем в С++. Я выше показал 1в1 тоже самое, только оно не работает в случае с динамикой.
И оно куда мощнее простого отношения база-наследники. Можно строить какие угодно иерархии, можно выбирать функции исходя из произвольной логики. Выше вы тоже пытаетесь написать что-то подобное, но функционал крайне скуден.
По-сути ради некой сомнительной фишки язык потерял возможности, которые несоизмеримо большие и лучшие. Я не знаю назначения вашего языка и сужу чисто со своей колокольни. Возможно обобщённое программирование, мета-программирование вам не особо нужно(кроме каких-то совсем базовых вещей).
И самое важное то, что язык с житом и задизайненный под жит — куда более мощный, нежели С++. А решил проблемы с динамическим диспатчем можно достаточно просто, особенно в вашем случае. Достаточно реализовать какой-то сахар, который, допустим, будет делать тоже самое, что я сделал в С++, только автоматически.
- для всех типов, объявленных как подтипы
seslomayer
28.09.2019 16:26А, это уже понятный тезис. Но это на практике не имеет никакого значения, как говорят питонисты (сарказм).
Хвалебные статьи, сравнения и прочее — всё это важно. Но ещё важнее следить за их состоятельностью. Ведь может получиться как-то так. Ведь адекватное сравнение и оценка — это залог успешного развития.
vikarti
28.09.2019 06:24Пример с новыми методами класс RGB и мол только два метода существует… это не везде так.
В Swift и Kotlin вполне себе написать в своем коде extension method для любого класса хоть системного и использовать.andreyverbin
29.09.2019 19:42extension methods != multiple dispatch. С помощью extension methods вы не сможете реализовать интерфейс.
Tiendil
28.09.2019 11:24Существует ли глубокое описание реализации механизма множественной диспетчеризации в Julia?
pdima
интересно, а почему С++ версия не на шаблонах
Pand5461 Автор
Больше кода бы потребовалось, чтобы продемонстрировать ту же идею — перегрузка функций и шаблоны работают только когда тип статически известен на этапе компиляции.
Если определяться, кто там будет кошкой, кто собакой, будет на основе ввода от пользователя — шаблоны тоже не помогут.
seslomayer
Нет.
Помогут. Единственный нюанс в том, что в С++(пока) не может получить всех наследников pet и нужно будет перечислить их руками. Диспатч без потери типа действует по принципу юниона, а его нужно забивать руками.