Severe overestimation of line height for significantly non-rectangular systems

[joeneeman, 2010-04-09 05:46:12]

Ok, I think I understand now what y_extent does and how the code works as a
whole. In addition to some comments in the code, I have a few general concerns,
ordered from most trivial to most serious:

- Regarding the Real vs. double naming, I'm almost 100% positive that "double"
is not intentionally used anywhere. I searched for "double" in lily/ and the
only occurrences are
  - in the signature of "double log_2 (double)"
  - in page-layout-problem.cc (which I wrote)
  - in simple-spacer.cc (which I wrote a substantial portion of)
So unless you can really find something that supports your interpretation,
please change all occurrences of "double" to "Real" in your patch.

- Do we need a separate Interval for Line_details.stencil_extent_? Why not just
reuse Line_details.*_of_line_extent_?

- The hanging variables are only needed temporarily, for the computation of
y_extent_, which is the really important variable. It would clutter up
Line_details less if you could make them local variables in the function that
computes y_extent_ instead of storing them in Line_details

- The name of y_extent_ should be changed, since we use "extent" to mean an
interval, not just a length. Perhaps height_? But you should also add a comment
to explain that it is not the height of the system per se, but the additional
height needed when it is put into context.

- Page_breaking::min_page_count used to just return (as the name suggests) the
smallest number of pages on which the systems will fit. Now, however, it
performs a crucial pre-processing step as a side-effect (computing y_extent_ and
modifying all of the cached Line_details). Could the computation of y_extent_ be
moved to compress_lines, which is already a crucial pre-processing step? This
would also make min_page_count less complicated (which would be nice, because it
was pretty complicated to begin with).

http://codereview.appspot.com/879043/diff/1/2
File lily/constrained-breaking.cc (right):

http://codereview.appspot.com/879043/diff/1/2#newcode514
lily/constrained-breaking.cc:514: stencil_extent_ = unsmob_stencil
(pb->get_property ("stencil")) ->extent (Y_AXIS);
Please initialize all of the variables you've added.

http://codereview.appspot.com/879043/diff/1/2#newcode541
lily/constrained-breaking.cc:541: void Line_details::compute_hangings (double
previous_begin, double previous_rest)
void
Line_details

http://codereview.appspot.com/879043/diff/1/3
File lily/include/constrained-breaking.hh (right):

http://codereview.appspot.com/879043/diff/1/3#newcode82
lily/include/constrained-breaking.hh:82: first_markup_line_ = false;
Please make sure that the new variables you added are always initialized.

http://codereview.appspot.com/879043/diff/1/6
File lily/page-spacing.cc (right):

http://codereview.appspot.com/879043/diff/1/6#newcode55
lily/page-spacing.cc:55: rod_height_ += line.y_extent_;
This is not correct for the first line on a page, since y_extent_ assumes that
there was a previous line.

http://codereview.appspot.com/879043/diff/1/6#newcode72
lily/page-spacing.cc:72: rod_height_ += line.y_extent_;
This is not correct for the same reason, but the fix is a little more
complicated...

[Boris Shingarov, 2010-04-13 12:58:39]

http://codereview.appspot.com/879043/diff/1/2
File lily/constrained-breaking.cc (right):

http://codereview.appspot.com/879043/diff/1/2#newcode514
lily/constrained-breaking.cc:514: stencil_extent_ = unsmob_stencil
(pb->get_property ("stencil")) ->extent (Y_AXIS);
On 2010/04/09 05:46:12, joeneeman wrote:
> Please initialize all of the variables you've added.

Done: now both constructors initialize the new scalars, and explicitly
initialize the new Intervals (even though the compiler would implicitly call the
0-arg constructor).

http://codereview.appspot.com/879043/diff/1/2#newcode541
lily/constrained-breaking.cc:541: void Line_details::compute_hangings (double
previous_begin, double previous_rest)
On 2010/04/09 05:46:12, joeneeman wrote:
> void
> Line_details

Done. (Also for the other two functions down below).

[Boris Shingarov, 2010-04-13 12:59:56]

http://codereview.appspot.com/879043/diff/1/3
File lily/include/constrained-breaking.hh (right):

