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/
