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

[Han-Wen Nienhuys]

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.

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

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

* Linked lists provide O(1) random insertion, but this is exactly the
algorithmic property we don't need at all in this problem. By
contrast, the buildings are sorted, and if we store them in an array,
we can use binary search for efficient searching. For example, we
generate glyph outlines for each character in every text in the score.
With binary search, we can quickly check if the bbox of the char is
within the outline, and avoid doing the work to generate and merge the
outline. This likely cuts the amount of merges by a factor 2: the
bottom half of a text above the staff is obscured by the bottom of the
staff, so it doesn't need to be processed at all.

Finally, to Dan's point: I haven't looked at heap profiling. The
google heap-profiler is available at
https://gperftools.github.io/gperftools/heapprofile.html, and I would
be happy to comment on heap profiles that anyone wishes to collect. My
educated guess is that the skyline code, with or without this patch,
will figure highly in the stats, simply because we compute skylines in
so much detail. For now, I don't intend to try this out: the skylines
are such an obvious time sink that that is the area to optimize. This
is reinforced by my other patch for skylines
(https://codereview.appspot.com/547980044/).

On Wed, Apr 22, 2020 at 1:39 AM <address@hidden> wrote:
>
> I am rather skeptical about the usefulness of such microoptimizations
> without influence on algorithmic complexity.  In return for better
> memory locality you buy into quite larger memory fragmentation, and we
> have scores of comparatively modest size already exhausting memory.  All
> that exhausted memory needs to get filled and processed, so it would
> rather seem like the true savings are not to be found in doing the same
> kind of work in a slightly faster but less maintainable manner with
> hand-written optimisations, but rather in figuring out why too much work
> is being done in the first place.
>
> The more one replaces standard tools and operations, the harder it
> becomes to figure out what kind of stuff actually goes wrong and fix it,
> or change the strategies and algorithms wholesale.
>
> https://codereview.appspot.com/583750043/



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