Re: Gets vertical skylines from grob stencils (issue 5626052)

[Joe Neeman]

On Sun, Feb 19, 2012 at 1:22 PM, address@hidden <address@hidden> wrote:

On Feb 19, 2012, at 10:31 PM, Joe Neeman wrote:

On Sun, Feb 19, 2012 at 11:59 AM, David Kastrup <address@hidden> wrote:

"address@hidden" <address@hidden> writes:

> I've now optimized the crap out of this sucker and cached as much as I
> can cache.

I'm not sure the caching is of much help.  What kind of information
would save recalculation?

>  For example, I get the sense that the new key signature skyline
> function is not much faster than the old, which means that either the
> lookups of cached accidental skylines or the merging of these skylines
> to create the signature takes a lot of time.

"Merging" sounds like O(n^2) unless one takes precautions.

No, it's O(n + m). (m is the length of the other skyline). Building a skyline from scratch is O(n log n). However, there may be room for more heuristics that speed things up (see non_overlapping_skyline, which resulted in a measurable speedup).

If you get a chance to look over the entirety of the patch w/ your speed-up glasses on, I'd appreciate it.  I know it looks like a lot, but the gist of it is that there are two main vertical-skylines functions (ly:grob::vertical-skylines-from-stencil and ly:grob::vertical-skylines-from-element-stencils) and the other skyline functions are (supposed to be) speed ups (ly:key-signature::vertical-skylines is probably the heftiest one).  Lemme know if in any of these things you see places where I may be creating bottlenecks, where Scheme code may be slowing things down, where I'm passing around too-large data structures, needless recalculation (if it winds up being a lot of recalculation - I know I do some in beam.cc w/ ly:beam::vertical-skylines, for example, but I'm not sure how much this slows things down).

[Sorry, forgot to reply all...]

 

I think you're going about things in the wrong order. I think that the first goal should be to make the code clear and correct. (In fact, if your code were "done" but slow, you could push it to master but with skylining disabled for most grobs by default. That way, people could test it and give feedback. They could even enable skylining on more grobs if they didn't mind the performance hit.) Then you should profile and benchmark it to figure out which parts need to be faster (use ./configure --enable-profiling). For example, do you know that making special cases for beams and key signatures actually helps?

Having said that, there are two places that I can think of which *might* speed things up:

 - you return a lot of vector<Box> in stencil-intergrate.cc. This might mean that a lot of things get copied (not sure about this -- c++11 is supposed to help here). It might speed things up if you pass around const vector<Box>& instead.

 - the skylines you generate are a lot more complicated than they need to be. For example, you approximate beams with 11 horizontal segments. If you were to implement my suggestion about turning line segments into skylines, you could represent a beam with 1 sloped segment.

I would encourage you to do the second part _before_ profiling, since I think it would make the code cleaner. The first part, though, you definitely shouldn't do unless you know that it's a problem.

By the way, could you update your git branch please?

Cheers,

Joe