Re: Getting the height of a system.

[Joe Neeman]

On Sun, 14 May 2006 20:40, Han-Wen Nienhuys wrote:
> Joe Neeman schreef:
> > We discussed this a bit a long time ago but I'm getting close to actually
> > implementing something so I thought I'd bring it up again.
> >
> > Getting the Y-extent of a system is potentially destructive, causing all
> > sorts of non-undoable caching and possibly suiciding of grobs. So I need
> > to do make a copy of the system before I can get its Y-extent.
> >
> > The problem is that there are a large number of possible lines in a
> > score. To copy a system, I need to do a full grob substitution for every
> > grob in that system. If each bar could be in up to N possible lines, I
> > need to do N full copies of the entire score and N full grob
> > substitutions in the
> > object_alist_. If we can fit up to K bars to a line then N is
> > approximately K(K-1)/2. In the scores I typically work with, N would be
> > around 50-60 so this is getting pretty expensive.
>
> It's much worse than that, because the cost of the substitution is
> actually proportional to the number grobs in the "long" System, i.e. the
> length of the entire score.  It would be much much better if you could
> make your algorithm compute the system heights of a complete line
> breaking configuration.

I think this could be even more expensive because my page breaker looks at a 
_lot_ of different line breaking configurations. On the score I have been 
using for coverage tests (Haydn op 76, no 3, 1st violin part), the page 
breaker tests more than 4000 different line breaking configurations so this 
is already much more expensive than doing it for 50-60 copies of the score.

> Also, it's not completely possible to compute the height of an isolated
> system: some grobs (notably spanners like slur) look at the next system
> to decide how to format across line breaks.

Would it be acceptable to skip those cases? This would be a good point to 
mention that I don't really need the exact height of the system -- just an 
approximation. The current approximation I am using (setting a score-wide 
system-height) is _very_ crude but it works pretty well as long as there are 
no RemoveEmptyStaffContexts or very high notes.

>
> > So I propose the following instead. I don't know a great deal (yet) about
> > the C++ internals of grobs so I'd appreciate knowing if this is
> > unworkable before I spend lots of time trying to implement it.
> >
> > 1) add a virtual Grob *save () and virtual void restore (Grob*) function
> > to every C++ Grob subclass. save() would be a bit like clone except that
> > it copies the object_alist_ and, for example, broken_intos_ in the case
> > of a Spanner.
> > Grob *copy = me->save ();
> > // make some changes to me
> > me->restore (copy);
> > and you end up with the same grob you started with.
> >
> > 2) save every grob in the score
> >
> > 3) for each possible system, using the original grobs,
> >     - work out the Y-extent
> >     - restore () every grob in that system
> >
> > The advantage is that we avoid fiddling around with the object_alist_
> > because this clone is never used -- it exists only to save the state of
> > the score before we mess it up with calling Y-extent. We also only have
> > to make one copy of the system and restore it N times instead of making N
> > copies.
>
> Sounds like a possiblity, but have you also considered break alignments?
> It's not only the object_alist_  (and property_alist_, as that too will
> change), but also other pointers like original_.

I hadn't, but it's just a matter of copying a few more bits of data, right?

>
> Secondly, although it will be nicely portable, it also sounds like a lot
> of work. Isn't it a lot easier to simply do a fork() and let the OS
> clean up after us? Perhaps if the vertical spacing is completely
> working, we can consider doing the full-blown copy and restore. Also,
> for large scores, fork() is an interesting option, as we could get some
> benefit from using SMP.

But then the OS would have to deal with copying the data and it can only do 
that in page-sized chunks. So wouldn't this just increase the amount of stuff 
that gets copied?

Getting a bit OT, the gomp project was recently checked in for GCC 4.2 
[http://gcc.gnu.org/wiki/GCC 4.2 Projects]. If you want to introduce 
parallelism, it might be a worthwhile thing to wait for since it is portable 
and _much_ easier to use than either fork() or pthreads.


There is actually another possibility that I've only just thought of so it's 
pretty half-baked:
Add an approximate-Y-extent to each grob that
1) leaves the grob constant (in particular no caching)
2) ignores anything in the object_alist_ that doesn't have a system.

Then we could even get away with not doing any break-substitutions (until it's 
time to typeset things, of course) with something like:
Real System::guess_line_height (Column_x_positions col)
{
        set_bound (LEFT, col.cols_[0]);
        set_bound (RIGHT, col.cols_.back ());
        for (vsize i = 0; i < col.cols_.size (); i++)
        {
                // translate axis (as in System::break_into_pieces)
                col.cols_[i].system_ = this;
        }
        set_loose_columns (this, &col);
        SCM h = this->get_property ("approximate-Y-extent");
        for (vsize i = 0; i < col.cols_.size (); i++)
        {
                // translate the axis back
                col.cols_.system_ = 0;
        }
        return scm_to_double (h);
}

That is, we can pretend we're working on the original system and get away with 
it because approximate-Y-extent will be guaranteed not to leave any 
side-effects. Condition (2) means that we can get away with doing it a system 
at a time. A spanner that crosses a line break will realise that it is 
crossing the line break and will try to provide a sensible guess.