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).
Cheers, MS
|