Bug 73530 – Optimize to not use pow() in the inner loop in AudioParamTimeline

• Status: RESOLVED
• Resolution: FIXED
• Component: Web Audio

[Wei James (wistoch)]

Optimize to not use pow() in the inner loop

[Mark Rowe (bdash)]

Can you be a little more specific as to what you’d like to optimize to not use pow() in the inner loop?

[Wei James (wistoch)]

Created attachment 117360 [details]
optimize to not use pow in the inner loop

[Wei James (wistoch)]

in AudioParamTimeline::valuesForTimeRangeImpl to handle AudioEvent, it is mentioned to optimize to not use pow() in the inner loop as it is just a simple exponential ramp. 

this patch to implement this optimization.

[Wei James (wistoch)]

(In reply to comment #1)
> Can you be a little more specific as to what you’d like to optimize to not use pow() in the inner loop?

an error occurs when I use webkit-patch to create this bug entry and leaves just a simple description. Sorry for it. I have added a more detailed information and patch. thanks

[Raymond Toy]

Thanks for the patch.  I have not yet examined it, but note that there is some discussion in the audio w3c group (http://lists.w3.org/Archives/Public/public-audio/2011OctDec/0107.html) about what the ramp is supposed to do.  The issue is that the starting value cannot currently be 0, because the ramp is, essentially, value1 * exp(t/T).  The implementation of the ramp may change.

[Kenneth Russell]

Comment on attachment 117360 [details]
optimize to not use pow in the inner loop

Raymond and I both reviewed the math and it looks correct. Despite the fact that the ramp function might be redefined soon, I think it's worth adding this optimization.

I think the patch needs to be rebaselined to top of tree though. Could you take care of that? r- just for this issue.

[Raymond Toy]

Also, can you add a comment on what the formula actually is and what the optimization is now doing to the formula?  I think the original is

v(t) = 2^((1-x(t))*v1 + x(t)*v2) with x(t) = (t-t1)*k

You've changed this to be

v(t+dt) = v(t)*2^((v2-v1)*k)

roughly.  This makes it easier to tell that the math is right.

[Wei James (wistoch)]

Created attachment 117522 [details]
optimize to not use pow in the inner loop -- updated 

Fix patch top tree issue and add comments to explain the formula

[Wei James (wistoch)]

(In reply to comment #5)
> Thanks for the patch.  I have not yet examined it, but note that there is some discussion in the audio w3c group (http://lists.w3.org/Archives/Public/public-audio/2011OctDec/0107.html) about what the ramp is supposed to do.  The issue is that the starting value cannot currently be 0, because the ramp is, essentially, value1 * exp(t/T).  The implementation of the ramp may change.

Raymond, thanks for the information. I noticed the notes Alistair sent out. 

If the final exponential ramp algorithm finalized, I have the interest to implement it then. thanks

[Wei James (wistoch)]

(In reply to comment #6)
> (From update of attachment 117360 [details])
> Raymond and I both reviewed the math and it looks correct. Despite the fact that the ramp function might be redefined soon, I think it's worth adding this optimization.
> 
> I think the patch needs to be rebaselined to top of tree though. Could you take care of that? r- just for this issue.

Ken, thanks for the review. I have updated the patch based on the top of WebKit tree. Also, I added some comments to explain the algorithm of optimization.

[Kenneth Russell]

Comment on attachment 117522 [details]
optimize to not use pow in the inner loop -- updated 

Thanks for the update. Looks good. Please use "webkit-patch upload" in the future to upload patches as it will streamline some of the process. If you'd like this committed please mark it "cq?". r=me

[Wei James (wistoch)]

(In reply to comment #11)
> (From update of attachment 117522 [details])
> Thanks for the update. Looks good. Please use "webkit-patch upload" in the future to upload patches as it will streamline some of the process. If you'd like this committed please mark it "cq?". r=me

Ken, thanks for the review and the remind. I have marked it as cq?. could you please help to commit it? thanks

[Kenneth Russell]

(In reply to comment #12)
> (In reply to comment #11)
> > (From update of attachment 117522 [details] [details])
> > Thanks for the update. Looks good. Please use "webkit-patch upload" in the future to upload patches as it will streamline some of the process. If you'd like this committed please mark it "cq?". r=me
> 
> Ken, thanks for the review and the remind. I have marked it as cq?. could you please help to commit it? thanks

I'll mark it r+ as soon as it passes the Chromium Linux EWS bot.

[Kenneth Russell]

(In reply to comment #13)
> (In reply to comment #12)
> > (In reply to comment #11)
> > > (From update of attachment 117522 [details] [details] [details])
> > > Thanks for the update. Looks good. Please use "webkit-patch upload" in the future to upload patches as it will streamline some of the process. If you'd like this committed please mark it "cq?". r=me
> > 
> > Ken, thanks for the review and the remind. I have marked it as cq?. could you please help to commit it? thanks
> 
> I'll mark it r+ as soon as it passes the Chromium Linux EWS bot.

Er, I meant cq+.

[Wei James (wistoch)]

(In reply to comment #13)
> (In reply to comment #12)
> > (In reply to comment #11)
> > > (From update of attachment 117522 [details] [details] [details])
> > > Thanks for the update. Looks good. Please use "webkit-patch upload" in the future to upload patches as it will streamline some of the process. If you'd like this committed please mark it "cq?". r=me
> > 
> > Ken, thanks for the review and the remind. I have marked it as cq?. could you please help to commit it? thanks
> 
> I'll mark it r+ as soon as it passes the Chromium Linux EWS bot.

thanks.

[Chris Rogers]

Can we get a layout test to validate?  The currentTime var is no longer getting updated - may not be correct...

[Chris Rogers]

Wei thanks for the patch!  I'm on vacation right now, but would like refine this a bit more when I get back (hope you can wait).  Btw the starting at zero issue is not a bug so I dont't expect the math to change.

[Wei James (wistoch)]

(In reply to comment #16)
> Can we get a layout test to validate?  The currentTime var is no longer getting updated - may not be correct...

Roger, thanks for the comments. 

Is there any reference to write layout test for webaudio AudioParam? I have tried to write a layout test but failed to find a reference and don't know how to use the layout test to verify the change.  So I just wrote some unit tests to verify the correctness of the optimization algorithm and test the performance of the function. 

for the var currentTime, it is a local variable and not used after the if statement for ExponentialRampToValue, so I just ignore it. you can double check it. 

thanks

[Wei James (wistoch)]

(In reply to comment #17)
> Wei thanks for the patch!  I'm on vacation right now, but would like refine this a bit more when I get back (hope you can wait).  Btw the starting at zero issue is not a bug so I dont't expect the math to change.

Roger, that's ok for me. It is my honor if I can contribute to webaudio. I am very interested in this area but still a newbie. Hope I can be an expert on this area and contribute more to it in future. thanks

[Kenneth Russell]

Comment on attachment 117522 [details]
optimize to not use pow in the inner loop -- updated 

Since Chris indicated this needs more work I'm changing the review state to r-. Let's iterate more next week.

[Chris Rogers]

(In reply to comment #19)
> (In reply to comment #17)
> > Wei thanks for the patch!  I'm on vacation right now, but would like refine this a bit more when I get back (hope you can wait).  Btw the starting at zero issue is not a bug so I dont't expect the math to change.
> 
> Roger, that's ok for me. It is my honor if I can contribute to webaudio. I am very interested in this area but still a newbie. Hope I can be an expert on this area and contribute more to it in future. thanks

James, thanks for you patience.  I'm getting back around Dec. 11 and look forward to working more with you.  Thanks for your help!

[Wei James (wistoch)]

(In reply to comment #21)
> (In reply to comment #19)
> > (In reply to comment #17)
> > > Wei thanks for the patch!  I'm on vacation right now, but would like refine this a bit more when I get back (hope you can wait).  Btw the starting at zero issue is not a bug so I dont't expect the math to change.
> > 
> > Roger, that's ok for me. It is my honor if I can contribute to webaudio. I am very interested in this area but still a newbie. Hope I can be an expert on this area and contribute more to it in future. thanks
> 
> James, thanks for you patience.  I'm getting back around Dec. 11 and look forward to working more with you.  Thanks for your help!

roger, I have marked the patch as r?, could you help to review it? thanks

[Chris Rogers]

I'll try to have a look tomorrow.

[Chris Rogers]

Comment on attachment 117522 [details]
optimize to not use pow in the inner loop -- updated 

View in context: https://bugs.webkit.org/attachment.cgi?id=117522&action=review

> Source/WebCore/webaudio/AudioParamTimeline.cpp:262
> +                // So v(t+dt) = v(t) * 2 ^ (k * sampleFrameTimeIncr * (v2 - v1))

This can be made quite a bit simpler if you get rid of the log2() conversions on lines 249:250 and do the math directly in linear space.

Then you can have something like:

double numSampleFrames = deltaTime * sampleRate;
double multiplier = pow(value2 / value1, 1 / numSampleFrames);


Note: I really wish we still were using double-precision here, but to avoid warnings caused by 64bit -> 32bit conversion (double -> float)
we switched a lot of this code over to use float.  Later to avoid accumulated error we probably need to look at this a bit more closely and switch some code back to using doubles.

but (at least for now), we should calculate "numSampleFrames" and "multiplier" as float

> Source/WebCore/webaudio/AudioParamTimeline.cpp:269
> +                writeIndex++;

I would remove lines 264:269

> Source/WebCore/webaudio/AudioParamTimeline.cpp:273
> +                double multiplier = powf(2.0f, k * sampleFrameTimeIncr * (value2 - value1));

and calculate multiplier as I suggest above (but using float)

> Source/WebCore/webaudio/AudioParamTimeline.cpp:276
> +                    values[writeIndex] = temp;

We need to maintain/update the two variables "value" and "currentTime" since they're propagated to other parts of the code within this loop.

I would suggest this code for the inner loop:

values[writeIndex] = value;
value *= multiplier;
currentTime += sampleFrameTimeIncr;


*** actually the "currentTime" updating can be pulled outside of the loop here and in the linear case...

[Wei James (wistoch)]

Comment on attachment 117522 [details]
optimize to not use pow in the inner loop -- updated 

View in context: https://bugs.webkit.org/attachment.cgi?id=117522&action=review

>> Source/WebCore/webaudio/AudioParamTimeline.cpp:262
>> +                // So v(t+dt) = v(t) * 2 ^ (k * sampleFrameTimeIncr * (v2 - v1))
> 
> This can be made quite a bit simpler if you get rid of the log2() conversions on lines 249:250 and do the math directly in linear space.
> 
> Then you can have something like:
> 
> double numSampleFrames = deltaTime * sampleRate;
> double multiplier = pow(value2 / value1, 1 / numSampleFrames);
> 
> 
> Note: I really wish we still were using double-precision here, but to avoid warnings caused by 64bit -> 32bit conversion (double -> float)
> we switched a lot of this code over to use float.  Later to avoid accumulated error we probably need to look at this a bit more closely and switch some code back to using doubles.
> 
> but (at least for now), we should calculate "numSampleFrames" and "multiplier" as float

thanks, I will follow this to update the patch. thanks

>> Source/WebCore/webaudio/AudioParamTimeline.cpp:269
>> +                writeIndex++;
> 
> I would remove lines 264:269

A question: if we remove this block, the first value will be defaultValue. is it correct?

>> Source/WebCore/webaudio/AudioParamTimeline.cpp:273
>> +                double multiplier = powf(2.0f, k * sampleFrameTimeIncr * (value2 - value1));
> 
> and calculate multiplier as I suggest above (but using float)

I will do it. thanks

>> Source/WebCore/webaudio/AudioParamTimeline.cpp:276
>> +                    values[writeIndex] = temp;
> 
> We need to maintain/update the two variables "value" and "currentTime" since they're propagated to other parts of the code within this loop.
> 
> I would suggest this code for the inner loop:
> 
> values[writeIndex] = value;
> value *= multiplier;
> currentTime += sampleFrameTimeIncr;
> 
> 
> *** actually the "currentTime" updating can be pulled outside of the loop here and in the linear case...

got it. thanks

[Chris Rogers]

> > I would remove lines 264:269
> 
> A question: if we remove this block, the first value will be defaultValue. is it correct?
> 

value is initialized to defaultValue at the top of the function, but also its value can change multiple times through the loop as different segments are processed.
So, it should be already at the correct value.

[Wei James (wistoch)]

Created attachment 118942 [details]
Patch

[Wei James (wistoch)]

(In reply to comment #26)
> > > I would remove lines 264:269
> > 
> > A question: if we remove this block, the first value will be defaultValue. is it correct?
> > 
> 
> value is initialized to defaultValue at the top of the function, but also its value can change multiple times through the loop as different segments are processed.
> So, it should be already at the correct value.

thanks, I have updated the patch. please help to review. thanks

[Chris Rogers]

Comment on attachment 118942 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=118942&action=review

> Source/WebCore/webaudio/AudioParamTimeline.cpp:267
> +                float multiplier = powf(value2 / value1, 1 / numSampleFrames);

We should handle the case where value1 is zero to avoid divide-by-zero, and make multiplier zero in this case.

I think we should remove the comments on lines 249:259 and 261:266 and have a very simple one or two line comment directly describing the math in 267, something like:

// The value goes exponentially from value1 to value2 in a duration of deltaTime seconds (corresponding to numSampleFrames).
// Compute the per-sample multiplier.

[Wei James (wistoch)]

Comment on attachment 118942 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=118942&action=review

>> Source/WebCore/webaudio/AudioParamTimeline.cpp:267
>> +                float multiplier = powf(value2 / value1, 1 / numSampleFrames);
> 
> We should handle the case where value1 is zero to avoid divide-by-zero, and make multiplier zero in this case.
> 
> I think we should remove the comments on lines 249:259 and 261:266 and have a very simple one or two line comment directly describing the math in 267, something like:
> 
> // The value goes exponentially from value1 to value2 in a duration of deltaTime seconds (corresponding to numSampleFrames).
> // Compute the per-sample multiplier.

roger, for the case that value1 == 0 case, it will not go to this block. as the code said:

           if (value1 <= 0 || value2 <= 0) {
                // Handle negative values error case by propagating previous value.
                for (; writeIndex < fillToFrame; ++writeIndex)
                    values[writeIndex] = value;
            } else {
                   ......

I will simplify the comments. thanks

[Wei James (wistoch)]

Created attachment 118949 [details]
Patch

[Chris Rogers]

Looks fine to me.

[Kenneth Russell]

Comment on attachment 118949 [details]
Patch

Sounds good. rs=me

[Wei James (wistoch)]

(In reply to comment #33)
> (From update of attachment 118949 [details])
> Sounds good. rs=me

Ken, I mark this patch as cq?, could you help to land it? thanks

[WebKit Review Bot]

Comment on attachment 118949 [details]
Patch

Clearing flags on attachment: 118949

Committed r102733: <http://trac.webkit.org/changeset/102733>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.