http://codereview.appspot.com/879043/diff/1/3#newcode82
lily/include/constrained-breaking.hh:82: first_markup_line_ = false;
On 2010/04/09 05:46:12, joeneeman wrote:
> Please make sure that the new variables you added are always initialized.

Done.

[Boris Shingarov, 2010-04-13 13:35:40]

http://codereview.appspot.com/879043/diff/1/6
File lily/page-spacing.cc (right):

http://codereview.appspot.com/879043/diff/1/6#newcode55
lily/page-spacing.cc:55: rod_height_ += line.y_extent_;
On 2010/04/09 05:46:12, joeneeman wrote:
> This is not correct for the first line on a page, since y_extent_ assumes that
> there was a previous line.

Hmmmm.  y_extent_ is calculated as a side effect of min_page_count().  The case
of first line is carefully handled: the calculation of hanging does not assume a
previous line, and the "if (i>0)" distinguishes between the hanging of the
previous line or 0 if there is no previous line.  Is there something that I
missed here?

[Boris Shingarov, 2010-04-13 13:52:39]

> - Regarding the Real vs. double naming, I'm almost 100% positive that "double"
> is not intentionally used anywhere.

Ok, done, replaced double with Real.

> - Do we need a separate Interval for Line_details.stencil_extent_? Why not
just
> reuse Line_details.*_of_line_extent_?

I wouldn't be happy to reuse it.  Logically, which one is it?  And when
debugging, it also helps to be able to easily see which case we are dealing
with.  In other words, stencil_extent is not a special case of any of
*_of_line_extent.

> - The hanging variables are only needed temporarily, for the computation of
> y_extent_, which is the really important variable. It would clutter up
> Line_details less if you could make them local variables in the function that
> computes y_extent_ instead of storing them in Line_details

Right, but I found having the whole array of hangings of great help in debugging
why pure and non-pure heights diverge.  In the publication I am helping to
typeset, we are very far from getting vertical space estimations right: pages
are underfilled/overfilled all the time.  I debug these by measuring the actual
hangings with a ruler, and then comparing them with the hangings in the vector
of Line_details.

> - The name of y_extent_ should be changed, since we use "extent" to mean an
> interval, not just a length. Perhaps height_?

No, height_ would collide with the other use of the term.  The word "space" is
taken, too.  How about "tallness".

> - Page_breaking::min_page_count used to just return (as the name suggests) the
> smallest number of pages on which the systems will fit. Now, however, it
> performs a crucial pre-processing step as a side-effect (computing y_extent_
and
> modifying all of the cached Line_details). Could the computation of y_extent_
be
> moved to compress_lines, which is already a crucial pre-processing step? This
> would also make min_page_count less complicated (which would be nice, because
it
> was pretty complicated to begin with).

Surely a nice idea.  I'll investigate.

As to the other points, see my comments inside the Rietveld issue.

[joeneeman, 2010-04-13 20:49:06]

http://codereview.appspot.com/879043/diff/1/6
File lily/page-spacing.cc (right):

http://codereview.appspot.com/879043/diff/1/6#newcode55
lily/page-spacing.cc:55: rod_height_ += line.y_extent_;
On 2010/04/13 13:35:40, Boris Shingarov wrote:
> Hmmmm.  y_extent_ is calculated as a side effect of min_page_count().  The
case
> of first line is carefully handled

Actually, this has made me realize that there is a bug in min_page_count() also.
The point is that min_page_count spaces the systems as tightly as possible,
whereas Page_spacing does not necessarily. Therefore the systems that are at the
top of a page according to min_page_count may not be at the top of a page here.
Therefore, for each system, you need to compute the tallness_ with respect both
to the previous system and with respect to the top of the page (maybe you need
to only store the first, since the
second is easy to compute on-the-fly) because you don't know which one you will
need for a given system.

[Boris Shingarov, 2010-04-13 23:40:06]

> Therefore, for each system, you need to compute the tallness_ with respect
both
> to the previous system and with respect to the top of the page

But how will the code using the tallness, select between the two?  Does it mean
that we have to change the Page_spacing code?

[joeneeman, 2010-04-14 00:07:12]

