Summary: | Optimize to not use pow() in the inner loop in AudioParamTimeline | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Product: | WebKit | Reporter: | Wei James (wistoch) <james.wei> | ||||||||||
Component: | Web Audio | Assignee: | Wei James (wistoch) <james.wei> | ||||||||||
Status: | RESOLVED FIXED | ||||||||||||
Severity: | Normal | CC: | crogers, james.wei, kbr, rtoy, webkit.review.bot | ||||||||||
Priority: | P2 | ||||||||||||
Version: | 528+ (Nightly build) | ||||||||||||
Hardware: | Unspecified | ||||||||||||
OS: | Unspecified | ||||||||||||
Attachments: |
|
Description
Wei James (wistoch)
2011-11-30 23:35:24 PST
Can you be a little more specific as to what you’d like to optimize to not use pow() in the inner loop? Created attachment 117360 [details]
optimize to not use pow in the inner loop
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. (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 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. 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.
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. 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
(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 (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. 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
(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 (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. (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+. (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. Can we get a layout test to validate? The currentTime var is no longer getting updated - may not be correct... 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. (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 (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 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.
(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! (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 I'll try to have a look tomorrow. 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... 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 > > 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.
Created attachment 118942 [details]
Patch
(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 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. 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 Created attachment 118949 [details]
Patch
Looks fine to me. Comment on attachment 118949 [details]
Patch
Sounds good. rs=me
(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 Comment on attachment 118949 [details] Patch Clearing flags on attachment: 118949 Committed r102733: <http://trac.webkit.org/changeset/102733> All reviewed patches have been landed. Closing bug. |