Self modifying algorithm?

Question

I try to implement a generic IIR filter. The main is as follows:

    // Loop over all SOS sections:
    value_type y = x;
    BOOST_FOREACH( Sos& n, m_sos )
    {
        y = update( n, y );
    }

with:

...update( Sos& sos, const value_type& x ) const
{

    const value_type xs = sos.m_s * x;

    const value_type w0 =   xs
                          - sos.m_a( 1 ) * sos.m_w( 0 )
                          - sos.m_a( 2 ) * sos.m_w( 1 );

    const value_type y =   w0
                         + sos.m_b( 1 ) * sos.m_w( 0 )
                         + sos.m_b( 2 ) * sos.m_w( 1 );

    sos.m_w( 1 ) = sos.m_w( 0 );
    sos.m_w( 0 ) = w0;

    return y;
}

The coefficients m_a, m_b are variable and read from a file once during runtime. Therefore the values are unknown during compile time. Depending on the designed filter it can happen that some coefficients are 1.0 or 0.0. Therefore the corresponding operation can be omitted. This will save a lot performance. For sure I can now optimize the code to be fast for one dedicated filter but as mentioned the implementation shall be very generic. My first idea was some kind of self modifiying algorithm...but maybe someone has a cool idea or hint... :)

I have 5 variable coefficients. The if() stuff costs a lot performance. — Maik, Nov 05 '14 at 18:30
Q is: What kind of solutions do I have to "optimize" the code during runtime depending on the used coefficients. e.g. exchange the implementation in some generic way. — Maik, Nov 05 '14 at 18:42

score 3 · Answer 1 · answered Nov 05 '14 at 18:42

You can make a templated version of your filtering function. I don't know how to apply this directly to your code, but consider the following:

// Z1 means "coefficient 1 is zero"
template <bool Z1, bool Z2, bool Z3, bool Z4, bool Z5>
...update( Sos& sos, const value_type& x ) const
{
    value_type coef1 = Z1 ? 0 : sos.m_a( 1 ); // or whatever else
    value_type coef2 = Z2 ? 0 : ...;
    value_type coef3 = Z3 ? 0 : ...;
    value_type coef4 = Z4 ? 0 : ...;
    value_type coef5 = Z5 ? 0 : ...;

    ... // the rest of your code
}

So far, this defines 32 different functions, each of which is maximally optimized (compiler should detect multiplication by a zero constant and optimize code). Then, you can use an array of function pointers:

auto my_table[] = {
    &update<0, 0, 0, 0, 0>,
    &update<0, 0, 0, 0, 1>,
    ...
    &update<1, 1, 1, 1, 1>
};

Then have a check for your coefficients where performance is not important (where it reads the coefficients from a file), get a function pointer from the array, and store it in your object Sos.

I am sorry if this sounds too vague; I didn't understand your code enough to express my idea in compilable code.

score 2 · Answer 2 · answered Nov 05 '14 at 18:46

With only 5 coefficients it would be feasible to generate all 2^5 code permutations and then select the appropriate permutation at runtime (e.g. "new Updater00110()" if the first second and fifth coefficients are 0 and the third and fourth coefficients are non-zero); this assumes that the code is the same when a coefficient is 0 or 1, if these are different then you're looking at 3^5 permutations which might bloat your code too much.

Peformance-wise the unused classes / functions shouldn't clutter up the cache or anything like that.

In the past when I've had to generate several code permutations like this then I've used a helper program (usually written in an interpreted language like Python) to automatically generate the code / files for all 2^5 permutations.

score 1 · Answer 3 · answered Nov 08 '14 at 13:02

Q: What kind of solutions do I have to "optimize" the code during runtime depending on the used coefficients?

So basically you want a code that "compiles and optimizes itself" during runtime. Technically this is possible: for example here. Mainly you would call the C/C++ compiler from your code, create a code page and jump into it using a function pointer.

From practical perspective, I wouldn't recommend it. Compiling during runtime will take time. Of course, if it's done only once, it might pay off. The problem is that your compiled binary will generate lots of requirements and will be hard to distribute.

My recommendations would be the following:

Make your filter function as inline - This will save the time for passing parameters to your function. If you only use 5 coefficients, this might be worth the try.
Verify the occurrence of cases where your coefficients are 1.0 or 0.0. It might be that these cases are very rare so you don't need to worry about them.
Check if your design can be implemented using a pre-computed set of values, computed only once at initialization.

Self modifying algorithm?

3 Answers3