Parsing expressions into functions

General Usage Performance
21

I guess all I’m trying to say is that heavy runtime code generation (and metaprogramming in general) should be used sparingly because it’s usually harder on the compiler and harder to reason about. Often the cleanest solution is to combine the bare minimum of metaprogramming with a bunch of normal helper functions. Hence my comment about passing in coefficient arrays rather than hard coding them in the generated expressions.

Regardless of that, you know the details of your problem and if you’ve got something working that’s great.

2 Likes
22

Hey, just a quick update. I was playing around with introducing multiple different expression forms at once, to see if it maintained performance and I came across some interesting behaviour.

Basically, using the const definitions and FunctionWrappers the code is performing great, but even with FunctionWrappers, there are circumstances where it doesn’t work properly. Basically if I define some of the expressions using an if/else statement in the for loop, then the type stability seems to disappear. Whereas if I define the same different expressions directly in a single for loop using a sequential construction, or even part in the global scope, part in the for loop, the array is type stable and the performance is great.

Here’s an example where I’m just using one expression for odd numbers and a different expression for even numbers, constructed using the different approaches described above:

using BenchmarkTools, FunctionWrappers

const FunWrap = FunctionWrappers.FunctionWrapper{Float64,Tuple{Float64}}

const coefficients = rand(1000)
const exponents = rand(1000)
y = zeros(1000)

# Alternating expressions defined via if statement
functions1 = []
for i in 1:1000
  if isodd(i)
    push!(functions1, FunWrap(x -> coefficients[i]*x^exponents[i]))
  else
    push!(functions1, FunWrap(x -> coefficients[i] + x^exponents[i]))
  end
end
functions1 = convert(Array{typeof(functions1[1]),1},functions1)

# Alternating expressions defined via a single complete for loop
functions2 = []
for i in 1:500
  push!(functions2, FunWrap(x -> coefficients[2i-1]*x^exponents[2i-1]))
  push!(functions2, FunWrap(x -> coefficients[2i] + x^exponents[2i]))
end
functions2 = convert(Array{typeof(functions2[1]),1},functions2)

# Alternating expressions defined first in global scope then in a for loop
functions3 = []
  push!(functions3, FunWrap(x -> coefficients[2-1]*x^exponents[2-1]))
  push!(functions3, FunWrap(x -> coefficients[2] + x^exponents[2]))
for i in 2:500
  push!(functions3, FunWrap(x -> coefficients[2i-1]*x^exponents[2i-1]))
  push!(functions3, FunWrap(x -> coefficients[2i] + x^exponents[2i]))
end
functions3 = convert(Array{typeof(functions2[1]),1},functions3)

function callfunc(functions,x,y)
  Threads.@threads for i in 1:1000
    y[i] = functions[i](x)
  end
end

# Explicit expressions evaluated using single complete for loop
function explicitfunc(coefficients,exponents,x,y)
  Threads.@threads for i in 1:500
    y[2i-1] = coefficients[2i-1]*x^exponents[2i-1]
    y[2i] = coefficients[2i] + x^exponents[2i]
  end
end

@btime callfunc(functions1,1.23,y)
@btime callfunc(functions2,1.23,y)
@btime callfunc(functions3,1.23,y)
@btime explicitfunc(coefficients,exponents,1.23,y)

returning

  112.064 μs (1800 allocations: 26.92 KiB)  # if/else construction, function calls
  21.590 μs (1 allocation: 48 bytes)        # complete for loop, function calls
  21.590 μs (1 allocation: 48 bytes)        # global/for loop, function calls
  16.963 μs (1 allocation: 64 bytes)        # explicit definitions

This isn’t really an issue for me as it’s easy to code around, but I thought it might be worth mentioning. It’s odd that even with the functionwrapper, the fact that one’s defined in the if clause and the other in the else clause seems to be obscuring the types or something. I’m not sure if it has something to do with scopes? I would have thought going between global and the for loop scope would have caused the same issues in that case.

23

Oh, that’s a tricky one. You’ve just run into the following performance pitfall: performance of captured variables in closures · Issue #15276 · JuliaLang/julia · GitHub

Unfortunately the compiler can’t always work out that a captured binding (in this case i) will not be modified in the surrounding scope (or from some other location) and this is one such case. I hope I’m using the terminology correctly here…

One workaround is the “let trick”:

functions1 = []
for i in 1:1000
  if isodd(i)
    let i=i
      push!(functions1, FunWrap(x -> coefficients[i]*x^exponents[i]))
    end
  else
    let i=i
      push!(functions1, FunWrap(x -> coefficients[i] + x^exponents[i]))
    end
  end
end
functions1 = convert(Array{typeof(functions1[1]),1},functions1)
3 Likes