Почему упрощенные математические уравнения работают (немного) медленнее, чем их эквиваленты с гораздо большим количеством операций в Джулии-Ланге? - PullRequest
3 голосов
/ 23 мая 2019

В курсе C ++ меня учили, что такие приемы, как избегать повторяющихся вычислений, используют больше сложений вместо умножения, избегая мощностей и так далее, чтобы повысить производительность. Однако когда я попытался оптимизировать код в Julia-Lang, я был удивлен противоположным результатом.

Например, вот несколько уравнений без математической оптимизации (все коды написаны в Julia 1.1, а не в JuliaPro):

function OriginalFunction( a,b,c,d,E )
    # Oprations' count:
    # sqrt: 4
    # ^: 14
    # * : 14
    # / : 10
    # +: 20
    # -: 6
    # = : 0+4
    x1 = (1/(1+c^2))*(-c*d+a+c*b-sqrt(E))
    y1 = d-(c^2*d)/(1+c^2)+(c*a)/(1+c^2)+(c^2*b)/(1+c^2)-(c*sqrt(E))/(1+c^2)

    x2 = (1/(1+c^2))*(-c*d+a+c*b+sqrt(E))
    y2 = d-(c^2*d)/(1+c^2)+(c*a)/(1+c^2)+(c^2*b)/(1+c^2)+(c*sqrt(E))/(1+c^2)

    return [ [x1;y1] [x2;y2] ]
end

Я оптимизировал их с помощью нескольких трюков, в том числе:

  1. (a*b + a*c) -> a*(b+c) потому что сложение быстрее, чем умножение.
  2. a^2 -> a*a избегать силовой операции.
  3. Если длинная операция используется хотя бы дважды, присвойте ее переменной, чтобы избежать повторных вычислений. Например:
x = a * (1+c^2); y = b * (1+c^2)
->
temp = 1+c^2
x = a * temp; y = b * temp
  1. Конвертируйте Int в Float64, чтобы компьютеру не приходилось это делать (во время выполнения или во время компиляции). Например:

1/x -> 1.0/x

Результат дает эквивалентные уравнения с гораздо меньшим количеством операций:

function SimplifiedFunction( a,b,c,d,E )
    # Oprations' count:
    # sqrt: 1
    # ^: 0
    # *: 9
    # /: 1
    # +: 4
    # -: 6
    # = : 5+4
    temp1 = sqrt(E)
    temp2 = c*(b - d) + a
    temp3 = 1.0/(1.0+c*c)
    temp4 = d - (c*(c*(d - b) - a))*temp3
    temp5 = (c*temp1)*temp3
    x1 = temp3*(temp2-temp1)
    y1 = temp4-temp5

    x2 = temp3*(temp2+temp1)
    y2 = temp4+temp5

    return [ [x1;y1] [x2;y2] ]
end

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

function Test2Functions( NumberOfTests::Real )
    local num = Int(NumberOfTests)
    # -- Generate random numbers
    local rands = Array{Float64,2}(undef, 5,num)
    for i in 1:num
        rands[:,i:i] = [rand(); rand(); rand(); rand(); rand()]
    end

    local res1 = Array{Array{Float64,2}}(undef, num)
    local res2 = Array{Array{Float64,2}}(undef, num)
    # - Test OriginalFunction
    @time for i in 1:num
        a,b,c,d,E = rands[:,i]
        res1[i] = OriginalFunction( a,b,c,d,E )
    end
    # - Test SimplifiedFunction
    @time for i in 1:num
        a,b,c,d,E = rands[:,i]
        res2[i] = SimplifiedFunction( a,b,c,d,E )
    end
    return res1, res2
end
Test2Functions( 1e6 )

Однако оказалось, что две функции используют одинаковое количество памяти, но упрощенная имеет больше времени для сбора мусора и работает примерно на 5% медленнее:

julia> Test2Functions( 1e6 )
  1.778731 seconds (7.00 M allocations: 503.540 MiB, 47.35% gc time)
  1.787668 seconds (7.00 M allocations: 503.540 MiB, 50.92% gc time)

julia> Test2Functions( 1e6 )
  1.969535 seconds (7.00 M allocations: 503.540 MiB, 52.05% gc time)
  2.221151 seconds (7.00 M allocations: 503.540 MiB, 56.68% gc time)

julia> Test2Functions( 1e6 )
  1.946441 seconds (7.00 M allocations: 503.540 MiB, 55.23% gc time)
  2.099875 seconds (7.00 M allocations: 503.540 MiB, 59.33% gc time)

