Компилятор Julia не оптимизируется, когда функции передается функция

SECOND EDIT: Этот запрос на перенос в github устранит проблему. Пока работает Julia v0.5 +, анонимные функции будут такими же быстрыми, как и обычные функции. Итак, закрытый случай.

EDIT: Я обновил определения вопросов и функций до более общего случая.

Для простого примера компилятор Julia, похоже, не оптимизируется, когда функция передается функции или функция определена внутри функции. Это меня удивляет, так как это очень часто встречается в пакетах оптимизации. Правильно ли я делаю что-то глупое? Ниже приведен простой пример:

f(a::Int, b::Int) = a - b    #A simple function

function g1(N::Int, fIn::Function)   #Case 1: Passing in a function
    z = 0
    for n = 1:N
        z += fIn(n, n)
    end
end

function g2(N::Int)   #Case 2: Function defined within a function
    fAnon = f
    z = 0
    for n = 1:N
        z += fAnon(n, n)
    end
    return(z)
end

function g3(N::Int)   #Case 3: Function not defined within function
    z = 0
    for n = 1:N
        z += f(n, n)
    end
    return(z)
end

Затем я запускаю следующий код ко времени трех случаев:

#Run the functions once
g1(10, f)   
g2(10)
g3(10)

@time g1(100000000, f)
@time g2(100000000)
@time g3(100000000)

И тайминги:

elapsed time: 5.285407555 seconds (3199984880 bytes allocated, 33.95% gc time)
elapsed time: 5.424531599 seconds (3199983728 bytes allocated, 32.59% gc time)
elapsed time: 2.473e-6 seconds (80 bytes allocated)

Распределение памяти и сбор мусора для первых двух случаев. Может ли кто-нибудь объяснить, почему?

Ответы

Ответ 1

Так забавно, что нужно использовать @code_warntype в Julia 0.4, который показывает следующее:

julia> @code_warntype g1(10, f)
Variables:
  N::Int64
  fIn::F
  z::Any
  #s1::Int64
  n::Int64

Body:
  begin  # none, line 2:
      z = 0 # line 3:
... snip ....
      z = z + (fIn::F)(n::Int64,n::Int64)::Any::Any

Таким образом, проблема заключается в выводе типа возврата f, который действительно может быть чем угодно. Проблема (как я понимаю) заключается в том, что Julia компилирует метод для каждой комбинации типов. У нас есть код, созданный здесь для любой функции, поэтому все может вернуться. Было бы аккуратно, если Function был параметрическим по типу возврата, потому что тогда мы могли бы сделать что-то умнее, чем Function{T<:Any,Int}.

Мое решение состояло в том, чтобы изменить его на z += fIn(n, n)::Int, и это позволяет z всегда быть Int, но я все еще вижу

(top(typeassert))((fIn::F)(n::Int64,n::Int64)::Any,Int)::Int64

в выводе @code_warntype, что имеет смысл, потому что он по-прежнему остается Any, я просто уверен, что это не загрязняет остальных. Но я думаю, что он все равно должен генерировать код, чтобы проверить, что это на самом деле Int. Позволяет называть эту новую версию g1A:

julia> @time g1(1000000, f)
elapsed time: 0.124437357 seconds (30 MB allocated, 2.82% gc time in 1 pauses with 0 full sweep)
elapsed time: 0.121653131 seconds (30 MB allocated, 2.51% gc time in 2 pauses with 0 full sweep)
elapsed time: 0.120805345 seconds (30 MB allocated, 1.17% gc time in 1 pauses with 0 full sweep)

julia> @time g1A(1000000, f)
elapsed time: 0.085875439 seconds (30 MB allocated, 5.20% gc time in 1 pauses with 0 full sweep)
elapsed time: 0.074592531 seconds (30 MB allocated, 4.67% gc time in 2 pauses with 0 full sweep)
elapsed time: 0.078681071 seconds (30 MB allocated, 4.75% gc time in 1 pauses with 0 full sweep)

Итак, некоторые выгоды, но не идеальные. Это известная проблема, которая углубляется во внутренние работы Юлии. Связанное обсуждение:

Ответ 2

Это исправлено в Julia v0.5. Все три случая должны иметь такую ​​же производительность, что и g3.