[LAD] Strange Jack1 problem

[Fons Adriaensen]

On Thu, Aug 13, 2015 at 06:25:04PM -0400, Paul Davis wrote:

> You continually insinuate that I do a poor job of managing jack1, and
> there's some truth to that.  I'm entirely happy to turn it over to you
> if you want to handle the pull requests, emails, releases and the rest
> of the stuff that goes with it.

No, but I am willing to tackle the current issue provided that
the solution doesn't end up in some black hole.

The solution I have in mind does not use DFS but is based on the 
'forward activation' model as in Jack2 (and which is implicitly
used to control the current sorting as well).

Ideally it would not modify the engine->clients list at all but
maintain its own data. But apparently many other parts of the
system depend of having the actual 'sorted' list, so at least
for now the algorithm will use this list and keep it in order.

The part that actually computes the sequence of clients would run
only when the dependencies change (currently it's done after each
connection change):

  - client added or removed,
  - first connection between two clients is made,
  - last connection between two clients is removed.

The complexity of this algorithm is linear in the number of 
clients and the number of depencies between them (multiple 
connections count as a single dependency). It runs once over 
the list of clients, and for each one, once over the list of 
other clients which depend on output from the current one. 
There is no recursion in this part.

That means it *could* also be run in the actual cycle, i.e.
in the context of each client after its process() has run,
provided the required data is available there. In that case
it would also automatically run clients in parallel if the
dependencies allow it. Could be an interesting option for
the future, but it requires a lot more work. Also because
the explicitly sorted list (which would not be needed any
more) is used in so many other places.

'Delayed' connections (those that create a cycle) can be
reverted to normal ones as soon as possible (the current
implementation does this only when the entire graph has
becomes cycle-free). This does not require any additional
data. In particular it does not require access to the
actual connection lists, apart for updating the marker
that is currently there. So if that is not used anywhere
else (not sure) it can be removed.

Just let me know if you're interested.

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)