Bug 73530 - Optimize to not use pow() in the inner loop in AudioParamTimeline
Summary: Optimize to not use pow() in the inner loop in AudioParamTimeline
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Audio (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Wei James (wistoch)
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2011-11-30 23:35 PST by Wei James (wistoch)
Modified: 2011-12-13 20:57 PST (History)
5 users (show)

See Also:


Attachments
optimize to not use pow in the inner loop (2.16 KB, patch)
2011-12-01 00:14 PST, Wei James (wistoch)
kbr: review-
Details | Formatted Diff | Diff
optimize to not use pow in the inner loop -- updated (2.89 KB, patch)
2011-12-01 16:41 PST, Wei James (wistoch)
no flags Details | Formatted Diff | Diff
Patch (3.19 KB, patch)
2011-12-12 19:52 PST, Wei James (wistoch)
no flags Details | Formatted Diff | Diff
Patch (2.10 KB, patch)
2011-12-12 21:29 PST, Wei James (wistoch)
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Wei James (wistoch) 2011-11-30 23:35:24 PST
Optimize to not use pow() in the inner loop
Comment 1 Mark Rowe (bdash) 2011-11-30 23:56:45 PST
Can you be a little more specific as to what you’d like to optimize to not use pow() in the inner loop?
Comment 2 Wei James (wistoch) 2011-12-01 00:14:02 PST
Created attachment 117360 [details]
optimize to not use pow in the inner loop
Comment 3 Wei James (wistoch) 2011-12-01 00:17:02 PST
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.
Comment 4 Wei James (wistoch) 2011-12-01 00:30:16 PST
(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
Comment 5 Raymond Toy 2011-12-01 09:03:13 PST
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 6 Kenneth Russell 2011-12-01 11:39:04 PST
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.
Comment 7 Raymond Toy 2011-12-01 12:18:53 PST
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.
Comment 8 Wei James (wistoch) 2011-12-01 16:41:05 PST
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
Comment 9 Wei James (wistoch) 2011-12-01 16:46:36 PST
(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
Comment 10 Wei James (wistoch) 2011-12-01 16:49:38 PST
(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 11 Kenneth Russell 2011-12-01 16:51:41 PST
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
Comment 12 Wei James (wistoch) 2011-12-01 17:03:39 PST
(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
Comment 13 Kenneth Russell 2011-12-01 17:06:24 PST
(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.
Comment 14 Kenneth Russell 2011-12-01 17:06:35 PST
(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+.
Comment 15 Wei James (wistoch) 2011-12-01 21:08:55 PST
(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.
Comment 16 Chris Rogers 2011-12-02 02:18:42 PST
Can we get a layout test to validate?  The currentTime var is no longer getting updated - may not be correct...
Comment 17 Chris Rogers 2011-12-02 02:30:44 PST
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.
Comment 18 Wei James (wistoch) 2011-12-02 05:36:52 PST
(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
Comment 19 Wei James (wistoch) 2011-12-02 05:42:00 PST
(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 20 Kenneth Russell 2011-12-02 12:41:25 PST
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.
Comment 21 Chris Rogers 2011-12-02 19:59:50 PST
(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!
Comment 22 Wei James (wistoch) 2011-12-11 17:36:40 PST
(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
Comment 23 Chris Rogers 2011-12-11 22:56:24 PST
I'll try to have a look tomorrow.
Comment 24 Chris Rogers 2011-12-12 16:10:13 PST
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 25 Wei James (wistoch) 2011-12-12 17:28:51 PST
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
Comment 26 Chris Rogers 2011-12-12 17:40:06 PST
> > 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.
Comment 27 Wei James (wistoch) 2011-12-12 19:52:01 PST
Created attachment 118942 [details]
Patch
Comment 28 Wei James (wistoch) 2011-12-12 19:52:57 PST
(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 29 Chris Rogers 2011-12-12 20:10:59 PST
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 30 Wei James (wistoch) 2011-12-12 21:12:11 PST
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
Comment 31 Wei James (wistoch) 2011-12-12 21:29:39 PST
Created attachment 118949 [details]
Patch
Comment 32 Chris Rogers 2011-12-13 15:47:07 PST
Looks fine to me.
Comment 33 Kenneth Russell 2011-12-13 15:51:35 PST
Comment on attachment 118949 [details]
Patch

Sounds good. rs=me
Comment 34 Wei James (wistoch) 2011-12-13 16:34:56 PST
(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 35 WebKit Review Bot 2011-12-13 20:57:11 PST
Comment on attachment 118949 [details]
Patch

Clearing flags on attachment: 118949

Committed r102733: <http://trac.webkit.org/changeset/102733>
Comment 36 WebKit Review Bot 2011-12-13 20:57:17 PST
All reviewed patches have been landed.  Closing bug.