Use a stable sort when ordering MIDI items (issue 353790043 by MrBobo1239@gmail.com)

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Use a stable sort when ordering MIDI items (issue 353790043 by MrBobo1239@gmail.com)

MrBobo1239
Reviewers: ,

Message:
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.

Description:
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")

Please review this at https://codereview.appspot.com/353790043/

Affected files (+13, -1 lines):
   M flower/include/std-vector.hh
   M lily/midi-walker.cc


Index: flower/include/std-vector.hh
diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh
index  
589f7c0db2063a2110241668c5d2ac7ba39d39ce..4a46339bad5ca064f586b85815345e4c0a7c587a  
100644
--- a/flower/include/std-vector.hh
+++ b/flower/include/std-vector.hh
@@ -168,6 +168,18 @@ vector_sort (vector<T> &v,
    sort (v.begin () + b, v.begin () + e, less);
  }

+template<typename T, typename Compare>
+void
+vector_stable_sort (vector<T> &v,
+             Compare less,
+             vsize b = 0, vsize e = VPOS)
+{
+  if (e == VPOS)
+    e = v.size ();
+
+  stable_sort (v.begin () + b, v.begin () + e, less);
+}
+
  template<typename T>
  void
  reverse (vector<T> &v)
Index: lily/midi-walker.cc
diff --git a/lily/midi-walker.cc b/lily/midi-walker.cc
index  
c54bc6a6b458391e91a47812064fc9803d29ae2a..68b2c34de57e8667743be9253fffe0c929c913ed  
100644
--- a/lily/midi-walker.cc
+++ b/lily/midi-walker.cc
@@ -57,7 +57,7 @@ Midi_walker::Midi_walker (Audio_staff *audio_staff,  
Midi_track *track, int start
    track_ = track;
    index_ = 0;
    items_ = audio_staff->audio_items_;
-  vector_sort (items_, audio_item_less);
+  vector_stable_sort (items_, audio_item_less);
    //Scores that begin with grace notes start at negative times. This
    //is OK - MIDI output doesn't use absolute ticks, only differences.
    last_tick_ = start_tick;



_______________________________________________
lilypond-devel mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Use a stable sort when ordering MIDI items (issue 353790043 by MrBobo1239@gmail.com)

Carl Sorensen
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?


https://codereview.appspot.com/353790043/

_______________________________________________
lilypond-devel mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Use a stable sort when ordering MIDI items (issue 353790043 by MrBobo1239@gmail.com)

MrBobo1239
In reply to this post by MrBobo1239
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?

https://codereview.appspot.com/353790043/

_______________________________________________
lilypond-devel mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Use a stable sort when ordering MIDI items (issue 353790043 by MrBobo1239@gmail.com)

Dan Eble
In reply to this post by Carl Sorensen
On Oct 31, 2018, at 14:00, [hidden email] 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


_______________________________________________
lilypond-devel mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Use a stable sort when ordering MIDI items (issue 353790043 by MrBobo1239@gmail.com)

nine.fierce.ballads
In reply to this post by MrBobo1239
> (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.

https://codereview.appspot.com/353790043/

_______________________________________________
lilypond-devel mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Use a stable sort when ordering MIDI items (issue 353790043 by MrBobo1239@gmail.com)

Carl Sorensen-3
In reply to this post by Dan Eble


On 10/31/18, 7:32 PM, "Dan Eble" <[hidden email]> wrote:

    On Oct 31, 2018, at 14:00, [hidden email] 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
 

_______________________________________________
lilypond-devel mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Use a stable sort when ordering MIDI items (issue 353790043 by MrBobo1239@gmail.com)

MrBobo1239
In reply to this post by MrBobo1239
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/.)

https://codereview.appspot.com/353790043/

_______________________________________________
lilypond-devel mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Use a stable sort when ordering MIDI items (issue 353790043 by MrBobo1239@gmail.com)

nine.fierce.ballads
In reply to this post by MrBobo1239
On 2018/11/01 03:23:21, c_sorensen wrote:

> On 10/31/18, 7:32 PM, "Dan Eble" <mailto:[hidden email]> 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."

https://codereview.appspot.com/353790043/
_______________________________________________
lilypond-devel mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Use a stable sort when ordering MIDI items (issue 353790043 by MrBobo1239@gmail.com)

nine.fierce.ballads
In reply to this post by MrBobo1239
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.


https://codereview.appspot.com/353790043/

_______________________________________________
lilypond-devel mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Use a stable sort when ordering MIDI items (issue 353790043 by MrBobo1239@gmail.com)

Carl Sorensen
In reply to this post by MrBobo1239
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


https://codereview.appspot.com/353790043/

_______________________________________________
lilypond-devel mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/lilypond-devel