Re: Alternative to linewidth=-1

[Han-Wen]

I'm putting this on the ML again, it saves me the trouble of
putting it down for posteriority :-).

address@hidden writes:
> > on the whole (well perhaps more O(n log n + k n^2 ) with a very small
> 
> Oh yes, but O(n log n) is also slow compared to O(n). (I remember 
> replacing a <set> with a <vector> on a simple one million elements sieve 
> of erathostenes. I got a facter 20 speed up - 2 seconds instead of 40 - 
> because log_2(1000000) = 20)
> 
> Are there other parts of lily than the spacing that is nlogn (if we 
> asssume the same amount of variables,etc)?


The linebreaking is O(M L), where M is # measures per line, and L #
lines. Generating the spacing is O(S N), where S is the number of
systems, and N the number of measures. I'm taking a log factor, since
I guess that almost all storage (eg. resizing vectors, malloc) will
take a log factor somewhere.

If you want to know what is taking the time, you can run a profile. At
the moment, for moderate scores, "the interpreting music" phase is
relatively slow, esp. since you have to do debugging of durations with
it. There is some improvement to be made, by predefining which
engravers take what music events.

One big thing that comes to mind is the break substitution. The
present model is that there is one long line of music, and that line
is broken into multiple pieces. On the pointer side, it means
substitution must be done i.e.

  for (int i = 0; i < broken_line_count; i++)
    {
      system[i] = big_system ->clone ();
      system[i]->mutable_property_alist_
        = substitute (big_system->mutable_property_alist_);
    }

This is quadratic, but maybe not in a big way. The number of systems
is proportional (with small constant) to the length of the piece, the
length of mutable_property_alist_ is proportional to the number of
grobs in the piece (ie. proportional with large constant to the length
of the piece). The substitute routine itself is straightforward
(fast), although it does allocate a lot of memory in teensy bits.

It would be an interesting optimization to see if you can optimize the
break substitution (which happens for every spanner, btw), to be
quicker. The crux of the issue that the grobs are ordered like this in
the grob lists:

        system3 system3 ... system3 (*)  system2 system2 .. system2 (**)
        system1 ... system1

When you're doing the substitution for system3, then there is no need
to look beyond (*). When you do it  for system2, then start at (*),
end at (**). Currently, every substitution just walks the entire list.

The simplest idea that comes to my mind to fix this, is to convert the
list to a vector temporarily, see where the (*) points in the list are
(I'd guess that this should be possible in linear time), and modify
the existing list-substitution function to start at (*) take an (**)
argument. Probably this is only worth the trouble for long lists, so
you should determine if this worth the trouble first.


see break-substitution.cc

The other biggie is Garbage Collection; this is why I say that you
should profile before trying to optimize. I recently was shocked to
find out that lilypond spends 20 to 50 % in GC; GUILE uses mark&sweep
GC, which is linear in the amount of heap used (length of score). It
doesn't know we have this large heap, so it gets invoked probably a
linear number of times as well.  I'm looking into writing a
generational GC for GUILE, but if you want to take that off my hands,
you're welcome :)








-- 

Han-Wen Nienhuys   |   address@hidden   |   http://www.cs.uu.nl/~hanwen