В чем разница между @code_native, @code_typed и @code_llvm в Джулии?

Ответ 1

Стандартная реализация CPython Python анализирует исходный код и делает некоторую предварительную обработку и упрощение - ака "понижение" - превращение ее в удобный для пользователя, удобный для восприятия формат, называемый " bytecode". Это то, что отображается, когда вы "разбираете" функцию Python. Этот код не является исполняемым аппаратным обеспечением - он "исполняется" интерпретатором CPython. Формат байт-кода CPython довольно прост, отчасти потому, что то, что интерпретаторы имеют тенденцию делать хорошо - если байт-код слишком сложный, он замедляет работу интерпретатора, а отчасти потому, что сообщество Python имеет тенденцию повышать премию по простоте, иногда ценой высокой производительности.

Реализация Julia не интерпретируется, она точно в срок (JIT) скомпилирована. Это означает, что когда вы вызываете функцию, она преобразуется в машинный код, который выполняется непосредственно на собственном оборудовании. Этот процесс довольно немного сложнее, чем синтаксический анализ и понижение до байт-кода, что делает Python, но взамен этой сложности Джулия получает свою прописную скорость. (PyPy JIT для Python также намного сложнее, чем CPython, но также, как правило, намного быстрее - повышенная сложность - довольно типичная стоимость для скорости.) Четыре уровня "разборки" кода Julia дают вам доступ к представлению метода Julia реализация для конкретных типов аргументов на разных этапах преобразования из исходного кода в машинный код. Я буду использовать следующую функцию, которая вычисляет следующее число Фибоначчи после аргумента в качестве примера:

function nextfib(n)
    a, b = one(n), one(n)
    while b < n
        a, b = b, a + b
    end
    return b
end

julia> nextfib(5)
5

julia> nextfib(6)
8

julia> nextfib(123)
144

Сниженный код. Макрос @code_lowered отображает код в формате, который ближе всего к байтовому коду Python, но вместо того, чтобы быть предназначенным для выполнения интерпретатором, он предназначен для дальнейшей трансформации с помощью компилятор. Этот формат в значительной степени является внутренним и не предназначен для потребления человеком. Код преобразуется в " одно статическое присваивание", в котором "каждая переменная назначается ровно один раз, и каждая переменная определяется до ее использования". Циклы и условные обозначения преобразуются в gotos и метки, используя единую конструкцию unless/goto (это не отображается в юлиле пользовательского уровня). Здесь наш примерный код в пониженной форме (в Julia 0.6.0-pre.beta.134, который есть именно то, что у меня есть):

julia> @code_lowered nextfib(123)
CodeInfo(:(begin
        nothing
        SSAValue(0) = (Main.one)(n)
        SSAValue(1) = (Main.one)(n)
        a = SSAValue(0)
        b = SSAValue(1) # line 3:
        7:
        unless b < n goto 16 # line 4:
        SSAValue(2) = b
        SSAValue(3) = a + b
        a = SSAValue(2)
        b = SSAValue(3)
        14:
        goto 7
        16:  # line 6:
        return b
    end))

Вы можете увидеть узлы SSAValue и конструкторы unless/goto и метки. Это не так сложно читать, но опять же, это также не означает, что это будет просто для потребления человеком. Пониженный код не зависит от типов аргументов, за исключением того, что они определяют, для какого тела метода вызывать - до тех пор, пока тот же метод вызывается, применяется тот же пониженный код.

Типированный код. Макрос @code_typed представляет реализацию метода для определенного набора типов аргументов после ввода типа и вставка. Это воплощение кода похоже на пониженную форму, но с выражениями, аннотированными информацией о типе, и некоторыми вызовами общих функций, замененными их реализациями. Например, вот код типа для нашей примерной функции:

julia> @code_typed nextfib(123)
CodeInfo(:(begin
        a = 1
        b = 1 # line 3:
        4:
        unless (Base.slt_int)(b, n)::Bool goto 13 # line 4:
        SSAValue(2) = b
        SSAValue(3) = (Base.add_int)(a, b)::Int64
        a = SSAValue(2)
        b = SSAValue(3)
        11:
        goto 4
        13:  # line 6:
        return b
    end))=>Int64

Вызовы one(n) заменены литеральным значением Int64 1 (в моей системе по умолчанию используется целочисленный тип Int64). Выражение b < n было заменено его реализацией в терминах slt_int intrinsic ( "целое число со знаком меньше" ) и результат этого был аннотирован с типом возврата Bool. Выражение a + b также было заменено его реализацией в терминах add_int intrinsic, а его тип результата аннотируется как Int64. И возвращаемый тип всего тела функции был аннотирован как Int64.

