Rewrite Skyline code

Rewrite Skyline code

    
    * Do not use contiguous buildings. Instead, Y=-infinity is represented
      by simply omitting the building. This reduces memory requirements
      (for example, an empty skyline needs no buildings at all.), and
      obviates the Skyline::normalize() call which takes ~1 % of CPU.
    
    * Buildings store Y coordinate of the left edge, rather than the
      intercept at x==0.0.  This avoid excessive rounding problems when X
      is large, and lets us compute building.height_at(x[LEFT]) cheaply.
    
    * Avoid using infinity and NaN. We only let the X coordinates at the
      edges be infinite (which is only necessary if a minimum height is
      specified)
    
    * Simplify the merge code, using less nested if statements.
    
    * Add a unittest for the Skyline code
    
    * Debug output is produced with Lookup::segments_to_line_stencil()
    
    * Consolidate print and print_points

[hanwenn, 2020-04-19 21:43:26]

(this still needs some work, but the speedup might be worth an early look)

[dak, 2020-04-19 22:35:39]

On 2020/04/19 21:43:26, hanwenn wrote:
> (this still needs some work, but the speedup might be worth an early look)

* Buildings store Y coordinate of the left edge, rather than the
  intercept at x==0.0.  This avoid excessive rounding problems when X
  is large, and lets us compute building.height_at(x[LEFT]) cheaply.

Since intercept computation order depends on the execution of the merge
algorithm and we use floating point arithmetic rather than fixed point, this
would make results a lot less reproducible.

I understand the sentiment and thought about it as well, but it would only work
if the _original_ coordinates were retained even after intersection and
additional intersections still worked based on the original coordinates, making
the merge order (mostly) irrelevant with regard to error propagation.

[Dan Eble, 2020-04-21 04:25:05]

https://codereview.appspot.com/547980044/diff/548010043/lily/skyline.cc
File lily/skyline.cc (right):

https://codereview.appspot.com/547980044/diff/548010043/lily/skyline.cc#newco...
lily/skyline.cc:348: result.push_back (buildings->at (0));
at() involves a boundary check that is not necessary here.  front() or [0] would
be better.

https://codereview.appspot.com/547980044/diff/548010043/lily/skyline.cc#newco...
lily/skyline.cc:862: // testing
I love the idea of testing, though I think we'll want to find a way to avoid
bloating LilyPond with test code.

[hanwenn, 2020-04-21 07:57:03]

On 2020/04/19 22:35:39, dak wrote:
> On 2020/04/19 21:43:26, hanwenn wrote:
> > (this still needs some work, but the speedup might be worth an early look)
> 
> * Buildings store Y coordinate of the left edge, rather than the
>   intercept at x==0.0.  This avoid excessive rounding problems when X
>   is large, and lets us compute building.height_at(x[LEFT]) cheaply.
> 
> Since intercept computation order depends on the execution of the merge
> algorithm and we use floating point arithmetic rather than fixed point, this
> would make results a lot less reproducible.

Hmm, OK. You say "a lot less". Did we measure this, and is this an important
characteristic of the code?

> I understand the sentiment and thought about it as well, but it would only
work
> if the _original_ coordinates were retained even after intersection and
> additional intersections still worked based on the original coordinates,
making
> the merge order (mostly) irrelevant with regard to error propagation.

FWIW, I want to reduce the precision of the outlines anyway (because they are
way more detailed than necessary), and that is going introduce much larger
errors than propagated errors.

[hanwenn, 2020-04-21 07:58:10]

https://codereview.appspot.com/547980044/diff/548010043/lily/skyline.cc
File lily/skyline.cc (right):

https://codereview.appspot.com/547980044/diff/548010043/lily/skyline.cc#newco...
lily/skyline.cc:348: result.push_back (buildings->at (0));
On 2020/04/21 04:25:05, Dan Eble wrote:
> at() involves a boundary check that is not necessary here.  front() or [0]
would
> be better.

Done.

https://codereview.appspot.com/547980044/diff/548010043/lily/skyline.cc#newco...
lily/skyline.cc:862: // testing
On 2020/04/21 04:25:05, Dan Eble wrote:
> I love the idea of testing, though I think we'll want to find a way to avoid
> bloating LilyPond with test code.

I agree that this approach is unorthodox, but I there is little alternative. The
data structure under test is a smob, so testing without setting up the GUILE
infrastructure will be hard. For the amount of unittests we currently have (ie.
none), it is a lot of overhead to setup an extra compile, integrate the testing
into the build, and keep the test framework in sync with the main code's GUILE
integration. 

We could compile enclose the code with #ifndef NDEBUG and use the same mechanism
that we use to suppress assert statements (although I think those are shipped in
production code too?)

