Optimising switching algorithms based on value of struct field

General Usage
, ,
1

I’m working on a simulation in Julia, where the “centrepiece” is some struct, which can have a few boolean properties associated with it.

mutable struct Sim
   """ data """
   
   prop_a::Bool
   prop_b::Bool
   ...

end

In the simulation I call a function to get the some energy dependent on this struct ten-thousands to millions of times, let’s call this function getE(s::Sim). Any of the properties being false, means that I don’t want to include some term in this energy function, and thus can speed up this function by not checking a few of the data fields in the struct (which would otherwise be accessing the fields to add zeros to some float in the end).

Thus, in other words the implementation of getE depends on the properties of s. I can some if statements and only access the fields the corresponding properties are true. This is quite fast, but there still is a small performance hit, especially if I need to do multiple checks.

I thought it might be faster to just write all the functions beforehand and save one of them in the Sim struct itself. Thus

mutable struct Sim
   """ data """
   
   prop_a::Bool
   prop_b::Bool
   ...

   efunc::Function

end

When I change one of the props, which doesn’t happen often, I just change the function being referenced in the struct, so that no checks have to be done at runtime. Sadly, the performance hit by accessing the referenced function turns out to be orders of magnitude higher than checking the properties every time.

julia> @btime getE(s)
  13.556 ns (0 allocations: 0 bytes)

julia> @btime getECheckProp(s)
  14.404 ns (0 allocations: 0 bytes)

julia> @btime s.efunc(s)
  53.287 ns (1 allocation: 16 bytes)

Here getE(s) is the base algorithm, getECheckProp(s) checks the corresponding properties before calling getE(s), and s.efunc is just a reference to getE directly.

Any suggestions of how I could build my program to get as close to the performance of calling getE(s) directly?

2

Probably you just need to parametrize your structure to the type of function:

mutable struct Sim{F<:Function}
    ...
    efunc::F
end

otherwise efunc is abstractly typed. (consider making the structure immutable as well, that may help the compiler to do optimizations).

2 Likes
3

Yep, you’re completely right. Now I can just redefine the method to any of the predefined methods, instead of the function itself. This works, thanks!

1 Like
4

Actually, there is one sidenote:

Say I have predefined getE1(g), getE2(g) .... I need to programatically change s.efunc when I change one of the props. Naively I would do something like this:

function setPropB(s)
  s.prop_b = true
  s.efunc(s) = getE2(s)
end

this immediately gives the error

ERROR: syntax: Global method definition around ... needs to be placed at the top level, or use "eval".

Instead trying

function setPropB(s)
  s.prop_b = true
  eval(:(s.efunc(s) = begin; getE2(s); end ))
end

works, but is MetaProgramming, if I’m not mistaken, which is often discouraged here. Are there any caveats to using eval in this way?

5

Maybe you want

6

That doesn’t work if you define efunc to be type stable like Imiq suggested

mutable struct Sim{F<:Function}
    ...
    efunc::F
end

And actually the whole point of my original post was, that that makes calling efunc very slow.

7

Sorry, I didn’t read the history. In that case you won’t be able to reassign efunc. Each function has its own type. Maybe you can have two function fields and a boolean field to indicate which function to use. It would be type stable, but you would need to check the boolean on each invocation which would slow it down, but maybe not as much as type instability.

1 Like
8

Yes indeed that would indeed be faster than type instability in the function, but still gives a performance hit that I would like to overcome. Doing what Imiq suggested together with the eval trick does solve the speed problem though.

9

Indeed, the whole point is to keep efunc constant, so that the compiler can optimize the code for it.

You probably want to define what Sim is only once (make it immutable, that will makes things clear and the overall program structure will probably get better, even if at first sight it looks more cumbersome).

You would, do, then:

struct Sim{F<:Function}
     param::Bool
     efunc::F
end

function setSim( some parameters )
       ...
    efunc(s) = whatever
    return Sim(param, efunc)
end

sim = setSim( ... )

# now on, use `sim` as a static structure.
10

Maybe another alternative is to parametrize Sim not the function iself, but o the type of function. I think there are many packages which use this strategy. Something like:

struct Sim{T}
    param1::Bool
    param2::Bool
    # do not store the function here
end

struct FunctionType1 end
struct FunctionType2 end

# initialize sim:
sim = Sim{FunctionType1}(param1, param2)

# and define the functions to apply to sim, according to its type:

efunc(s::Sim{FunctionType1}) = something
efunc(s::Sim{FunctionType2}) = another something

By the way, if the possible Sims have different types and number of parameters, then it is even better to just define different containing structs for each type of simulations, and dispatch on them:

struct SimType1
   p1::Bool
end

struct SimType2
    p1::Bool
    p2::Float64
end

sim = SimType1(p1)

efunc(s::SimType1) = something
efunc(s::SimType2) = another something

ps: @f.ij forget the eval option, don’t go that route (answering to your post bellow).

11

I think I found a caveat: for eval to work I think s needs to be defined globally. This causes some problems with inner constructors for example:

function getE(s)
  ...
                end
