Hmmm, interesting. Yes my library is similar but A LOT simpler (and more intuitive) to use / get into, I think. Please have a look into how my library works and let me know if you agree. Sent from my iPad On 05 Dec 2012, at 4:19 PM, Christian Henning <chhenning@gmail.com> wrote:

Hi all,

On Wed, Dec 5, 2012 at 9:16 AM, Hartmut Kaiser <hartmut.kaiser@gmail.com> wrote:

...

...

Is there any interest out there for a library that allows you to create fast, efficient flow-based programs with an easy-to-use object-oriented interface? (http://en.wikipedia.org/wiki/Flow-based_programming)

I've created an open-source library that does this, called "DSPatch" ( http://sourceforge.net/projects/dspatch) and would like to contribute it to the Boost Libraries.

Please let me know if this sounds like something you'd like to see in Boost.

Is this somehow similar to this library?

http://dancinghacker.com/code/dataflow/

Regards, Christian

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

I'll get cracking on some more detailed documentation on the DSPatch website ASAP. Thanks for the heads up. Sent from my iPad On 05 Dec 2012, at 5:13 PM, Klaim - Joël Lamotte <mjklaim@gmail.com> wrote:

On Wed, Dec 5, 2012 at 3:47 PM, Marcus Tomlinson < themarcustomlinson@gmail.com> wrote:

...

Hmmm, interesting. Yes my library is similar but A LOT simpler (and more intuitive) to use / get into, I think. Please have a look into how my library works and let me know if you agree.

If you could provide some code example in your documentations (like dataflow doc does) it would be easier (at least for me) to build an opinion on the differences between the two libraries.

By the way, it seems that dataflow have been reviewed already and was rejected (both for lack of reviews and apparently confusion: http://lists.boost.org/Archives/boost/2008/09/142198.php ) It would be good to analyze this before submitting your library, to avoid rejection.

This library makes me think a lot about the intel Threading Building Blocks "Flow" framework that seems to work the same for a specific concept. It could have been implemented with this kind of library.

Personally I find these library interesting but I 'm not sure there is a need in my current projects.

Joel Lamotte

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

I believe that you should be looking at SystemC's Transaction-Level Modeling (TLM) piece for a comparison of a higher level abstraction modeling system. It should be noted that SystemC is cross-platform. In a previous life, I served on the SystemC TLM committee. When teaching SystemC, we used both airport luggage handling and shipping company package handling systems as models to teach the techniques of creating various system abstractions. For a conference I did a session on how to connect the system simulations to a real-time external system (simulator to frame buffer) as a demonstration of how the simulations could interact with real-world bits. Charles Wilson Software Development Senior Engineer Dell | Product Group

-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost- bounces@lists.boost.org] On Behalf Of Marcus Tomlinson Sent: Wednesday, December 05, 2012 11:27 AM To: boost@lists.boost.org Subject: Re: [boost] Flow-based programming library for Boost?

Hmm, well SystemC is clearly very powerful and can easily achieve the same results, but my particular domain is more the higher-level, cross platform, easy-to-use, PC applications. OMNet++ is closer to what I have, but my aim is total abstraction from the particular application. DSPatch allows you to build flow-based programs for any application you can think of.

I looked at many implantations of this nature while developing DSPatch and found that there was almost always a steep learning curve to using them. Not only do I want to make dataflow / flow-based programming easier for developers, I want to make it more accessable. Hopefully if I can get the support I need to get this project on Boost, it'll be widely accessible and helpful to people like me who are/were looking for something like this. This kind of programming paradigm is so useful in so many applications, it really shouldn't be as niche a topic as it is. Perhaps it's always been portrayed as too complex?

Sent from my iPad

On 05 Dec 2012, at 5:36 PM, Vicente Botet <vicente.botet@wanadoo.fr> wrote:

...

Marcus Tomlinson wrote

...

Is there any interest out there for a library that allows you to create fast, efficient flow-based programs with an easy-to-use object-oriented interface? (http://en.wikipedia.org/wiki/Flow-based_programming)

I've created an open-source library that does this, called "DSPatch" ( http://sourceforge.net/projects/dspatch) and would like to contribute it to the Boost Libraries.

Please let me know if this sounds like something you'd like to see in Boost.

Hi,

how your library compare to SystemC or OMNet++?

Vicente

-- View this message in context: http://boost.2283326.n4.nabble.com/Flow-based-programming-library- for- Boost-tp4639450p4639477.html Sent from the Boost - Dev mailing list archive at Nabble.com.

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On 12/6/2012 7:37 AM, Marcus Tomlinson wrote:

This is a very powerful and impressive modeling system, but its very intimidating! Don't get me wrong, this is obviously my opinion. I believe this is why so few people use (or are even aware of) flow-based programming in their projects (hobbyists + companies).

(Your posting format is difficult to respond to as it doesn't wrap properly and you should avoid top posting) My experience has been that FBP has been used extensively and for quite some time in automotive, aerospace and general controls industries via Matlab's Simulink which allows graphical design, editing, simulation and testing, with subsequent code generation to low level (C, C++, ADA, ...). Most of these users are Mechanical/Electrical engineers who are not particularly adept with modern C++(IMHO of course). Jeff

One of the main issues we ran into teaching EE's how to use SystemC was that they didn't have a solid background in C++ (most were C folk). As a result, we spent a day on C++, three on basic SystemC and a day on transaction level modeling. It's important to note that SystemC handles multiple levels of abstraction within the same simulation. You can simply work at the very abstract level of messages being sent from system to system if you wish. You can also create simulations with specific elements having higher levels of specificity. For some (chip folk) the actual signals on the wire are simulated. In practice, you would only work with the high-resolution model elements to debug them. Once you were happy, you would retain only the abstract version with appropriate timing information. Charles Wilson Senior Software Development Engineer Dell | Enterprise Solutions Group

-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost- bounces@lists.boost.org] On Behalf Of Jeff Flinn Sent: Thursday, December 06, 2012 12:12 PM To: boost@lists.boost.org Subject: Re: [boost] Flow-based programming library for Boost?

...

This is a very powerful and impressive modeling system, but its very intimidating! Don't get me wrong, this is obviously my opinion. I believe this is why so few people use (or are even aware of) flow-based programming in

On 12/6/2012 7:37 AM, Marcus Tomlinson wrote: their projects (hobbyists + companies).

(Your posting format is difficult to respond to as it doesn't wrap properly and you should avoid top posting)

My experience has been that FBP has been used extensively and for quite some time in automotive, aerospace and general controls industries via Matlab's Simulink which allows graphical design, editing, simulation and testing, with subsequent code generation to low level (C, C++, ADA, ...).

Most of these users are Mechanical/Electrical engineers who are not particularly adept with modern C++(IMHO of course).

Jeff

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

To she'd some light on what applications can be build using such a library, it may be worth providing a little history on how it came to be. I originally designed DSPatch to be a re-usable, modular process-chain engine I could use when writing audio applications (much like the patching engines found in DAW programs such as Pro Tools, FL Studio, etc.), but it eventually developed into a generic FBP framework, not limited to any particular signal / data type. The primary aim of this library is to allow fast, fluent, RUN-TIME circuit configuration (wiring, thread count adjustment, control, etc.), all while maintaining a steady flow of data through the system. This is very important when playing audio say, in a live setting (e.g. DJing), where adjusting the circuit (e.g. adding new components, or rewiring) should not effect the steady flow of audio data to the sound card. Audio is not the only application DSPatch is useful in though. I've already seen DSPatch used to model control circuits for instruments and controls on simulators. The point is that DSPatch is a generic framework for any process-chain oriented application, supporting complex configurations such as feedback loops, branch synchronization, integrated circuits and value type-adaptive IO. This is what I mean by: "total abstraction from the particular application" -which differentiates this library from a library like OMNet++. I am quite confident that DSPatch could have a very gentle learning curve in comparison to the others, but due to the scarcity in documentation I'm afraid I may be hindering the project in that respect currently. I will definitely be fleshing out the documentation ASAP! I hope this helps at all? On 05 Dec 2012, at 11:34 PM, "Vicente J. Botet Escriba" <vicente.botet@wanadoo.fr> wrote:

Le 05/12/12 18:26, Marcus Tomlinson a écrit :

...

Hmm, well SystemC is clearly very powerful and can easily achieve the same results, but my particular domain is more the higher-level, cross platform, easy-to-use, PC applications. How is your context different? Could you describe the kind of applications using your library? OMNet++ is closer to what I have, but my aim is total abstraction from the particular application. What do you mean? DSPatch allows you to build flow-based programs for any application you can think of. Could you elaborate on this?

I looked at many implantations of this nature while developing DSPatch and found that there was almost always a steep learning curve to using them. This is the case for any complete framework. Not only do I want to make dataflow / flow-based programming easier for developers, I want to make it more accessable. How do you think do you achieve that compared to them?

...

Hopefully if I can get the support I need to get this project on Boost, it'll be widely accessible and helpful to people like me who are/were looking for something like this. This kind of programming paradigm is so useful in so many applications, it really shouldn't be as niche a topic as it is. Perhaps it's always been portrayed as too complex? Note that SystemC and OMNet++ have a quite different engine. To which you library is closer and how it is different?

Best, Vicente

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Thomas, thanks for the support :) I do understand where Dave is coming from though, the overhead of constructing the circuit (particularly one that is static throughout the lifetime of the application) on startup can be avoided with compile-time wiring. My intention was to create a library that allows for building both static and/or dynamic circuits, hence it was designed with particular focus on run-time. Your HPX work is very interesting! I'm curious, what are your thoughts on my approach to parallel execution in DSPatch (explained in my previous post)? On 06 Dec 2012, at 9:24 AM, Thomas Heller <thom.heller@gmail.com> wrote:

On 12/05/2012 10:34 PM, Vicente J. Botet Escriba wrote:

...

Le 05/12/12 18:26, Marcus Tomlinson a écrit :

...

Hmm, well SystemC is clearly very powerful and can easily achieve the same results, but my particular domain is more the higher-level, cross platform, easy-to-use, PC applications. How is your context different? Could you describe the kind of applications using your library? OMNet++ is closer to what I have, but my aim is total abstraction from the particular application. What do you mean? DSPatch allows you to build flow-based programs for any application you can think of. Could you elaborate on this? I've been working with Dataflows for past couple of months and I agree. Dataflow or Flow-Based programming is a very nifty paradigm to express programs. Especially when it comes to parallel execution. I am not working in a signal processing background where this technique is well known. I investigated this programming paradigm in the past for one specific linear algebra application (Results can be seen here: http://stellar.cct.lsu.edu/pubs/isc2012.pdf and here: http://www10.informatik.uni-erlangen.de/Publications/Theses/2012/Heller_MA12...). We constructed the dataflow tree completely dynamicly in an almost natural way (modulo the syntatic differences). So i have to disagree with Dave Abrahams that purely compile-time based dataflow "wiring" is the most efficient way.

...

...

I looked at many implantations of this nature while developing DSPatch and found that there was almost always a steep learning curve to using them.

This is the case for any complete framework.

...

Not only do I want to make dataflow / flow-based programming easier for developers, I want to make it more accessable. How do you think do you achieve that compared to them?

...

Hopefully if I can get the support I need to get this project on Boost, it'll be widely accessible and helpful to people like me who are/were looking for something like this. This kind of programming paradigm is so useful in so many applications, it really shouldn't be as niche a topic as it is. Perhaps it's always been portrayed as too complex? Note that SystemC and OMNet++ have a quite different engine. To which you library is closer and how it is different?

Best, Vicente

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

This library was particularly designed to allow wiring to be done at run-time but I will look into compile time-wiring. If I could just quickly do some motivation though: Building large computations out of smaller ones will not effect performance (in a run-time sense) at all due to the way I've designed the multithreading: The multi-threading aspect of DSPatch was designed to allow the user to specify the number of threads in which he/she required the circuit to process rather than the thread count growing as the system did. So for example, an application running on a quad core system could be limited to 4 threads in order to allow each core to handle just one thread. This essentially how it works: The circuit runs through its array of components, calling each components process method in a single thread loop. As each component is done processing it hands over control to the next waiting circuit thread. Therefore, if you had 5 components in a process chain, and 5 circuit threads, at any one point in time you could have one thread per component processing in parallel. With this in place, you now also have the option to select 0 circuit threads. In this state, the circuit's Tick() and Reset() methods can be called in a while loop, for example, in the main application thread. I've added a null thread class that just implements stub methods so DSPatch can compile on platforms with no native thread support. What I've just described are circuit threads (threads that traverse the whole circuit). Another thread type is the component thread. The component thread simply ticks a single component over and over. As the circuit class inherits from component, we use it's component thread to tick the circuit automatically whilst using the main application thread for control. I hope this clarifies my definition of "efficient". On 06 Dec 2012, at 4:43, Dave Abrahams <dave@boostpro.com> wrote:

on Wed Dec 05 2012, Marcus Tomlinson <themarcustomlinson-AT-gmail.com> wrote:

...

Is there any interest out there for a library that allows you to create fast, efficient flow-based programs with an easy-to-use object-oriented interface? (http://en.wikipedia.org/wiki/Flow-based_programming)

I've created an open-source library that does this, called "DSPatch" ( http://sourceforge.net/projects/dspatch) and would like to contribute it to the Boost Libraries.

Please let me know if this sounds like something you'd like to see in Boost.

If you want such a library to be truly efficient, you should be able to wire together the dataflows at compile-time and not pay any overhead for composing large computations out of smaller ones. The accumulators library uses something like a dataflow model, with the "wiring" done completely at compile-time.

-- Dave Abrahams BoostPro Computing Software Development Training http://www.boostpro.com Clang/LLVM/EDG Compilers C++ Boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Dave Abrahams wrote:

on Wed Dec 05 2012, Marcus Tomlinson <themarcustomlinson-AT-gmail.com> wrote:

...

Is there any interest out there for a library that allows you to create fast, efficient flow-based programs with an easy-to-use object-oriented interface? (http://en.wikipedia.org/wiki/Flow-based_programming)

I've created an open-source library that does this, called "DSPatch" ( http://sourceforge.net/projects/dspatch) and would like to contribute it to the Boost Libraries.

Please let me know if this sounds like something you'd like to see in Boost.

If you want such a library to be truly efficient, you should be able to wire together the dataflows at compile-time and not pay any overhead for composing large computations out of smaller ones. The accumulators library uses something like a dataflow model, with the "wiring" done completely at compile-time.

Note this is embodied in the boost.range library. Robert Ramey

Dave Abrahams wrote:

If you want such a library to be truly efficient, you should be able to wire together the dataflows at compile-time and not pay any overhead for composing large computations out of smaller ones. The accumulators library uses something like a dataflow model, with the "wiring" done completely at compile-time.

Because of your remark I studied the Accumulators library, and I must say it's very elegant indeed. Dependencies between computations are resolved at compile-time (wow!) so they don't add unnecessary overhead at run-time and everything will be executed in the most efficient order. However, note the word "order". Boost.Accumulators was clearly designed under the assumption of single-threaded operation and tightly interdependent computations. I believe it might very well be the best possible approach under those assumptions, but when the assumptions don't apply other considerations may call for a different solution. "Dataflow" is a very general term, but the people who advertise with that word typically mean something more specific, i.e. lock-free multithreading with message passing. The underlying assumptions are more or less opposite to the assumptions in Boost.Accumulators: computations can run concurrently without waiting for each other, as long as they have input available and they can dispose of their output somewhere. If computations can take place /at the same time/ it does not really matter whether connections are made at compile-time or run- time; /waiting/ is eliminated altogether so the building of connections at run-time adds only constant overhead. That constant overhead is worth it if accepting it helps you to avoid other problems. Note that the "wires" built by Accumulators at compile-time are /logical/ connections between /types/ that represent operations. Message passing "wires" are /physical/ connections between /threads/. Instantiating the latter kind of connection at compile-time seems very hard, if not impossible. Actually I think the Accumulators framework and lock-free message passing are completely orthogonal. One could use a "dataflow" library to connect threads at run-time while composing computations for the individual threads at compile-time with Boost.Accumulators, and get the best of both worlds. I hope I'm making sense. Please let me know what you think. -Julian

Dave, I'm a bit confused after reading your post. In part I think we're not actually disagreeing about the relative merits of static and dynamic wiring and the possibility to combine them. In part I'm puzzled by what seems to me to be your bolder claim: the possibility of statically wired asynchronous concurrent message passing. In part I wonder whether my implicit assumptions about inter-thread message passing might have been too implicit. I'll try to touch upon each of these issues below, as coherently as I can manage. Dave Abrahams wrote:

on Wed Dec 12 2012, Julian Gonggrijp wrote:

...

[...] If computations can take place /at the same time/ it does not really matter whether connections are made at compile-time or run- time; /waiting/ is eliminated altogether so the building of connections at run-time adds only constant overhead.

It's not just the cost of *building* of dynamic connections but the cost of traversing them.

I was assuming dynamic connections of the following type: a fixed-size continuous (circular) buffer in memory, a producer thread that is continuously appending data to the end of the buffer, and a consumer thread that is continuously removing data from the front of the buffer. This can be done lock-free and wait-free, but you're right that there's still some cost involved because of pointer arithmetic and the occasional cache miss. Still I don't see how you could avoid this cost without giving up on the asynchronous behaviour altogether. I'll return to that question below.

Of course if your sub-computations happen to have large granularity, these costs may be swamped by others,

Here I believe we're not disagreeing at all. You seem to be implying that for very tightly interdependent computations static, single- threaded connections are most efficient, while for more coarse-grained computations concurrency is the best solution. I already wanted to make this point in my previous post.

but a truly flexible system would allow you to tune the approach to the problem.

The accumulators library was first used in a massively-parallel context with each process running thousands or millions of accumulator sets. Obviously it really depends on your problem domain but that might be a more efficient way to break down the parallel processing. Of course a truly flexible system would (as Jeremiah suggested his design does) allow you to combine static and dynamic wiring (sort of like Xpressive does).

...

That constant overhead is worth it if accepting it helps you to avoid other problems. Note that the "wires" built by Accumulators at compile-time are /logical/ connections between /types/ that represent operations. Message passing "wires" are /physical/ connections between /threads/.

The accumulators library's wires are just as "physical" as any others, they're just encoded in the instruction stream instead of in mutable data. I don't see the relevance of your emphasis on the word "types."

...

Instantiating the latter kind of connection at compile-time seems very hard, if not impossible.

No, you could easily use threads with a system like the accumulators framework.

Given the context of my assumptions and the text that you're replying to, in all of the above you seem to be suggesting that the asynchronous, buffered message passing that I described could also be implemented statically but still concurrently and asynchronously, in such a way that the mutable buffer is replaced by something in the instruction stream. I find it very hard to imagine how this could be done, because at compile time it's impossible to predict how the instruction streams of both threads will be aligned during run-time. If something like that could actually be done, *please* enlighten me. :-) Alternatively I could take your remark "you could easily use threads with a system like the accumulators framework" in isolation, and then I'd interpret it completely differently: "you can build coarse-grained single-threaded computations from fine-grained ones using Accumulators, and then connect multiple of those coarse-grained computations asynchronously using dynamic buffers". As I said I agree with that, but given the context I'm unsure whether that is what you meant.

...

Actually I think the Accumulators framework and lock-free message passing are completely orthogonal.

Exactly. It seems as though you're now contradicting yourself.

I meant to say that the Accumulators framework and the (buffered asynchronous) lock-free message passing serve different needs and that these needs may occur independently, so there can be programs with both needs, hence calling for application of both techniques in parallel. As far as I'm concerned this is in line with everything I've said before. If this is your point, I must conclude that all of our discussion has been one big misunderstanding, because it was my point as well.

...

One could use a "dataflow" library to connect threads at run-time while composing computations for the individual threads at compile-time with Boost.Accumulators, and get the best of both worlds.

I hope I'm making sense. Please let me know what you think.

I think you eventually made sense :-)

Assuming that our discussion was based on misunderstanding and that we're actually agreeing, one thing is still bothering me. You appear to believe that the same library should provide for both ways of composing computations, i.e. the static single-threaded one (like Accumulators) and the dynamic asynchronous one. I doubt that would be the right thing to do, because the modes of composition are not related in their underlying logic (contrary to the static and dynamic expressions in Xpressive) and because they pose very different requirements on the subcomputations that are to be composed. In the dynamic multithreaded mode of composition the producer and the consumer can be as unrelated as any function that writes to a std::vector and any other function that reads from it. As the Accumulators mode of composition involves much tighter coupling between the operations, they need to have much more in common, e.g. features and dependencies in Accumulators. -Julian

Thanks for clarifying, Dave. I'm glad to know that we're mostly on the same page. Dave Abrahams wrote:

on Sat Dec 15 2012, Julian Gonggrijp wrote:

...

[...] In part I'm puzzled by what seems to me to be your bolder claim: the possibility of statically wired asynchronous concurrent message passing.

I don't see why it shouldn't be possible.

In retrospect I do see why you didn't see it. Note the word "asynchronous". I'll get back to this point below.

...

[...] I believe we're not disagreeing at all. You seem to be implying that for very tightly interdependent computations static, single- threaded connections are most efficient, while for more coarse-grained computations concurrency is the best solution.

s/is/might be/

True.

In the degenerate case where the dependency graph is strictly linear, concurrency might be completely wasted unless you're able to take advantage of pipelining.

Isn't execution of linearly dependent operations always a pipeline? Assuming that, isn't every vertex in a dependency graph a pipeline by itself? Assuming that, isn't pipelining the entire purpose of any form of computational composition?

And there's still a question of how that concurrency is carved up. If you have a complicated dependency graph and you can run several of these flow graphs in parallel, but each in a single thread (as described below), that seems likely to induce less synchronization than if you try to run the nodes of a single flow graph in parallel. Of course whether that decomposition can work depends on your problem.

You have a point. But: suppose that you have two operations, A and B, and you want to output B(A(item)) for each item out of a collection of inputs. The alternatives that you're suggesting are (1) have operation A executed by one thread and operation B by the other, then pipeline these threads; (2) have two (or more) identical threads, each taking an equal share of the inputs and executing B o A. In scenario (2) the threads don't need to communicate, so you're right that it will involve less waiting if you generalize this to more complex computations, but now we're not taking into account that (1) is only a member out of a much larger class of solutions to the same problem. If we realistically assume that one operation takes longer than the other, let's say that B takes three times the amount of time of A, then the following network will prove superior to (1) and (2) on the condition that you have a CPU with at least four hardware threads: (1b) We use four execution threads (or any multiple). The first takes the inputs, applies operation A on them and divides the intermediate results between the other three threads. The other three threads apply operation B, each to their own share of the intermediate results. This also generalizes to more complex dependency graphs. In fact, the more operations are involved, the more likely you are to find significantly different execution times.

<schnipp>

:-)

...

[...] I find it very hard to imagine how this could be done, because at compile time it's impossible to predict how the instruction streams of both threads will be aligned during run-time. If something like that could actually be done, *please* enlighten me. :-)

Well, I have to admit, that sounds difficult. But you don't necessarily need more than a single-value buffer for each sub-computation, do you?

Indeed you don't, in fact I think you almost never do. Rather, the multiple-value buffer is mostly an optimization that enables asynchronous operation. The sender can push another value to the queue even if the receiver didn't pop the previous one yet, and vice versa. On top of that, every thread only needs to wait for its own preemptions, not for those of the other threads (unless preemption takes longer than filling/emptying the buffer). The problem with a single-value buffer, whether static or dynamic, is really that it can't be asynchronous; production and consumption of a message must always take turns. I believe this largely defeats the purpose of concurrency. Regardless, if you are to implement concurrent message passing with a static single-value buffer, you still have the problem that you'll somehow have to align the instruction streams of both threads. Now this seems less remote to me than the same thing with a multiple-value buffer, but I imagine that the act of aligning the instruction streams would add considerable overhead at run-time. After all, wouldn't that just be a barrier?

...

[...] You appear to believe that the same library should provide for both ways of composing computations, i.e. the static single-threaded one (like Accumulators) and the dynamic asynchronous one. I doubt that would be the right thing to do, because the modes of composition are not related in their underlying logic (contrary to the static and dynamic expressions in Xpressive) and because they pose very different requirements on the subcomputations that are to be composed.

You may be right.

...

[...] As the Accumulators mode of composition involves much tighter coupling between the operations, they need to have much more in common, e.g. features and dependencies in Accumulators.

Hmm, I don't think I buy that last part of the argument, but I also don't think we're very far apart now.

It might not be important enough to elaborate on. I agree that we're probably not far apart. -Julian

on Sun Dec 16 2012, Julian Gonggrijp <j.gonggrijp-AT-gmail.com> wrote:

...

In the degenerate case where the dependency graph is strictly linear, concurrency might be completely wasted unless you're able to take advantage of pipelining.

Isn't execution of linearly dependent operations always a pipeline?

Yes, but pipelining doesn't help if the input period exceeds the pipeline latency.

Assuming that, isn't every vertex in a dependency graph a pipeline by itself?

I suppose it's a degenerate pipeline, but I don't know what you're getting at.

Assuming that, isn't pipelining the entire purpose of any form of computational composition?

IMO the purpose of computational composition is to manage complexity through re-use.

...

And there's still a question of how that concurrency is carved up. If you have a complicated dependency graph and you can run several of these flow graphs in parallel, but each in a single thread (as described below), that seems likely to induce less synchronization than if you try to run the nodes of a single flow graph in parallel. Of course whether that decomposition can work depends on your problem.

You have a point. But: suppose that you have two operations, A and B, and you want to output B(A(item)) for each item out of a collection of inputs. The alternatives that you're suggesting are

(1) have operation A executed by one thread and operation B by the other, then pipeline these threads; (2) have two (or more) identical threads, each taking an equal share of the inputs and executing B o A.

In scenario (2) the threads don't need to communicate, so you're right that it will involve less waiting if you generalize this to more complex computations, but now we're not taking into account that (1) is only a member out of a much larger class of solutions to the same problem. If we realistically assume that one operation takes longer than the other, let's say that B takes three times the amount of time of A, then the following network will prove superior to (1) and (2) on the condition that you have a CPU with at least four hardware threads:

(1b) We use four execution threads (or any multiple). The first takes the inputs, applies operation A on them and divides the intermediate results between the other three threads. The other three threads apply operation B, each to their own share of the intermediate results.

This also generalizes to more complex dependency graphs. In fact, the more operations are involved, the more likely you are to find significantly different execution times.

Yes. -- Dave Abrahams BoostPro Computing Software Development Training http://www.boostpro.com Clang/LLVM/EDG Compilers C++ Boost

...

Is there any interest out there for a library that allows you to create fast, efficient flow-based programs with an easy-to-use object-oriented interface? (http://en.wikipedia.org/wiki/Flow-based_programming)

I've created an open-source library that does this, called "DSPatch" ( http://sourceforge.net/projects/dspatch) and would like to contribute it to the Boost Libraries.

Please let me know if this sounds like something you'd like to see in Boost.

If you want such a library to be truly efficient, you should be able to wire together the dataflows at compile-time and not pay any overhead for composing large computations out of smaller ones. The accumulators library uses something like a dataflow model, with the "wiring" done completely at compile-time.

That's definitely one use case. In our experience it is much more important to compose the dataflow graph at runtime, though. Mainly, most of the time we don't know the shape of the dataflow graph to be constructed at compile time yet. Regards Hartmut --------------- http://boost-spirit.com http://stellar.cct.lsu.edu

On 12/13/2012 9:30 AM, Jeff Flinn wrote:

On 12/13/2012 8:44 AM, Hartmut Kaiser wrote:

...

...

...

Is there any interest out there for a library that allows you to create fast, efficient flow-based programs with an easy-to-use object-oriented interface? (http://en.wikipedia.org/wiki/Flow-based_programming)

I've created an open-source library that does this, called "DSPatch" ( http://sourceforge.net/projects/dspatch) and would like to contribute it to the Boost Libraries.

Please let me know if this sounds like something you'd like to see in Boost.

If you want such a library to be truly efficient, you should be able to wire together the dataflows at compile-time and not pay any overhead for composing large computations out of smaller ones. The accumulators library uses something like a dataflow model, with the "wiring" done completely at compile-time.

That's definitely one use case. In our experience it is much more important to compose the dataflow graph at runtime, though. Mainly, most of the time we don't know the shape of the dataflow graph to be constructed at compile time yet.

Perhaps being able to compose a mix run-time and compile-time components all Eric Niebler's Xpressive.

uggh, that should read: Perhaps being able to compose a mix of run-time and compile-time components ala Eric Niebler's Xpressive. Jeff

I will have some time to contribute, Please let me know If you want some coding help. Regards --Dev On Sat, Dec 15, 2012 at 6:52 AM, Topher Cooper <topher@topherc.net> wrote:

I've only had time to read over the documentation quickly, but I found the discussion interesting, and I thought I would throw out some thoughts, with the caveat that I might have missed something.

1) /Simplicity is a simplistic goal/. Generally good design means that doing simple things is simple and doing more complex things is more complex proportionately (and no more than proportionately) to the degree of additional complexity. This may mean that there are many "components" (methods, parameters, libraries, classes, or whatever) and options but that at any given time most can be ignored. Part of the design process is to be clear what can be ignored when, and part of the implementation is documentation (whatever form that that takes) that makes it easy to focus on what one needs for a task and to be barely aware that there is more available (this, by the way, is my one complaint about the use of "literate programming" mechanisms -- there is a tendency to over-rely on them with a resulting mass of undifferentiated information).

One of the tools for accomplishing this are careful selection early on of an explicit set of use cases. Careful use of defaults, especially of defaults that interact intelligently with explicits (this can lead to a system that from a usage viewpoint that "just does what is expected" but which can be a bear to implement and formally describe, with lots of "unlesses" and "with this combination of factors this, and with this combination that"), as well as things like policies and pre-specified frameworks that specify lots of things all at once.

2) /Single vs multiple inputs?/ There seems to be a natural way to handle a need for multiple inputs -- one interposes a component with an expandable set of individual inputs and a single output.

That's a good, well integrated /mechanism/ but a weak /interface/. The reason is that the combining component is conceptually very closely tied to the input. I would suggest that a library of common ways of handling multiple inputs ("tuplers", "ands", "ors", "averagers", etc. as well as the current "only one allowed"), and that these be "declared" (or, given the run-time reconfigurability "redeclared") along with the input itself. Any wire addressed to the input actually gets attached to the combiner, and redeclaration would automatically pass the existing inputs to the new combiner.

Of course, in line with my previous comment, there should be a default, as well as a way to declare the default over some sense of scope.

3) /Typed inputs, outputs -- and thus wires and signals/? Flexibility and performance may be primary in your use-cases, but that doesn't mean reliability has zero value. I really should not be able to attach an RGB wire to an input meant to process an aerial heading just because they both use a 3-tuple of numbers for representation. Its conceivable that one could generate tons of nonsense data without detection this way. Typing won't protect you, of course, from the result of attaching an RGB wire to the wrong RGB input, but decades of experience with strong typing has shown that it can radically cut down on the frequency of errors. (Note that this is not an argument against C++ template style duck typing generally: its compile time nature makes for a different circumstances, especially in situations where there is less of a tendency to use general purpose types with more specific operations -- e.g., R(), G() and B() rather than first, second, third or get<1>(), get<2>() and get<3>() -- than I suspect is the case with many uses of this package).

