[linux-audio-dev] XAP spec - early scribbles

Simon Jenkins sjenkins at blueyonder.co.uk
Mon Mar 3 14:47:00 UTC 2003


  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".

>>==============================================================================
>> Copyright (c) Simon Jenkins 2003 licence to be decided (GPL/LGPL/dual?)
>>============================================================================*/
>>#ifndef GSORT_H_INCLUDED
>>#define GSORT_H_INCLUDED
>>
>>#ifndef ushort
>>#define ushort unsigned short
>>#endif
>>
>>#ifndef uint
>>#define uint unsigned int
>>#endif
>>
>>#ifdef __cplusplus
>>extern "C"
>>{
>>#endif
>>
>>typedef int gsort_error;
>>
>>/*================
>> QUICK INTERFACE:
>>================== 
>>The quick interface is for apps with lightweight sorting requirements. 
>>They've
>>got a flat graph stored elsewhere in whatever format they use. They want to
>>describe the graph to the gsort library and be told what order the nodes
>>should be executed in. They don't need to customise the sort algorithm too
>>much. They don't need gsort's representation of the graph to persist or be
>>modifiable or re-sortable: When they modify and resort they'll just re-init
>>the library, describe the new graph and be told the new execution order */
>>
>>#ifndef GSORT_HIDE_QUICK_INTERFACE
>>
>>gsort_error
>>gsort_Q_Initialise( void );
>>
>>gsort_error
>>gsort_Q_Cleanup( void );
>>
>>gsort_error
>>gsort_Q_AddNode( void *Node, uint NumInputs, uint NumOutputs, ushort 
>>Flags );
>>/* is void* Node ok? would int NodeID be better? */
>>
>>/* the flags privide required information...
>>   GSORT_QIF_NODE_IS_ROOT
>>
>>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 */
>>
>>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 );

>>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...

...The list would be something like an std::list<gsort::CGraphNode> 
internally,
which is why you can't have it :). But the pointers that gsort_Q_GetNextNode
is returning are your *own* pointers to your *own* data structures. If you
need a list, you can walk once down gsort_Q_GetNextNode linking your own
structures into your own list in whatever way suits you best.

>>#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.

>>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.

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.

>>#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. :)

>>gsort_handle
>>gsort_NewGraph( ushort Flags, void *Data, gsort_callback Callback );
>>
>>gsort_error
>>gsort_DeleteGraph( gsort_handle Graph );
>>
>>gsort_handle
>>gsort_NewNode( ushort Flags, void *Data, gsort_callback Callback );
>>
>>gsort_error
>>gsort_AddNode( gsort_handle Node, gsort_handle Graph );
>>
>>gsort_error
>>gsort_RemoveNode( gsort_handle Node, gsort_handle Graph );
>>
>>gsort_error
>>gsort_DeleteNode( gsort_handle Node );
>>
>>gsort_handle
>>gsort_NewInput( ushort Flags, void *Data, gsort_callback Callback );
>>
>>gsort_error
>>gsort_AddInput( gsort_handle Input, gsort_handle Node );
>>
>>gsort_error
>>gsort_RemoveInput( gsort_handle Input, gsort_handle Node );
>>
>>gsort_error
>>gsort_DeleteInput( gsort_handle Input );
>>
>>gsort_handle
>>gsort_NewOutput( ushort Flags, void *Data, gsort_callback Callback );
>>
>>gsort_error
>>gsort_AddOutput( gsort_handle Output, gsort_handle Node );
>>
>>gsort_error
>>gsort_RemoveOutput( gsort_handle Output, gsort_handle Node );
>>
>>gsort_error
>>gsort_DeleteOutput( gsort_handle Output );
>>
>>/* 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.

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 :)


>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.

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

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.

>>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.

>> 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.

>>~ 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.

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.

>>~ non-audio applications
>>    
>>
>
>what are the non-audio requirements ?
>
There aren't any requirements exactly, just the following thoughts:

Other classes of app need to do this kind of stuff: Potential "clients"
Other classes of app already do this kind of stuff: Potential solutions

>  
>
>>#endif /* !GSORT_HIDE_FULL_INTERFACE */
>>
>>#ifdef __cplusplus
>>}
>>#endif
>>
>>#endif /* GSORT_H_INCLUDED */
>>
>>
>>    
>>
>
>  
>
Simon Jenkins
(Bristol, UK)





More information about the Linux-audio-dev mailing list