julia> Test2Functions( 1e6 )
  1.836350 seconds (7.00 M allocations: 503.540 MiB, 53.37% gc time)
  2.011242 seconds (7.00 M allocations: 503.540 MiB, 58.43% gc time)

julia> Test2Functions( 1e6 )
  1.856081 seconds (7.00 M allocations: 503.540 MiB, 53.44% gc time)
  2.002087 seconds (7.00 M allocations: 503.540 MiB, 58.21% gc time)

julia> Test2Functions( 1e6 )
  1.833049 seconds (7.00 M allocations: 503.540 MiB, 53.55% gc time)
  1.996548 seconds (7.00 M allocations: 503.540 MiB, 58.41% gc time)

julia> Test2Functions( 1e6 )
  1.846894 seconds (7.00 M allocations: 503.540 MiB, 53.53% gc time)
  2.053529 seconds (7.00 M allocations: 503.540 MiB, 58.30% gc time)

julia> Test2Functions( 1e6 )
  1.896265 seconds (7.00 M allocations: 503.540 MiB, 54.11% gc time)
  2.083253 seconds (7.00 M allocations: 503.540 MiB, 58.10% gc time)

julia> Test2Functions( 1e6 )
  1.910244 seconds (7.00 M allocations: 503.540 MiB, 53.79% gc time)
  2.085719 seconds (7.00 M allocations: 503.540 MiB, 58.36% gc time)

Может ли кто-нибудь сказать мне, почему? Скорость 5%, вероятно, не стоит того, чтобы за нее бороться даже в некоторых критических по производительности кодах, но мне все еще любопытно: как я могу помочь компилятору Julia в создании более быстрого кода?

Ответы [ 2 ]

7 голосов
/ 23 мая 2019

Причина в том, что вы запускаете сборку мусора во втором цикле (а не в первом). Если вы выполните GC.gc() перед циклами, вы получите более сопоставимые результаты:

function Test2Functions( NumberOfTests::Real )
    local num = Int(NumberOfTests)
    # -- Generate random numbers
    local rands = Array{Float64,2}(undef, 5,num)
    for i in 1:num
        rands[:,i:i] = [rand(); rand(); rand(); rand(); rand()]
    end

    local res1 = Array{Array{Float64,2}}(undef, num)
    local res2 = Array{Array{Float64,2}}(undef, num)
    # - Test OriginalFunction
    GC.gc()
    @time for i in 1:num
        a,b,c,d,E = rands[:,i]
        res1[i] = OriginalFunction( a,b,c,d,E )
    end
    # - Test SimplifiedFunction
    GC.gc()
    @time for i in 1:num
        a,b,c,d,E = rands[:,i]
        res2[i] = SimplifiedFunction( a,b,c,d,E )
    end
    return res1, res2
end

# call this twice as the first time you may have precompilation issues
Test2Functions( 1e6 )
Test2Functions( 1e6 )

Однако, в общем, для проведения бенчмаркинга лучше использовать пакет BenchmarkTools.jl.

julia> function OriginalFunction()
           a,b,c,d,E = rand(5)
           x1 = (1/(1+c^2))*(-c*d+a+c*b-sqrt(E))
           y1 = d-(c^2*d)/(1+c^2)+(c*a)/(1+c^2)+(c^2*b)/(1+c^2)-(c*sqrt(E))/(1+c^2)
           x2 = (1/(1+c^2))*(-c*d+a+c*b+sqrt(E))
           y2 = d-(c^2*d)/(1+c^2)+(c*a)/(1+c^2)+(c^2*b)/(1+c^2)+(c*sqrt(E))/(1+c^2)
           return [ [x1;y1] [x2;y2] ]
       end
OriginalFunction (generic function with 2 methods)

julia>

julia> function SimplifiedFunction()
           a,b,c,d,E = rand(5)
           temp1 = sqrt(E)
           temp2 = c*(b - d) + a
           temp3 = 1.0/(1.0+c*c)
           temp4 = d - (c*(c*(d - b) - a))*temp3
           temp5 = (c*temp1)*temp3
           x1 = temp3*(temp2-temp1)
           y1 = temp4-temp5
           x2 = temp3*(temp2+temp1)
           y2 = temp4+temp5
           return [ [x1;y1] [x2;y2] ]
       end
SimplifiedFunction (generic function with 2 methods)

