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

[David Kastrup]

Han-Wen Nienhuys <address@hidden> writes:

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

I disagree.

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

You can still benchmark it as needed.

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

Can you state how iterating through a container in sorted order requires
different code using STL lists and STL 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.
>
> 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.

Most of the skyline data is not needed because it does not survive a
merge with other skyline data.  That is different to other
divide-and-conquer kinds of algorithms because those algorithms retain
the amount of data while merging.  If the merged skylines are
consistently of quite different size, the divide-and-conquer O (lg N)
performance moves more in the O (n^2) direction, an effect known from
Quicksort.

Now that's not at issue with this patch.  What I point out here is that
moving from one STL container to another STL container is a standard
programming technique that is _exactly_ why the STL library has
iterators, and C++11 has for loops that can easily iterate through
containers in sequence without even requiring convoluted iterator
declarations.  So there is just no point in not doing this in a manner
where it isn't hardcoding one container type throughout.

-- 
David Kastrup