Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(84)

Issue 583750043: Use vectors rather than lists for skylines. (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
1 month, 3 weeks ago by hanwenn
Modified:
4 weeks, 1 day ago
Reviewers:
Dan Eble, hahnjo, carl.d.sorensen, dak, Carl
CC:
lilypond-devel_gnu.org
Visibility:
Public.

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 #

Unified diffs Side-by-side diffs Delta from patch set Stats (+119 lines, -145 lines) Patch
M lily/include/skyline.hh View 1 2 3 4 5 6 7 8 3 chunks +11 lines, -14 lines 0 comments Download
M lily/skyline.cc View 1 2 3 4 5 6 7 8 24 chunks +108 lines, -131 lines 0 comments Download

Messages

Total messages: 43
hanwenn
reserve
1 month, 3 weeks ago (2020-04-12 14:17:54 UTC) #1
hanwenn
ptr iso. ref
1 month, 3 weeks ago (2020-04-12 15:25:02 UTC) #2
hanwenn
notes to self about optimization
1 month, 3 weeks ago (2020-04-12 15:40:57 UTC) #3
hanwenn
This is likely a timing fluke due to thermal throttling too. Hold off on reviewing.
1 month, 3 weeks ago (2020-04-13 18:51:22 UTC) #4
hahnjo
On 2020/04/13 18:51:22, hanwenn wrote: > This is likely a timing fluke due to thermal ...
1 month, 3 weeks ago (2020-04-14 06:57:08 UTC) #5
hanwenn
Sure. On Tue, Apr 14, 2020 at 8:57 AM <jonas.hahnfeld@gmail.com> wrote: > > On 2020/04/13 ...
1 month, 3 weeks ago (2020-04-14 07:25:02 UTC) #6
hanwenn
update timings; rebase on interval building.
1 month, 2 weeks ago (2020-04-17 14:58:36 UTC) #7
hanwenn
On 2020/04/17 14:58:36, hanwenn wrote: > update timings; rebase on interval building. I measured more ...
1 month, 2 weeks ago (2020-04-17 15:02:38 UTC) #8
Carl
LGTM Carl
1 month, 2 weeks ago (2020-04-17 15:07:50 UTC) #9
hahnjo
On 2020/04/17 15:02:38, hanwenn wrote: > On 2020/04/17 14:58:36, hanwenn wrote: > > update timings; ...
1 month, 2 weeks ago (2020-04-17 18:53:56 UTC) #10
hanwenn
On Fri, Apr 17, 2020 at 8:53 PM <jonas.hahnfeld@gmail.com> wrote: > > > update timings; ...
1 month, 2 weeks ago (2020-04-17 19:07:44 UTC) #11
Dan Eble
On 2020/04/17 19:07:44, hanwenn wrote: > The profile data itself is also a more precise ...
1 month, 2 weeks ago (2020-04-17 22:44:12 UTC) #12
hanwenn
On 2020/04/17 22:44:12, Dan Eble wrote: > On 2020/04/17 19:07:44, hanwenn wrote: > > The ...
1 month, 2 weeks ago (2020-04-18 11:13:11 UTC) #13
hanwenn
dan, diff against master
1 month, 2 weeks ago (2020-04-18 11:16:43 UTC) #14
hanwenn
I'm uploading a diff against master, so James can run this through tests. Intention is ...
1 month, 2 weeks ago (2020-04-18 11:17:14 UTC) #15
hanwenn
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#newcode74 lily/skyline.cc:74: for (vector<Building>::const_iterator i = b.begin (); i != b.end ...
1 month, 2 weeks ago (2020-04-18 11:25:36 UTC) #16
Dan Eble
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#newcode75 lily/skyline.cc:75: i.print (); I'm sorry, I gave you imperfect advice ...
1 month, 2 weeks ago (2020-04-18 11:38:17 UTC) #17
hanwenn
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#newcode75 ...
1 month, 2 weeks ago (2020-04-21 07:38:33 UTC) #18
dak
I am rather skeptical about the usefulness of such microoptimizations without influence on algorithmic complexity. ...
1 month, 2 weeks ago (2020-04-21 23:39:55 UTC) #19
Dan Eble
On 2020/04/21 23:39:55, dak wrote: > influence on algorithmic complexity. In return for better memory ...
1 month, 2 weeks ago (2020-04-21 23:59:33 UTC) #20
hanwenn
current master: 4f906b95aea99f2a47d5ba037f7421e5bb933c42 (origin/master) Issue 5908: get_path_list: use loop instead of tail recursion Command being ...
1 month, 2 weeks ago (2020-04-22 07:43:17 UTC) #21
Dan Eble
On 2020/04/22 07:43:17, hanwenn wrote: > Finally, to Dan's point: I haven't looked at heap ...
1 month, 2 weeks ago (2020-04-22 20:52:04 UTC) #22
dak
On 2020/04/22 07:43:17, hanwenn wrote: > current master: > > 4f906b95aea99f2a47d5ba037f7421e5bb933c42 (origin/master) Issue 5908: > ...
1 month, 1 week ago (2020-04-23 16:01:20 UTC) #23
dak
On 2020/04/23 16:01:20, dak wrote: > On 2020/04/22 07:43:17, hanwenn wrote: > > * The ...
1 month, 1 week ago (2020-04-23 17:43:46 UTC) #24
hanwenn
On Thu, Apr 23, 2020 at 6:01 PM <dak@gnu.org> wrote: > > I disagree David's ...
1 month, 1 week ago (2020-04-23 21:53:57 UTC) #25
dak
Han-Wen Nienhuys <hanwenn@gmail.com> writes: > On Thu, Apr 23, 2020 at 6:01 PM <dak@gnu.org> wrote: ...
1 month, 1 week ago (2020-04-23 22:17:35 UTC) #26
hahnjo
I generally agree with David that having the code agnostic of the container would be ...
1 month, 1 week ago (2020-04-24 07:08:51 UTC) #27
hanwenn
Here is how I have experienced this discussion: DAK: this is micro-optimization that causes memory ...
1 month, 1 week ago (2020-04-24 12:34:01 UTC) #28
hanwenn
jonas
1 month, 1 week ago (2020-04-24 12:35:14 UTC) #29
hanwenn
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#newcode183 lily/skyline.cc:183: vector<Building>::iterator i; On 2020/04/24 07:08:50, hahnjo wrote: > move ...
1 month, 1 week ago (2020-04-24 12:37:02 UTC) #30
hahnjo
Han-Wen, any reason not to use range-based loops in the places I pointed to in ...
1 month, 1 week ago (2020-04-24 13:04:37 UTC) #31
hanwenn
On Fri, Apr 24, 2020 at 3:04 PM <jonas.hahnfeld@gmail.com> wrote: > > Han-Wen, any reason ...
1 month, 1 week ago (2020-04-24 13:09:53 UTC) #32
dak
hanwenn@gmail.com writes: > Here is how I have experienced this discussion: > > DAK: this ...
1 month, 1 week ago (2020-04-24 13:15:10 UTC) #33
hahnjo
On 2020/04/24 13:09:53, hanwenn wrote: > On Fri, Apr 24, 2020 at 3:04 PM <mailto:jonas.hahnfeld@gmail.com> ...
1 month, 1 week ago (2020-04-24 13:16:17 UTC) #34
hanwenn
On Fri, Apr 24, 2020 at 3:15 PM David Kastrup <dak@gnu.org> wrote: > > > ...
1 month, 1 week ago (2020-04-24 13:18:11 UTC) #35
dak
Han-Wen Nienhuys <hanwenn@gmail.com> writes: > On Fri, Apr 24, 2020 at 3:15 PM David Kastrup ...
1 month, 1 week ago (2020-04-24 13:29:43 UTC) #36
hanwenn
drop normalize()
1 month, 1 week ago (2020-04-25 19:38:50 UTC) #37
dak
On 2020/04/24 13:15:10, dak wrote: > mailto:hanwenn@gmail.com writes: > > > Here is how I ...
1 month, 1 week ago (2020-04-26 10:26:17 UTC) #38
hahnjo
Looks good with respect to using auto. One question inline, might be a missing reference. ...
1 month, 1 week ago (2020-04-26 11:28:19 UTC) #39
hanwenn
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#newcode584 lily/skyline.cc:584: for (auto const b : buildings_) On 2020/04/26 11:28:19, ...
1 month, 1 week ago (2020-04-26 12:37:17 UTC) #40
hanwenn
jonas final comment
1 month, 1 week ago (2020-04-26 12:37:44 UTC) #41
hahnjo
LGTM (interesting that you found unused methods from 2012 :D)
1 month, 1 week ago (2020-04-26 15:01:05 UTC) #42
hanwenn
1 month ago (2020-05-02 22:24:49 UTC) #43
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.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b