Optimization using look up table

I have made some c code for a progr开发者_开发技巧am, which does some psycho-acoustics on sound data.

There is a piece of code which runs very slowly.

I think it would be best to use a look up table. How would one go about implementing it?

Any pointers or help would be appreciated! :)

Your values are not equidistant so it is not that easy. But its still possible: take your greatest common divisor of all your condition-values (thats here 50) and then make your table

byteout = lut[difference/50 + 12];

And in the lookup table you can just use your values in the posted order, where you duplicate the entries in case your stepping is 100.

Btw it just see, there is a mistake, all your negative cases are catched by your first <=0 (my example assumes that you want to omit the first case).

Firstly, take a look at where you want that first check against 0, as it makes all of your negative checks pointless.

Secondly, I would probably construct a lookup table as an array of 1300 elements, offset by 500 (your lowest negative value). Each element would be the result you want when you look up that number. If you are looking for something less than -500, don't check the array.

So it would look something like this:

table[0] = 0b0110; // -500 through -599
table[1] = 0b0110;
...
table[100] = 0b0101; // -400 through -499
table[101] = 0b0101;
...

Lookup would be:

if (value <= -600) {
    return 0b0111;
}
else {
    return table[value + 600];
}

It's a small enough number of values that the size of the array is not prohibitive. Initialize with a loop at the beginning of your program.

Binary search for the win.

Store all possible values in an array, and be sure to sort them.

Start in the middle and see if difference is less than that value. If so, move to the middle of what's left of your cursor and try again. If not, move to the right. Keep going until you find the value you want, and then use that.

Your array could be of structs that have the minimum value and the corresponding byteout value.

EDIT: To clear up possible misunderstandings, with "every possible value" I don't mean every number between -1400 and 1400, just values you check against in your original code.

Let's look at the first bit:

if (difference <= 0)
  byteout = 0b0000;
else if (difference <= -600)
  byteout = 0b0111;

Let's say you have a value of -601.

Is it <= 0? Yes, so byteout = 0b0000;

you never get to the -600. So effectively, ALL negative values are 0b0000. This may or may not be by design, but if it is you can get rid of all other negative values.

Otherwise, I would consider reducing this to a formula (with as few branches as possible) or going with @Ebomike's solution of a precomputed lookup table and binary search.