If we start having lots of unittests (which would be great!) we can consider
splitting of unittests is worth it.

[hanwenn, 2020-04-24 15:50:22]

don't trim zero width buildings

[hahnjo, 2020-04-24 16:33:05]

https://codereview.appspot.com/547980044/diff/567490043/lily/include/skyline.hh
File lily/include/skyline.hh (right):

https://codereview.appspot.com/547980044/diff/567490043/lily/include/skyline....
lily/include/skyline.hh:152: }
Why do you need all of this in the header file? As far as I can see, nobody else
is calling these methods, so the argument of inlinining does not apply.

https://codereview.appspot.com/547980044/diff/567490043/lily/skyline-pair.cc
File lily/skyline-pair.cc (left):

https://codereview.appspot.com/547980044/diff/567490043/lily/skyline-pair.cc#...
lily/skyline-pair.cc:100: Skyline_pair::print_points () const
You should not delete a function without removing the declaration in
lily/include/skyline-pair.hh. Also this seems unrelated to the performance
improvements.

https://codereview.appspot.com/547980044/diff/567490043/lily/skyline.cc
File lily/skyline.cc (right):

https://codereview.appspot.com/547980044/diff/567490043/lily/skyline.cc#newco...
lily/skyline.cc:780: Skyline::to_segments (Axis horizon_axis) const
What's the advantage of this code over the old method?

https://codereview.appspot.com/547980044/diff/567490043/scm/define-grobs.scm
File scm/define-grobs.scm (right):

https://codereview.appspot.com/547980044/diff/567490043/scm/define-grobs.scm#...
scm/define-grobs.scm:1657: (stencil . ,ly:paper-column::print)
Is this change intentional? And intentionally in this review?

[hanwenn, 2020-04-24 17:12:48]

https://codereview.appspot.com/547980044/diff/567490043/lily/include/skyline.hh
File lily/include/skyline.hh (right):

https://codereview.appspot.com/547980044/diff/567490043/lily/include/skyline....
lily/include/skyline.hh:152: }
On 2020/04/24 16:33:04, hahnjo wrote:
> Why do you need all of this in the header file? As far as I can see, nobody
else
> is calling these methods, so the argument of inlinining does not apply.

trimmed this a bit.

https://codereview.appspot.com/547980044/diff/567490043/lily/skyline-pair.cc
File lily/skyline-pair.cc (left):

https://codereview.appspot.com/547980044/diff/567490043/lily/skyline-pair.cc#...
lily/skyline-pair.cc:100: Skyline_pair::print_points () const
On 2020/04/24 16:33:04, hahnjo wrote:
> You should not delete a function without removing the declaration in
> lily/include/skyline-pair.hh. Also this seems unrelated to the performance
> improvements.

the print() function prints the building in terms of y-intercept at x=0.0 +
slope. Since we don't store the y-intercept anymore, that is useless now. The
points are also more convenient for debugging, which is the only objective of
this function.

https://codereview.appspot.com/547980044/diff/567490043/lily/skyline.cc
File lily/skyline.cc (right):

https://codereview.appspot.com/547980044/diff/567490043/lily/skyline.cc#newco...
lily/skyline.cc:780: Skyline::to_segments (Axis horizon_axis) const
On 2020/04/24 16:33:04, hahnjo wrote:
> What's the advantage of this code over the old method?

the buildings making up the skylines have become non-contiguous, so you can't
simply connect all the points any more.  (If you'd do that, there would be
diagonal line segments printed in debug output that aren't really there.)

https://codereview.appspot.com/547980044/diff/567490043/scm/define-grobs.scm
File scm/define-grobs.scm (right):

https://codereview.appspot.com/547980044/diff/567490043/scm/define-grobs.scm#...
scm/define-grobs.scm:1657: (stencil . ,ly:paper-column::print)
On 2020/04/24 16:33:04, hahnjo wrote:
> Is this change intentional? And intentionally in this review?

thanks, no. I was already wondering why the cell count shot up in the profile
:-)

[hanwenn, 2020-04-24 17:56:36]

