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 <d...@gnu.org> 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 - hanw...@gmail.com - http://www.xs4all.nl/~hanwen
