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

[dak]

On 2020/04/22 07:43:17, hanwenn wrote:
> current master:
> 
> 4f906b95aea99f2a47d5ba037f7421e5bb933c42 (origin/master) Issue 5908:
> get_path_list: use loop instead of tail recursion
> 
> Command being timed: "out/bin/lilypond.4f906b95ae -I carver MSDM"
> User time (seconds): 34.30
> Maximum resident set size (kbytes): 1139208
> 
> this patch:
> 
> 889131d584f77f44acc8d801ce254d7d2ba85aa4 (HEAD, vector-skyline) Use
> vectors rather than lists for skylines.
> Command being timed: "out/bin/lilypond.889131d584 -I carver MSDM"
> User time (seconds): 31.66
> Maximum resident set size (kbytes): 1054432
> 
> 
> 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.  When the flow and functionality
functionality of the skyline code here does not depend on whether one
uses vectors or lists, the actual exchange should be of one typedef. 
Then one is free to change the implementation at a whim and when other
conditions may change, like changes in the memory support.  C++ is a
painful language for one reason: not sacrificing functionality while
still being able to separate data types and algorithms in a modular
manner.  We pay the price for using C++ so we should also reap the
rewards in usability.  STL provides a unified interface to containers
for a reason.

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

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

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.

I actually do have some half-finished code for that sitting somewhere
that postpones merges of significantly different sized subskylines.  One
of the problem areas was, unhard to guess, ensuring results that would
not (or not significantly) depend on merge order for numeric reasons
because that makes things awfully irreproducible.

https://codereview.appspot.com/583750043/