Note that this is a run time type -- whether or not it is implemented via run-time type labels or as a reflection (no pun intended) of the C++ type system is not the issue. Performance wouldn't be an issue since the checking would occur when a wire is attached and wouldn't have any overhead during "ticks". If it is purely run-time, however, there wouldn't be any obvious way to enforce that the type placed on an output has any relation to the type label. On the other hand, dynamically modifying the output of a component would not be possible. Maybe a mix would be the right thing, though I'm not sure exactly how that would be done.

Of course, I would think that a "not type specified" type, providing the present behavior, would be appropriate, and is a reasonable default. However, specifying a different default, within some scope, would be valuable as well -- if you are simulating logic circuits then either 2-state or 3-state logic signals would be a good default, even if parts of the system, dealing with edge-triggered circuitry or A/D/A, or analog sensors, need other types.

4) /Compile-time vs run-time configuration? /(a.k.a., declaration vs execution?) There seems to be the potential for large gains in fixed compile-time configuration and in some cases, in reliability. On the other hand, its clear that the primary intended use cases require more flexibility. It would seem that, once again, a hybrid system would useful. What occurs to me is that one should be able to create components by combining "primitive" components (classes derived from DspComponent) at compile time using the same concepts (wires, inputs, outputs) as the run-time system. Prototypes could be turned into fixed sets of components when fully understood and debugged, and also compiled units could be replaced by the same set of primitive components wired together dynamically (in fact, it might be possible for the class representing the hard-wired version to automatically include a static method that could be called to create a soft wired version of itself, an instance method instead of or in addition to the static one would allow compiled components to be hot-swapped out for a run-time configurable version of itself).

