11 Aug
2015
11 Aug
'15
8:33 p.m.
On Mon, Aug 10, 2015 at 04:43:01PM -0400, Paul Davis wrote:
it provides output indicating the logic decisions that
lead to the
execution order.
I spent most of the day trying to convinve myself that I was
overlooking something. But in the end the conclusion of all
that work is this:
* The algorithm used by Jack1 to determine the order of
* running clients in each cycle is fundamentally flawed.
The reason in mathematical terms is quite simple.
Both the relations 'A feeds B' and its transitive closure
'A feeds B, maybe indirectly' define only a *partial order*
on the set of clients. Now all classical sorting algorithms,
including the merge sort used in this case, assume a *total
order* of the set to be sorted, and may not produce the
correct result if only a partial order is defined.
It's easy to see this in a less abstract way. All classical
sorting algos are designed to reduce the number of compare()
calls. For example, if they find that a == b and a == c
they will in most cases avoid testing b against c, since
under total order it must be true that b == c.
Now if a '0' return from the compare() function does not
mean equality but rather 'not connected' things change.
Using the example above, you *can not* conclude that b
and c are not connected.
So all it takes is a few unconnected clients or two
or more independent chains to increase the probability
that a classical sort algorithm will fail to produce
a correct sequence.
I actually worked out the example I posted yesterday
with pencil and paper, including all the merge sorts.
This produced exactly the results posted. So there
is no bug in the current code, it is just the wrong
algorithm.
To find a linear sequence preserving the order of a
partially ordered set you need what is known as
'topological sorting'. It's usually implemente using
depth-first search (DFS) with post-order output.
Ciao,
--
FA
A world of exhaustive, reliable metadata would be an utopia.
It's also a pipe-dream, founded on self-delusion, nerd hubris
and hysterically inflated market opportunities. (Cory Doctorow)
11 Aug
11 Aug
8:39 p.m.
New subject: Strange Jack1 problem
On Tue, Aug 11, 2015 at 2:33 PM, Fons Adriaensen <fons(a)linuxaudio.org> wrote:
To find a linear sequence preserving the order of a
partially ordered set you need what is known as
'topological sorting'. It's usually implemente using
depth-first search (DFS) with post-order output.
Simon (last name forgotten right now) added a variation on topological
sort years ago, specifically to deal with some issues. His comment
was:
/* How the sort works:
*
* Each client has a "sortfeeds" list of clients indicating which clients
* it should be considered as feeding for the purposes of sorting the
* graph. This list differs from the clients it /actually/ feeds in the
* following ways:
*
* 1. Connections from a client to itself are disregarded
*
* 2. Connections to a driver client are disregarded
*
* 3. If a connection from A to B is a feedback connection (ie there was
* already a path from B to A when the connection was made) then instead
* of B appearing on A's sortfeeds list, A will appear on B's sortfeeds
* list.
*
* If client A is on client B's sortfeeds list, client A must come after
* client B in the execution order. The above 3 rules ensure that the
* sortfeeds relation is always acyclic so that all ordering constraints
* can actually be met.
*
* Each client also has a "truefeeds" list which is the same as sortfeeds
* except that feedback connections appear normally instead of reversed.
* This is used to detect whether the graph has become acyclic.
*
*/
8:41 p.m.
New subject: Strange Jack1 problem
That said, we became aware that a similar algorithm, implemented by
Torben Hohn when he parallelized Ardour, that forms part of the Ardour
"DSP engine" was also flawed and was replaced with topological sorting
within the last couple of years.
On Tue, Aug 11, 2015 at 2:39 PM, Paul Davis <paul(a)linuxaudiosystems.com> wrote:
On Tue, Aug 11, 2015 at 2:33 PM, Fons Adriaensen
<fons(a)linuxaudio.org> wrote:
To find a linear sequence preserving the order of
a
partially ordered set you need what is known as
'topological sorting'. It's usually implemente using
depth-first search (DFS) with post-order output.
Simon (last name forgotten right now) added a variation on topological
sort years ago, specifically to deal with some issues. His comment
was:
/* How the sort works:
*
* Each client has a "sortfeeds" list of clients indicating which clients
* it should be considered as feeding for the purposes of sorting the
* graph. This list differs from the clients it /actually/ feeds in the
* following ways:
*
* 1. Connections from a client to itself are disregarded
*
* 2. Connections to a driver client are disregarded
*
* 3. If a connection from A to B is a feedback connection (ie there was
* already a path from B to A when the connection was made) then instead
* of B appearing on A's sortfeeds list, A will appear on B's sortfeeds
* list.
*
* If client A is on client B's sortfeeds list, client A must come after
* client B in the execution order. The above 3 rules ensure that the
* sortfeeds relation is always acyclic so that all ordering constraints
* can actually be met.
*
* Each client also has a "truefeeds" list which is the same as sortfeeds
* except that feedback connections appear normally instead of reversed.
* This is used to detect whether the graph has become acyclic.
*
*/
8:47 p.m.
New subject: Strange Jack1 problem
To follow up, Ardour explicitly builds a DAG and uses a topo sort.
The change was never made to Jack1 because of a lack of time (even
time to just verify that it had the same issue, even though that
seemed likely).
I also want to make it clear that my previous reference to Torben
wasn't intended to blame him for the design: he had taken the design
in Jack and applied it to the isomorphous problem inside Ardour,
without any of us realizing at that time that it was probably
inadequate/wrong.
8:48 p.m.
New subject: Strange Jack1 problem
On Tue, Aug 11, 2015 at 02:39:50PM -0400, Paul Davis wrote:
On Tue, Aug 11, 2015 at 2:33 PM, Fons Adriaensen
<fons(a)linuxaudio.org> wrote:
???
Amazed as I was, and convinced that the problem was the result of a recent
change, I tried to 'bisect' this on git. Result: this goes back to at least
2006.
What is implemented is not a topological sort at all. And the classical
trick of inverting the dependency in case of a cycle has nothing to do
with it.
Ciao,
--
FA
A world of exhaustive, reliable metadata would be an utopia.
It's also a pipe-dream, founded on self-delusion, nerd hubris
and hysterically inflated market opportunities. (Cory Doctorow)
To find a linear sequence preserving the order of
a
partially ordered set you need what is known as
'topological sorting'. It's usually implemente using
depth-first search (DFS) with post-order output.
Simon (last name forgotten right now) added a variation on topological
sort years ago, specifically to deal with some issues. His comment
was:
/* How the sort works:
... 
10:24 p.m.
New subject: Strange Jack1 problem
On 11 Aug 2015, at 19:48, Fons Adriaensen
<fons(a)linuxaudio.org> wrote:
Fons,
I wrote that comment whilst implementing what the list agreed was the best way to deal
with cycles in the graph. Its not “how the sort works” so much as “how we fudged the sort
to deal with cycles”.
I think the underlying sort mechanism was the same before I did that: Call the sort
function using the transitive closure of the who-feeds-who relation as the comparison.
(Except now its the who-feeds-who-after-inverting-feedback-connections relation).
That was always *supposed* to achieve a topological sort (before and after the feedback
mods) but you’re saying it doesn’t: The merge sort behind jack_slist_sort can outright
fail with a partial ordering because, if A isn’t connected to B and B isn’t connected to
C, it may never even ask about the relationship between A and C.
In which case yes, its a bug and it goes way back.
Simon Jenkins
Bristol, UK
Simon (last name forgotten right now) added a variation on topological
sort years ago, specifically to deal with some issues. His comment
was:
/* How the sort works:
...
???
11:33 p.m.
New subject: Strange Jack1 problem
On Tue, Aug 11, 2015 at 09:23:28PM +0100, Simon Jenkins wrote:
I wrote that comment whilst implementing what the list
agreed
was the best way to deal with cycles in the graph. Its not
“how the sort works” so much as “how we fudged the sort to
deal with cycles”.
Indeed.
I think the underlying sort mechanism was the same
before I did
that
It seems to have been like that for as long as the the git history
goes back, which is to 2006.
That was always *supposed* to achieve a topological
sort
But it doesn't. For at least ten years I just trusted that
Jack was doing this 'the right way', after all it's one of
its most basic tasks. And e.g. AMS which is at least as old
as Jack has always used DFS, a classical and well-known
solution for this sort of problem.
It wouldn't be too difficult to fix this, but it won't be
a simple five-line patch either...
Ciao,
--
FA
A world of exhaustive, reliable metadata would be an utopia.
It's also a pipe-dream, founded on self-delusion, nerd hubris
and hysterically inflated market opportunities. (Cory Doctorow)
12 Aug
12 Aug
12:50 a.m.
New subject: Strange Jack1 problem
I think the
underlying sort mechanism was the same before I did
that
It seems to have been like that for as long as the the git history
goes back, which is to 2006.
1:25 a.m.
New subject: Strange Jack1 problem
Although it pains me to say it, I think the simple fact is that none
of the people close enough to the code understood that we need to use
topological sort.
When we ran into problem inside Ardour in 2011, we came to realize
that toposort was the "standard" solution for this, but back in
2001-2004, none of the people who mattered with respect to this code
realized that is was (a) necessary (b) a well-known solution.
On Tue, Aug 11, 2015 at 6:48 PM, Simon Jenkins <sjenkins(a)steppity.com> wrote:
Fons,
Turns out my patch was late 2004 but I’ve confirmed — quick look — that minus the
feedback connection stuff it was doing the same before. (Just gotta add there was also a
substantial explanatory comment right where I dropped mine).
I note though that drivers were/are treated as a special case and forced to the front,
and that historically the major use cases for Jack would have involved connections to a
driver, likely the same driver, at some point. Not saying that fixes the problem but it
may have helped disguise it for so long: It took your entirely free-floating n2j/j2n
chain, plus other clients started and stopped at the right moment, before it did something
noticeably wrong.
Simon
I think
the underlying sort mechanism was the same before I did
that
It seems to have been like that for as long as the the git history
goes back, which is to 2006.
3190
days inactive
3190
days old
linux-audio-dev@lists.linuxaudio.org
8 comments
3 participants
participants (3)
-
Fons Adriaensen -
Paul Davis -
Simon Jenkins