On 2010/04/13 23:40:06, Boris Shingarov wrote:
> > Therefore, for each system, you need to compute the tallness_ with respect
> both
> > to the previous system and with respect to the top of the page
> 
> But how will the code using the tallness, select between the two?  Does it
mean
> that we have to change the Page_spacing code?

Yes, but not by a huge amount: in append_system, you need to do something like

if (!rod_height_)
  // use begin-of-page-tallness
else
  // use normal tallness

In prepend_system, do something like
rod_height_ -= first_line_.begin_of_page_tallness_;
rod_height_ += first_line_.tallness_;
rod_height_ += line.tallness_;
because the line that used to be first is no longer first and the new line is
now first.

[Boris Shingarov, 2010-04-14 11:58:34]

> if (!rod_height_)
>   // use begin-of-page-tallness
> else
>   // use normal tallness

So then we do not need to keep two versions of tallness, because
begin-of-page-tallness is simply the old "height", i.e. the size of the unite()
of the begin-of-line extent and the rest-of-line extent.

But I am very curious about the design point you mentioned: that min_pages()
tries to pack as tight as possible, but the actual spacer may choose a wider
spacing.  How can this be?  Don't we make our final decision about where to
break the pages, at the breaking stage?  and therefore we would want to keep
*all* height estimations to be as close to reality as possible?  See, my main
problem today is that there appear all sorts of places in our book that seem to
break the estimation of height, the result being, huge, butt-ugly variation in
the bottom margin (from 1/4'' to 2''), making the book completely unacceptable
for print.  This bug we are on, is one major contributor; there are more that I
will have to fix, too.  So I really want to understand the design behind this
breaking/spacing difference.  If we decide on a particular breaking at the
breaking stage, how can the later spacer stage use different designations of
which systems are begin-of-page vs further-on-page?

[joeneeman, 2010-04-14 16:36:33]

On 2010/04/14 11:58:34, Boris Shingarov wrote:
> > if (!rod_height_)
> >   // use begin-of-page-tallness
> > else
> >   // use normal tallness
> 
> So then we do not need to keep two versions of tallness, because
> begin-of-page-tallness is simply the old "height", i.e. the size of the
unite()
> of the begin-of-line extent and the rest-of-line extent.

Right.

> But I am very curious about the design point you mentioned: that min_pages()
> tries to pack as tight as possible, but the actual spacer may choose a wider
> spacing.

The Page_spacing class is part of the page-breaking calculation (as opposed to
the page-layout calculation, which is done in Page_layout_problem).
Page_breaking::min_page_count is used (as the name suggests) to find the minimum
number of pages required for the music, but the actual number of pages used is
determined by the scoring system in Page_spacing. See
Page_breaking::space_systems_on_n_pages for an example of how Page_spacing and
Page_spacer are used.

So you're right that the final decision about which systems to put on which
pages is done at the page-breaking stage. But it has not yet been done when
min_page_count is called.

[Boris Shingarov, 2010-04-20 01:16:39]

There may have been be another bug hiding in Page_spacing::prepend_system() for
ages:

if (rod_height_)
  rod_height_ += first_line_.title_ ? line.title_padding_ : line.padding_;

Should it really be "first_line_.title_?" here,
as opposed to "line.title_?"?

This is apart from the issue whether the padding's semantics is "above" or
"below" the line/title, but what I am observing is that when there are many
title lines on a page, title_padding_ does not get to be used; this leads in
this case to *overestimation* and the music does not fit on the page.

[joeneeman, 2010-04-20 02:17:50]

This definitely looks better, but I pointed out a few more small things. There
are several places where the formatting is not consistent with the surrounding
code. I pointed out a few, but there are probably others: try running the
fixcc.py script in scripts/auxiliar to find code style issues.

- I still really don't like the separate handling of extents for titles and
systems, for two reasons:
    1. the layout code shouldn't have to care whether a particular line is a
system of a title. It should only care about the geometry.
    2. with the current code, it is possible to have an inconsistent state and a
programming_error. If you would simplify Line_details, these problems would
simply disappear.

  Think of it this way: each line is represented by some outline. For titles,