That's a lot of work, of course, and I'm certainly not in a position to do it.

5) /Object-Oriented vs Generic Interface?/ -- I'm not going to take sides here, but it seems unlikely that the small overhead of run-time-bound calls would make much of a difference except in the limited case of a large network of simple components (e.g., a large, low-level, logic gate system) with high sequentiality and very little I/O or logging. In any other circumstances, I would say that the time for the indirection would be completely swamped by the component internals, by other kinds of system overhead and by I/O. That doesn't mean that generic programming isn't preferable but only that the performance overhead of virtual calls isn't an argument for it unless one can show that the non-monitored, large logic-gate type system requiring high-performance is an important design case.

Just some thoughts, hope someone finds them useful or at least interesting.

Topher

______________________________**_________________ Unsubscribe & other changes: http://lists.boost.org/** mailman/listinfo.cgi/boost<http://lists.boost.org/mailman/listinfo.cgi/boost>

Topher Cooper wrote:

5) /Object-Oriented vs Generic Interface?/ -- I'm not going to take sides here, but it seems unlikely that the small overhead of run-time-bound calls would make much of a difference except in the limited case of a large network of simple components (e.g., a large, low-level, logic gate system) with high sequentiality and very little I/O or logging. In any other circumstances, I would say that the time for the indirection would be completely swamped by the component internals, by other kinds of system overhead and by I/O. That doesn't mean that generic programming isn't preferable but only that the performance overhead of virtual calls isn't an argument for it unless one can show that the non-monitored, large logic-gate type system requiring high-performance is an important design case.

