Issue 4129050: Introduce Beam_scoring_problem::quant_range, for quickly filtering out invalid positions. (Closed)
|
Created:
13 years, 2 months ago by hanwenn Modified:
13 years, 2 months ago CC:
lilypond-devel_gnu.org Visibility:
Public. |
DescriptionIntroduce Beam_scoring_problem::quant_range, for quickly filtering out invalid positions.
This reduces the number of scoring passes from 40k to 20k in
morgenlied.ly with #'region-size = 4.
Patch Set 1 #
Total comments: 1
Patch Set 2 : fix tremolo beams. #
MessagesTotal messages: 9
Introduce Beam_scoring_problem::quant_range, for quickly filtering out invalid positions. This reduces the number of scoring passes from 40k to 20k in morgenlied.ly with #'region-size = 4. note - i'll use this to throw out collisions which aren't colliding in the future.
Sign in to reply to this message.
LGTM, but I can't do a regtest today :( http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc File lily/beam-quanting.cc (right): http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc#newcode215 lily/beam-quanting.cc:215: } Very cool stuff! I won't have time to do a regtest today, but I see what you're doing and it makes a lot of sense. One suggestion: perhaps we should create an enum: enum Stem_dir_scenarios { ALL_UP, ALL_DOWN, DOWN_TO_UP, UP_TO_DOWN, WACKY } that provides a tag for the beam which is then used in this function. My rationale is as follows: There are several functions that cycle through all the stems of a beam before we get to this one (the slope calculating function, for example). If this distinction can be added to a beam before you get here, it can save you a bit of code-duping and it can also constrain the problem even further. If I'm reading this correctly, you're accounting for the first four scenarios in the enum proposed above but not the 5th, where there are stems do not go uniformly from one direction to another (something like c,,16 [c''''' c,, c''''' c,, c,, c'''' ] may do the trick). In this case, you could squish the range even more on the ed side - it would look a lot like your code for the -ed side.
Sign in to reply to this message.
On 2011/02/04 12:08:04, MikeSol wrote: > LGTM, but I can't do a regtest today :( Regtest comparison looks fine.
Sign in to reply to this message.
On Fri, Feb 4, 2011 at 10:08 AM, <mtsolo@gmail.com> wrote: > LGTM, but I can't do a regtest today :( > > > http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc > File lily/beam-quanting.cc (right): > > http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc#newcode215 > lily/beam-quanting.cc:215: } > Very cool stuff! > I won't have time to do a regtest today, but I see what you're doing and > it makes a lot of sense. > One suggestion: perhaps we should create an enum: > enum Stem_dir_scenarios { ALL_UP, ALL_DOWN, DOWN_TO_UP, UP_TO_DOWN, > WACKY } that provides a tag for the beam which is then used in this > function. My rationale is as follows: It's for dealing with UP/UP and DOWN/DOWN configs for the outer stems. Collisions that fall below (for UP/UP) the edges of quant_range will never really collide. UP/UP and DOWN/DOWN are the normal configurations, so they would account for 99% of the beam cases. -- Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen
Sign in to reply to this message.
On Feb 4, 2011, at 10:19 AM, Han-Wen Nienhuys wrote: > On Fri, Feb 4, 2011 at 10:08 AM, <mtsolo@gmail.com> wrote: >> LGTM, but I can't do a regtest today :( >> >> >> http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc >> File lily/beam-quanting.cc (right): >> >> http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc#newcode215 >> lily/beam-quanting.cc:215: } >> Very cool stuff! >> I won't have time to do a regtest today, but I see what you're doing and >> it makes a lot of sense. >> One suggestion: perhaps we should create an enum: >> enum Stem_dir_scenarios { ALL_UP, ALL_DOWN, DOWN_TO_UP, UP_TO_DOWN, >> WACKY } that provides a tag for the beam which is then used in this >> function. My rationale is as follows: > > It's for dealing with UP/UP and DOWN/DOWN configs for the outer stems. > Collisions that fall below (for UP/UP) the edges of quant_range will > never really collide. UP/UP and DOWN/DOWN are the normal > configurations, so they would account for 99% of the beam cases. > True, although I think it's important to account for all beaming cases if possible. My old collision code used to work with first_normal_stem and last_normal_stem, but the problem I ran into is that if there are stems in the interior that go in directions other than these (for example, if the beam stems are down [ up up up up up up up down ], which happens a lot in Debussy), looking at just these stems does not reflect what's actually going on w/ the beam. I don't think accounting for all beam cases adds significant overhead to the code: if anything, difficult beaming can simply revert to the old non-optimized behavior (or a variant of it). Cheers, MS
Sign in to reply to this message.
On Feb 4, 2011, at 10:30 AM, Mike Solomon wrote: > On Feb 4, 2011, at 10:19 AM, Han-Wen Nienhuys wrote: > >> On Fri, Feb 4, 2011 at 10:08 AM, <mtsolo@gmail.com> wrote: >>> LGTM, but I can't do a regtest today :( >>> >>> >>> http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc >>> File lily/beam-quanting.cc (right): >>> >>> http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc#newcode215 >>> lily/beam-quanting.cc:215: } >>> Very cool stuff! >>> I won't have time to do a regtest today, but I see what you're doing and >>> it makes a lot of sense. >>> One suggestion: perhaps we should create an enum: >>> enum Stem_dir_scenarios { ALL_UP, ALL_DOWN, DOWN_TO_UP, UP_TO_DOWN, >>> WACKY } that provides a tag for the beam which is then used in this >>> function. My rationale is as follows: >> >> It's for dealing with UP/UP and DOWN/DOWN configs for the outer stems. >> Collisions that fall below (for UP/UP) the edges of quant_range will >> never really collide. UP/UP and DOWN/DOWN are the normal >> configurations, so they would account for 99% of the beam cases. >> > True, although I think it's important to account for all beaming cases if possible. My old collision code used to work with first_normal_stem and last_normal_stem, but the problem I ran into is that if there are stems in the interior that go in directions other than these (for example, if the beam stems are down [ up up up up up up up down ], which happens a lot in Debussy), looking at just these stems does not reflect what's actually going on w/ the beam. I don't think accounting for all beam cases adds significant overhead to the code: if anything, difficult beaming can simply revert to the old non-optimized behavior (or a variant of it). > > Cheers, > MS > I just integrated all of my work into Han-Wen's new quanting stuff. None of it seems to be broken - all of the collisions are still avoided. http://codereview.appspot.com/4131044 Please disregard the previous Rietveld issue on this subject. Cheers, MS
Sign in to reply to this message.
On Fri, Feb 4, 2011 at 1:30 PM, Mike Solomon <mikesol@ufl.edu> wrote: > On Feb 4, 2011, at 10:19 AM, Han-Wen Nienhuys wrote: > >> On Fri, Feb 4, 2011 at 10:08 AM, <mtsolo@gmail.com> wrote: >>> LGTM, but I can't do a regtest today :( >>> >>> >>> http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc >>> File lily/beam-quanting.cc (right): >>> >>> http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc#newcode215 >>> lily/beam-quanting.cc:215: } >>> Very cool stuff! >>> I won't have time to do a regtest today, but I see what you're doing and >>> it makes a lot of sense. >>> One suggestion: perhaps we should create an enum: >>> enum Stem_dir_scenarios { ALL_UP, ALL_DOWN, DOWN_TO_UP, UP_TO_DOWN, >>> WACKY } that provides a tag for the beam which is then used in this >>> function. My rationale is as follows: >> >> It's for dealing with UP/UP and DOWN/DOWN configs for the outer stems. >> Collisions that fall below (for UP/UP) the edges of quant_range will >> never really collide. UP/UP and DOWN/DOWN are the normal >> configurations, so they would account for 99% of the beam cases. >> > True, although I think it's important to account for all beaming cases if possible. This is a performance optimization, ie. a way to run collision detection without performance impact if the object does not really collide, so it does not need to deal with all cases. -- Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen
Sign in to reply to this message.
On Feb 5, 2011, at 7:40 AM, Han-Wen Nienhuys wrote: > On Fri, Feb 4, 2011 at 1:30 PM, Mike Solomon <mikesol@ufl.edu> wrote: >> On Feb 4, 2011, at 10:19 AM, Han-Wen Nienhuys wrote: >> >>> On Fri, Feb 4, 2011 at 10:08 AM, <mtsolo@gmail.com> wrote: >>>> LGTM, but I can't do a regtest today :( >>>> >>>> >>>> http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc >>>> File lily/beam-quanting.cc (right): >>>> >>>> http://codereview.appspot.com/4129050/diff/1/lily/beam-quanting.cc#newcode215 >>>> lily/beam-quanting.cc:215: } >>>> Very cool stuff! >>>> I won't have time to do a regtest today, but I see what you're doing and >>>> it makes a lot of sense. >>>> One suggestion: perhaps we should create an enum: >>>> enum Stem_dir_scenarios { ALL_UP, ALL_DOWN, DOWN_TO_UP, UP_TO_DOWN, >>>> WACKY } that provides a tag for the beam which is then used in this >>>> function. My rationale is as follows: >>> >>> It's for dealing with UP/UP and DOWN/DOWN configs for the outer stems. >>> Collisions that fall below (for UP/UP) the edges of quant_range will >>> never really collide. UP/UP and DOWN/DOWN are the normal >>> configurations, so they would account for 99% of the beam cases. >>> >> True, although I think it's important to account for all beaming cases if possible. > > This is a performance optimization, ie. a way to run collision > detection without performance impact if the object does not really > collide, so it does not need to deal with all cases. > From reading the code (correct me if I'm wrong), the upper collision in the attachment would be taken into account because its stems all point in the same direction, whereas the bottom one would not because its first and last stem do not completely reflect the beam's stems' directions.
Sign in to reply to this message.
On Sat, Feb 5, 2011 at 1:51 PM, Mike Solomon <mikesol@ufl.edu> wrote: >>> True, although I think it's important to account for all beaming cases if possible. >> >> This is a performance optimization, ie. a way to run collision >> detection without performance impact if the object does not really >> collide, so it does not need to deal with all cases. >> > > From reading the code (correct me if I'm wrong), the upper collision in the attachment would be taken into account because its stems all point in the same direction, whereas the bottom one would not because its first and last stem do not completely reflect the beam's stems' directions. ? I'm intending to short-cut situations like the one in the image attached; the lower note head is outside the range allowed for the beam, so it makes no sense checking it for collisions. > Is there any way that I could measure what type of performance hit LilyPond is taking with this more robust beam-collision code? I am not really qualified to speak to what type of trade-off is acceptable, but it'd be good to have an actual benchmark to make the comparison. You can get a rough impression using ly:beam-score-count. Another option is to run a profile on a beam-heavy piece. The last time I did that, IIRC, beam scoring was ~ 10% of total time spent: not enough for it to be worth optimizing a lot, but important enough that making it much slower will be noticeable. This was a long time ago, so, the balance of expenses may have changed though. -- Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen
Sign in to reply to this message.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