julia>

julia> using BenchmarkTools

julia> @btime OriginalFunction()
  136.211 ns (7 allocations: 528 bytes)
2×2 Array{Float64,2}:
 -0.609035  0.954271
  0.724708  0.926523

julia> @btime SimplifiedFunction()
  137.201 ns (7 allocations: 528 bytes)
2×2 Array{Float64,2}:
 0.284514  1.58639
 0.922347  0.979835

julia> @btime OriginalFunction()
  137.301 ns (7 allocations: 528 bytes)
2×2 Array{Float64,2}:
 -0.109814  0.895533
  0.365399  1.08743

julia> @btime SimplifiedFunction()
  136.429 ns (7 allocations: 528 bytes)
2×2 Array{Float64,2}:
 0.516157  1.07871
 0.219441  0.361133

И мы видим, что они имеют сопоставимую производительность. В общем, вы можете ожидать, что компиляторы Julia и LLVM сделают для вас большую часть оптимизаций такого типа (конечно, это не всегда гарантируется, но в этом случае кажется, что это происходит).

EDIT

Я упростил функции следующим образом:

function OriginalFunction( a,b,c,d,E )
    x1 = (1/(1+c^2))*(-c*d+a+c*b-sqrt(E))
    y1 = d-(c^2*d)/(1+c^2)+(c*a)/(1+c^2)+(c^2*b)/(1+c^2)-(c*sqrt(E))/(1+c^2)
    x2 = (1/(1+c^2))*(-c*d+a+c*b+sqrt(E))
    y2 = d-(c^2*d)/(1+c^2)+(c*a)/(1+c^2)+(c^2*b)/(1+c^2)+(c*sqrt(E))/(1+c^2)
    x1, y1, x2, y2
end

function SimplifiedFunction( a,b,c,d,E )
    temp1 = sqrt(E)
    temp2 = c*(b - d) + a
    temp3 = 1.0/(1.0+c*c)
    temp4 = d - (c*(c*(d - b) - a))*temp3
    temp5 = (c*temp1)*temp3
    x1 = temp3*(temp2-temp1)
    y1 = temp4-temp5
    x2 = temp3*(temp2+temp1)
    y2 = temp4+temp5
    x1, y1, x2, y2
end

Чтобы сосредоточиться только на ядре вычислений и запустить @code_native на них. Вот они (без комментариев, чтобы их укоротить).

        .text
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $112, %rsp
        vmovaps %xmm10, -16(%rbp)
        vmovaps %xmm9, -32(%rbp)
        vmovaps %xmm8, -48(%rbp)
        vmovaps %xmm7, -64(%rbp)
        vmovaps %xmm6, -80(%rbp)
        vmovsd  56(%rbp), %xmm8         # xmm8 = mem[0],zero
        vxorps  %xmm4, %xmm4, %xmm4
        vucomisd        %xmm8, %xmm4
        ja      L229
        vmovsd  48(%rbp), %xmm9         # xmm9 = mem[0],zero
        vmulsd  %xmm9, %xmm3, %xmm5
        vsubsd  %xmm5, %xmm1, %xmm5
        vmulsd  %xmm3, %xmm2, %xmm6
        vaddsd  %xmm5, %xmm6, %xmm10
        vmulsd  %xmm3, %xmm3, %xmm6
        movabsq $526594656, %rax        # imm = 0x1F633260
        vmovsd  (%rax), %xmm7           # xmm7 = mem[0],zero
        vaddsd  %xmm7, %xmm6, %xmm0
        vdivsd  %xmm0, %xmm7, %xmm7
        vsqrtsd %xmm8, %xmm8, %xmm4
        vsubsd  %xmm4, %xmm10, %xmm5
        vmulsd  %xmm5, %xmm7, %xmm8
        vmulsd  %xmm9, %xmm6, %xmm5
        vdivsd  %xmm0, %xmm5, %xmm5
        vsubsd  %xmm5, %xmm9, %xmm5
        vmulsd  %xmm3, %xmm1, %xmm1
        vdivsd  %xmm0, %xmm1, %xmm1
        vaddsd  %xmm5, %xmm1, %xmm1
        vmulsd  %xmm2, %xmm6, %xmm2
        vdivsd  %xmm0, %xmm2, %xmm2
        vaddsd  %xmm1, %xmm2, %xmm1
        vmulsd  %xmm3, %xmm4, %xmm2
        vdivsd  %xmm0, %xmm2, %xmm0
        vsubsd  %xmm0, %xmm1, %xmm2
        vaddsd  %xmm10, %xmm4, %xmm3
        vmulsd  %xmm3, %xmm7, %xmm3
        vaddsd  %xmm1, %xmm0, %xmm0
        vmovsd  %xmm8, (%rcx)
        vmovsd  %xmm2, 8(%rcx)
        vmovsd  %xmm3, 16(%rcx)
        vmovsd  %xmm0, 24(%rcx)
        movq    %rcx, %rax
        vmovaps -80(%rbp), %xmm6
        vmovaps -64(%rbp), %xmm7
        vmovaps -48(%rbp), %xmm8
        vmovaps -32(%rbp), %xmm9
        vmovaps -16(%rbp), %xmm10
        addq    $112, %rsp
        popq    %rbp
        retq
