Issue 583750043: Use vectors rather than lists for skylines. (Closed)
Description Use vectors rather than lists for skylines.
Linked lists have poor locality. This yields a ~7% speedup on the
Carver MDSM score.
Remove Skyline::normalize():
* this is rare; it never occurs in the entire regtest
* there is no inherent problem with having adjacent empty buildings.
* it is expensive to remove elements from the middle of a vector
* Skyline::normalize is responsible for ~1% of CPU in the MSDM score.
Benchmark data
benchmark for arguments: input/regression/mozart-hrn-3
raw data: {'30c845d383': [3.76, 3.77, 3.76], '83b4b71d01': [3.62, 3.59, 3.6]}
Delta against 30c845d383: Fix font-name-add-files.ly on GUILE v2
83b4b71d01 - Use vectors rather than lists for skylines.
med diff -0.160000
med diff -4.255319 % (83b4b71d01 is faster)
benchmark for arguments: -I carver MSDM
raw data: {'30c845d383': [53.51, 51.92, 52.25], '83b4b71d01': [49.5, 48.36, 48.41]}
Delta against 30c845d383: Fix font-name-add-files.ly on GUILE v2
83b4b71d01 - Use vectors rather than lists for skylines.
med diff -3.840000
med diff -7.349282 % (83b4b71d01 is faster)
Patch Set 1 #Patch Set 2 : reserve #Patch Set 3 : ptr iso. ref #Patch Set 4 : notes to self about optimization #Patch Set 5 : update timings; rebase on interval building. #
Total comments: 4
Patch Set 6 : dan, diff against master #
Total comments: 27
Patch Set 7 : jonas #
Total comments: 2
Patch Set 8 : drop normalize() #
Total comments: 2
Patch Set 9 : jonas final comment #MessagesTotal messages: 43
ptr iso. ref
Sign in to reply to this message.
notes to self about optimization
Sign in to reply to this message.
This is likely a timing fluke due to thermal throttling too. Hold off on reviewing.
Sign in to reply to this message.
On 2020/04/13 18:51:22, hanwenn wrote: > This is likely a timing fluke due to thermal throttling too. > > Hold off on reviewing. Shall we put the patch on Needs_work then?
Sign in to reply to this message.
Sure. On Tue, Apr 14, 2020 at 8:57 AM <jonas.hahnfeld@gmail.com> wrote: > > On 2020/04/13 18:51:22, hanwenn wrote: > > This is likely a timing fluke due to thermal throttling too. > > > > Hold off on reviewing. > > Shall we put the patch on Needs_work then? > > https://codereview.appspot.com/583750043/ -- Han-Wen Nienhuys - hanwenn@gmail.com - http://www.xs4all.nl/~hanwen
Sign in to reply to this message.
update timings; rebase on interval building.
Sign in to reply to this message.
On 2020/04/17 14:58:36, hanwenn wrote: > update timings; rebase on interval building. I measured more carefully, and the speedup appears genuine.
Sign in to reply to this message.
On 2020/04/17 15:02:38, hanwenn wrote: > On 2020/04/17 14:58:36, hanwenn wrote: > > update timings; rebase on interval building. > > I measured more carefully, and the speedup appears genuine. Confirmed. However I advocate against using -pg when timing the complete executable. After all it's doing work that a "release" binary does not.
Sign in to reply to this message.
On Fri, Apr 17, 2020 at 8:53 PM <jonas.hahnfeld@gmail.com> wrote: > > > update timings; rebase on interval building. > > > > I measured more carefully, and the speedup appears genuine. > > Confirmed. > > However I advocate against using -pg when timing the complete > executable. After all it's doing work that a "release" binary does not. I can see that, but the cost of recompiling things all the time is pretty high. The profile data itself is also a more precise source for measuring improvements that are close to the noise level, like https://codereview.appspot.com/551730043/ -- Han-Wen Nienhuys - hanwenn@gmail.com - http://www.xs4all.nl/~hanwen
Sign in to reply to this message.
On 2020/04/17 19:07:44, hanwenn wrote: > The profile data itself is also a more precise source for measuring > improvements that are close to the noise level, like > https://codereview.appspot.com/551730043/ Investigating improvements that are close to the noise level--never mind, I won't tell you how to spend your time. 5.5% is nice, though. Thanks. https://codereview.appspot.com/583750043/diff/555670043/lily/skyline.cc File lily/skyline.cc (right): https://codereview.appspot.com/583750043/diff/555670043/lily/skyline.cc#newco... lily/skyline.cc:74: for (vector<Building>::const_iterator i = b.begin (); i != b.end (); i++) for (auto i : b) https://codereview.appspot.com/583750043/diff/555670043/lily/skyline.cc#newco... lily/skyline.cc:219: for (; cit != scp->end (); cit++) ++cit
Sign in to reply to this message.
On 2020/04/17 22:44:12, Dan Eble wrote: > On 2020/04/17 19:07:44, hanwenn wrote: > > The profile data itself is also a more precise source for measuring > > improvements that are close to the noise level, like > > https://codereview.appspot.com/551730043/ > > Investigating improvements that are close to the noise level--never mind, I > won't tell you how to spend your time. But you do drop a cloaked suggestion. The noise level is contextually determined: if you do more experiments under better controlled circumstances, the noise level decreases. But it takes more time, and it is time I can't do other work on LilyPond; there is only so much coffee one can drink on a single day. (You'd think that a 4-core machine would be able to put the lilypond task on a dedicated CPU, but it looks it doesn't work like that in practice.) I'm pretty sure there is still significant gains (say, 10%) to be had in everything related to skyline processing. For example, we create (way too detailed) glyph outlines, and even though they're constant, they're not cached. We can probably also shortcut the glyph -> SCM lists -> skyline path by constructing the skyline directly from the freetype outline. The skyline functions construct both boxes and buildings, where just buildings would suffice. Many of these inefficiencies will be solved in smaller steps, with smaller (~1%) gains. For the MSDM score, a 1% gain is 0.4 seconds, while we see 0.3s variability between runs. So, unfortunately, yes, working on performance has to happen at the noise level. > 5.5% is nice, though. Thanks. > > https://codereview.appspot.com/583750043/diff/555670043/lily/skyline.cc > File lily/skyline.cc (right): > > https://codereview.appspot.com/583750043/diff/555670043/lily/skyline.cc#newco... > lily/skyline.cc:74: for (vector<Building>::const_iterator i = b.begin (); i != > b.end (); i++) > for (auto i : b) > > https://codereview.appspot.com/583750043/diff/555670043/lily/skyline.cc#newco... > lily/skyline.cc:219: for (; cit != scp->end (); cit++) > ++cit both done.
Sign in to reply to this message.
dan, diff against master
Sign in to reply to this message.
I'm uploading a diff against master, so James can run this through tests. Intention is to submit the 'interval' change first and separately.
Sign in to reply to this message.
https://codereview.appspot.com/583750043/diff/555670043/lily/skyline.cc File lily/skyline.cc (right): https://codereview.appspot.com/583750043/diff/555670043/lily/skyline.cc#newco... lily/skyline.cc:74: for (vector<Building>::const_iterator i = b.begin (); i != b.end (); i++) On 2020/04/17 22:44:12, Dan Eble wrote: > for (auto i : b) Done. https://codereview.appspot.com/583750043/diff/555670043/lily/skyline.cc#newco... lily/skyline.cc:219: for (; cit != scp->end (); cit++) On 2020/04/17 22:44:12, Dan Eble wrote: > ++cit Done.
Sign in to reply to this message.
https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc File lily/skyline.cc (right): https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:75: i.print (); I'm sorry, I gave you imperfect advice here because I had an iterator on my mind. Now that I see i.print(), I realize that it should be for (auto &i : b) to guarantee that it uses a reference to the item rather than making a copy of the item. Again, sorry.
Sign in to reply to this message.
On 2020/04/18 11:38:17, Dan Eble wrote: > https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc > File lily/skyline.cc (right): > > https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... > lily/skyline.cc:75: i.print (); > I'm sorry, I gave you imperfect advice here because I had an iterator on my > mind. Now that I see i.print(), I realize that it should be for (auto &i : b) > to guarantee that it uses a reference to the item rather than making a copy of > the item. Again, sorry. Thanks for the correction! It's debugging code, so either way is fine.
Sign in to reply to this message.
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.
Sign in to reply to this message.
On 2020/04/21 23:39:55, dak wrote: > 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 Han-Wen, do you have tools and time available to measure the impact of this patch on memory use?
Sign in to reply to this message.
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 <dak@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 - hanwenn@gmail.com - http://www.xs4all.nl/~hanwen
Sign in to reply to this message.
On 2020/04/22 07:43:17, hanwenn wrote: > Finally, to Dan's point: I haven't looked at heap profiling. ... > For now, I don't intend to try this out I was asking for David's benefit. Personally, this change doesn't concern me. In my professional work, we usually avoid lists for some of the reasons you mentioned. -- Dan
Sign in to reply to this message.
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.
Sign in to reply to this message.
On 2020/04/23 16:01:20, dak wrote: > On 2020/04/22 07:43:17, hanwenn wrote: > > * The linked list has an overhead of 2 pointers, on a 4x Real > > datastructure, ie. 50% overhead. By the way: C++11 has Forward_list which would be another plugin container type with less overhead. I actually have some sort routine for that lying around here that I offered several times on the libc++ list without pickup. Someone benchmarked it to be about 30% faster than what's in there, on average (and, as its a merge sort, with a worst case hardly worse) but I gave up trying to forcefeed it to them after a few tries. Did not take any extra memory apart from an O(lg n) stack maintained manually rather than recursively. Now what would probably work reasonably well is to just collect buildings without bothering to look at them, clean up via a priority queue when one has gathered enough material and merge ultimately. Priority queues can be well done with vectors. All of those more order-ignorant methods will want arithmetic that is largely order-independent.
Sign in to reply to this message.
On Thu, Apr 23, 2020 at 6:01 PM <dak@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. > > * 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. Well, my point is that you have the option to make the tradeoff. If you use linked lists, you don't get the tradeoff. 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. > > * 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. ? If we have a vector<Building> of capacity 32, that takes 1536 bytes. After it's merged into another skyline, we deallocate those 1536 bytes, so it can later be used as a vector fo 192 Grob* or 64 Tie_configuration_variation. We use vectors of all kinds of sizes pervasively, so there will always be an efficient reuse of that chunk of memory. > 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. -- Han-Wen Nienhuys - hanwenn@gmail.com - http://www.xs4all.nl/~hanwen
Sign in to reply to this message.
Han-Wen Nienhuys <hanwenn@gmail.com> writes: > On Thu, Apr 23, 2020 at 6:01 PM <dak@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
Sign in to reply to this message.
I generally agree with David that having the code agnostic of the container would be an improvement. This doesn't need to be a typedef yet as reserve() is unique to std::vector (at least not in std::list) and makes sense in the places it is used here. A rather obvious change (that I'm very surprised you didn't do in the first place) is replacing all iterator types by auto. Neither the code nor the reader should care what the type is, and it is long enough to considerably clutter the code. Even better, just use range-based loops, that should be standard C++ style by now. Also the patch is currently very hard to read because it still has the Interval changes that should be in master already (so it probably doesn't even apply). What I'm not happy about is changing the patch status based on saying it's a "philosphical discussion". Every comment should be considered important, and it has happened often enough that something induces the submitter's creativity that might sound philosophical at first. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc File lily/skyline.cc (right): https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:183: vector<Building>::iterator i; move into for loop and make auto https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:189: vector<Building>::iterator last = i; auto https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:216: vector<Building>::const_iterator cit = scp->begin (); auto (2x) https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:319: for (vector<Building>::const_iterator i = buildings.begin (); auto or range-based for https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:565: vector<Building>::iterator end = buildings_.end (); auto or range-based for https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:574: for (vector<Building>::iterator i = buildings_.begin (); i != end; i++) auto or range-based for https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:620: for (vector<Building>::const_iterator i = buildings_.begin (); auto or range-based for https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:677: vector<Building>::const_iterator j = other.buildings_.begin (); auto (2x) https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:711: vector<Building>::const_iterator i; move into for and auto or range-based for https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:727: vector<Building>::const_iterator i; move into for and auto or range-based for https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:748: for (vector<Building>::const_iterator i (buildings_.begin ()); auto or range-based for https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:760: for (vector<Building>::const_reverse_iterator i (buildings_.rbegin ()); auto or range-based for https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:792: for (vector<Building>::const_iterator i (buildings_.begin ()); auto or range-based for
Sign in to reply to this message.
Here is how I have experienced this discussion: DAK: this is micro-optimization that causes memory fragmentation. HW: No, it's not; here is a benchmark that shows decreased memory use as well. DAK: We could use even different data structures in the future. HW: This seems very philosophical to me. Maybe I misunderstood, because the hardcoding of a specific STL container type predates this patch. If you want me to use "auto" instead of "vector<Building>::const_iterator", can you just point to the line in the code and say "could you use auto instead of an iterator here"? thanks,
Sign in to reply to this message.
jonas
Sign in to reply to this message.
https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc File lily/skyline.cc (right): https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:183: vector<Building>::iterator i; On 2020/04/24 07:08:50, hahnjo wrote: > move into for loop and make auto Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:189: vector<Building>::iterator last = i; On 2020/04/24 07:08:50, hahnjo wrote: > auto Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:216: vector<Building>::const_iterator cit = scp->begin (); On 2020/04/24 07:08:51, hahnjo wrote: > auto (2x) Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:319: for (vector<Building>::const_iterator i = buildings.begin (); On 2020/04/24 07:08:51, hahnjo wrote: > auto or range-based for Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:565: vector<Building>::iterator end = buildings_.end (); On 2020/04/24 07:08:50, hahnjo wrote: > auto or range-based for Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:574: for (vector<Building>::iterator i = buildings_.begin (); i != end; i++) On 2020/04/24 07:08:51, hahnjo wrote: > auto or range-based for Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:620: for (vector<Building>::const_iterator i = buildings_.begin (); On 2020/04/24 07:08:51, hahnjo wrote: > auto or range-based for Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:677: vector<Building>::const_iterator j = other.buildings_.begin (); On 2020/04/24 07:08:51, hahnjo wrote: > auto (2x) Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:711: vector<Building>::const_iterator i; On 2020/04/24 07:08:51, hahnjo wrote: > move into for and auto or range-based for Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:727: vector<Building>::const_iterator i; On 2020/04/24 07:08:50, hahnjo wrote: > move into for and auto or range-based for Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:748: for (vector<Building>::const_iterator i (buildings_.begin ()); On 2020/04/24 07:08:51, hahnjo wrote: > auto or range-based for Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:760: for (vector<Building>::const_reverse_iterator i (buildings_.rbegin ()); On 2020/04/24 07:08:51, hahnjo wrote: > auto or range-based for Done. https://codereview.appspot.com/583750043/diff/577780043/lily/skyline.cc#newco... lily/skyline.cc:792: for (vector<Building>::const_iterator i (buildings_.begin ()); On 2020/04/24 07:08:51, hahnjo wrote: > auto or range-based for Done.
Sign in to reply to this message.
Han-Wen, any reason not to use range-based loops in the places I pointed to in the last patch set? https://codereview.appspot.com/583750043/diff/545930043/lily/skyline.cc File lily/skyline.cc (right): https://codereview.appspot.com/583750043/diff/545930043/lily/skyline.cc#newco... lily/skyline.cc:184: for (vector<Building>::iterator i = buildings_.begin (); auto https://codereview.appspot.com/583750043/diff/545930043/lily/skyline.cc#newco... lily/skyline.cc:753: for (vector<Building>::const_reverse_iterator i (buildings_.rbegin ()); auto or rather range-based for
Sign in to reply to this message.
On Fri, Apr 24, 2020 at 3:04 PM <jonas.hahnfeld@gmail.com> wrote: > > Han-Wen, any reason not to use range-based loops in the places I pointed > to in the last patch set? I'm rewriting a lot of this code anyway in https://codereview.appspot.com/547980044/ so changing it to range loops involves more wasted editing. I can do it if you care about it, though. -- Han-Wen Nienhuys - hanwenn@gmail.com - http://www.xs4all.nl/~hanwen
Sign in to reply to this message.
hanwenn@gmail.com writes: > Here is how I have experienced this discussion: > > DAK: this is micro-optimization that causes memory fragmentation. > > HW: No, it's not; here is a benchmark that shows decreased memory use as > well. > > DAK: We could use even different data structures in the future. > > HW: This seems very philosophical to me. It is interesting that you call it "philosophical" to want to change data structures while getting a patch of yours reviewed that wants to change data structures. In particular after I indicated that I even have code. Why is it "philosophical" when someone other than you does it? > Maybe I misunderstood, because the hardcoding of a specific STL > container type predates this patch. Changing the used container type would be a reasonable point of time for changing the hardcoding, particularly since it facilitates comparisons. Also C++11 makes this considerably less awkward than previously, and code written with lists in mind tends to require less adaptation to use via vectors than the other way round, anyway. It's not just the time that a computer may save when going through the code that is important. Humans are worth consideration as well. > If you want me to use "auto" instead of > "vector<Building>::const_iterator", can you just point to the line in > the code and say "could you use auto instead of an iterator here"? Wouldn't "everywhere" be sort of obvious? > https://codereview.appspot.com/583750043/ -- David Kastrup
Sign in to reply to this message.
On 2020/04/24 13:09:53, hanwenn wrote: > On Fri, Apr 24, 2020 at 3:04 PM <mailto:jonas.hahnfeld@gmail.com> wrote: > > > > Han-Wen, any reason not to use range-based loops in the places I pointed > > to in the last patch set? > > I'm rewriting a lot of this code anyway in > https://codereview.appspot.com/547980044/ so changing it to range > loops involves more wasted editing. I can do it if you care about it, > though. Oh right, I forgot. Either way is fine for me, I guess you'll get conflicts with both.
Sign in to reply to this message.
On Fri, Apr 24, 2020 at 3:15 PM David Kastrup <dak@gnu.org> wrote: > > > If you want me to use "auto" instead of > > "vector<Building>::const_iterator", can you just point to the line in > > the code and say "could you use auto instead of an iterator here"? > > Wouldn't "everywhere" be sort of obvious? yes, it would. However when you talk about fragmentation, or your experiments about alternative merge algorithms, I get the impression you are not concerned with the actual code in the patch. So that is why I ask you to point to the code. -- Han-Wen Nienhuys - hanwenn@gmail.com - http://www.xs4all.nl/~hanwen
Sign in to reply to this message.
Han-Wen Nienhuys <hanwenn@gmail.com> writes: > On Fri, Apr 24, 2020 at 3:15 PM David Kastrup <dak@gnu.org> wrote: >> > >> > If you want me to use "auto" instead of >> > "vector<Building>::const_iterator", can you just point to the line in >> > the code and say "could you use auto instead of an iterator here"? >> >> Wouldn't "everywhere" be sort of obvious? > > yes, it would. However when you talk about fragmentation, or your > experiments about alternative merge algorithms, I get the impression > you are not concerned with the actual code in the patch. So that is > why I ask you to point to the code. I can address several issues in a single mail. -- David Kastrup
Sign in to reply to this message.
drop normalize()
Sign in to reply to this message.
On 2020/04/24 13:15:10, dak wrote: > mailto:hanwenn@gmail.com writes: > > > Here is how I have experienced this discussion: > > > > DAK: this is micro-optimization that causes memory fragmentation. > > > > HW: No, it's not; here is a benchmark that shows decreased memory use as > > well. > > > > DAK: We could use even different data structures in the future. > > > > HW: This seems very philosophical to me. > > It is interesting that you call it "philosophical" to want to change > data structures while getting a patch of yours reviewed that wants to > change data structures. In particular after I indicated that I even > have code. > > Why is it "philosophical" when someone other than you does it? > > > Maybe I misunderstood, because the hardcoding of a specific STL > > container type predates this patch. > > Changing the used container type would be a reasonable point of time for > changing the hardcoding, particularly since it facilitates comparisons. > Also C++11 makes this considerably less awkward than previously, and > code written with lists in mind tends to require less adaptation to use > via vectors than the other way round, anyway. At any rate, this is not "philosophical" really. The kind of action done here is also provided by C++' container adaptor std::queue which can be based off std::list as well as std::deque where the latter is a compromise in storage use and locality between vectors and lists and would well worth be checking out as well. Hard-coding to one particular container type makes this a lot more expensive and does not allow revisiting the decision for later versions of compiler/library or actually entirely different compilers.
Sign in to reply to this message.
Looks good with respect to using auto. One question inline, might be a missing reference. https://codereview.appspot.com/583750043/diff/557770050/lily/skyline.cc File lily/skyline.cc (right): https://codereview.appspot.com/583750043/diff/557770050/lily/skyline.cc#newco... lily/skyline.cc:584: for (auto const b : buildings_) I think this will do a copy of every building. Did you actually want to use for (auto const &b : buildings_) ?
Sign in to reply to this message.
https://codereview.appspot.com/583750043/diff/557770050/lily/skyline.cc File lily/skyline.cc (right): https://codereview.appspot.com/583750043/diff/557770050/lily/skyline.cc#newco... lily/skyline.cc:584: for (auto const b : buildings_) On 2020/04/26 11:28:19, hahnjo wrote: > I think this will do a copy of every building. Did you actually want to use > for (auto const &b : buildings_) > ? Done.
Sign in to reply to this message.
jonas final comment
Sign in to reply to this message.
LGTM (interesting that you found unused methods from 2012 :D)
Sign in to reply to this message.
commit eaf40071f56ca2ca337dc7684c0da3f307f070bd Author: Han-Wen Nienhuys <hanwen@lilypond.org> Date: Fri Apr 17 16:37:44 2020 +0200 Use vectors rather than lists for skylines.
Sign in to reply to this message.
|