Thank you for your considerate remarks, Topher. I've isolated the part above because I thought it needed an immediate response, but rest assured that I found the rest of your email valuable as well. My response: I think you're right and I stand corrected. Admitting this also makes me more consistent with my recent reply to Dave Abrahams [1]. I apologise, especially to Marcus Tomlinson, for making the presumed overhead of OOD seem more important than it is. -Julian ______ [1] http://lists.boost.org/Archives/boost/2012/12/199196.php

Marcus Tomlinson wrote:

As per some very good observations from guys on the mailing (in particular: Julian and Klaim), I've made a few updates to the DSPatch library that I hope are some steps in the right direction:

I definitely agree that your updates seem to be steps in the right direction. I wasn't able to see the interface simplifications in DspComponent and DspCircuit from the documentation, but after Topher's comments I assume this is due to limitations in the documentation.

There are still some issues on the backlog I haven't got to yet, such as: upgrading the DspWire struct to a smarter class, possibly introducing safe pointers, improving documentation, and providing a mechanism for multiple signal transfer. I'll be tackling these next.

I look forward to your future updates. Please keep up the enthousiasm. -Julian PS (very much off-topic): I happen to be a guy, but some women are called Julian too. Just saying. :-)

On 12/18/2012 1:23 AM, Marcus Tomlinson wrote:

