Почему эти две части кода Джулии работают так по-разному? - PullRequest
0 голосов
/ 01 ноября 2018
function c1()
        x::UInt64 = 0
        while x<= (10^8 * 10)
                x+=1
        end
end

function c2()
        x::UInt64 = 0
        while x<= (10^9)
                x+=1
        end
end

function c3()
        x::UInt64 = 0
        y::UInt64 = 10^8 * 10
        while x<= y
                x+=1
        end
end

function c4()
        x::UInt64 = 0
        y::UInt64 = 10^9
        while x<= y
                x+=1
        end
end

Должен быть таким же, верно?

@time c1()

0.019102 seconds (40.99 k allocations: 2.313 MiB)

@time c1()

0.000003 seconds (4 allocations: 160 bytes)

@time c2()

9.205925 seconds (47.89 k allocations: 2.750 MiB)

@time c2()

9.015212 seconds (4 allocations: 160 bytes)

@time c3()

0.019848 seconds (39.23 k allocations: 2.205 MiB)

@time c3()

0.000003 seconds (4 allocations: 160 bytes)

@time c4()

0.705712 seconds (47.41 k allocations: 2.719 MiB)

@time c4()

0.760354 seconds (4 allocations: 160 bytes)

Ответы [ 2 ]

0 голосов
/ 01 ноября 2018

Речь идет об оптимизации литералов Юлией во время компиляции с использованием степени квадратов. Джулия может оптимизировать, если показатель степени может быть получен только путем умножения на квадрат или мощность 0,1,2,3. Я полагаю, что это сделано путем понижения x^p до x^Val{p} для целого числа p и использования специализации компилятора (или встраивания плюс метапрограммирование, я не уверен, что здесь правильный термин, но это то, что вы найдете в Лиспе; аналогичные методы используются для автоматического дифференцирования от источника к источнику в Джулии, см. Zygote.jl ) методы понижения кода до константы, если p равно 0,1,2,3 или степень 2.

Джулия понижает 10^8 до встроенный literal_pow (а затем power_by_squaring), и это понижается до постоянной, затем Джулия понижает constant * 10, чтобы получить другую постоянную, а затем реализует все время, пока цикл не нужен и удаляет цикл и так далее, все во время компиляции .

Если вы измените 10^8 на 10^7 в c1, вы увидите, что он будет оценивать число и цикл во время выполнения. Однако, если вы замените 10^8 на 10^4 или 10^2, вы увидите, что он будет обрабатывать все вычисления во время компиляции. Я думаю, что julia не настроена специально на оптимизацию во время компиляции, если показатель степени равен степени 2, но вместо этого компилятор оказывается способным оптимизировать (понижая код до константы) код только для этого случая.

Случай, в котором p равен 1,2,3, жестко запрограммирован в Юлии. Это снова оптимизируется за счет снижения кода до встроенной версии literal_pow и последующей специализации компиляции.

Вы можете использовать макросы @code_llvm и @code_native, чтобы увидеть, что происходит. Давайте попробуем.

julia> f() = 10^8*10
julia> g() = 10^7*10

julia> @code_native f()
.text
; Function f {
; Location: In[101]:2
    movl    $1000000000, %eax       # imm = 0x3B9ACA00
    retq
    nopw    %cs:(%rax,%rax)
;}

julia> @code_native g()
.text
; Function g {
; Location: In[104]:1
; Function literal_pow; {
; Location: none
; Function macro expansion; {
; Location: none
; Function ^; {
; Location: In[104]:1
    pushq   %rax
    movabsq $power_by_squaring, %rax
    movl    $10, %edi
    movl    $7, %esi
    callq   *%rax
;}}}
; Function *; {
; Location: int.jl:54
    addq    %rax, %rax
    leaq    (%rax,%rax,4), %rax
;}
    popq    %rcx
    retq
;}

См. f() оказывается просто константой, в то время как g() будет оценивать вещи во время выполнения.

Я думаю, что Джулия начала трюк с целочисленным возведением в степень этот коммит , если вы хотите копать больше.

РЕДАКТИРОВАТЬ: Давайте оптимизировать время компиляции c2

Я также подготовил функцию для вычисления показателей целых и целых чисел, с помощью которых Юлия также будет оптимизировать для показателей не от степени 2. Я не уверен, что это правильно во всех случаях.