В отличие от пониженного кода, который зависит только от типов аргументов для определения тела метода, детали типизированного кода зависят от типов аргументов:

julia> @code_typed nextfib(Int128(123))
CodeInfo(:(begin
        SSAValue(0) = (Base.sext_int)(Int128, 1)::Int128
        SSAValue(1) = (Base.sext_int)(Int128, 1)::Int128
        a = SSAValue(0)
        b = SSAValue(1) # line 3:
        6:
        unless (Base.slt_int)(b, n)::Bool goto 15 # line 4:
        SSAValue(2) = b
        SSAValue(3) = (Base.add_int)(a, b)::Int128
        a = SSAValue(2)
        b = SSAValue(3)
        13:
        goto 6
        15:  # line 6:
        return b
    end))=>Int128

Это типизированная версия функции nextfib для аргумента Int128. Литерал 1 должен быть расшифрован до Int128, а типы результатов операций имеют тип Int128 вместо Int64. Набранный код может быть совсем другим, если реализация типа значительно отличается. Например, nextfib для BigInts значительно больше задействован, чем для простых "битовых типов", таких как Int64 и Int128:

julia> @code_typed nextfib(big(123))
CodeInfo(:(begin
        $(Expr(:inbounds, false))
        # meta: location number.jl one 164
        # meta: location number.jl one 163
        # meta: location gmp.jl convert 111
        [email protected]_5 = $(Expr(:invoke, MethodInstance for BigInt(), :(Base.GMP.BigInt))) # line 112:
        $(Expr(:foreigncall, (:__gmpz_set_si, :libgmp), Void, svec(Ptr{BigInt}, Int64), :(&[email protected]_5), :([email protected]_5), 1, 0))
        # meta: pop location
        # meta: pop location
        # meta: pop location
        $(Expr(:inbounds, :pop))
        $(Expr(:inbounds, false))
        # meta: location number.jl one 164
        # meta: location number.jl one 163
        # meta: location gmp.jl convert 111
        [email protected]_6 = $(Expr(:invoke, MethodInstance for BigInt(), :(Base.GMP.BigInt))) # line 112:
        $(Expr(:foreigncall, (:__gmpz_set_si, :libgmp), Void, svec(Ptr{BigInt}, Int64), :(&[email protected]_6), :([email protected]_6), 1, 0))
        # meta: pop location
        # meta: pop location
        # meta: pop location
        $(Expr(:inbounds, :pop))
        a = [email protected]_5
        b = [email protected]_6 # line 3:
        26:
        $(Expr(:inbounds, false))
        # meta: location gmp.jl < 516
        SSAValue(10) = $(Expr(:foreigncall, (:__gmpz_cmp, :libgmp), Int32, svec(Ptr{BigInt}, Ptr{BigInt}), :(&b), :(b), :(&n), :(n)))
        # meta: pop location
        $(Expr(:inbounds, :pop))
        unless (Base.slt_int)((Base.sext_int)(Int64, SSAValue(10))::Int64, 0)::Bool goto 46 # line 4:
        SSAValue(2) = b
        $(Expr(:inbounds, false))
        # meta: location gmp.jl + 258
        [email protected]_7 = $(Expr(:invoke, MethodInstance for BigInt(), :(Base.GMP.BigInt))) # line 259:
        $(Expr(:foreigncall, ("__gmpz_add", :libgmp), Void, svec(Ptr{BigInt}, Ptr{BigInt}, Ptr{BigInt}), :(&[email protected]_7), :([email protected]_7), :(&a), :(a), :(&b), :(b)))
        # meta: pop location
        $(Expr(:inbounds, :pop))
        a = SSAValue(2)
        b = [email protected]_7
        44:
        goto 26
        46:  # line 6:
        return b
    end))=>BigInt

Это отражает тот факт, что операции с BigInts довольно сложны и связаны с распределением памяти и вызовами внешней библиотеки GMP (libgmp).

LLVM IR. Юля использует структуру компилятора LLVM для генерации машинного кода. LLVM определяет ассемблерный язык, который он использует в качестве общего промежуточного представления (IR) между различными проходами оптимизации компилятора и другими инструментами в рамках. Существуют три изоморфные формы LLVM IR:

• Бинарное представление, компактное и машиночитаемое.
• Текстовое представление, которое является многословным и несколько читаемым человеком.
• Представление в памяти, которое генерируется и потребляется библиотеками LLVM.

Julia использует LLVM С++ API для создания LLVM IR в памяти (форма 3), а затем вызывает некоторые профили оптимизации LLVM в этой форме. Когда вы выполняете @code_llvm, вы видите LLVM IR после генерации и некоторые оптимизации на высоком уровне. Вот код LLVM для нашего текущего примера:

