Overhead for autoregressive evaluation

[ArnoStrouwen]

I am using the trees for representing autoregressive models.
This means that the evaluation of the tree cannot be vectorized easily, since the input at an iteration depends on the output of the previous iteration.

The overhead for this seems to be quite high:

function autoregressive_sym()
    n = 1000 
    res = zeros(n)
    res[1] = 1.0
    for i in 2:n
        res[i] = sym_mul([res[i-1],1.01])
    end
    return res
end
@btime autoregressive_sym() # 109.630 μs

function autoregressive_sym2(sym_mul)
    n = 1000 
    res = zeros(n)
    res[1] = 1.0
    for i in 2:n
        res[i] = sym_mul([res[i-1],1.01])
    end
    return res
end
@btime autoregressive_sym2(sym_mul) # 97.618 μs

function autoregressive()
    n = 1000 
    res = zeros(n)
    res[1] = 1.0
    for i in 2:n
        res[i] = res[i-1]*1.01
    end
    return res
end
@btime autoregressive() # 896.484 ns

Any advice on how to speed this up, or what kind of alternative datastructure would be appropriate for my case?

[MilesCranmer]

Can you give a full example? I don't know what sym_mul is

[MilesCranmer]

Since your array is only 1 element, I guess I would recommend trying out StaticArrays.jl. Then it won't allocate a bunch of 1-elements arryas

[ArnoStrouwen]

Here is a full example, with static arrays added in. Doesn't seem to help much.

using DynamicExpressions
using BenchmarkTools
using StaticArrays

unary_ops = ()
binary_ops = (*,)
operators = GenericOperatorEnum(1 => unary_ops, 2 => binary_ops)
sym_mul = Node{Float64}(op=0x01, children = (Node{Float64}(feature=1),Node{Float64}(feature=2))) 

function autoregressive_sym()
    n = 1000 
    res = zeros(n)
    res[1] = 1.0
    for i in 2:n
        res[i] = sym_mul([res[i-1],1.01])
    end
    return res
end
@btime autoregressive_sym() # 94.459 μs (3999 allocations: 117.15 KiB)

function autoregressive_sym2(sym_mul)
    n = 1000 
    res = zeros(n)
    res[1] = 1.0
    for i in 2:n
        res[i] = sym_mul([res[i-1],1.01])
    end
    return res
end
@btime autoregressive_sym2(sym_mul) # 83.759 μs (3999 allocations: 117.15 KiB)

function autoregressive_sym3(sym_mul)
    n = 1000 
    res = zeros(n)
    res[1] = 1.0
    for i in 2:n
        res[i] = sym_mul(SVector(res[i-1],1.01))
    end
    return res
end
@btime autoregressive_sym3(sym_mul) # 88.210 μs (3000 allocations: 70.32 KiB)

function autoregressive()
    n = 1000 
    res = zeros(n)
    res[1] = 1.0
    for i in 2:n
        res[i] = res[i-1]*1.01
    end
    return res
end
@btime autoregressive() # 901.483 ns (3 allocations: 7.88 KiB)

[MilesCranmer]

Can you try a normal OperatorEnum?

[MilesCranmer]

Also for static, you should try using an MVector rather than an SVector

[ArnoStrouwen]

I believe normal OperatorEnum is slower, because it can't do scalar output:

unary_ops = ()
binary_ops = (*,)
operators = OperatorEnum(1 => unary_ops, 2 => binary_ops)
sym_mul = Node{Float64}(op=0x01, children = (Node{Float64}(feature=1),Node{Float64}(feature=2))) 

function autoregressive_sym()
    n = 1000 
    res = zeros(n)
    res[1] = 1.0
    for i in 2:n
        res[i] = sym_mul([res[i-1],1.01])[1]
    end
    return res
end
@btime autoregressive_sym() # 141.869 μs (6996 allocations: 226.41 KiB)

function autoregressive_sym2(sym_mul)
    n = 1000 
    res = zeros(n)
    res[1] = 1.0
    for i in 2:n
        res[i] = sym_mul([res[i-1],1.01])[1]
    end
    return res
end
@btime autoregressive_sym2(sym_mul) # 125.129 μs (6996 allocations: 226.41 KiB)

function autoregressive_sym3(sym_mul)
    n = 1000 
    res = zeros(n)
    res[1] = 1.0
    for i in 2:n
        res[i] = sym_mul(SVector(res[i-1],1.01))[1]
    end
    return res
end
@btime autoregressive_sym3(sym_mul) # 110.269 μs (4998 allocations: 132.76 KiB)

function autoregressive_sym4(sym_mul)
    n = 1000 
    res = zeros(n)
    res[1] = 1.0
    for i in 2:n
        res[i] = sym_mul(MVector(res[i-1],1.01))[1]
    end
    return res
end
@btime autoregressive_sym4(sym_mul) # 109.709 μs (4998 allocations: 132.76 KiB)

[MilesCranmer]

P.S., you might want to use the Expression interface which is a bit easier for building expressions:

operators = OperatorEnum(2 => (*,))
x1 = Expression(Node{Float64}(feature=1); operators)
x2 = Expression(Node{Float64}(feature=2); operators)

expr = x1 * x2