the outline is just a rectangle (say 2cm wide). For systems, the outline is a
little more accurate: we allow the first centimeter to have a different Y-extent
from the second centimeter. The nicest way to represent this situation is to use
two Intervals, one for each horizontal centimeter. For titles, just set both
intervals to the same extent.

  If you made this change, you could
    1. banish Line_details::height_is_stencil_based ()
    2. simplify Line_details::tallness ()
    3. simplify Line_details::full_height ()
    4. simplify Line_details::compute_hangings () (which, by the way, should
check height_is_stencil_based () rather than !stencil_extent_.empty ())
    5. remove a member from Line_details
  and the only cost would be the addition of a single line to Line_details
(Prob*, Output_def*).


> Right, but I found having the whole array of hangings of
> great help in debugging
> why pure and non-pure heights diverge.

Ok, but there are better ways to do this than by storing debugging information
in structs which get used in many different parts of the code. For example, you
could just do it in gdb:

(gdb) b page-breaking.cc:849
(gdb) commands 1
> printf "(%f, %f, %f)" prev_hanging prev_hanging_begin prev_hanging_rest
> c
> end

Or you could add
if (ddebug_page_breaking_scoring)
  {
    print_stuff ();
  }
to Page_breaking::compute_line_heights (). That way, all of the debug-supporting
code will be local to a single functions.

http://codereview.appspot.com/879043/diff/16001/17001
File lily/constrained-breaking.cc (right):

