Julia: tipos de funciones y rendimiento

Question

¿Hay alguna forma en Julia de generalizar un patrón como el siguiente?

function compute_sum(xs::Vector{Float64})
    res = 0
    for i in 1:length(xs)
        res += sqrt(xs[i])
    end
    res
end

Esto calcula la raíz cuadrada de cada elemento del vector y luego suma todo. Es mucho más rápido que las versiones "ingenuas" con comprensión de matrices o map, y tampoco asigna memoria adicional:

xs = rand(1000)

julia> @time compute_sum(xs)
  0.000004 seconds
676.8372556762225

julia> @time sum([sqrt(x) for x in xs])
  0.000013 seconds (3 allocations: 7.969 KiB)
676.837255676223

julia> @time sum(map(sqrt, xs))
  0.000013 seconds (3 allocations: 7.969 KiB)
676.837255676223

Desafortunadamente, la versión genérica "obvia" tiene un rendimiento terrible:

function compute_sum2(xs::Vector{Float64}, fn::Function)
    res = 0
    for i in 1:length(xs)
        res += fn(xs[i])
    end
    res
end

julia> @time compute_sum2(xs, x -> sqrt(x))
  0.013537 seconds (19.34 k allocations: 1.011 MiB)
676.8372556762225

Answer 1

La razón es que x -> sqrt(x)se define como una nueva función anónima con cada llamada a compute_sum2, por lo que esto provoca una nueva compilación cada vez que la llamas.

Si lo define incluso antes, por ejemplo, de esta manera:

julia> f = x -> sqrt(x)

entonces tiene:

julia> @time compute_sum2(xs, f) # here you pay compilation cost
  0.010053 seconds (19.46 k allocations: 1.064 MiB)
665.2469135020949

julia> @time compute_sum2(xs, f) # here you have already compiled everything
  0.000003 seconds (1 allocation: 16 bytes)
665.2469135020949

Tenga en cuenta que un enfoque natural sería definir una función con un nombre como este:

julia> g(x) = sqrt(x)
g (generic function with 1 method)

julia> @time compute_sum2(xs, g)
  0.000002 seconds
665.2469135020949

Puede ver que x -> sqrt(x)define una función anónima nueva cada vez que se encuentra cuando escribe, por ejemplo:

julia> typeof(x -> sqrt(x))
var"#3#4"

julia> typeof(x -> sqrt(x))
var"#5#6"

julia> typeof(x -> sqrt(x))
var"#7#8"

Tenga en cuenta que esto sería diferente si se definiera una función anónima en el cuerpo de una función:

julia> h() = typeof(x -> sqrt(x))
h (generic function with 2 methods)

julia> h()
var"#11#12"

julia> h()
var"#11#12"

julia> h()
var"#11#12"

y ves que esta vez la función anónima es la misma cada vez.

Answer 2

Además de la excelente respuesta por Bogumil, me gustaría añadir que una forma muy conveniente de generalizar esto es utilizar la función de programación funcional normal como map, reduce, fold, etc.

En este caso, está haciendo una maptransformación (a saber sqrt) y una reducción (a saber +), por lo que también puede lograr el resultado con mapreduce(sqrt, +, xs). Esto esencialmente no tiene gastos generales y es comparable a un bucle manual en rendimiento.

Si tiene una serie de transformaciones realmente complicadas, puede obtener un rendimiento óptimo y aún usar una función usando el paquete Transducers.jl.

Answer 3

Bogumił ya ha respondido a la parte sobre el tipo de función. Quiero señalar que su implementación ya está funcionando de la manera más eficiente posible, si se compara correctamente , pero se puede reemplazar por funciones integradas equivalentes:

julia> @btime compute_sum($xs) 2.149 μs (0 allocations: 0 bytes) 661.6571623823567 julia> @btime sum(sqrt, $xs)
  2.149 μs (0 allocations: 0 bytes)
661.6571623823567

julia> @btime compute_sum2($xs, sqrt) 2.149 μs (0 allocations: 0 bytes) 661.6571623823567 julia> @btime mapreduce(sqrt, +, $xs)
  2.149 μs (0 allocations: 0 bytes)
661.6571623823567

Y siempre es mejor usar una función no lambda equivalente a eta, si es posible: en flugar de x -> f(x). Especialmente para funciones integradas, ya que a veces se envían en.

Answer 4

Las otras respuestas son bastante completas, pero quería señalar que puede omitir los corchetes sum([sqrt(x) for x in xs])y obtener la versión más rápida de todas:

julia> using BenchmarkTools

julia> @btime compute_sum($xs) 1.779 μs (0 allocations: 0 bytes) 679.0943275393031 julia> @btime sum([sqrt(x) for x in $xs])
  1.626 μs (1 allocation: 7.94 KiB)
679.0943275393028

julia> @btime sum(map(sqrt, $xs)) 1.628 μs (1 allocation: 7.94 KiB) 679.0943275393028 julia> @btime sum(sqrt(x) for x in $xs)
  1.337 μs (0 allocations: 0 bytes)
679.0943275393031

También tenga en cuenta que en mi computadora, el maestro de Julia compute_sumes la forma más lenta, no la más rápida, de sumar estos números.