#5217 random results for the merge-rests-engraver regression test

[Knut Petersen]

There is some randomness in the placement of dots. The merge-rests-engraver.ly regtest (git-version557dc7) exposes the problem as the output might be one of the two attached pngs. The probability for both results is identical on my system.

Update Nov 5th 2019
Issue 5217: Fix sorting order without outside-staff-priority

If the two Grobs have no outside-staff-priority, the compare function
staff_priority_less() would relate the two pointers. This may lead to
changing sorting orders in subsequent runs, apparently resulting in
"random" positions in the regression tests rest-dot-position.ly and
sometimes merge-rests-engraver.ly.
Solve this by keeping the original order in the vector:
Mark two Grobs without outside-staff-priority as being equal by
always returning false (none is less than the other), and
use vector_stable_sort() to keep equal items in their relation.

http://codereview.appspot.com/554960043

[Anonymous]

I went through the checkins one-by-one ('soft resetting' HEAD on my local git repo each time) and did the make test-baseline/make check for each commit. I have identified that it is from this commit onwards:

Add system-by-system output to SVG backend
author  Étienne Beaulé <beauleetienne0@gmail.com>   
    Thu, 17 Aug 2017 08:28:39 +0100 (04:28 -0300)
committer   James Lowe <pkx166h@gmail.com>  
    Sat, 26 Aug 2017 10:39:01 +0100 (10:39 +0100)
commit  6824b081b69449a8471f1b64c618c8e4903eeaff

when the funny reg test diff starts to show up

[David Kastrup]

That's peculiar since that commit only changes scm/framework-svg.scm (apart from a trivial Doc change). That should not even be used unless producing SVG.

[Anonymous]

So I went back again and tried one more time round - in case I hadn't really reset my branch. Hmmm, it is frustrating. I don't always hit it. I had nothing until I got to this later checkin:

Author: Thomas Morley <thomasmorley65@gmail.com>  2017-08-29 09:24:26
Committer: Thomas Morley <thomasmorley65@gmail.com>  2017-09-04 22:07:04
Parent: 4ca9913c540dfbfc7f598c07735c90139138327b (Issue 5137/2: Doc: Add how to use set-global-fonts for non-music fonts)
...

    Register Merge_rests_engraver

    Change docs and reg-test accordingly

and then, because one example is not 'proof' I ran it again on the same checkin and didn't get anything (I did a distclean etc).

[Knut Petersen]

If I port current masters merge-rests-engraver.ly back to the old syntax

< \version "2.21.0"
> \version "2.19.60"
< \consists "Merge_rests_engraver"
> \consists #Merge_rests_engraver

and start a regtest loop I see that the problem is already present in

commit 212ca268e813cd72eca8c07e714e1b6669cba747
Author: Jay Anderson horndude77@gmail.com
Date: Mon Jun 19 12:58:17 2017 +0100

Create engravers for merging rests

Issue 1228

This commit includes engravers
for merging rests and multimeasure
rests among multiple voices.

[Thomas Morley]

FWIW,
I looked through our regtests searching for { r4. } in simultaneous music and found only:
dot-column-rest-collision.ly
dots.ly
merge-rests-engraver.ly
rest-dot-position.ly

merge-rests-engraver.ly is the single one with three voices

I then modified rest-dot-position.ly :

mus = {
    r\longa. r\breve.
    r1. r2. r4.
    \once \override Rest.style = #'classical r4.
    r8. r16. r32. r64. r64.
}

