Re: Rewrite Skyline code (issue 547980044 by address@hidden)

[hanwenn]

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#newcode175
> 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.

https://codereview.appspot.com/547980044/