Han-Wen Nienhuys <hanw...@gmail.com> writes: > On Thu, Apr 23, 2020 at 6:01 PM <d...@gnu.org> 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