[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: address@hidden
Subject: Re: Gets vertical skylines from grob stencils (issue 5626052)
Date: Sun, 19 Feb 2012 23:22:18 +0200

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 w/ ly:beam::vertical-skylines, for example, but I'm not sure how much this slows things down).


reply via email to

[Prev in Thread] Current Thread [Next in Thread]