Hi Topher, thanks for the post :)

...

1) /Simplicity is a simplistic goal/. Generally good design means that doing simple things is simple and doing more complex things is more complex proportionately (and no more than proportionately) to the degree of additional complexity. This may mean that there are many "components" (methods, parameters, libraries, classes, or whatever) and options but that at any given time most can be ignored. Part of the design process is to be clear what can be ignored when, and part of the implementation is documentation (whatever form that that takes) that makes it easy to focus on what one needs for a task and to be barely aware that there is more available.

I hope that I am at least close to achieving this. DSPatch was designed with just this in mind. Even the documentation was structured as to describe only the bare essentials to using DSPatch up front, while providing the possibility for additional functionality based on those essentials.

That's a start, but minimal documentation for the remainder, a lack of a good way to understand why/when you would want each additional piece, means that there is a sudden, very sharp, upward kink in the problem-complexity vs solution-complexity graph. As it stands, it looks like too much internals (documented only by code) to understand why you would want to use this or that. Generally they seem to be justified by optimization concerns rather than increase in functionality. That requires an understanding of what and why the system needs some help optimizing.

...

One of the tools for accomplishing this are careful selection early on of an explicit set of use cases. Careful use of defaults, especially of defaults that interact intelligently with explicits (this can lead to a system that from a usage viewpoint that "just does what is expected" but which can be a bear to implement and formally describe, with lots of "unlesses" and "with this combination of factors this, and with this combination that"), as well as things like policies and pre-specified frameworks that specify lots of things all at once.

