On Sun, Feb 19, 2012 at 1:22 PM, m...@apollinemike.com < m...@apollinemike.com> wrote:
> > 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). > [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
_______________________________________________ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
