Julia: types de fonctions et performances

Question

Y a-t-il un moyen pour Julia de généraliser un modèle comme celui-ci?

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

Cela calcule la racine carrée de chaque élément vectoriel, puis additionne tout. Il est beaucoup plus rapide que les versions "naïves" avec compréhension des tableaux ou map, et n'alloue pas non plus de mémoire supplémentaire:

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

Malheureusement, la version générique "évidente" est terriblement performante:

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 raison en est qu'elle x -> sqrt(x)est définie comme une nouvelle fonction anonyme à chaque appel à compute_sum2, donc cela provoque une nouvelle compilation à chaque fois que vous l'appelez.

Si vous le définissez avant même, par exemple comme ceci:

julia> f = x -> sqrt(x)

alors vous avez:

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

Notez qu'une approche naturelle serait de définir une fonction avec un nom comme celui-ci:

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

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

Vous pouvez voir que x -> sqrt(x)définit une nouvelle fonction anonyme à chaque fois qu'elle est rencontrée lorsque vous écrivez par exemple:

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

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

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

Notez que ce serait différent si une fonction anonyme était définie dans un corps de fonction:

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"

et vous voyez que cette fois la fonction anonyme est la même à chaque fois.

Answer 2

En plus de l'excellente réponse de Bogumil, je voudrais juste ajouter que d' une manière très pratique de généraliser est d'utiliser la fonction de programmation fonctionnelle normale comme map, reduce, fold, etc.

Dans ce cas, vous effectuez une maptransformation (à savoir sqrt) et une réduction (à savoir +), vous pouvez donc également obtenir le résultat avec mapreduce(sqrt, +, xs). Cela n'a pratiquement pas de surcharge et est comparable à une boucle manuelle en termes de performances.

Si vous avez une série de transformations vraiment compliquée, vous pouvez obtenir des performances optimales tout en utilisant une fonction en utilisant le package Transducers.jl.

Answer 3

Bogumił a déjà répondu à la partie sur le type de fonction. Je tiens à souligner que votre implémentation fonctionne déjà aussi efficacement que possible, si elle est correctement comparée , mais peut être remplacée par des fonctions intégrées équivalentes:

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

Et il est toujours préférable d'utiliser une fonction non lambda équivalente à eta, si possible: fau lieu de x -> f(x). Surtout pour les fonctions intégrées, car elles sont parfois envoyées.

Answer 4

Les autres réponses sont assez complètes, mais je voulais souligner que vous pouvez simplement omettre les crochets sum([sqrt(x) for x in xs])et obtenir la version la plus rapide de toutes:

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

Notez également que sur mon ordinateur, le maître Julia compute_sumest le moyen le plus lent, et non le plus rapide, de faire la somme de ces nombres.