With a framework that is (or at least tries to be) generic, it is hard to describe or list use cases. There are so many uses for DSPatch that I am not aware of. I understand what you're saying though, and once again, I hope that with my tutorials and example application I am achieving this. If not, please let me know what's lacking.

I'm talking about use cases for design. Its quite likely that many of these would never be implemented. Also, examples and tests are generally much simpler systems than real ones -- that is required to make them quickly understandable. You certainly didn't spend a lot of thought on how to make generating two random Booleans and anding them together easy and efficient. Inevitably, any designer is going to have some thoughts about how even a generic package is going to be used, which essentially amount to vague, unwritten use cases. That means there are unexaminable assumptions. Creating explicit use cases -- representing different patterns of usage that are deemed important -- makes the assumptions more obvious, and may also suggest other use cases. A use case is not necessary a description of an application, though that is frequently useful in pinning it down. It might be (a somewhat more elaborate version of) something like "A large number of simple nodes each with relatively few inputs and outputs, simple signals, only about 20% of the nodes activated on any given cycle, with linear dependency chains that, however, vary radically from cycle to cycle." That might, for example, describe a controller of some sort specified at the logic-gate level. That is generic, but looking at what could be done to optimize such cases, and trying to understand how those optimizations might interact with other use cases, as well as what is needed to make any such application easier to implement.

...

I really should not be able to attach an RGB wire to an input meant to process an aerial heading just because they both use a 3-tuple of numbers for representation. Its conceivable that one could generate tons of nonsense data without detection this way.

I guess I could argue that in a real-world situation, connecting 2 terminals that source and sink data packets of the same structure (header, CRC etc.), regardless of the payload (nonsense to the receiver or not) these packets would be accepted. However...

Now that shows the effects of an implicit (not necessarily wrong) set of use cases. You feel that typical "real world" uses would involve complex, specialized, structured objects as signals, such as streaming audio packets straight off a network. My intuition (obviously not backed up by a formal use case analysis) is that a significant sub-group of usages would use much simpler, generic data types -- strings, numbers, booleans, enums, tuples, vectors (for example, representing labeled messages), etc.These might repesent control signals, power levels, "facts" etc. There are also more complex generic kinds of data, for example statistical distributions. The distributions are complex entities but they might represent multiple different kinds of quantities within the same application (fluctuating temperatures, pressures, fluid flow rates, for example). Even a system which primarily uses more complex signal types, could use these more generic kinds of signals as well, representing things like system clock ticks (I mean that as a domain quantity, rather than the network cycles), error counts, activations, etc. Tell me -- how often in your conventional programming do you pass numbers, bools, strings etc to procedures rather than encapsulating each in a specific class with unique access protocols that represent the intended use, Age, Name, IdentificationNumber, ResourceAvailable, etc.? Actually, just looking at your interface gives me the answer -- as often as most of us. Thinking about it, I think my sense of this being a likely pattern of usage is based on a sense that an important use case (or set of use cases) would be for discrete simulations. Its not the most likely thing I would use it for, but it seems like a natural. After all, Object Oriented Programming was originally invented for this purpose, and this matches almost precisely how such systems are conceptualized.

On Sun, Dec 9, 2012 at 12:59 AM, Marcus Tomlinson < themarcustomlinson@gmail.com> wrote:

http://www.adaptaudio.com/DSPatch

Very very quick look (just looked at the code itself): 1. why do you use unsafe pointers in the example? 2. why to you require pointers instead of references in the 3. I know this is common in old style c++, but any system that makes me create objects on the heap then makes me put them in another object that becomes the (life) owner of these objects because it is said so in the documentation but it's not visible in the code is very suspicious to me (Qt is an infamous example of this but for good historical reasons). Smart pointers are far better alternatives as they make the ownership apparent in the code and easily spottable when reading the code. Please use some kind of smart pointer, or let the user make sure the objects are alive when they are used. Joel Lamotte

