|
|
Created:
5 years, 5 months ago by bobo1239 Modified:
5 years, 5 months ago CC:
lilypond-devel_gnu.org Visibility:
Public. |
DescriptionUse a stable sort when ordering MIDI items
Fixes the issue described here:
https://lists.gnu.org/archive/html/lilypond-user/2015-02/msg00035.html
(undeterministic reordering of events at the same MIDI timestamp; e.g.
"\sustainOff\sustainOn")
Patch Set 1 #
MessagesTotal messages: 10
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.
Sign in to reply to this message.
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?
Sign in to reply to this message.
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?
Sign in to reply to this message.
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
Sign in to reply to this message.
> (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.
Sign in to reply to this message.
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
Sign in to reply to this message.
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/.)
Sign in to reply to this message.
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."
Sign in to reply to this message.
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.
Sign in to reply to this message.
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
Sign in to reply to this message.
|