On Feb 19, 2012, at 10:31 PM, Joe Neeman wrote: > On Sun, Feb 19, 2012 at 11:59 AM, David Kastrup <d...@gnu.org> wrote: > "m...@apollinemike.com" <m...@apollinemike.com> 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). Cheers, MS
_______________________________________________ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