Hi Joel, thanks for your time! (Again) :) Funny story about safe pointers... I originally used safe pointers instead of standard pointers, but eventually removed them due to the performance hit was inducing. Admittedly though, I was using a reference counting pointer that was causing a bottle neck due to thread safety critical sections. I will definitely look into using another safe pointer implementation that comes closer to mirroring the performance of a standard pointer. Components do store their own names, perhaps I didn't make this clear. The circuit requires the component to have a name before being added to the circuit, passing the name into the AddComponent() method invokes a just-in-time call to that component's SetName() method as to ensure it has a name on entering the component collection. I will try make this clearer in documentation. In terms of why components should have names in a circuit: Where this becomes very useful is in serialization / deserialization. With this in place, you could serialize / deserialize an entire circuit to and from a single self-contained circuit object (e.g. Via a factory). Similarly, a circuit can be passed around by reference on its own, giving receivers access to all circuit components via their IDs rather than having to manage both circuit and component references everywhere. By a static version of the system do you mean compile-time circuit configuration? I've mentioned before that I am interested to explore this avenue but run-time wiring was chosen by design. DSPatch is designed to be very run-time oriented, allowing manipulation of circuits while they're live. I saw a system like this as more useful personally, as you have a the choice of static / dynamic circuits via one interface. Inheritance is a major part of how this library works, so I can't really tell you how I would do it without at the moment. But it is a valid point. Removing the need to inherit could make the system a more flexible. Inheritance is not uncommon though in a system like this, VST plugins are an example. On 09 Dec 2012, at 2:52 AM, Klaim - Joël Lamotte <mjklaim@gmail.com> wrote:

I took a second quick look before going to bed:

4. why can't the component contain their id/name? 5. is it really necessary to have id/component name? 6. how do you plan to allow a static version of such system? 7. could it be done without inheritance? what would be the tradoff then?

Joel Lamotte

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Hi Julian, thanks for the post. I see a pattern forming :) I think I need to make my documentation clearer in a number of places. Ok, in DSPatch, circuits provide 2 main purposes: encapsulation of a component network, and parallel processing control (see more on how parallel processing is done see: http://www.adaptaudio.com/DSPatch/spec_page.html). Components don't have to be added to a circuit to be routed together, this is just recommended due to the advantages (mentioned above) gained in this approach. Components have ConnectInput / DisconnectInout methods that can be called directly in order to create component networks outside of a circuit. You are correct, there isn't a way to extract multiple values from a single input. This is because each component input can only accept one wire at a time. When another wire is connected to an input that already has a connected wire, that wire is replaced with the new one. This is not the case with outputs though. One output can be distributed to multiple inputs. This is definitely something that should be explained explicitly (I'll add it to the list). I don't see dynamic typing as a limitation, I see it as quite useful. Lets say your processing an input stream of audio samples. With dynamic typing, you can adjust the audio's sample size at run-time and have the component input adapt dynamically without breaking flow. I also have to disagree with you that object-oriented design has nothing to offer to dataflow programming, but perhaps this is just one man's opinion against other. On 09 Dec 2012, at 5:02 AM, Julian Gonggrijp <j.gonggrijp@gmail.com> wrote:

Marcus Tomlinson wrote:

...

Is there any interest out there for a library that allows you to create fast, efficient flow-based programs with an easy-to-use object-oriented interface? (http://en.wikipedia.org/wiki/Flow-based_programming)

I've created an open-source library that does this, called "DSPatch" ( http://sourceforge.net/projects/dspatch) and would like to contribute it to the Boost Libraries.

I'm certainly interested in a Boost library that offers efficient flow-based multithreading with an interface that is as simple as possible. In fact I have some ideas of my own which I would gladly present to the mailing list when I find more time.

As has been pointed out by other people, there are lots of dataflow libraries out there, all offering similar functionality. I believe the reason for this is that it's hard to get right. In particular, it's hard to offer the functionality through an interface that is truly simple enough.

I think your proposal suffers from this same problem. As far as I'm concerned users should not need to inherit from a class in order to do flow-based programming, nor should they need to create a circuit object to provide wiring between the working components -- let alone have to invoke methods on said object for each worker /and/ for each connection. The connection methods have four arguments, which is too much.

On top of that I think a dataflow programming library can and should be more powerful. Your framework allows for many-to-many connections, but as far as I can tell from your documentation there are no standard facilities that handle generic patterns such as distributing worker output over multiple receivers. There doesn't seem to be a way to directly extract multiple values in succession from an input DspSignal(Bus). Polymorphism on the connections is handled by dynamic typing while it could be static. I suspect there are more limitations.

Finally I believe object oriented design offers no advantage for dataflow programming. It's not really in line with common Boost style either.

Concluding, while I fullheartedly agree with your intentions, I would vote against your library if you were to submit it for a formal review. I'm sorry to say this but I think Boost needs something that is both simpler and more flexible.

-Julian

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Thanks again for taking the time to look at my code Julian, it's a big help :)

Suggestion: describe for each member function what it does. And give a shorter, more conceptual overview at the front page of how the library works and why. Note that you find the need to expand upon your documentation while it's already quite beefy. Some of your classes have lots of public methods. These are clear signals that your library is not simple enough.

I've added a sort overview to the introduction section, I think this should help. In terms of the method descriptions / number of public methods, I'm gonna have to tackle that over a weekend I think, both valid points!

...

From that page I gather that there may be threads specific to a component as well as "general" (circuit) threads that take up work from each component in a circuit in turn. What is the motivation for this design? How do you avoid having two threads execute the same component's job on the same inputs, especially if one is a component thread and one is a circuit thread?

Am I right to assume that the circuit object is not necessary to enable multithreading?

Component threads and circuit threads don't interact, they perform completely different tasks. Component threads even act on physically different memory than the circuit threads do (so access violations are not a concern). The motivation for this design is actually the answer to your second question -you have the option of multi threading via a circuit object, or directly via the components themselves. However, as I have just rediscovered, the interconnected, free-running components approach is currently incomplete. I will get onto finishing this next. Good observation! Thanks :)

IIUC you have to "extract" the wire from the source component and manually assign it an index or name. Why not just take a wire object as the sole argument and give it an index automatically? In addition you can connect only one wire at a time. Why not offer a ConnectInputs method that takes a collection of wires?

I'm not sure I understand what your suggesting. Should you be able to instantiate a wire object externally and pass it in a an argument to an AddWire() method in the component? I think I know where you're going with this (and the multiple wire thing), the problem is that I don't assume anything wrt input and output signals. It is not assumed that one component's outputs all connect 1:1 as a bus to another component's inputs, it's also not assumed that the signal name of an output corresponds to the equivalent signal name of an input. I see this as flexibility, but perhaps it could be perceived and overly complex.

Actually I find this interface really worrying because it seems to suggest that a component needs to know about other components in order to receive input from wires. On the specification page I read that the /wires/ need to know about the components as well. "Separation of concerns" is not being fully applied here. I would strongly prefer a more generic interface where wires can operate regardless of whether they're connected to components and vice versa.

Good point, I will look into upgrading the DspWire structure to a smarter class that isolates dependency and exposes safe methods for signal retrieval. On conception I did feel that this was going to have to change at some point.

1) why can an input accept only a single wire at a time and 2) why can't wires transport multiple values at a time?

What would be returned from a call to the input's GetValue() method in a case where there are multiple wires connected to it, or where there are multiple values assigned? Remember, you can transfer arrays over wire link -still regarded as single values. Otherwise, do you suggest there be the option to continually call GetValue() on an input until all wires / values are processed?

...