mutable struct Sim{F <: Function}
  ...
  
  efunc::F
  
  Sim(...,prop_a,...) = ( sim = new{typeof(getE)}(..., getE); 
    if prop_a
       eval(:(s.efunc(s) = begin; getE1(s);  end));
    else
       eval(:(s.efunc(s) = begin; getE2(s);  end))
    end
    return sim )

s = Sim(...,true,...)

ERROR: LoadError: UndefVarError: s not defined

Adding the prefix global in front of sim within the inner constructor fixes the problem and doesn’t actually create a globally defined variable named sim, but feels wrong

mutable struct Sim{F <: Function}
  ...
  
  efunc::F
  
  Sim(...,prop_a,...) = ( global sim = new{typeof(getE)}(..., getE); 
    if prop_a
       eval(:(s.efunc(s) = begin; getE1(s);  end));
    else
       eval(:(s.efunc(s) = begin; getE2(s);  end))
    end
    return sim )

s = Sim(...,true,...)

Moreover, to change the function, what I did before:

function setPropB(s)
  s.prop_b = true
  eval(:(s.efunc(s) = begin; getE2(s); end ))
end

only works if s is in the global namespace, the function argument doesn’t actually matter for the eval function. I would now need to resort to macros and:

macro name(arg)
           string(arg)
end

function setPropB(s)
  simname = @name s
  s.prop_b = true
  eval( Meta.parse("$simname.efunc(s) = getE2(s)") )
end

but again, uses meta programming which is discouraged.

12

I would not try to use dispatch for something that is inherently dynamic (the bool parameter values.)

Just use a regular branch, they are much faster than dynamic dispatch. Just run your test and branch, an possibly store the result of your test in a separate field on object creation.

Then

getE(s::Sim) = s.test_result ? branch1(s) : branch2(s)
1 Like
13

I do have to change the data fields of Sim quite often though (though most often it’s writing to arrays so that’s not a problem). Allocating a new struct when I change a parameter doesn’t seem great. Moreover, then I have the problem that I now have to have a type unstable global variable sim, which doesn’t seem great for performance either, since I call a lot of functions on sim, right?

I did actually try the eval option, and while not very elegant and using meta programming, it does achieve what I wanted, with no performance hit of using any of the functions.

14

Storing the function in the struct is a bad idea, imho. Even if you parameterize the struct on the function type, it is inherently type-unstable, since the parameter depends on your bool parameters.

Using a branch is better, imho.

15

Hard to say without a more general view of your code. But, in my imagination, you would be passing the sim object as a parameter to the functions that do the job, so you won’t have ever a global parameter.

sim = SimType1(p1)

result = simulation(sim)

etc...

with that, simulation will specialize to sim of type SimType1. if you have inside that a call to getE(s) = ... and you have previously defined getE(s::SimType1) = something, your code won’t have any branch, any dinamic dispatch, etc, the whole thing will just be compiled to the specialized type of sim you are defining from start.

ps: What I’m imagining you want to achieve is something with the following type of functionality:

sim = SimGravitational(params...)

# or

sim = SimMolecular(params...)

result = simulation(sim)

in which case you would have very different definitions of the energy and forces functions, like:

energy(s::SimGravitational) = gravitational energy

energy(s::SimMolecular) = molecular energy

etc.
16

I don’t exactly see how parameter dependence causes type instability. The parameters are not checked by the function in this way, since I make sure that the correct function is stored when changing one of the parameters (which function is correct depends on the combination of parameters).

Branching might be an option though. I’m building a multi-threaded, interactive simulation. The simulation update itself is continuously run on a thread in a while true loop, basically. I could make the while loop be dependent on a global variable, so that other threads close the thread and open a new branched one when changing one of the parameters. Does anyone know how much overhead this would cause? I.e. while true vs while var == true.

17

I see, I think I didn’t do a good enough job explaining what I’m trying to do. Basically I’m building an interactive (multi-threaded) Monte Carlo simulation based on Ising-like models. What you’re saying I’ve already implemented, but wasn’t necessarily what I was looking for in this case (e.g. I have different structs for different type of ising models, and these are indeed just initialised once when the simulation is started). However, for a single model, I still might want to change these parameters and optimise the energy function.

As an example, I might want to add a magnetic field that’s not always on. The magnetic field being on would add an external value for each site in a lattice which has to be taken into account when updating. If the field is off, however, I don’t wan’t to access the magnetic field at all, as this slows down the calculation of the energy considerably. Thus, I want a way to be able to turn this magnetic field on and off mid simulation, and get the optimal speed in either case. Of course, when the field is on calculations will be a bit slower, but that’s unavoidable. What does seem avoidable is the overhead when the magnetic field is off. I might try the branching option though. This way I only need to check ever wether my main Monte Carlo thread should be running, and just close and reopen it if I change the parameters.

18

And that’s the type instability. The compiler cannot know beforehand which function/parameter is the correct one, because it depends on runtime values, and is not known statically.

Perhaps it’s not so bad, type instabilities can be acceptable, especially if it doesn’t occur in a hot loop.

19

But the types of the parameters are stable, just not the values.
Or do you mean the type of the function? In that case that’s why I thought before that changing the method, not the function itself, might be a good solution, like Imiq suggested. However, then you run into the problems I mentioned in an earlier post.

20

Yes. But, perhaps that’s acceptable.