On 2020/04/24 17:12:48, hanwenn wrote:
>
https://codereview.appspot.com/547980044/diff/567490043/lily/include/skyline.hh
> File lily/include/skyline.hh (right):
> 
>
https://codereview.appspot.com/547980044/diff/567490043/lily/include/skyline....
> lily/include/skyline.hh:152: }
> On 2020/04/24 16:33:04, hahnjo wrote:
> > Why do you need all of this in the header file? As far as I can see, nobody
> else
> > is calling these methods, so the argument of inlinining does not apply.
> 
> trimmed this a bit.
> 
> https://codereview.appspot.com/547980044/diff/567490043/lily/skyline-pair.cc
> File lily/skyline-pair.cc (left):
> 
>
https://codereview.appspot.com/547980044/diff/567490043/lily/skyline-pair.cc#...
> lily/skyline-pair.cc:100: Skyline_pair::print_points () const
> On 2020/04/24 16:33:04, hahnjo wrote:
> > You should not delete a function without removing the declaration in
> > lily/include/skyline-pair.hh. Also this seems unrelated to the performance
> > improvements.
> 
> the print() function prints the building in terms of y-intercept at x=0.0 +
> slope. Since we don't store the y-intercept anymore, that is useless now. The
> points are also more convenient for debugging, which is the only objective of
> this function.
> 
> https://codereview.appspot.com/547980044/diff/567490043/lily/skyline.cc
> File lily/skyline.cc (right):
> 
>
https://codereview.appspot.com/547980044/diff/567490043/lily/skyline.cc#newco...
> lily/skyline.cc:780: Skyline::to_segments (Axis horizon_axis) const
> On 2020/04/24 16:33:04, hahnjo wrote:
> > What's the advantage of this code over the old method?
> 
> the buildings making up the skylines have become non-contiguous, so you can't
> simply connect all the points any more.  (If you'd do that, there would be
> diagonal line segments printed in debug output that aren't really there.)
> 
> https://codereview.appspot.com/547980044/diff/567490043/scm/define-grobs.scm
> File scm/define-grobs.scm (right):
> 
>
https://codereview.appspot.com/547980044/diff/567490043/scm/define-grobs.scm#...
> scm/define-grobs.scm:1657: (stencil . ,ly:paper-column::print)
> On 2020/04/24 16:33:04, hahnjo wrote:
> > Is this change intentional? And intentionally in this review?
> 
> thanks, no. I was already wondering why the cell count shot up in the profile
> :-)

grmbl.- and now the speed difference is gone again.  I hate my autoscaling CPU.

[hanwenn, 2020-04-24 18:51:54]

https://codereview.appspot.com/547980044/diff/567490043/lily/include/skyline.hh
File lily/include/skyline.hh (right):

https://codereview.appspot.com/547980044/diff/567490043/lily/include/skyline....
lily/include/skyline.hh:152: }
On 2020/04/24 17:12:48, hanwenn wrote:
> On 2020/04/24 16:33:04, hahnjo wrote:
> > Why do you need all of this in the header file? As far as I can see, nobody
> else
> > is calling these methods, so the argument of inlinining does not apply.
> 
> trimmed this a bit.

looks like GCC doesn't want to inline the functions if I do that, leading to
significant slowdown.

[hanwenn, 2020-04-24 20:46:59]

get rid of interval

[dak, 2020-04-24 23:07:56]

On 2020/04/19 22:35:39, dak wrote:
> On 2020/04/19 21:43:26, hanwenn wrote:
> > (this still needs some work, but the speedup might be worth an early look)
> 
> * Buildings store Y coordinate of the left edge, rather than the
>   intercept at x==0.0.  This avoid excessive rounding problems when X
>   is large, and lets us compute building.height_at(x[LEFT]) cheaply.
> 
> Since intercept computation order depends on the execution of the merge
> algorithm and we use floating point arithmetic rather than fixed point, this
> would make results a lot less reproducible.
> 
> I understand the sentiment and thought about it as well, but it would only
work
> if the _original_ coordinates were retained even after intersection and
> additional intersections still worked based on the original coordinates,
making
> the merge order (mostly) irrelevant with regard to error propagation.

Actually, one way to keep this pretty order independent would be just not to
intersect until the final pass and use the preceding passes just for throwing
out those line segments that are completely shadowed by others.  This should not
keep all that much more data but would have to deal with a larger current
working set where max/min relations are checked.  I have no clear view on the
expected performance impact.

[hahnjo, 2020-04-27 07:01:28]

https://codereview.appspot.com/547980044/diff/572060043/lily/include/skyline.hh
File lily/include/skyline.hh (right):

https://codereview.appspot.com/547980044/diff/572060043/lily/include/skyline....
lily/include/skyline.hh:34: #include "offset.hh"
Please don't separate the lily includes - actually interval.hh is already
included above

https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc
File lily/skyline.cc (right):

https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc#newco...
lily/skyline.cc:28: #include "skyline.hh"
As discussed in other reviews, skyline.hh should be the very first include and
system headers should be last

https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc#newco...
lily/skyline.cc:171: class BuildingQueue
Do you really need a custom type for this? It really much looks like an iterator
(and you can call methods on the current item by using the -> operator)

https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc#newco...
lily/skyline.cc:175: Building front_;
In any case, this causes copies on every call to next(). If you need to retain
this data structure, is there a reason not to use a pointer to the current
element? AFAICS you don't modify the underlying vector when using a
BuildingQueue