vI =   \new Voice { \override Rest.color = #red    \voiceOne   \mus }
vII =  \new Voice { \override Rest.color = #green  \voiceTwo   \mus }
vIII = \new Voice { \override Rest.color = #cyan   \voiceThree \mus }
vIV =  \new Voice { \override Rest.color = #yellow \voiceFour  \mus }

{
    \set Score.timing = ##f
    \set Staff.instrumentName = #(lilypond-version)
    \mus
    \bar "" \break
    << \vI \vII >>
    \bar "" \break
    << \vI \vII \vIII >>
    \bar "" \break
    << \vI \vII \vIII \vIV >>
}

If you look at the output you see dots moving depending on \voiceXxxx
To make it more obvious colors are applied.

So far I the results are not random, though I always checked in-file and not running the regtests.
Maybe of some help, though.

Btw, some output is really poor, imho, see the dots for short rests in the outer voices.

[Knut Petersen]

If you look at the output you see dots moving depending on \voiceXxxx
To make it more obvious colors are applied.

So far I the results are not random, though I always checked in-file and not running the regtests.
Maybe of some help, though.

Well, that dots change the position depending on \voiceXxx is not a problem, although your example clearly shows that some work could be invested into this code. The problem is that we have one input and lilypond randomly choses between two places for that one dot in the second voice.

[Anonymous]

But is it random? I mean on every patch test I do now I get this this reg test diff pop up. If it were random then this would not happen - (unless I am very lucky!)

[Knut Petersen]

50 regression tests with no changes
"1" means "we hit the problem",
"0" means "files are identical"

Result array: 10001100000001100000000110000110001110100000000000

A minor editing at the end of merge-rests-engraver.ly seems to mask the problem here:

Original unstable version:

 <<
    \compressFullBarRests
    \new Voice { \voiceOne \voiceA }
    \new Voice { \voiceTwo \voiceB }
    \new Voice { \voiceThree \voiceC }
  >>

Stable version:

 <<
    \compressFullBarRests
    \new Voice { \voiceTwo \voiceB }
    \new Voice { \voiceOne \voiceA }
    \new Voice { \voiceThree \voiceC }
  >>

[Knut Petersen]

Ok. That "stable version" above isn't stable .... 2 in 100 regtests exposed the problem again.

[Thomas Morley]

I've put my code above as 'aaa-voiced-rest-dots.ly' into the regtest and did a regtest comparison without any changes.
And it is triggered!! (As well as the usual merge-rest-engraver.ly)
See attached.
So I think it's proofed that something else is fishy, not the merge-rest-code/regtest.
Let me emphasize again: merge-rest-engraver.ly was the single regtest with three voices containing simultaneous r4.
Now I added another one, and it is triggered as well!!

[Thomas Morley]

I did regression-tests with the attached regtest 'aaa-voiced-dotted-rests.ly' (old syntax, to make it work even for 2.16) with checkouts of previous stables, i.e. 2.18 and 2.16.
(For difficulties getting it work see the thread starting http://lists.gnu.org/archive/html/lilypond-devel/2017-10/msg00144.html)
Results attached as well.

The dots are placed quite randomly for every tested version.

Maybe we should have a regtest for explecitely testing dotted rests for more than two voices. Even if going on everyones nerves until the problem is solved.

[Thomas Morley]

Obviously I can't attach more than one file file ...

[Thomas Morley]

the regtest

[Thomas Morley]

I think I've found the culprit, I needed to revive LilyDev2 which is based upon Ubuntu 10.04 with
GNU Make 3.81
gcc (Ubuntu 4.4.3-4ubuntu5.1) 4.4.3

First bad commit is

commit 1c24c56886cd85f04283ac61e8a0deea172035ed
Author: Mike Solomon mike@apollinemike.com
Date: Wed Jan 18 08:22:31 2012 +0100

Prevents DotColumns from triggering VerticalAlignment

This is issue 2180
lilypond-version 2.15.27

And was meant to improve issue 1986

And was changed with issue 2468

Obviously the initially reported problem persisted and persists, but was never detected until merge-rests-engraver.ly introduced simultaneous dotted rests for more than two voices.

There may have been more changes after 2468, ofcourse.

What a mess ...

[David Kastrup]

Huh. It contains a call
+ vector_sort (dots, pure_position_less);
which uses a non-stable sort I guess. One could check whether using vector_stable_sort makes any difference. Not that I have a clue what I am doing here... The problem is that likely even with a stable sort, the order of comparisons is not guaranteed, and the code looks like it triggers some semi-recursive evaluation.

[Thomas Morley]

I could give it a try, but not before next weekend ...

[Thomas Morley]

I now locally changed vector_sort to vector_stable_sort in dot-column.cc.
After doing so I've run make test-baseline and make check:
The dots in input/regression/rest-dot-position.ly are still not consistent positioned.
Thus I think that change doesn't help, at least not solely.

[David Kastrup]

"Thomas Morley" thomas-morley@users.sourceforge.net writes:

I now locally changed vector_sort to vector_stable_sort in dot-column.cc.
After doing so I've run make test-baseline and make check:
The dots in input/regression/rest-dot-position.ly are still not consistent positioned.
Thus I think that change doesn't help, at least not solely.

Ok, it was worth a try. I may even have concocted that experiment
myself previously but could not remember reliably any more.

Thanks!

--
David Kastrup

[Jonas Hahnfeld]

I've tried to approach this systematically and made the observation that the moving dots might be related to what other regression tests are built for check (and maybe in what order? not sure if that is stable across invocations). Based on that, I've created a small set of input files (see attached archive) that really changes at random on subsequent invocations of lilypond -dread-file-list names.ly, at least on my system.

I went on to understand what is causing the non-determinism. From what I found so far, it looks like some functions might be called in a different order in subsequent invocations of lilypond. I've also put a small diff into above archive which adds a few printfs: Sometimes Dot_column::calc_positioning_done is called before Rest_collision::force_shift_callback_rest, on another invocation it might be the other way around. The problem is that Rest_collision::force_shift_callback_rest calls Grob::translate_axis which updates a cache and changes the Y position.

At least that's what it looks like to me right now, without knowing which ordering of above functions would be correct. But a changing order at random seems odd, doesn't it? Posting here in case somebody with more experience goes like "hey, that can be easily fixed like this". Otherwise I'll try to understand what's causing the different orders and how it can be turned off.

[David Kastrup]

"Jonas Hahnfeld" hahnjo@users.sourceforge.net writes:

I've tried to approach this systematically and made the observation
that the moving dots might be related to what other regression tests
are built for check (and maybe in what order? not sure if that is
stable across invocations). Based on that, I've created a small set of
input files (see attached archive) that really changes at random on
subsequent invocations of lilypond -dread-file-list names.ly, at
least on my system.

I went on to understand what is causing the non-determinism. From what
I found so far, it looks like some functions might be called in a
different order in subsequent invocations of lilypond. I've also put a
small diff into above archive which adds a few printfs: Sometimes
Dot_column::calc_positioning_done is called before
Rest_collision::force_shift_callback_rest, on another invocation it
might be the other way around. The problem is that
Rest_collision::force_shift_callback_rest calls
Grob::translate_axis which updates a cache and changes the Y
position.

At least that's what it looks like to me right now, without knowing
which ordering of above functions would be correct. But a changing
order at random seems odd, doesn't it?

Turn off address space randomization and chances are that things become
more deterministic. As it is, certain data structures like Scheme
hashes are traversed in orders that depend on address allocation orders.

The current situation of random results for successive runs on identical
input is probably not significantly worse than pseudorandom results that
are only deterministic if you change absolutely nothing. Whether
minimal unrelated changes (including compilation with different
compiler/libraries) lead to considerable changes in results or no
changes at all: in practice that does not likely make a lot of
difference. It's only a bit baffling for people used to the consistency
of computers.

Posting here in case somebody with more experience goes like "hey,
that can be easily fixed like this". Otherwise I'll try to understand
what's causing the different orders and how it can be turned off.

--
David Kastrup

[Jonas Hahnfeld]

I had the same idea, but I still see non-deterministic results for my simple example after running echo 0 | sudo tee /proc/sys/kernel/randomize_va_space which should turn off ASLR. I'll try the kernel parameter tomorrow and let you know if that changes anything.

[Jonas Hahnfeld]

So the reason is that staff_priority_less compares pointers in the default case. I'm not entirely sure why those change even without ASLR, but maybe Guile's garbage collection and / or timing of allocation play a role?

[David Kastrup]

"Jonas Hahnfeld" hahnjo@users.sourceforge.net writes:

So the reason is that staff_priority_less compares pointers in the
default case. I'm not entirely sure why those change even without
ASLR, but maybe Guile's garbage collection and / or timing of
allocation play a role?

This is pretty appalling. I see that

• /* if neither grob has an outside-staff priority, the ordering will have no
• effect -- we just need to choose a consistent ordering. We do this to
• avoid the side-effect of calculating extents. */
• if (isinf (priority_1))
• return g1 < g2;

has been added in
commit 8eafccec8c45891d8e00366ca2f67f67a9c93cf9
Author: Joe Neeman joeneeman@gmail.com
Date: Sun Jan 21 14:04:13 2007 +0200

Enable one-pass stretching for PianoStaff

and seems of little relation to the commit message. It would likely be
saner to just return false instead of introducing some random order that
serves no point. Of course this will still warrant using a stable sort.

P.S.: I see that you already proposed a patch doing exactly that.

[Jonas Hahnfeld]

Issue 5217: Fix sorting order without outside-staff-priority

If the two Grobs have no outside-staff-priority, the compare function
staff_priority_less() would relate the two pointers. This may lead to
changing sorting orders in subsequent runs, apparently resulting in
"random" positions in the regression tests rest-dot-position.ly and
sometimes merge-rests-engraver.ly.
Solve this by keeping the original order in the vector:
* Mark two Grobs without outside-staff-priority as being equal by
always returning false (none is less than the other), and
* use vector_stable_sort() to keep equal items in their relation.

http://codereview.appspot.com/554960043