From the tutorial it was quite clear to me that this would be possible, but it appears that the user would have to implement this by themself every time. There is no ready facility to abstract and automate it. Besides, given that components can extract only a single value from each input at a time, the possibility to output multiple values at once is only marginally useful.

When i say an output can be distributed to many inputs, I mean that one outgoing signal can be received by multiple components. An output simply provides its current produced value to any component that wishes to use it. An example of this could be a global sample rate provider to many audio processing components. I think I know where the confusion is coming from. In DSPatch, the terms input/output, and signal are interchangeable. Input/output bus = signal bus.

You can do polymorphism in safer, more or less "static" ways. Consider Boost.Variant.

Will do.

OOD is a useful tool with some uncontroversial use cases, such as game engines. However it should never be a goal in itself.

I think a good example of where OO dataflow has been extremely successful is in Steinberg's VST framework.

I wrote:

I'm certainly interested in a Boost library that offers efficient flow-based multithreading with an interface that is as simple as possible. In fact I have some ideas of my own which I would gladly present to the mailing list when I find more time.

In the meanwhile I would like to refer to FastFlow [1], which as far as I can tell hasn't been mentioned yet in this thread. It's similar to DSPatch with respect to OOD, but it offers two particular features that I think are more powerful and would be more fitting for a Boost submission. The first is the use of producer-consumer queues as the primary means to transfer data between two threads. I believe this is really THE way to go, because the data are buffered and neither producer nor consumer will need to wait for the other unless the buffer is full or empty. Note that in a sense the DSPatch wire is a special case of the producer-consumer queue where the buffer has only one slot, so it's always either full or empty, forcing the producer and consumer components to work strictly in tandem. The other feature is the use of dedicated threads to create one-to- many and many-to-one connections out of only pure one-to-one connections. The FastFlow authors refer to these as "emitters" and "collectors", respectively. This simplifies the implementation and improves throughput in scenarios where a thread has multiple inputs or multiple outputs. Moreover, in combination with generic design this would allow for some nifty off-the-shelf tools such as tuple zipping/unzipping, distributing/interlacing, etcetera. Topher Cooper independently came up with a similar idea in [2]. Nonetheless FastFlow still isn't my "dream library". One reason for that is that it isn't generic. Another reason is that to my taste it behaves too much like a framework instead of like a toolkit. One symptom of that is the requirement on users to derive from a class (like in DSPatch) and to override methods. Finally, while FastFlow makes an admirable attempt at providing abstractions for complex high- level use cases ("skeletons"), doing simple things is not simple (thankfully adopting this way of talking about simplicity from [2]). Hope this will help the discussion! -Julian _______ [1] http://calvados.di.unipi.it/dokuwiki/doku.php?id=ffnamespace:about [2] http://lists.boost.org/Archives/boost/2012/12/199333.php

Marcus Tomlinson wrote:

...

Note that in a sense the DSPatch wire is a special case of the producer-consumer queue where the buffer has only one slot, so it's always either full or empty, forcing the producer and consumer components to work strictly in tandem.

Quick question about this. In FastFlow (and other dataflow libraries), when you create parallel branches of components (equal length or of different number of components), does the result of a piece of data diverging across these branches arrive at the converging point all at the same time?

Probably not (regardless of the length of the parallel branches). Is this something that DSPatch would guarantee, even when the branches have different numbers of components? That would be interesting.

...

The other feature is the use of dedicated threads to create one-to- many and many-to-one connections out of only pure one-to-one connections. The FastFlow authors refer to these as "emitters" and "collectors", respectively. This simplifies the implementation and improves throughput in scenarios where a thread has multiple inputs or multiple outputs.

Referring to a thread as having multiple inputs and outputs leads me to believe that a "threads" and "components" / "processes" are directly related? Does this mean the more components you have, the more threads you require?

Yes, for convenience I've been assuming a one-to-one relationship between components and threads. This is the default in FastFlow and I think it makes sense. It isn't a necessity, though; you could also take a fixed number of threads and have them handle a variable number of components in turn. I'm not sure whether or how FastFlow implements such a thing but I'm sure it can be done in principle. -Julian

Marcus Tomlinson wrote:

...

Probably not (regardless of the length of the parallel branches). Is this something that DSPatch would guarantee, even when the branches have different numbers of components? That would be interesting.

Yes, DSPatch does this. This is what I refer to as branch synchronization on the feature list. It is that fact that DSPatch can guarantee this whilst maintaining high performance via parallel processing that makes it uniquely powerful I think.

That's fascinating, but I now realise that such a guarantee could also be provided with something like the FastFlow library. Or rather, you can't guarantee that the results from the same diverged datum will /arrive/ at the same time, but you can construct the converging component such that it will /take/ them at the same time. The end result is the same. This makes me a bit sceptical about the high performance part. FastFlow can synchronise the converging point without requiring that the components within the branches operate in lock-step. Surely that allows for more fluid concurrency? Perhaps a little benchmark would be good. -Julian

Marcus Tomlinson wrote:

...

Note that in a sense the DSPatch wire is a special case of the producer-consumer queue where the buffer has only one slot, so it's always either full or empty, forcing the producer and consumer components to work strictly in tandem.

Can I just quickly clarify that DSPatch does make use of producer-consumer pattern -Signals are buffered. The consumer has a slot per thread used to process the circuit (4 threads : 4 slots in each buffer). While one signal is being processed by the component, other incoming signals are being queued. Remember, one of the core features that DSPatch provides is the ability to run DSPatch circuits using no threads at all. This approach to the producer-consumer problem is designed as such to be scalable in this respect.

It appears that this doesn't change anything about the fact that components are forced to work strictly in tandem. Regardless, some questions for further clarification: - Who owns the buffers? The circuit? - Who are the producers/consumers? The threads? If both of my guesses are correct, am I right to conclude that the threads are rotating over the components, and that the one-slot-per- thread approach to the buffers is the way to ensure that they can read and write concurrently without a need for locking? -Julian

Marcus Tomlinson wrote:

...

- Who owns the buffers? The circuit? - Who are the producers/consumers? The threads?

If both of my guesses are correct, am I right to conclude that the threads are rotating over the components, and that the one-slot-per- thread approach to the buffers is the way to ensure that they can read and write concurrently without a need for locking?

Components own the buffers as members, one for incoming signals and one for outgoing signals. You are correct in your conclusion that threads cycle over the components, so as each component is ticked, it consumes from the outgoing buffers of the components connected to it's inputs, then produces into it's own outgoing buffer (and so on). And yes, you are correct, this is designed as such to avoid locking.

Each component has its own input and output buffers. Then how do data travel from one component's output buffer to another component's input buffer? In an additional step between the component executions? -Julian

Vicente J. Botet Escriba wrote:

Le 05/12/12 13:31, Marcus Tomlinson a écrit :

...

I've created an open-source library that does this, called "DSPatch" ( http://sourceforge.net/projects/dspatch) and would like to contribute it to the Boost Libraries.

Just wanted to share this

http://goparallel.sourceforge.net/data-flow-mic-cuts-multi-thread-overhead/

Also relevant: http://audiob.us/ especially given that it is an audio application, like VST which seems to be a source of inspiration for DSPatch. -Julian