Оптимизировать сильно векторизованный код в Юлии? - PullRequest
Новая
       8

Оптимизировать сильно векторизованный код в Юлии?

0 голосов
/ 15 января 2019

Я хочу оптимизировать следующий код в Julia, он написан в сильно векторизованной форме, в которой такие языки, как MATLAB, превосходят. Точно такой же код в MATLAB занимает Elapsed time is 0.277608 seconds., это в 2,8 раза быстрее, поэтому я подумал, что что-то можно сделать в Джулии. Честно говоря, я заметил, что MATLAB по умолчанию использует многопоточность, поэтому нет проблем, если многопоточность включена и в Julia. Спасибо за помощь. 

function fit_xlin(x, y, w)
    n = length(x)
    regularization = 1.0e-5
    xx_0_0 = fill(sum(w.*1)   , n)
    xx_1_0 = fill(sum(w.*x)   , n)
    xx_0_1 = fill(sum(w.*x)   , n)
    xx_1_1 = fill(sum(w.*x.*x), n)
    xy_0   = fill(sum(w.*y)   , n)
    xy_1   = fill(sum(w.*x.*y), n)
    xx_1_0 .+= regularization
    xx_0_1 .+= regularization

    xxk_0_0 = xx_0_0 .- w.*1
    xxk_1_0 = xx_1_0 .- w.*x
    xxk_0_1 = xx_0_1 .- w.*x
    xxk_1_1 = xx_1_1 .- w.*x.*x
    xyk_0   = xy_0   .- w.*y
    xyk_1   = xy_1   .- w.*x.*y

    det = xxk_0_0.*xxk_1_1 .- xxk_0_1.*xxk_1_0
    c0  = (xxk_1_1.*xyk_0  .- xxk_0_1.*xyk_1)./det
    c1  = (-xxk_1_0.*xyk_0 .+ xxk_0_0.*xyk_1)./det

    y_est = c0 .+ c1.*x
end 

using BenchmarkTools
function test_xlin()
    x = rand( 0.0:4.0, 5000_000)
    y = rand( 0.0:4.0, 5000_000)
    w = rand( 0.0:4.0, 5000_000)
    @btime fit_xlin($x, $y, $w)
end

Это время как: 

    julia> test_xlin();
      775.292 ms (46 allocations: 877.38 MiB)

1 Ответ

0 голосов
/ 16 января 2019

Вот код, который все еще векторизован, и он не использует многопоточность. На моем компьютере он работает более чем в два раза быстрее, чем оригинал, но кое-что еще можно сделать здесь.

Кстати, я серьезно сомневаюсь, что код Matlab особенно оптимизирован, так как происходят некоторые очень расточительные операции - ненужное распределение, ненужные операции (sum(w.*1) действительно плохо, умножение массива на 1 и выделение дополнительного массива в процессе это ужасно расточительно :) Кроме того, вам не нужно выделять какие-либо векторы xx_0_0, xx_1_0 в Matlab, вы можете просто использовать трансляцию, как в Джулии.

В любом случае, вот моя первая попытка: 

function fit_xlin2(x, y, w)
    regularization = 1.0e-5

    sumwx = (w' * x) + regularization
    sumwy = (w' * y)
    sumwxx = sum(a[1]*a[2]^2 for a in zip(w, x))
    sumwxy = sum(prod, zip(w, x, y))

    wx = w .* x
    xxk_0_0 = sum(w) .- w
    xxk_1_0 = sumwx .- wx
    xxk_1_1 = sumwxx .- wx .* x
    xyk_0 = sumwy .- w .* y
    xyk_1 = sumwxy .- wx .* y

    det = xxk_0_0 .* xxk_1_1 .- xxk_1_0 .* xxk_1_0
    c0  = (xxk_1_1 .* xyk_0  .- xxk_1_0 .* xyk_1)./det
    c1  = (-xxk_1_0 .* xyk_0 .+ xxk_0_0 .* xyk_1)./det

    return c0 .+ c1 .* x
end

Редактировать: Вы можете получить достаточное ускорение, если де-векторизовать основной цикл. Этот код ~ в 17 раз быстрее исходного кода Julia, все еще однопоточный и вполне читаемый: 

function fit_xlin_loop(x, y, w)
    if !(size(x) == size(y) == size(w))
        error("Input vectors must have the same size.")
    end

    regularization = 1.0e-5

    sumw = sum(w)
    sumwx = (w' * x) + regularization
    sumwy = (w' * y)
    sumwxx = sum(a[1]*a[2]^2 for a in zip(w, x))
    sumwxy = sum(prod, zip(w, x, y))

    y_est = similar(x)
    @inbounds for i in eachindex(y_est)
        wx = w[i] * x[i]
        xxk_0_0 = sumw - w[i]
        xxk_1_0 = sumwx - wx
        xxk_1_1 = sumwxx - wx * x[i]
        xyk_0 = sumwy - w[i] * y[i]
        xyk_1 = sumwxy - wx * y[i]

        det = xxk_0_0 * xxk_1_1 - xxk_1_0 * xxk_1_0
        c0  = (xxk_1_1 * xyk_0 - xxk_1_0 * xyk_1) / det
        c1  = (-xxk_1_0 * xyk_0 + xxk_0_0 * xyk_1) / det

        y_est[i] = c0 + c1 * x[i]
    end
    return y_est
end
...