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:
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).
Another possible speedup could come from the initial building of the skylines using add_boxes: when the children of an axis-group mostly don't have skylines, then we gather up all of their extent boxes, before turning them into one skyline and merging it (this is O(n log n) in the number of children). If the children do have skylines, we merge them one at a time (this is O(n^2), but it didn't use to matter because there were very few children that had their own skylines). To fix this, you could make a constructor for skylines that takes a vector of skylines and merges them recursively, in the same way that internal_build_skyline merges boxes recursively.
Again, you should only do this if you have evidence that the skyline merges caused by add_boxes are taking lots of time.
Cheers,
Joe