L229:
        movabsq $throw_complex_domainerror, %rax
        movl    $72381680, %ecx         # imm = 0x45074F0
        vmovapd %xmm8, %xmm1
        callq   *%rax
        ud2
        ud2
        nop

и

        .text
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $64, %rsp
        vmovaps %xmm7, -16(%rbp)
        vmovaps %xmm6, -32(%rbp)
        vmovsd  56(%rbp), %xmm0         # xmm0 = mem[0],zero
        vxorps  %xmm4, %xmm4, %xmm4
        vucomisd        %xmm0, %xmm4
        ja      L178
        vmovsd  48(%rbp), %xmm4         # xmm4 = mem[0],zero
        vsqrtsd %xmm0, %xmm0, %xmm0
        vsubsd  %xmm4, %xmm2, %xmm5
        vmulsd  %xmm3, %xmm5, %xmm5
        vaddsd  %xmm1, %xmm5, %xmm5
        vmulsd  %xmm3, %xmm3, %xmm6
        movabsq $526593928, %rax        # imm = 0x1F632F88
        vmovsd  (%rax), %xmm7           # xmm7 = mem[0],zero
        vaddsd  %xmm7, %xmm6, %xmm6
        vdivsd  %xmm6, %xmm7, %xmm6
        vsubsd  %xmm2, %xmm4, %xmm2
        vmulsd  %xmm3, %xmm2, %xmm2
        vsubsd  %xmm1, %xmm2, %xmm1
        vmulsd  %xmm3, %xmm1, %xmm1
        vmulsd  %xmm1, %xmm6, %xmm1
        vsubsd  %xmm1, %xmm4, %xmm1
        vmulsd  %xmm3, %xmm0, %xmm2
        vmulsd  %xmm2, %xmm6, %xmm2
        vsubsd  %xmm0, %xmm5, %xmm3
        vmulsd  %xmm3, %xmm6, %xmm3
        vsubsd  %xmm2, %xmm1, %xmm4
        vaddsd  %xmm5, %xmm0, %xmm0
        vmulsd  %xmm0, %xmm6, %xmm0
        vaddsd  %xmm1, %xmm2, %xmm1
        vmovsd  %xmm3, (%rcx)
        vmovsd  %xmm4, 8(%rcx)
        vmovsd  %xmm0, 16(%rcx)
        vmovsd  %xmm1, 24(%rcx)
        movq    %rcx, %rax
        vmovaps -32(%rbp), %xmm6
        vmovaps -16(%rbp), %xmm7
        addq    $64, %rsp
        popq    %rbp
        retq
L178:
        movabsq $throw_complex_domainerror, %rax
        movl    $72381680, %ecx         # imm = 0x45074F0
        vmovapd %xmm0, %xmm1
        callq   *%rax
        ud2
        ud2
        nopl    (%rax,%rax)

Возможно, вам не захочется подробно разбирать его, но вы можете видеть, что упрощенная функция использует несколько меньше инструкций, но только несколько, что может удивить, если вы сравните исходные коды. Например, оба кода вызывают sqrt только один раз (поэтому оптимизированы множественные вызовы sqrt в первой функции).

0 голосов
/ 24 мая 2019

Во многом причина в том, что Джулия автоматически выполняет некоторые из ваших оптимизаций (в частности, я знаю, что фиксированные целочисленные степени компилируются в эффективные последовательности умножений). Постоянное распространение, вероятно, также может позволить компилятору превратить 1 в 1,0. В общем, компилятор Джулии очень агрессивен в том, чтобы сделать ваш код быстрым, пока он может делать вывод типов.

...