Is it possible to optimize this function?

Question

Hi,

after profiling a lot I found out that this method takes up most of the % of calculation time. I don't really see a way to optimize, since it is a horrible function. (it is...) Maybe someone can show me some nice idea or so?

public static double perceivedLoudness(double L_G, double L_ETQ, double a0) {
  double t1 = 1d + 1 / 4d * Math.pow(10d, 0.1d * (L_G - a0 - L_ETQ));
  double t2 = Math.pow(t1, 0.25);
  return 0.064d * Math.pow(10, 0.025 * L_ETQ) * (t2 - 1);
 }

Here is the improved version:

public static double perceivedLoudness(double L_G, double L_ETQ, double a0) {
  double x = L_G - a0 - L_ETQ;
  double t1 = 0.25 * Math.exp(0.230259 * x) + 1;
  double t2 = Math.sqrt(Math.sqrt(t1));
  return ltqFactors[(int)L_ETQ]  * (t2 - 1);
 }

The lookup for ltqFactors goes this way. ltqValues hold 20 points from the given ltq function, that approx should be sufficiant.

for( int i = 0; i < etqValues.length; ++i) {
  ltqFactors[(int)etqValues[i]] = 0.064d * Math.exp(etqValues[i] * 0.05756462732485114210d);
  }

Edit: After more test runs with more files, I come up to a ~100% speed up:

• Old: 6,2% with 7000000 calls
• New: 3,2% 8000000 calls.

Thank you so far!

Edit2: I don't know which answer to accept. :( With some other improvements (mostly lookup tables) the processing time for 9000 sound files went down from 4:30min to 3:28min.

I will keep this question open to see if there are other ideas, but then accept one answer.

Edit: I'm kind of frustrated now. I use a JFace treeviewer to let the user browse the results, and it need more time to update than the calculations itself. :/

Answer 1

1. try to cache some values (I guess L_G and L_ETQ are not that variable, right?)
2. try to implement in architecture dependent code and use JNI.

Answer 2

The math does not immediately look like it can be reordered to avoid any duplicate calculations, so the approach to take depends on how this function is used and how accurate results you need.

The best approach would be avoiding recalculating the value for the same set of input values. Can your code save calculation results for the same input values? If not, you could have a cache for values, but be careful that doubles can have very many values, you might want to fold the doubles into a known interval (e.g. from 0 to 1 folds into integers from 0 to 99).

Answer 3

Your function seems to be analytic, I would suggest replacing it entirely with an interpolation method. This way, you reduce the expensive calls to Math.Pow to a few arithmetical operations.

The best in this case should be rational function approximation. Your function is likely to have poles in the complex plane, this usually defeats polynomial interpolation.

Note that you have two variables: L_G - a0 - L_ETQ and L_ETQ. Interpolation should be performed in one variable only.

I'd go for rational function approximation of t2 as a function of L_G - a0 - L_ETQ. Take a look at Numerical Recipes for implementation techniques.

Also, for the last part, replace

Math.pow(10, 0.025 * L_ETQ); 

by

Math.exp(L_ETQ * 0.05756462732485114210d)

(which is exp(L_ETQ * 0.025 * log(10))).

So you should be fine with a handful of arithmetical operations and one exponential.

EDIT: See a graph of t2 as a funtion of L_G - a0 - L_ETQ.

EDIT: Replace

double t1 = 1d + 1 / 4d * Math.pow(10d, 0.1d * (L_G - a0 - L_ETQ)); 
double t2 = Math.pow(t1, 0.25);

by

double x = L_G - a0 - L_ETQ;
double t1 = 0.25 * Math.exp(0.230259 * x) + 1;
double t2 = Math.sqrt(Math.sqrt(t1));

and you should gain some more %. At this point, rational approximation may be overengineering: you have two exp, and two sqrt.

Answer 4

I would guess

double t2 = Math.sqrt(Math.sqrt(t1));

is faster than

double t2 = Math.pow(t1, 0.25);

Answer 5

In glancing at that paper you reference, it seems that L_ETQ and a0 are simply a function of the frequency (Bark) of the sound.

So, at the very least you could come up with a table of the results of various calculations for given frequencies. For example, cache the results of:

.064 * Math.pow(10, 0.025 * L_ETQ)

by frequency. [Can also cache (a0 + L_ETQ) * .1]

Also, probably minor effect, if any, but I would convert the 1/4 to 0.25.

Answer 6

Pre-generate a lookup table for the range of inputs your program can handle.

It doesn't get any faster than that! :)

Answer 7

Caching the outputs, against the input params, may help:

http://en.wikipedia.org/wiki/Memoization

Answer 8

This hasn't been mention yet so I will.

You may want to consider moving from floating point math to integer. The operations are quite a bit faster. Graphics tend to use integer math rather than floating due to how floats are added and stored. You'll have to convert to and from, but I'm sure that you would receive quite a performance boost. The only issue with integer math is that you have to define how much precision you are willing to live with.

Answer 9

I would take some stackshots against it, to eliminate guesswork. That way I could be sure the time isn't being taken elsewhere, like in reading the data and converting it to floating point, or in opening/closing files. When I was sure this routine took a major % of time, I'm pretty sure it will be spending nearly all its time in calls to the Math functions, and in converting L_ETQ to integer. It may be possible to memoize those math functions. Then again, as Alexandre said, you might be able to do it all with interpolation.

The thing is, you probably have more than one thing to optimize. If this takes like 180 seconds, and if 50%, say, of that time this routine is on the stack, then if you cut its time by half, you have reduced time by 45 seconds to 135 seconds. However, now this routine is only on the stack for 45/135 seconds or 1/3. That means some other things are using the other 2/3 or 90 seconds, and I bet there are some things in there you could optimize as well. If you can cut those down to, say, 45 seconds, then the total is down to 90, and the % taken by the math routine is back up to 50%, so maybe you can squeeze some more out of it. That's how it goes. Each time you cut down one part of it, other parts increase in percentage, so you can go after them, over and over until you've really squeezed it as much as possible.