http://codereview.appspot.com/879043/diff/16001/17001#newcode554
lily/constrained-breaking.cc:554: } else {
formatting

http://codereview.appspot.com/879043/diff/16001/17001#newcode602
lily/constrained-breaking.cc:602: {
formatting

http://codereview.appspot.com/879043/diff/16001/17004
File lily/page-breaking.cc (right):

http://codereview.appspot.com/879043/diff/16001/17004#newcode863
lily/page-breaking.cc:863: compute_line_heights ();
Given that you've gone to the trouble of breaking it into a separate function,
could you move this line to cache_line_details?

http://codereview.appspot.com/879043/diff/16001/17004#newcode880
lily/page-breaking.cc:880: }
formatting

http://codereview.appspot.com/879043/diff/16001/17005
File lily/page-spacing.cc (right):

http://codereview.appspot.com/879043/diff/16001/17005#newcode53
lily/page-spacing.cc:53: } else {
formatting

http://codereview.appspot.com/879043/diff/16001/17005#newcode76
lily/page-spacing.cc:76: rod_height_ += line.full_height();
space before (

[joeneeman, 2010-04-20 02:28:00]

On 2010/04/20 01:16:39, Boris Shingarov wrote:
> There may have been be another bug hiding in Page_spacing::prepend_system()
for
> ages:
> 
> if (rod_height_)
>   rod_height_ += first_line_.title_ ? line.title_padding_ : line.padding_;
> 
> Should it really be "first_line_.title_?" here,
> as opposed to "line.title_?"?

I think it's correct, but I'll have another look tomorrow when I'm less tired. I
really should have documented the semantics, but prepend_system and
append_system seem to be consistent with line.title_padding_ being the padding
between "line" and the following line, provided that the following line is a
title. So we check first_line_.title_ because first_line_ will (once we prepend
"line") come after "line," and so we want to include line.title_padding_ if and
only if the line that comes after it (first_line_) is a title.

> This is apart from the issue whether the padding's semantics is "above" or
> "below" the line/title, but what I am observing is that when there are many
> title lines on a page, title_padding_ does not get to be used; this leads in
> this case to *overestimation* and the music does not fit on the page.

If you email me a small example, I can take a closer look. I checked the
initialization of title_padding_ in constrained-breaking.cc and I didn't see any
obvious mistakes so I don't know what causes the bug.

[Boris Shingarov, 2010-04-20 19:23:36]

The more I debug the little example I sent you (I don't see a way to attach a
file to a comment here), the more puzzled I am.  How can it be that when the old
code calls pure_height(), it gets [-2,10], but our new begin-of-line-extent and
rest-of-line-extent are [0,-7.6] and [-2,-9.55]????  Ok, translations fine, I
don't care, but isn't the pure_height calculated in cached_extent (or whatever
it was called) simply as the union of begin and rest intervals?  And why on
earth would it compute correctly in all other examples (currently >500 systems
in our production manuscript), I just fail to see what's special about this
case.

[joeneeman, 2010-04-20 20:51:05]

On 2010/04/20 19:23:36, Boris Shingarov wrote:
> The more I debug the little example I sent you (I don't see a way to attach a
> file to a comment here), the more puzzled I am.  How can it be that when the
old
> code calls pure_height(), it gets [-2,10], but our new begin-of-line-extent
and
> rest-of-line-extent are [0,-7.6] and [-2,-9.55]????  Ok, translations fine, I
> don't care, but isn't the pure_height calculated in cached_extent (or whatever
> it was called) simply as the union of begin and rest intervals?  And why on
> earth would it compute correctly in all other examples (currently >500 systems
> in our production manuscript), I just fail to see what's special about this
> case.

The problem could be that you removed the extent-updating from compress_lines at
page-breaking.cc:103, so that when the title and the following line are merged
together, the extents are not updated. The code to merge the extents, by the
way, would be simpler if you removed stencil_extent_ (hint, hint).

I'm not sure about the discrepancy between pure-height and begin-of-line-extent.
Where is the call to pure-height that gives the weird result?

[Boris Shingarov, 2010-04-20 21:06:34]

> so that when the title and the following line are merged
> together, the extents are not updated.

We should probably document the design more clearly:
In which cases does line compression happen?  It was my understanding that the
purpose of compression was implementing the "do not break" flag: we glue
together those systems between which no pagebreak is allowed, before running the
pagebreaking algorithm, so it treats them as a single line.
I did not realize there was also something about compression and title lines.

> The code to merge the extents, by the
> way, would be simpler if you removed stencil_extent_ (hint, hint).

I'll try making a stencil-based line to be rectangular (begin==rest).

> I'm not sure about the discrepancy between pure-height and
begin-of-line-extent.
> Where is the call to pure-height that gives the weird result?

I was talking about comparing the old (pre-patch) and the new code.  The old
code was calling pure-height, and the returned extent's height is 12, while the
new code results in an extent which is only 9.5 high.

In light of what you say about title compression, the difference of 2.5 smells
suspiciously right.  Maybe that's what it is then.  I'm going to step through
the compression function right now to see if it is the culprit.

[joeneeman, 2010-04-20 21:08:04]

On 2010/04/20 21:06:34, Boris Shingarov wrote:
> > so that when the title and the following line are merged
> > together, the extents are not updated.
> 
> We should probably document the design more clearly:
> In which cases does line compression happen?  It was my understanding that the
> purpose of compression was implementing the "do not break" flag: we glue
> together those systems between which no pagebreak is allowed, before running
the
> pagebreaking algorithm, so it treats them as a single line.

Exactly.

> I did not realize there was also something about compression and title lines.

There is no page break allowed between a title and the following score, so those
lines always get compressed.

[Boris Shingarov, 2010-04-20 21:11:35]

> > I did not realize there was also something about compression and title
lines.
> 
> There is no page break allowed between a title and the following score, so
those
> lines always get compressed.

Well that's the bug then.
I'll prepare a new patch set now.

[Boris Shingarov, 2010-04-21 00:59:38]

This seems to fix all known problems.

Btw, make-test-baseline seems to fail with current origin/master?

[joeneeman, 2010-04-21 18:38:20]

On 2010/04/21 00:59:38, Boris Shingarov wrote:
> This seems to fix all known problems.

It looks much better to me. There seem to be some formatting problems, however.
Please run fixcc.py to fix them.

Also, you didn't address my complaint about the hanging variables being members
of Line_details instead of being local to a function. You don't _HAVE_ to change
them (ie. you're welcome to argue instead) but since you didn't mention that
complaint, I'm assuming you overlooked it.

> Btw, make-test-baseline seems to fail with current origin/master?

It works for me, what error are you getting?

[joeneeman, 2010-04-21 18:38:31]

http://codereview.appspot.com/879043/diff/34001/35002
File lily/include/constrained-breaking.hh (right):

http://codereview.appspot.com/879043/diff/34001/35002#newcode31
lily/include/constrained-breaking.hh:31: struct BeginRestShape
Begin_rest_shape
Actually, I find this name a little confusing (it sounds like it should be the
shape at the beginning of a rest). Maybe Line_shape is better?

[Boris Shingarov, 2010-04-21 19:07:39]

On 2010/04/21 18:38:20, joeneeman wrote:

> Also, you didn't address my complaint about the hanging variables being
members
> of Line_details instead of being local to a function. You don't _HAVE_ to
change
> them (ie. you're welcome to argue instead) but since you didn't mention that
> complaint, I'm assuming you overlooked it.

Actually, I did answer this.
Unfortunately I don't see Reitveld putting exact timestamps of reference numbers
to comments, but here is a cut-and-paste:

"Right, but I found having the whole array of hangings of great help in
debugging
why pure and non-pure heights diverge.  In the publication I am helping to
typeset, we are very far from getting vertical space estimations right: pages
are underfilled/overfilled all the time.  I debug these by measuring the actual
hangings with a ruler, and then comparing them with the hangings in the vector
of Line_details."

[Boris Shingarov, 2010-04-21 19:17:22]

> Actually, I find this name a little confusing (it sounds like it should be the
> shape at the beginning of a rest). Maybe Line_shape is better?

Neither is particularly telling to a person who is uninitiated about the
begin/rest hack.  But let it be Line_shape, just for the better euphony if we
can't come up with a name of better clarity.

[Boris Shingarov, 2010-04-21 19:21:01]

> There seem to be some formatting problems, however.
> Please run fixcc.py to fix them.

Just tried doing it.  It trumps on every line in the file, not just on the code
that I added/modified.

[joeneeman, 2010-04-21 19:36:41]

On 2010/04/21 19:07:39, Boris Shingarov wrote:
> On 2010/04/21 18:38:20, joeneeman wrote:
> 
> > Also, you didn't address my complaint about the hanging variables being
> members
> > of Line_details instead of being local to a function. You don't _HAVE_ to
> change
> > them (ie. you're welcome to argue instead) but since you didn't mention that
> > complaint, I'm assuming you overlooked it.
> 
> Actually, I did answer this.
> Unfortunately I don't see Reitveld putting exact timestamps of reference
numbers
> to comments, but here is a cut-and-paste:

> Right, but I found having the whole array of hangings of
> great help in debugging
> why pure and non-pure heights diverge.

And my reply a couple of days ago was:

Ok, but there are better ways to do this than by storing debugging information
in structs which get used in many different parts of the code. For example, you
could just do it in gdb:

(gdb) b page-breaking.cc:849
(gdb) commands 1
> printf "(%f, %f, %f)" prev_hanging prev_hanging_begin prev_hanging_rest
> c
> end

Or you could add
if (ddebug_page_breaking_scoring)
  {
    print_stuff ();
  }
to Page_breaking::compute_line_heights (). That way, all of the debug-supporting
code will be local to a single functions.

[joeneeman, 2010-04-21 19:50:10]

On 2010/04/21 19:21:01, Boris Shingarov wrote:
> > There seem to be some formatting problems, however.
> > Please run fixcc.py to fix them.
> 
> Just tried doing it.  It trumps on every line in the file, not just on the
code
> that I added/modified.

Yes, it does seem to complain a lot; perhaps I'll run fixcc.py on those files
after your patch is applied.

In the meantime, please check all your if, for and while blocks. Braces should
be indented and "else" always goes on a separate line:
if (foo)
  {
    bar ();
  }
else
  {
    baz ();
  }

[Boris Shingarov, 2010-04-21 21:14:31]

Ok, I just uploaded a new patch set: it fixes parenthesizing, renames the class,
and removes storage of local state.

[joeneeman, 2010-04-21 22:45:45]

For some reason, rietveld is only showing three modified files in the latest
patch (so I can't check, for example, if the formatting at system.cc:577 and
system.cc:586 is fixed. Also, I can't seem to conveniently download the whole
patch as one file (as opposed to downloading each revision and applying the
consecutively).

Could you email me a single patch with all your changes?

http://codereview.appspot.com/879043/diff/29002/46003
File lily/page-breaking.cc (right):

http://codereview.appspot.com/879043/diff/29002/46003#newcode845
lily/page-breaking.cc:845: {
Indent the brace

[Boris Shingarov, 2010-04-21 23:35:41]

Mail with full patch sent.