programmazione Staged - Il discorso di Jake Bolewski

Question

Versione: da Julia v0.4 in poi (io uso 0.5.0-dev + 433 (2015/09/29 15:39 UTC))

Riferimento: Jake Bolewski: Staged programming in Julia

Problema: Dopo aver visto il discorso di Jakes Bolewski riguardo StaticVec non ho capito l'idea dietro l'esempio con la funzione length.

julia> type StaticVec{T,N} 
     vals::Vector{T} 
     end 

julia> StaticVec(T,vals...) = StaticVec{T,length(vals)}([vals...]) 
StaticVec{T,N} 

julia> v= StaticVec(Float64,1,2,3) 
StaticVec{Float64,3}([1.0,2.0,3.0]) 

non messo in scena length:

julia> function Base.length{T,N}(v::StaticVec{T,N}) 
     N 
     end 
length (generic function with 58 methods) 

julia> code_llvm(length, (StaticVec{Float64,3},)) 

define i64 @julia_length_21889(%jl_value_t*) { 
top: 
    ret i64 3 
} 

e messo in scena length versione

julia> @generated function Base.length{T,N}(v::StaticVec{T,N}) 
     :(N) 
     end 
length (generic function with 58 methods) 

julia> code_llvm(length, (StaticVec{Float64,3},)) 

define i64 @julia_length_21888(%jl_value_t*) { 
top: 
    ret i64 3 
} 

dare lo stesso codice LLVM.

Suppongo di aver compreso l'idea alla base della programmazione a fasi, ma in questo particolare esempio non capisco l'intenzione dell'altoparlante. Qualcuno potrebbe spiegarmelo?

Answer 1

Questo esempio non è probabilmente la scelta migliore poiché, come si fa notare, non richiede affatto funzioni generate. Jiahao Chen ha recentemente scritto un blog post con un eccellente esempio di utilizzo di una funzione generata per un livellamento dei dati efficiente. Ecco una simile parte di codice al suo che migliora ulteriormente l'efficienza staccando M iterazioni nella parte anteriore e posteriore, evitando così rami nel corpo ciclo principale:

immutable SavitzkyGolayFilter{M,N} end 

wrapL(i, n) = ifelse(1 ≤ i, i, i + n) 
wrapR(i, n) = ifelse(i ≤ n, i, i - n) 

@generated function smooth!{M,N}(
    ::Type{SavitzkyGolayFilter{M,N}}, 
    data::AbstractVector, 
    smoothed::AbstractVector, 
) 
    # compute filter coefficients from the Jacobian 
    J = Float64[(i-M-1)^(j-1) for i = 1:2M+1, j = 1:N+1] 
    e₁ = [1; zeros(N)] 
    C = J' \ e₁ 

    # generate code to evaluate filter on data matrix 
    pre = :(for i = 1:$M end) 
    main = :(for i = $(M+1):n-$M end) 
    post = :(for i = n-$(M-1):n end) 
    for loop in (pre, main, post) 
     body = loop.args[2].args 
     push!(body, :(x = $(C[M+1]) * data[i])) 
     for j = reverse(1:M) 
      idx = loop !== pre ? :(i-$j) : :(wrapL(i-$j,n)) 
      push!(body, :(x += $(C[M+1-j]) * data[$idx])) 
     end 
     for j = 1:M 
      idx = loop !== post ? :(i+$j) : :(wrapR(i+$j,n)) 
      push!(body, :(x += $(C[M+1+j]) * data[$idx])) 
     end 
     push!(body, :(smoothed[i] = x)) 
    end 
    quote 
     n = length(data) 
     n == length(smoothed) || throw(DimensionMismatch()) 
     @inbounds $pre; @inbounds $main; @inbounds $post 
     return smoothed 
    end 
end 

smooth{S<:SavitzkyGolayFilter,T}(::Type{S}, data::AbstractVector{T}) = 
    smooth!(S, data, Vector{typeof(1.0*one(T))}(length(data))) 

Il codice generato per smooth(SavitzkyGolayFilter{3,4}, rand(1000)), per esempio, è la seguente:

n = length(data) 
n == length(smoothed) || throw(DimensionMismatch()) 
@inbounds for i = 1:3 
    x = 0.5670995670995674 * data[i] 
    x += 0.02164502164502159 * data[wrapL(i - 3, n)] 
    x += -0.1298701298701297 * data[wrapL(i - 2, n)] 
    x += 0.32467532467532445 * data[wrapL(i - 1, n)] 
    x += 0.32467532467532473 * data[i + 1] 
    x += -0.12987012987013022 * data[i + 2] 
    x += 0.021645021645021724 * data[i + 3] 
    smoothed[i] = x 
end 
@inbounds for i = 4:n-3 
    x = 0.5670995670995674 * data[i] 
    x += 0.02164502164502159 * data[i - 3] 
    x += -0.1298701298701297 * data[i - 2] 
    x += 0.32467532467532445 * data[i - 1] 
    x += 0.32467532467532473 * data[i + 1] 
    x += -0.12987012987013022 * data[i + 2] 
    x += 0.021645021645021724 * data[i + 3] 
    smoothed[i] = x 
end 
@inbounds for i = n-2:n 
    x = 0.5670995670995674 * data[i] 
    x += 0.02164502164502159 * data[i - 3] 
    x += -0.1298701298701297 * data[i - 2] 
    x += 0.32467532467532445 * data[i - 1] 
    x += 0.32467532467532473 * data[wrapR(i + 1, n)] 
    x += -0.12987012987013022 * data[wrapR(i + 2, n)] 
    x += 0.021645021645021724 * data[wrapR(i + 3, n)] 
    smoothed[i] = x 
end 
return smoothed 

Come si può immaginare, questo genera codice macchina molto efficiente. Spero che chiarisca un po 'il concetto di funzioni generate.