Re: Use vectors rather than lists for skylines. (issue 583750043 by address@hidden)

[Han-Wen Nienhuys]

On Thu, Apr 23, 2020 at 6:01 PM <address@hidden> wrote:

> > I disagree David's assessment on several theoretical grounds too:
> >
> > * "less maintainable manner with hand-written optimisations". I don't
> > see these in this patch. This (together with the Tie_performer) is the
> > only place in LilyPond that uses lists. We could get rid of std::list
> > on maintenance grounds alone.
>
> This patch may not be the best illustration of the problem, but it does
> leave something to be desired as well.

I think you are trying to have a philosphical discussion here, but
when you say this, then James puts it back on review. Given that your
discussion below seems largely theoretical, I'm setting it back to
countdown. Holler if you disagree.

> > * The linked list has an overhead of 2 pointers, on a 4x Real
> > datastructure, ie. 50% overhead. The vector has (assuming a 2x growth
> > strategy) 100% overhead. There is a little more overhead, but we could
> > tune that by adjustin the vector growth strategy. With a linked list,
> > there is no choice in space/time tradeoff.
>
> When I read "adjustin the vector growth strategy", that again sounds
> like microoptimisation by replacing STL algorithms with something
> homespun.  That just makes no sense since it ultimately will not buy us
> more than about 30% of performance while locking us into a code base
> that can neither be easily maintained nor brought up to speed in case
> STL improves or we want to plug in, say, a Boost library.  If we want to
> close LilyPond to further development, squeezing the last 30% of
> performance out in return for lots worse in maintainability.

Well, my point is that you have the option to make the tradeoff. If
you use linked lists, you don't get the tradeoff.

The idea that you can just swap out one data structure for the other
by doing a single typedef changes is in my experience a lie. Different
structures have different space/cpu tradeoffs, so you have to use them
in differen ways.


> > * The linked list approach is much worse for fragmentation. It has to
> > allocate a ton on 48-byte objects, some of which have long lifetime.
> > This will create a highly fragmented pool of 48-byte objects. We don't
> > have use for so many of these objects elsewhere. By contrast, the
> > vector approach will create a distribution of differently sized
> > objects, which can be recycled into other vectors.
>
> Vectors are usually grown in fixed growth factors and the elements of
> the vectors here are not something with a straightforward size such SCM.
>  So we have similar problems with vectors.

?

If we have a vector<Building> of capacity 32, that takes 1536 bytes.
After it's merged into another skyline, we deallocate those 1536
bytes, so it can later be used as a vector fo 192 Grob* or 64
Tie_configuration_variation. We use vectors of all kinds of sizes
pervasively, so there will always be an efficient reuse of that chunk
of memory.

> At any rate, if the code were written agnostic with regard to the
> actually used container, there would be no need to burn a final decision
> into code and one could revisit at some future time.  Or write
> yet-another-container that does a better job at merging structures with
> not automatically balanced subdivisions.

The real problem is not that the subdivisions are unbalanced: the
problem is that we first generate a lot of skyline data that we don't
need.

-- 
Han-Wen Nienhuys - address@hidden - http://www.xs4all.nl/~hanwen