Use a stable sort when ordering MIDI items

Use 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")

[bobo1239, 2018-10-31 16:19:31]

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.

[Carl, 2018-10-31 18:00:13]

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?

[bobo1239, 2018-10-31 21:04:55]

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?

[dan_faithful.be, 2018-11-01 01:31:57]

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

[Dan Eble, 2018-11-01 01:50:38]

> (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.

[c_sorensen, 2018-11-01 03:23:21]

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
 

[bobo1239, 2018-11-01 14:09:57]

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/.)

[Dan Eble, 2018-11-02 00:54:32]

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."

[Dan Eble, 2018-11-03 12:39:41]

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.

[Carl, 2018-11-03 15:43:41]

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