Re: Use a stable sort when ordering MIDI items (issue 353790043 by address@hidden)

[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/