Ответ 1
Доктор. Тезис Безансона, безусловно, является лучшим источником для описания внутренних органов Юлии:
4.3 Диспетчерская система
Система диспетчеризации Julias сильно напоминает многотодовые системы, найденные на некоторых объектно-ориентированных языках [17, 40, 110, 31, 32, 33]. Однако мы предпочитаем термин "отправка по типу", так как наша система фактически работает, отправив один аргумент типа tuple. Разница тонкая и во многих случаях не заметна, но имеет важные концептуальные последствия. Это означает, что методы не обязательно ограничиваются указанием типа для каждого аргумента "слот". Например, сигнатура метода может быть
Union{Tuple{Any,Int}, Tuple{Int,Any}}, которая соответствует вызовам, где оба, но не обязательно оба из двух аргументов, представляют собой Int. 2
Раздел продолжает описывать кеши типа и метода, сортировку по специфичности, параметрическую диспетчеризацию и неоднозначность. Обратите внимание, что типы кортежей являются ковариантными (в отличие от всех других типов Юлиана), чтобы соответствовать ковариантному поведению отправки метода.
Самый большой ключ здесь состоит в том, что определения методов сортируются по специфичности, поэтому это просто линейный поиск, чтобы проверить, является ли тип кортежа аргументов подтипом подписи. Так что просто O (n), правильно? Проблема в том, что проверка подтипов с полной общностью (в том числе Unions и TypeVars и т.д.) Сложна. На самом деле очень сложно. Хуже, чем NP-полный, он оценивается как П P 2 (см. полиномиальная иерархия) - это, даже если P = NP, эта проблема по-прежнему будет принимать неполиномиальное время! Это может быть даже PSPACE или хуже.
Конечно, лучшим источником того, как он работает, является реализация в JuliaLang/julia/src/gf.c (gf = общая функция). Там есть довольно полезный комментарий:
Кэш методов делится на три части: один для подписей, где первый аргумент - одноэлементный вид (
Type{Foo}), один из которых индексируется UID первого типа аргумента в обычных случаях и резерв таблица всего остального.
Итак, ответ на ваш вопрос о сложности поиска метода: "это зависит". При первом вызове метода с новым набором типов аргументов он должен пройти этот линейный поиск, ища соответствие подтипа. Если он находит один, он специализируется на этом методе для конкретных аргументов и помещает его в один из этих кешей. Это означает, что перед тем, как приступать к поиску жесткого подтипа, Julia может выполнить быструю проверку равенства с уже увиденными методами... и количество методов, которые необходимо проверить, еще больше уменьшено, поскольку кеши хранятся как hashtables на основе первого аргумента.
Но, на самом деле, ваш вопрос касался сложности отправки во время выполнения. В этом случае ответ довольно часто "какая отправка?" - потому что он был полностью удален! Джулия использует LLVM как компилятор с чуть-чуть впереди, где методы компилируются по требованию по мере необходимости. В исполняемом коде Julia типы должны быть конкретно выведены во время компиляции, поэтому отправка также может выполняться во время компиляции. Это полностью исключает служебные расходы диспетчера времени выполнения и потенциально даже встрояет найденный метод непосредственно в тело вызывающего абонента (если оно мало), чтобы удалить все служебные служебные вызовы функций и разрешить дальнейшие оптимизации вниз по течению. Если типы не конкретизированы, есть другие ошибки производительности, и я не профилировал, чтобы узнать, сколько времени обычно тратится на отправку. Есть способы, чтобы оптимизировать этот случай дальше, но, вероятно, большая рыба, чтобы жарить в первую очередь... и на данный момент, как правило, проще всего просто создать стабильную систему с горячим контуром.