julia> @code_llvm nextfib(123)

define i64 @julia_nextfib_60009(i64) #0 !dbg !5 {
top:
  br label %L4

L4:                                               ; preds = %L4, %top
  %storemerge1 = phi i64 [ 1, %top ], [ %storemerge, %L4 ]
  %storemerge = phi i64 [ 1, %top ], [ %2, %L4 ]
  %1 = icmp slt i64 %storemerge, %0
  %2 = add i64 %storemerge, %storemerge1
  br i1 %1, label %L4, label %L13

L13:                                              ; preds = %L4
  ret i64 %storemerge
}

Это текстовая форма LLVM IR в памяти для реализации метода nextfib(123). LLVM читать нелегко - он не предназначен для написания или чтения людьми большую часть времени, но он полностью указан и документирован. Как только вы получите это, это не трудно понять. Этот код перескакивает на метку L4 и инициализирует "регистры" %storemerge1 и %storemerge значением i64 (LLVM name for Int64) 1 (их значения производятся по-разному при переходе с разных местоположения - то, что делает инструкция phi). Затем он сравнивает icmp slt %storemerge с регистром %0 - который содержит аргумент, нетронутый для всего выполнения метода, и сохраняет результат сравнения в регистре %1. Он выполняет add i64 на %storemerge и %storemerge1 и сохраняет результат в регистр %2. Если %1 истинно, оно возвращается обратно к L4 и в противном случае оно переходит к L13. Когда код возвращается к L4, регистр %storemerge1 получает предыдущие значения %storemerge и %storemerge получает предыдущее значение %2.

Собственный код.. Поскольку Julia выполняет собственный код, последняя форма, которую принимает реализация метода, - это то, что машина фактически выполняет. Это всего лишь двоичный код в памяти, который довольно трудно читать, поэтому люди изобретали различные формы "языка ассемблера", которые представляют собой инструкции и регистры с именами и имеют некоторый простой синтаксис, чтобы помочь выразить какие инструкции. В общем, язык ассемблера остается близким к индивидуальному соответствию с машинным кодом, в частности, всегда можно "разобрать" машинный код в код сборки. Вот наш пример:

julia> @code_native nextfib(123)
    .section    __TEXT,__text,regular,pure_instructions
Filename: REPL[1]
    pushq   %rbp
    movq    %rsp, %rbp
    movl    $1, %ecx
    movl    $1, %edx
    nop
L16:
    movq    %rdx, %rax
Source line: 4
    movq    %rcx, %rdx
    addq    %rax, %rdx
    movq    %rax, %rcx
Source line: 3
    cmpq    %rdi, %rax
    jl  L16
Source line: 6
    popq    %rbp
    retq
    nopw    %cs:(%rax,%rax)

Это на Intel Core i7, который находится в семействе процессоров x86_64. Он использует только стандартные целые инструкции, поэтому не важно, что такое архитектура, но вы можете получить разные результаты для некоторого кода в зависимости от конкретной архитектуры вашего компьютера, поскольку JIT-код может отличаться для разных систем. Команды pushq и movq в начале представляют собой стандартную преамбулу функции, сохраняющую регистры в стеке; аналогично, popq восстанавливает регистры, а retq возвращается из функции; nopw - это 2-байтная команда, которая ничего не делает, включая просто для заполнения длины функции. Итак, мясо кода выглядит так:

    movl    $1, %ecx
    movl    $1, %edx
    nop
L16:
    movq    %rdx, %rax
Source line: 4
    movq    %rcx, %rdx
    addq    %rax, %rdx
    movq    %rax, %rcx
Source line: 3
    cmpq    %rdi, %rax
    jl  L16

Инструкции movl в верхнем регистре инициализации с 1 значением. Команды movq перемещают значения между регистрами, а команда addq добавляет регистры. Команда cmpq сравнивает два регистра и jl либо возвращается к L16, либо продолжает возвращаться из функции. Эта горстка целочисленных машинных команд в узком цикле - это именно то, что выполняется, когда выполняется вызов функции Julia, представленный в немного более приятной для человека форме. Легко понять, почему он работает быстро.

Если вы заинтересованы в компиляции JIT в целом по сравнению с интерпретируемыми реализациями, у Eli Bendersky есть отличная пара сообщений в блоге, где он перешел от простой интерпретаторной реализации языка к (простой) оптимизирующей JIT для одного и того же языка

• http://eli.thegreenplace.net/2017/adventures-in-jit-compilation-part-1-an-interpreter/
• http://eli.thegreenplace.net/2017/adventures-in-jit-compilation-part-2-an-x64-jit.html