@inline function ipow(base::Int, exp::Int)
    result = 1;
    flag = true;
    while flag
        if (exp & 1  > 0)
            result *= base;
        end
        exp >>= 1;
        base *= base;
        flag = exp != 0
    end

    return result;
end

Теперь замените 10^9 in c2 на ipow(10,9) и наслаждайтесь мощью оптимизации во время компиляции.

Также см. в этом вопросе для вычисления мощности по квадратам.

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

0 голосов
/ 01 ноября 2018

2-е ОБНОВЛЕНИЕ: Проверьте hckr ответ. Намного лучше, чем у меня.

ОБНОВЛЕНИЕ: Это не исчерпывающий ответ. Столько, сколько мне удалось разгадать, и мне пришлось сейчас сдаться из-за нехватки времени.

Я, вероятно, не лучший человек, чтобы ответить на этот вопрос, поскольку, что касается оптимизации компилятора, я знаю достаточно, чтобы быть опасным. Надеюсь, кто-то, кто понимает компилятор Джулии, немного лучше наткнется на этот вопрос и сможет дать более исчерпывающий ответ, потому что, насколько я вижу, ваша c2 функция выполняет огромную работу, которая ей не нужна.

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

julia> @btime c1()
  1.535 ns (0 allocations: 0 bytes)

Вы также можете увидеть это, используя @code_native c1() и @code_native c2(). Первая содержит всего пару строк, а вторая содержит гораздо больше инструкций. Также стоит отметить, что первый не содержит никаких ссылок на функцию <=, указывающую, что условие в цикле while было полностью оптимизировано.

Мы можем решить эту первую проблему, добавив оператор return x в нижней части обеих ваших функций, что заставит компилятор фактически заняться вопросом, каким будет окончательное значение x.

Однако, если вы сделаете это, вы заметите, что c1 все еще примерно в 10 раз быстрее, чем c2, что является второй загадкой в ​​вашем примере.

Мне кажется, что даже с return x достаточно умный компилятор обладает всей информацией, необходимой для полного пропуска цикла. То есть во время компиляции ему известно начальное значение x, точное значение преобразования внутри цикла и точное значение завершающего условия. Удивительно, но если вы запустите @code_native c1() (после добавления return x внизу), вы заметите, что оно действительно отработало возвращаемое значение функции прямо в собственном коде (cmpq $1000000001):

julia> @code_native c1()
    .text
; Function c1 {
; Location: REPL[2]:2
    movq    $-1, %rax
    nopw    (%rax,%rax)
; Location: REPL[2]:3
; Function <=; {
; Location: int.jl:436
; Function <=; {
; Location: int.jl:429
L16:
    addq    $1, %rax
    cmpq    $1000000001, %rax       # imm = 0x3B9ACA01
;}}
    jb  L16
; Location: REPL[2]:6
    retq
    nopl    (%rax)
;}

так что я не совсем уверен, почему он все еще выполняет какую-либо работу!

Для справки вот вывод @code_native c2() (после добавления return x):

julia> @code_native c2()
    .text
; Function c2 {
; Location: REPL[3]:2
    pushq   %r14
    pushq   %rbx
    pushq   %rax
    movq    $-1, %rbx
    movabsq $power_by_squaring, %r14
    nopw    %cs:(%rax,%rax)
; Location: REPL[3]:3
; Function literal_pow; {
; Location: none
; Function macro expansion; {
; Location: none
; Function ^; {
; Location: intfuncs.jl:220
L32:
    addq    $1, %rbx
    movl    $10, %edi
    movl    $9, %esi
    callq   *%r14
;}}}
; Function <=; {
; Location: int.jl:436
; Function >=; {
; Location: operators.jl:333
; Function <=; {
; Location: int.jl:428
    testq   %rax, %rax
;}}}
    js  L59
    cmpq    %rax, %rbx
    jbe L32
; Location: REPL[3]:6
L59:
    movq    %rbx, %rax
    addq    $8, %rsp
    popq    %rbx
    popq    %r14
    retq
    nopw    %cs:(%rax,%rax)
;}

Здесь явно много дополнительной работы для c2, которая не имеет для меня особого смысла. Надеюсь, кто-то, более знакомый с внутренностями Джулии, сможет пролить свет на это.

...