https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc#newco...
lily/skyline.cc:365: class LessThanBuilding
Can we just replace this functor by passing Building::less as a function
pointer?

[hanwenn, 2020-04-27 21:30:18]

I'm going to put this on pause for a bit. With removing normalize() from the
list -> vector patch, this is going to be a 1% performance deterioration, I
think. I have some ideas about introducing BuildingQueue so we can do raise and
shift more efficiently, but I have to first try it out.

https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc
File lily/skyline.cc (right):

https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc#newco...
lily/skyline.cc:175: Building front_;
On 2020/04/27 07:01:28, hahnjo wrote:
> In any case, this causes copies on every call to next(). If you need to retain
> this data structure, is there a reason not to use a pointer to the current
> element? AFAICS you don't modify the underlying vector when using a
> BuildingQueue

see the split_off() function.

[hahnjo, 2020-04-28 06:49:58]

https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc
File lily/skyline.cc (right):

https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc#newco...
lily/skyline.cc:175: Building front_;
On 2020/04/27 21:30:18, hanwenn wrote:
> On 2020/04/27 07:01:28, hahnjo wrote:
> > In any case, this causes copies on every call to next(). If you need to
retain
> > this data structure, is there a reason not to use a pointer to the current
> > element? AFAICS you don't modify the underlying vector when using a
> > BuildingQueue
> 
> see the split_off() function.

That could be made a function taking an iterator as argument, or am I missing
something? AFAICS it's making a copy of the current element, then modifies both
versions, and possibly advances the iterator.

[hanwenn, 2020-04-28 07:20:26]

On 2020/04/28 06:49:58, hahnjo wrote:
> https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc
> File lily/skyline.cc (right):
> 
>
https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc#newco...
> lily/skyline.cc:175: Building front_;
> On 2020/04/27 21:30:18, hanwenn wrote:
> > On 2020/04/27 07:01:28, hahnjo wrote:
> > > In any case, this causes copies on every call to next(). If you need to
> retain
> > > this data structure, is there a reason not to use a pointer to the current
> > > element? AFAICS you don't modify the underlying vector when using a
> > > BuildingQueue
> > 
> > see the split_off() function.
> 
> That could be made a function taking an iterator as argument, or am I missing
> something? AFAICS it's making a copy of the current element, then modifies
both
> versions, and possibly advances the iterator.

Sure.

The thing I am getting at is that we spend a lot of CPU cycles for doing shift
and raise, looping over all the elements to do trivial computations over them.
Doing such modifications also requires making a copy of the entire thing.

If we structure this as

 
  class Immutable_skyline : smob {
    vector<Building>  buildings_;
  }

  class Mutable_skyline : smob {
     Immutable_skyline *immutable_; // potentially shared between many
Mutable_skylines_
     Offset  off_
  };

we can keep work the offset handling into BuildingQueue (applying the offset to
each building we process in the merge). This is also better for cache locality.

[hahnjo, 2020-04-28 07:24:24]

On 2020/04/28 07:20:26, hanwenn wrote:
> On 2020/04/28 06:49:58, hahnjo wrote:
> > https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc
> > File lily/skyline.cc (right):
> > 
> >
>
https://codereview.appspot.com/547980044/diff/572060043/lily/skyline.cc#newco...
> > lily/skyline.cc:175: Building front_;
> > On 2020/04/27 21:30:18, hanwenn wrote:
> > > On 2020/04/27 07:01:28, hahnjo wrote:
> > > > In any case, this causes copies on every call to next(). If you need to
> > retain
> > > > this data structure, is there a reason not to use a pointer to the
current
> > > > element? AFAICS you don't modify the underlying vector when using a
> > > > BuildingQueue
> > > 
> > > see the split_off() function.
> > 
> > That could be made a function taking an iterator as argument, or am I
missing
> > something? AFAICS it's making a copy of the current element, then modifies
> both
> > versions, and possibly advances the iterator.
> 
> Sure.
> 
> The thing I am getting at is that we spend a lot of CPU cycles for doing shift
> and raise, looping over all the elements to do trivial computations over them.
> Doing such modifications also requires making a copy of the entire thing.
> 
> If we structure this as
> 
>  
>   class Immutable_skyline : smob {
>     vector<Building>  buildings_;
>   }
> 
>   class Mutable_skyline : smob {
>      Immutable_skyline *immutable_; // potentially shared between many
> Mutable_skylines_
>      Offset  off_
>   };
> 
> we can keep work the offset handling into BuildingQueue (applying the offset
to
> each building we process in the merge). This is also better for cache
locality.

So that's a possible improvement in the future, right?
In any case, currently BuildingQueue copies to front_ while iterating over the
Buildings, even if not modifying it in all cases. That certainly doesn't sound
right.