Code review - Issue 353790043: Use a stable sort when ordering MIDI itemshttps://codereview.appspot.com/2018-11-03T15:43:41+00:00rietveld
Message from unknown
2018-10-31T16:11:24+00:00bobo1239urn:md5:768dc9ee69e81e16ae11ea276779e9ef
Message from MrBobo1239@gmail.com
2018-10-31T16:19:31+00:00bobo1239urn:md5:622a5c8b5dc1f6a372a5c1525916dd38
Hi all,
this is a patch to fix the issue described here:
https://lists.gnu.org/archive/html/lilypond-user/2015-02/msg00035.html
(I'm surprised this hasn't been fixed until now.)
I'm not familiar with lilypond internals at all so I don't know whether this is correct way to fix this but it does seem logical that an unstable sort will cause these problems. My local .ly test file now doesn't exhibit the issue anymore but I'd be great if somebody else who has encountered this could confirm.
Message from Carl.D.Sorensen@gmail.com
2018-10-31T18:00:13+00:00Carlurn:md5:9196631c7889c7afd1dcf38ca49a560b
Why not always have our sort use stable_sort?
Have you tried with a large score (e.g. one from mutopia) to see what the resource implications are?
Message from MrBobo1239@gmail.com
2018-10-31T21:04:55+00:00bobo1239urn:md5:3f99a4d8462c629d931a9a37bd00c22a
I've built two versions of lilypond to measure the performance impact of always
using `stable_sort`.
The baseline (reference) is commit 964722f804 without any
modifications and the second build just changes `vector_sort` to use
`sort_stable`. The test file is from Mutopia-2015/11/04-2050
(http://www.mutopiaproject.org/cgibin/piece-info.cgi?id=2050) and the test
system is a Lenovo ThinkPad T460s with an Intel i7-6600U and 12GB RAM. I've used
the following commands to create the two outputs below:
perf stat -r 10 -d <path_to_lilypond> bwv1055-conductor.ly
/usr/bin/time -v <path_to_lilypond> bwv1055-conductor.ly
`sort`:
Performance counter stats for '/home/bobo1239/Development/Random/lilypond/build-reference/out/bin/lilypond bwv1055-conductor.ly' (10 runs):
21,613.72 msec task-clock:u # 0.999 CPUs utilized ( +- 0.19% )
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
340,246 page-faults:u # 15742.528 M/sec ( +- 0.00% )
40,607,746,357 cycles:u # 1878840.077 GHz ( +- 0.06% ) (62.49%)
73,173,364,431 instructions:u # 1.80 insn per cycle ( +- 0.02% ) (74.99%)
16,164,283,684 branches:u # 747889423.315 M/sec ( +- 0.03% ) (75.00%)
226,637,525 branch-misses:u # 1.40% of all branches ( +- 0.08% ) (75.00%)
20,248,799,400 L1-dcache-loads:u # 936871883.872 M/sec ( +- 0.04% ) (75.01%)
779,001,074 L1-dcache-load-misses:u # 3.85% of all L1-dcache hits ( +- 0.08% ) (75.01%)
184,127,652 LLC-loads:u # 8519222.165 M/sec ( +- 0.31% ) (50.00%)
37,654,926 LLC-load-misses:u # 20.45% of all LL-cache hits ( +- 0.26% ) (49.99%)
21.6255 +- 0.0422 seconds time elapsed ( +- 0.20% )
Command being timed: "/home/bobo1239/Development/Random/lilypond/build-reference/out/bin/lilypond bwv1055-conductor.ly"
User time (seconds): 21.09
System time (seconds): 0.80
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:21.95
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 825364
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 340382
Voluntary context switches: 4
Involuntary context switches: 189
Swaps: 0
File system inputs: 0
File system outputs: 8320
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
`stable_sort`:
Performance counter stats for '/home/bobo1239/Development/Random/lilypond/build/out/bin/lilypond bwv1055-conductor.ly' (10 runs):
21,699.81 msec task-clock:u # 0.999 CPUs utilized ( +- 0.24% )
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
340,048 page-faults:u # 15671.006 M/sec ( +- 0.01% )
40,292,081,825 cycles:u # 1856846.419 GHz ( +- 0.05% ) (62.49%)
72,518,173,202 instructions:u # 1.80 insn per cycle ( +- 0.03% ) (74.99%)
16,015,729,544 branches:u # 738079263.019 M/sec ( +- 0.03% ) (75.00%)
224,289,991 branch-misses:u # 1.40% of all branches ( +- 0.08% ) (75.00%)
20,058,669,196 L1-dcache-loads:u # 924396714.897 M/sec ( +- 0.02% ) (75.00%)
776,684,044 L1-dcache-load-misses:u # 3.87% of all L1-dcache hits ( +- 0.04% ) (75.01%)
182,114,444 LLC-loads:u # 8392680.090 M/sec ( +- 0.22% ) (50.00%)
37,614,299 LLC-load-misses:u # 20.65% of all LL-cache hits ( +- 0.22% ) (49.99%)
21.7127 +- 0.0517 seconds time elapsed ( +- 0.24% )
Command being timed: "/home/bobo1239/Development/Random/lilypond/build/out/bin/lilypond bwv1055-conductor.ly"
User time (seconds): 20.95
System time (seconds): 0.76
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:21.78
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 825452
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 340201
Voluntary context switches: 4
Involuntary context switches: 434
Swaps: 0
File system inputs: 0
File system outputs: 8256
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
Considering that the performance impact is immeasurable and the memory usage
doesn't change, I'd say that switching to `stable_sort` completely is indeed a
viable option.
Does anybody have concerns with switching or can I go ahead and
update the patch?
Message from dan@faithful.be
2018-11-01T01:31:57+00:00dan_faithful.beurn:md5:2a7f8298075b38254c74845eab913c48
On Oct 31, 2018, at 14:00, carl.d.sorensen@gmail.com wrote:
>
> Why not always have our sort use stable_sort?
Because when someone finally clears away std-vector.hh, they will be more likely to mess it up if sort() needs to be transformed into stable_sort() than if the functions parallel those in namespace std.
—
Dan
Message from nine.fierce.ballads@gmail.com
2018-11-01T01:50:38+00:00Dan Ebleurn:md5:96cd40c55b78f594ef8a7d56e174ca3d
> (I'm surprised this hasn't been fixed until now.)
Welcome to LilyPond, where you supply the fixes. Your change looks good to me, but judging from your questions, it sounds like it could be tested better.
Have you read the chapter on Regression Tests in the Contributor's Guide? You should follow the procedure and check whether your change has any impact on the MIDI regression tests. If there are changes, you should sift through them to make sure the changes are intended. If there are no changes, it probably means that the test coverage is poor (in this case) and you should add your tiny example as a new regression test.
Message from c_sorensen@byu.edu
2018-11-01T03:23:21+00:00c_sorensenurn:md5:46c2e8d5ef7584834c3f1197712acde6
On 10/31/18, 7:32 PM, "Dan Eble" <dan@faithful.be> wrote:
On Oct 31, 2018, at 14:00, carl.d.sorensen@gmail.com wrote:
>
> Why not always have our sort use stable_sort?
Because when someone finally clears away std-vector.hh, they will be more likely to mess it up if sort() needs to be transformed into stable_sort() than if the functions parallel those in namespace std.
Great answer. Thanks.
But I still wonder if we should use both sort and stable_sort. Seems like we have no reason (unless it's a performance issue) to use both.
Thanks,
Carl
Message from MrBobo1239@gmail.com
2018-11-01T14:09:57+00:00bobo1239urn:md5:e9d713b58c0cabe72a6ffa769b78e6ff
On 2018/11/01 01:50:38, Dan Eble wrote:
> > (I'm surprised this hasn't been fixed until now.)
>
> Welcome to LilyPond, where you supply the fixes. Your change looks good to me,
> but judging from your questions, it sounds like it could be tested better.
>
> Have you read the chapter on Regression Tests in the Contributor's Guide? You
> should follow the procedure and check whether your change has any impact on the
> MIDI regression tests. If there are changes, you should sift through them to
> make sure the changes are intended. If there are no changes, it probably means
> that the test coverage is poor (in this case) and you should add your tiny
> example as a new regression test.
I didn't know that the regression tests also cover the MIDI output. Thanks for
the pointer. I had to grab LilyDev as the regression tests fail locally with
"Undefined subroutine &main::get_index called at $LILY_DIR/Documentation/
lilypond-texi2html.init line 2408." and indeed, a change is caught for
input/regression/midi/staff-map-voice.midi:
@@ -5,8 +5,8 @@
ev (0, (255, 81, '\x0fB@'))
ev (3072, (255, 47, ''))
track 1 ev (0, (255, 33, '\x01'))
+ ev (0, (255, 3, 'treble:one'))
ev (0, (255, 89, '\xfd\x01'))
- ev (0, (255, 3, 'treble:one'))
ev (0, (144, 77, 90))
ev (0, (145, 72, 90))
ev (192, (144, 77, 0))
@@ -29,10 +29,10 @@
ev (960, (145, 77, 90))
ev (1152, (144, 80, 0))
ev (1152, (145, 77, 0))
+ ev (1152, (144, 79, 90))
ev (1152, (145, 75, 90))
- ev (1152, (144, 79, 90))
+ ev (1344, (144, 79, 0))
ev (1344, (145, 75, 0))
- ev (1344, (144, 79, 0))
ev (1344, (144, 77, 90))
ev (1344, (145, 74, 90))
ev (1536, (144, 77, 0))
Don't know about the first change but the other two do make the output more
consistent.
(I've also hit a regression in input/regression/rest-dot-position.ly but AFAIKT
that is https://sourceforge.net/p/testlilyissues/issues/5217/.)
Message from nine.fierce.ballads@gmail.com
2018-11-02T00:54:32+00:00Dan Ebleurn:md5:19b5d888a48111798255ed66b19c8644
On 2018/11/01 03:23:21, c_sorensen wrote:
>
> On 10/31/18, 7:32 PM, "Dan Eble" <mailto:dan@faithful.be> wrote:
>
> But I still wonder if we should use both sort and stable_sort. Seems like we
> have no reason (unless it's a performance issue) to use both.
Using a stable_sort where it isn't necessary could miscue later maintainers who are not familiar with the context. I don't appreciate stuff like that when I'm reading unfamiliar code, but it's also easily remedied with the short comment, e.g. "stable_sort is just paranoia; equivalent items are not expected."
Message from nine.fierce.ballads@gmail.com
2018-11-03T12:39:41+00:00Dan Ebleurn:md5:20fb50cab385e78e2b0a67172955b05e
The ticket for this review is https://sourceforge.net/p/testlilyissues/issues/5434/ .
Carl, it sounds like James needs clarification as to whether you are still pressing for changing more sort calls to stable_sort calls. MHO is that this change stands fine on its own.
Message from Carl.D.Sorensen@gmail.com
2018-11-03T15:43:41+00:00Carlurn:md5:e1fc9b26870957f2fbb924baa02a2a0d
On 2018/11/03 12:39:41, Dan Eble wrote:
> The ticket for this review is
> https://sourceforge.net/p/testlilyissues/issues/5434/ .
>
> Carl, it sounds like James needs clarification as to whether you are still
> pressing for changing more sort calls to stable_sort calls. MHO is that this
> change stands fine on its own.
I'm fine to have it submitted as-is.
Carl