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

[jonas . hahnfeld]

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

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.

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