Allocations in large function


#1

I am playing around with code generation for the evaluation of multivariate polynomials and hit a problem which I do not completely understand. The problem is already ocurring for the following function

function strange_allocations!(u, coefficients, x)
    x1 = x[1]
    x1_1 = x1
    x1_2 = x1_1 * x1
    x2 = x[2]
    x2_1 = x2
    x2_2 = x2_1 * x2
    x3 = x[3]
    x3_1 = x3
    x3_2 = x3_1 * x3
    x4 = x[4]
    x4_1 = x4
    x4_2 = x4_1 * x4
    x5 = x[5]
    x5_1 = x5
    x5_2 = x5_1 * x5
    x6 = x[6]
    x6_1 = x6
    x6_2 = x6_1 * x6
    x7 = x[7]
    x7_1 = x7
    x7_2 = x7_1 * x7
    x8 = x[8]
    x8_1 = x8
    x8_2 = x8_1 * x8
    x9 = x[9]
    x9_1 = x9
    x9_2 = x9_1 * x9
    x10 = x[10]
    x10_1 = x10
    x10_2 = x10_1 * x10
    x11 = x[11]
    x11_1 = x11
    x11_2 = x11_1 * x11
    x12 = x[12]
    x12_1 = x12
    x12_2 = x12_1 * x12
    x13 = x[13]
    x13_1 = x13
    x13_2 = x13_1 * x13
    x14 = x[14]
    x14_1 = x14
    x14_2 = x14_1 * x14
    x15 = x[15]
    x15_1 = x15
    x15_2 = x15_1 * x15
    u .= zero(Float64)
    c = coefficients[1] * x1_1 * x5_1 * x6_1 * x7_1 * x10_1 * x11_1 * x12_1 * x15_2
    _x1 = x1
    _x2 = _x1 * x2
    _x3 = _x2 * x3
    _x4 = _x3 * x4
    _x5 = _x4 * x5
    _x6 = _x5 * x6
    _x7 = _x6 * x7
    _x8 = _x7 * x8
    _x9 = _x8 * x9
    _x10 = _x9 * x10
    _x11 = _x10 * x11
    _x12 = _x11 * x12
    _x13 = _x12 * x13
    _x14 = _x13 * x14
    _y15 = x15
    _y14 = _y15 * x14
    _y13 = _y14 * x13
    _y12 = _y13 * x12
    _y11 = _y12 * x11
    _y10 = _y11 * x10
    _y9 = _y10 * x9
    _y8 = _y9 * x8
    _y7 = _y8 * x7
    _y6 = _y7 * x6
    _y5 = _y6 * x5
    _y4 = _y5 * x4
    _y3 = _y4 * x3
    _y2 = _y3 * x2
    u[1] = muladd(c * 2, _y2, u[1])
    u[2] = muladd(c * _x1, _y3, u[2])
    u[3] = muladd(c * _x2, _y4, u[3])
    u[4] = muladd(c * _x3, _y5, u[4])
    u[5] = muladd(c * 2 * _x4, _y6, u[5])
    u[6] = muladd(c * 2 * _x5, _y7, u[6])
    u[7] = muladd(c * 2 * _x6, _y8, u[7])
    u[8] = muladd(c * _x7, _y9, u[8])
    u[9] = muladd(c * _x8, _y10, u[9])
    u[10] = muladd(c * 2 * _x9, _y11, u[10])
    u[11] = muladd(c * 2 * _x10, _y12, u[11])
    u[12] = muladd(c * 2 * _x11, _y13, u[12])
    u[13] = muladd(c * _x12, _y14, u[13])
    u[14] = muladd(c * _x13, _y15, u[14])
    u[15] = muladd(c * 3, _x14, u[15])
    u
end

If you call the function with

coefficients = rand(1)
x = rand(15)
u = zeros(15)

@btime strange_allocations!($u, $coefficients, $x)

Then @btime reports 40.967 ns (7 allocations: 112 bytes). Why are allocations happening? Is the function exceeding the stack limit and then moving things to the heap instead? Is the limit somewhere documented?

Update: This behaviour seems only to happen for Julia v0.6.1, on master (8 days old) everything works as expected! Does anybody know wether this change will be backported?


#2

You are hitting https://github.com/JuliaLang/julia/issues/14821. Change

c = coefficients[1] * x1_1 * x5_1 * x6_1 * x7_1 * x10_1 * x11_1 * x12_1 * x15_2

to

c =  coefficients[1] * (x1_1 * x5_1 * x6_1 * x7_1) * (x10_1 * x11_1 * x12_1 * x15_2)

Help understanding allocation on scalar function and possible ways to avoid it
#3

Indeed, that resolves it. Thank you!!