Julia Compiler scheint nicht zu optimieren, wenn eine Funktion eine Funktion übergeben wird

Question

ZWEITE BEARBEITUNG:This pull request auf github wird das Problem beheben. Solange Julia v0.5 + läuft, sind anonyme Funktionen genauso schnell wie normale Funktionen. Also Fall geschlossen.

EDIT: Ich habe die Frage und Funktion Definitionen zu einem allgemeineren Fall aktualisiert.

Für ein einfaches Beispiel scheint der Julia-Compiler nicht zu optimieren, wenn eine Funktion eine Funktion übergeben oder eine Funktion innerhalb einer Funktion definiert ist. Das überrascht mich, da dies in Optimierungspaketen sicherlich sehr häufig vorkommt. Habe ich Recht oder mache ich etwas Dummes? Ein einfaches Beispiel:

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 

Dann laufe ich den folgenden Code, die drei Fälle zu Zeit:

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

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

Und die Zeiten sind:

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) 

Viele Speicherzuweisung und die Garbage Collection für die ersten beiden Fälle. Könnte jemand erklären warum?

Answer 1

So ein Spaß, was zu tun ist, Gebrauch @code_warntype in Julia 0,4, was zeigt folgendes:

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 

Das Problem ist also mit Inferenz des Rückgabetyp f, das wirklich alles sein könnte. Das Problem (so wie ich es verstehe) besteht darin, dass Julia eine Methode für jede Typenkombination kompiliert. Wir haben hier Code für alle Funktion generiert, so dass alles zurückkommen könnte. Es wäre nett, wenn Function beim Rückgabetyp parametrisch wäre, weil wir dann etwas schlauer machen könnten wie Function{T<:Any,Int}.

war meine Lösung es z += fIn(n, n)::Int zu ändern, und das erlaubt z immer ein Int zu sein, aber ich noch

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

im @code_warntype Ausgabe zu sehen, was Sinn macht, denn es ist wirklich noch ein Any ist, Ich sorge nur dafür, dass der Rest nicht verschmutzt wird. Aber ich denke, es muss immer noch Code generieren, um zu überprüfen, ob es tatsächlich ein Int ist. Nennen wir diese neue Version 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) 

So einige Gewinne, aber nicht ideal. Dies ist ein bekanntes Problem, das tief in Julias Inneres eindringt. Siehe auch:

• #1090 return type declarations
• #210 function types
• #1864 anonymous function calls have a huge overhead
• #9863 Someone needs to write a FAQ entry on functions-as-variables

Answer 2

Dies ist in Julia v0.5 behoben. Alle drei Fälle sollten die gleiche Leistung wie g3 jetzt geben.