Subject: Re: [linux-audio-dev] XAP spec - early scribbles
From: torbenh_AT_gmx.de
Date: Tue Mar 04 2003 - 12:27:13 EET
On Mon, Mar 03, 2003 at 08:36:04PM +0000, Simon Jenkins wrote:
> torbenh_AT_gmx.de wrote:
>
> >On Sun, Mar 02, 2003 at 09:06:02PM +0000, Simon Jenkins wrote:
> >
> >
> >>torbenh_AT_gmx.de wrote:
> >>
> >>
> >>
> >>>ok ... now to the API...
> >>>
> >>>
> >>>
> >>Here's my thinking so far, modulo some of your comments
> >>
> >>(I'll need to think a bit more about some other of your comments,
> >>eg what you need for galan)
> >>
> >>
> >
> >me too... but as you stated: you're the graph sort head :)
> >
> >
> >
> >>/*============================================================================
> >>File: gsort.h
> >>==============================================================================
> >>
> >>Purpose: C interface to gsort library
> >>
> >>Project: gsort library
> >>
> >>Tabs: 4
> >>
> >>Version: proposal.0.0.1
> >>
> >>Comments: Very rough draft, doesn't compile.
> >>
> >> This version presumes a C++/STL implementation completely
> >>hidden
> >> behind a C API, but that hasn't been decided yet. Alternatives
> >> could be:
> >>
> >> an implementation that exposes enough internal data
> >>structures for
> >> apps to manipulate graphs directly rather than solely via
> >>the API.
> >> (Problem with this is that the implementation needs inheritance
> >> which would have to be "hand rolled" in C, were it to be exposed
> >> to the application.)
> >>
> >>
> >
> >where do you use inheritance ?
> >
> You've already spotted the obvious place, later on, where a graph can be
> used as a node.
> This is where the C++ functionality is actually touched (or, at least,
> is prodded at with
> handles) by the application. Internal to the library, and so less
> relevant to this API, there
> might be cause to build a little heirarchy starting with "CGraphObject".
i could build a C++ wrapper around my generator class
inheriting from CGraphObject:
it now looks like this:
struct GeneratorClass {
char *name; /* human-readable name - and also
tag for save/load, so MUST be unique */
/* Event inputs */
gint in_count;
char **in_names;
AEvent_handler_t *in_handlers;
/* Event outputs */
gint out_count;
char **out_names;
/* Signal inputs */
gint in_sig_count;
InputSignalDescriptor *in_sigs;
/* Signal outputs */
gint out_sig_count;
OutputSignalDescriptor *out_sigs;
/* Control descriptors */
ControlDescriptor *controls;
int numcontrols;
/* Instance methods */
int (*initialize_instance)(Generator *g);
void (*destroy_instance)(Generator *g);
AGenerator_pickle_t unpickle_instance;
AGenerator_pickle_t pickle_instance;
};
struct Generator {
GeneratorClass *klass;
char *name;
/* Links to other Generators */
GList **in_events; /* array of GLists of EventLinks */
GList **out_events;
GList **in_signals;
GList **out_signals;
/* Sample caching for multiple (realtime) reads */
/* note that we don't cache randomaccess signal generators */
SAMPLETIME last_sampletime;
SAMPLE **last_buffers;
int *last_buflens;
gboolean *last_results;
/* Controls */
GList *controls;
/* per-class data */
void *data;
};
would convert to :
class CGraphGeneratorObject : public CGraphObject {
Generator *g;
public:
cppGenerator( GeneratorClass *klass, string name ) {
g=gen_new_generator( klass, name );
}
cppGenerator( ObjectStoreItem *item ) {
g = gen_unpickle( item );
}
~cppGenerator( ) {
gen_kill_generator( g );
}
EventLink *link( int is_signal, cppGenerator *src, int src_q, cppGenerator *dst, int dst_q ) {
return gen_link( is_signal, src, src_q, dst, dst_q );
}
// I would rather use this one but galan does not:
EventLink *link( is_signal, Input *i, Output *o );
// hmmm unlink does not match here (any idea?)
ObjectStoreItem *pickle( ObjectStore *db ) {
gen_pickle( g, db );
}
// think i must describe the lists etc by
// inheriting from list<T> or something...
}
>
> >>==============================================================================
> >>Copyright (c) Simon Jenkins 2003 licence to be decided (GPL/LGPL/dual?)
> >>============================================================================*/
dont know...
> >>
> >>and some minimal customisation of the sort...
> >> GSORT_QIF_LATE_AS_POSSIBLE
> >> GSORT_QIF_EARLY_AS_POSSIBLE
> >> (2 flags because default is don't care)
> >> GSORT_QIF_FEEDBACK_WELCOME
> >> GSORT_QIF_FEEDBACK_UNWELCOME
> >> (2 flags because default is don't care)
> >> GSORT_QIF_INCLUDE_IF_UNCONNECTED */
ok... nice...
> >>
> >>gsort_error
> >>gsort_Q_AddConnect( void *SNode, uint SOut, void *DNode, uint DOut );
> >>
> Whoops! That should say:
> gsort_Q_AddConnect( void *SNode, uint SOut, void *DNode, uint DIn );
oh i missed that one :)
>
> >>gsort_error
> >>gsort_Q_SortGraph( void );
> >>
> >>void *
> >>gsort_Q_GetNextNode( void );
> >>/* after calling gsort_Q_SortGraph, call this repeatedly to get the
> >>execution order. Returns 0 when finished. Self resetting so if you need to
> >>be told twice, just start calling it again. */
> >>
> >>
> >
> >hmmm... i would like to have this a list or is this not a list internally ?
> >
> Remembering that this version of the proposal presumes a pure C interface to
> a C++/STL implementation...
ah yes i forgot that..
then the interface is fine with me...
>
> >>#endif /* !GSORT_HIDE_QUICK_INTERFACE */
> >>
> >>/*===============
> >>FULL INTERFACE:
> >>=================
> >>The full interface is for apps with heavyweight graph sorting
> >>requirements ie
> >>they need some or all of the following functionality:
> >>~ multiple, persistent, modifiable graphs
> >>~ nodes with changing numbers of inputs and outputs
> >>~ graphs-within-graphs
> >>~ customiseable sorting
> >>~ more information about the execution order, eg about feedback loops
> >>~ serialisation of graphs
> >>
> >>
> >
> >yes...
> >
> Its worth pointing out here that the full interface is completely
> non-interoperable
> with the quick interface. You use one or the other. The full interface
> is the "real"
> interface to the library. The quick interface lets you sort your own
> graphs without
> getting "sucked in" to the library's model.
ok... you could state this clearer with your defines:
#ifdef GSORT_QUICK
quick_interface()
#else
full_interface()
#endif
>
> >>It is possible, but not obligatory, for an app to use gsort to hold the
> >>sole
> >>representation of its graph(s) when using the full interface.
> >>
> >>
> >
> >this is nice...
> >
> >
> >>graphs-within-graph functionality is accessed simply by passing a graph
> >>handle into a function that expects a node handle. These never turn up in
> >>the execution list, but the stuff inside them does (works recursively with
> >>sub-sub-graphs etc as well) */
> >>
> >>
> >
> >nice idea... i begin to understand why you want ids...
> >but a void * is a unique id also ... needs a smarter hash function than an
> >ID
> >but no more i think.
> >
> The question about pointers vs IDs really applied to the quick interface
> only. Those
> pointers (or IDs) in the quick interface were the app's own values,
> whereas a
> gsort_handle is the library's handle on one of its internal classes.
ok now i get get it...
always forgetting STL :)
lets see how it would look with the C++ wrapper for my objects..
>
> Whether or not to use void* as the type for gsort_handle is an
> implementation
> issue. Whatever the underlying type, its just a "gsort_handle" so far as
> the app is
> concerned. Its got to be something that can be passed and returned by
> value in a
> C function call, and it might be nice if 0 could represent a failed
> allocation.
ok...
>
> >>#ifndef GSORT_HIDE_FULL_INTERFACE
> >>
> >>typedef void * gsort_handle;
> >>
> >>gsort_error
> >>gsort_Initialise( int InitGraphHandles );
> >>
> >>gsort_error
> >>gsort_Cleanup( void );
> >>
> >>gsort_handle
> >>gsort_NewGraph( ushort Flags, void *Data, gsort_callback Callback );
> >>/* The callback functions have nothing to do with runtime execution of the
> >>graph. They're for the application to receive - and possibly provide -
> >>information during the sort process. Pass in 0 if you're not bothered.
> >>The Data pointer is for the sole use and convenience of the application.
> >>*/
> >>
> >>
> >
> >signature of gsort ?
> >i bet you know already...
> >
> You lose! I only have a hazy cloud of ideas concerning this. :)
typedef rettype? (*gsort_callback)( void *Data, (CGraphObject * | Generator *)? );
> >>
> >>/* question: is a type InputOutput (to express the fact that a node is
> >>going to be doing in-place processing) required? Need to think about
> >>whether/when this might affect sorting decisions */
> >>
> >>
> >
> >could be a hint on the Node... (CAN_DO_INPLACE)
> >
> >thoughts about sort order impact:
> >
> > notinplace2
> > / \
> >-- notinplace1 < > inplace2
> > \ /
> > inplace1
> >
> >
> >would be optimal if sorted_list = [notinplace1, notinplace2, inplace1,
> >inplace2]
> >
> >as inplace1 would destroy output buffer of notinplace1
> >
> There's "inplace replace" where a node writes its output over the top of
> its input
> buffer to reduce the cache hit, but that's not a property of the node but an
> opportunity for optimisation of the sort order so that the app can reuse
> buffers.
>
> This aspect of inplace is equivalent to your request that the library
> tell you what
> your temporary vars are. I avoided the issue in amble by letting the
> compiler
> work it out for me, but I think the library really is going to have to
> do this by
> itself. Time to dig out those old compiler volumes and remember how its
> done.
i had some thoughts on the traversal but i think i wont be catching
up with you...
at least i think i know how to fix davids sort now.
But it involves detecting all cycles in the not directed
graph... and using this information to find joins and splits of
there is one cycle in the above graph...
traversal to notinplace2 would stop at notinplace1 because
cycle context changed. function would return ptr to notinplace1.
traversal to inplace1 equivalent...
now both calls returned notinplace1 and that is where the search
shall continue....
well the description is somewhat clunky but code would follow....
how do i detect the cycles ?
this is a popular algorithm i guess... any pointers ?
is it possible to do that O(n) ?
>
> And then there's "inplace add" where a node mixes its output into a
> buffer. This *is* a node property.
>
> You could be telling the library: "generate an implied mixer for me wherever
> several outputs meet at the same input. Then optimise it away again wherever
> you can use a run_adding node".
>
> Or you could even be telling it: "I want to join connections together in
> thin
> air, not just at my inputs. These connections are implied mixer nodes but
> again, I want them optimised away wherever run_adding is available".
>
> But before tying the library too closely to these particular optimisation
> techniques its worth pausing to remember that
>
> node2
> / \
> -- node1 < > node4 --
> \ /
> node3
>
> is also an opportunity to execute node2 and node3 simultaneously :)
oh right to express this the return value should be a tree...
hmm ... (not ?)
which semantics would this have ?
>
>
> >if there was inplace3 parallel to inplace1 we would have to decide
> >which one should do the inplace processing...
> >
> >hmmm... what is better ?
> >
> >- copy output buffer and do inplace processing for both...
> >- do inplace only once
> >
> >this example suggests run_adding()
> >but if the parallells would be >1 plugin chains run_adding() would be only
> >used on
> >the end of the parallel structure...
> >
> >
> >
> >
> >>
> >>gsort_error
> >>gsort_Connect( gsort_handle Input, gsort_handle Output );
> >>/* wrong? Connections should be first class objects, not relations? */
> >>
> >>
> >
> >why ?
> >do we have metadata on a connection ?
> >
> >i believe metadata on a connection can be avoided...
> >but i am not sure...
> >
> I think connections should be first class objects:
>
> Editing ~
> Suppose you're feeding a load of inputs from a single
> output, but you want to unplug from the output and
> plug it in elsewhere. Without careful handling, your
> relations will disappear in a puff of smoke the moment
> you pull the plug! Thats what happened on early
> Nord Modular software. They had to fix it.
i dont get that... please explain more...
>
> Heirarchical Graphs ~
> Whenever a connection goes into or out of a sub-graph
> you've got 2 connections in the representation which must
> become a single connection in the flattened graph. There
> can be long chains of these if the "real" nodes are at the
> bottom of a deep heirarchy. Again, careful handling
> required if the connections are just relations
right is see this...
>
> Connection Properties ~ Expressing things such as
> (The library knows that...) Connection A is a feedback path
> (The application knows that...) Connection B is yellow
> (The sort algorithm for a non-audio application knows that...)
> Connection C is part of a clock-tree that is explicitly controlling
> the execution order of some of the nodes.
now this is of course a point...
what do you mean with a clock tree ?
>
> >>gsort_error
> >>gsort_Disconnect( gsort_handle Input, gsort_handle Output );
> >>/* wrong? Connections should be first class objects, not relations? */
> >>
> >>/* plus more functions to...
> >>~ customise the sort
> >>~ trigger the sort
> >>~ find out (about) the execution order
> >>~ navigate around the graph (if you're using gsort to hold your sole
> >>representation of the graph you may need these to find out what it says!)
> >>
> >>
> >
> >this should be able to return a tree
> >of unexpanded graphs.
> >
> Yes. You'd always be editing and navigating the unexpanded, heirarchical
> graph.
> (Though "expand" would be an available editing operation). It would only be
> expanded internally to the library during a sort, this wouldn't overwrite or
> flatten the heirarchical representation.
cool very nice thing...
i hope i can fit this into galan somehow...
this asks for another component...
>
> >>serialise the graph */
> >>
> >>
> >
> >ok... here is the polymorphy beginning...
> >application needs to use struct Node from gsort.h
> >
> >this could be also done with
> >gsort_nodes_foreach( gsort_handle graph, gsort_callback cb, boolean
> >enter_subgraphs, void *data )
> >
>
>
> >>/* ALSO THINKING HARD ABOUT...
> >>~ non-audio-rate connections eg control signals
> >>
> >>
> >
> >David stated that (at least in the XAP model) there would be no difference
> >for the sort algorithm...
> >it seems correct to me.
> >
> I'm trying to think about the most general model, at least at this
> stage. It might
> become unmanageably complex and need to be stripped back. OTOH its
> possible that a
> whole lot of complexity could suddenly disappear behind a simple abstaction.
would be nice...
what is the most general model ?
>
> >>~ higher level graph editing functions
> >>
> >>
> >
> >like automatic connecting ins and outs with same names ?
> >copy/paste ?
> >select chain ?
> >select parallel block ?
> >
> That sort of thing, yes.
>
> >>~ non-pull sort semantics eg push/dataflow, insertion order, clocked,
> >>others?
> >>
> >>
> >
> >please describe more... sounds interesting...
> >
> Not so interesting for audio. "Pull" is the right way to do it if you've got
> feedback. By analysing backwards from the outputs you detect the
> unavoidable sources of feedback and deal with them one at a time. You
> never introduce any avoidable latency at all, or at least you shouldn't.
>
> "Push" works for graphs without cycles and it practically sorts itself.
> The trouble is that it encounters any feedback at its destination, rather
> than at its source.
>
> Insertion order is a non-sort, executing everything in the order in which
> it was entered into the list of nodes. Useless unless the app or its user
> already know the exact execution order required, or if they really don't
> care.
why should this app use gsort ?
ah... for the graph... ok...
>
> Clocked is where some connections in and out of nodes are clocks that
> control when the node should be executed. There are graphical programming
> languages that do this. You can't fully sort it because the execution
> order is at least partially determined at runtime.
galan needs this...
i have event handling code in the plugins
these can be triggered by clocks...
if the library would find out these codepaths it would be ideal...
hmm... how should that be returned ?
-- torben Hohn http://galan.sourceforge.net -- The graphical Audio language
This archive was generated by hypermail 2b28 : Tue Mar 04 2003 - 16:07:04 EET