Thanks for the reminder. I'll remove "Boost" from the library name. On 6/10/07, Rene Rivera <grafikrobot@gmail.com> wrote:

Yigong Liu wrote:

...

... feature of Boost.Join is to ...

Since no one has mentioned it before <http://www.boost.org/more/discussion_policy.htm#lib_names>.

Thanks for the suggestions. First I thought about physically remove "Boost" prefix from the name (and have done it to my website). Your suggestions sounds better, so i can keep the name while adding a notice in header in the doc saying "it is not boost library yet...". On 6/11/07, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:

...

On 6/10/07, Rene Rivera <grafikrobot@gmail.com> wrote:

...

Since no one has mentioned it before <http://www.boost.org/more/discussion_policy.htm#lib_names>. On 6/11/07, Yigong Liu <yigongliu@gmail.com> wrote: Thanks for the reminder. I'll remove "Boost" from the library name.

Quoting from the linked page:

"Note that this policy only applies to discussions, not to the documentation, directory structure, or even identifiers in the code of potential Boost libraries."

So I think that keeping that name in the library and in the documentation (maybe modulo a notice that says that the library has not yet been accepted) is fine. You just need to say "the proposed Boost Join library" when discussing it on the mailing list or elsewhere. May be that was exactly what you meant, but I just wanted to clarify.

HTH,

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

I haven't done any benchmark yet. I don't see why concurrency using the proposed Boost.Join library will be inherently "slower" than other implementations. I have implemented some of the optimizations mentioned in the Comega paper (implemented in Comega compiler) using template techniques. I believe there are still more im provements to be made. However considering how much resources Intel has put into optimizing TBB.... That is also why we propose libraries to the community / list for review so that more experts can have a look of the implementation and find the weakness. Thanks for looking into it. Yigong On 6/11/07, Mathias Gaunard <mathias.gaunard@etu.u-bordeaux1.fr> wrote:

Yigong Liu wrote:

...

2> implementing data parallel algorithms (parallel loop and map-reduce) using Join, which is helpful for programming today's multi-core machines.

Have you benchmarked those against "faster" implementations, like the algorithms in Intel Threading Building Blocks, to see what the performance overhead of join calculus is?

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

Hello, On 6/11/07, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:

AFAIK, Intel does use lock-free techniques heavily in its thread library to wasting time on concurrency primitives,

You correctly point out that the Join library does not contain or depend on lock-free algorithms. The implementation of Join library follows the design outlined in "Compiling Join-Patterns" paper and further developed in JoCaml, Comega and C#.Joins. It explores using C++ template programming to capture the design idea and optimizations developed thru this lineage of languages and libraries. Indeed specific lock-free algorithms and data structures are not in the design consideration. so I do not think

the current implementation of your library would compare favorably with it. On the other hand, I do not see why the same techniques couldn't be applied equally to your library.

Could you be more specific about the places in code and design of the Join library where i should improve? My number one purpose of proposing this library is to invite experts on this list to review its design and implementation. Please be specific to the point to be helpful. Also i have been talking to Microsoft researchers who developed Cw and C#.Joins library to discuss design and implementation trade-offs and learnt a lot. Hopefully based on all these feedbacks, the Join library can be improved to be a real useful library. You need to be an expert on lock free programming (which I am not) to

take advantage of it, and experts in this area are still uncommon, so you may have an hard time optimizing your library.

Are you considering libraries not based on lock-free algorithms inherently inferior to or unoptimized compared with libraries with lock-free algorithms? Could you expand on this a little more? if you can use Join's implementation as examples, it will be more educational for me. To me, what is best about Join is that its primitives (async/synch methods and chords) supports a high level asynchronous concurrency programming model: orchestration of asynchronous events/messages/data_flows, which is well suited to developing today's asynchronous, distributed applications. And these primitives happen to be fundamental enough so that you can use them to encode various concurrency designs as demonstrated in over a dozen tutorials. There are many concurrency models, such as STM, futures and deferred methods, and of course lock-free algorithms. Join is just one of them, and it is not silver bullet. You may want check out other boost concurrency libraries such as the futures and defer library by Braddock Gaskill. Thanks for looking into Join. Yigong http://channel.sourceforge.net

Hello, On 6/13/07, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:

I'm not really familiar with either the implementation of the Join library nor with lock-free design, but from a quick glance at the code, I see in boost/join/base/port.hpp:asynch_f [1] that you use mutex protected deque to enqueue async calls. This is probably one place that would benefit from a lock-free deque; also probably the fact that the max queue size is bounded might help with this optimization.

Thanks for spending time looking into code and reply. This is encouraging that some experts start checking details. Each object with async / synch / chords and inheriting actor class will have only one mutex protect ALL states related to concurrency / synchronization / asynchrony, which are distributed over async / synch / actor classes. One scenario may better explain, suppose an async method is called, the calling thread will first grab the mutex, then do the following: 1> push passed argument to queue, 2> turn on a bit in a bitmap representing the message arrival status of all async / synch methods of this object, 3> check this "global" bitmap against the bitmaps of all chords to find which chord has all the messages it need to be ready to fire 4> if a chord is ready to fire, do the following: 4.1> extract all the arguments from the queues of async / synch methods of this chord, and bind theses arguments to the defined chord body method, 4.2> if the chord has a synch method, wake up the calling thread of that synch method to run the chord body, 4.3> otherwise spawn a new task in executor's thread pool to run the chord body 5> The calling thread of async method will release the mutex and return. So the mutex is not only for protecting queue, it is used to protect the whole process, its data structures and operations. All the queues and data structures don't have any their own protections, they are plain STL containers, all protected by this global mutex. The above call-sequence and similar ones are critical to the performance of Join. From Jocaml to Cw, people have done much to optimize these critical paths. My implementations mostly follows Cw. I don't know about lock-free algorithms. From what i learnt from browsing web, i only see lock-free algorithms for basic data structures (stacks , queues) and algorithms, which may not be able to provide much help for the above described call-sequence with heavily customized data structures. I could be wrong, please correct.

Not at all. Plain well designed lock-full (?) algorithm are fast enough 99% of the times (even as fast as lock-free). Is just that a more optimized implementation would cover even the remaining 1%. Do you have any benchmark? And not just synthetic benchmarks, but some real application written with both classic locks & condvars and with Join patterns. This would be useful to compare both the benefits in code simplicity and in performance (if any). Even if Join where slower, if it would really simplify the design of concurrent applications it would be a win.

I cannot agree more about this. I am looking any ways to improve under current design. I have done some initial optimization with template partial specializatin, for example. For async methods, there are two template classes defined: 1> async<void(arg)>: this is async method which does pass argument, this class use a queue to buffer the message 2> async<void(void)>: this is a async method which does not pass any arguments, this class will not use queues, instead it use a integer to count how many times it has been called. This ways the semantics is maintained with much less overhead. Based on method signatures, compiler will automatically choose the best-fit template classes to use. Similarly, for synch<> methods, there are four template classes defined to allow compiler to choose. I haven't done any benchmark comparison yet. I'll try to do some profiling and benchmarking when i get the time and resources. Some implementation of design documentation would be greatly useful,

but I think most of it can be deduced from the Microsoft papers, is that right?

Yes, the current implementation mostly follow Cw paper. The most notable differences are the handling of synchronous methods, exceptions and chord priorities. Thanks Yigong

Hello, On 6/12/07, Scott Woods <scottw@qbik.com> wrote:

The oldest solution in C/C++; pointers to?

eg; vector<async<...> *>

smart_ptrs?

I can also vaguely guess why you would want vectors of async/synch but vectors of actor? Isnt it a base and therefore vectors of base would involve slicing?

Don't fully understand the problem space so I wont be embarrassed if these are ignored.

Thanks for the suggestions. Indeed i am thinking that maybe i should use vector<async<void(data)> &(*)> in the first place. The specific application case for this is when we apply Join to some applications of orchestration of data flows. Suppose we are writing code to collect data from 16 external data channels, we can define useful orchestration/synchronization patterns over these channels, e.g. when channel 4,5,6,7 all have data arrived, we call handler method1, when channel 6,7,8,9 have data available, we call handler 2. So users don't want to define/handle each specific channel. By using vector<async<> > (without &/*) i can create a bunch of channels in one shot, which is quite useful. Maybe i should look into some kind of var-array for this purpose. Allowing copying of actor/async/synch objects are dangerous and could mess up how Join works. Each of them maintains status info about on-going messaging. Cw discourage the copying by only allowing defining async/chords in "class" objects which are instantiated from heap and disallowing their use in "struct". I am trying to boost::noncopyable for this. Still learning Join. Its going to take a while. At language level it's quite

simple but the underlying model is less so and is "outside the box". The best I can do at the moment is try to translate the examples into SDL. For reasons I have not truly clarified this translation is only successful in one direction, i.e. Join -> SDL. I suspect that the systems expressible in SDL may be a superset of those expressable in Join. Or more Join-based code is required to support the more complex SDL systems.

Its a bit of a struggle and I dont know that the comparison is even valid.

You are not alone. Generally I found Join does require a bit of mindset change. When i develop the samples, often i found i am back to mindset of shared-memory/locks state, need a bit of effort to adjust it. There are some design "idioms" related to Join, which i collected from the join/Cw papers i have read, i put it in the section of document "OO concurrency design based on Join". Chord is the core of design which defines asynchrony, synchronization and concurrency at the same time. Regarding to the translation between SDL and the Join library, first they are tools for different purposes. The Join library is to provide a minimum set of primitives to build asynchronous concurrent applications, its focus is good integration with C++ language and library features (inheritance, copying...); while SDL is more system modelling and analysis (i dont know SDL, please correct me if i am wrong). Definitely SDL will have more facilities for modeling purpose; If you can find some modeling tools based on Join calculus, that may be more comparable. Also Join's core is asynchronous. I dont know much about SDL and modeling, so please dont take my words too seriously. Thanks Yigong

Hello, On 6/13/07, Scott Woods <scottw@qbik.com> wrote:

Yes. I have this lingering feeling that it is a cute abstraction at language level that relieves the developer from the headache of concurrency. Just right at this moment I think I have a chord-ache.

FSMs.

Yes, we can use Join to encode some state-machine. The basic idea is that we use async methods to represent the states of objects and using chord to define which actions should be performed in which states. e.g. async<void()> state1; async<void()> state2; ... chord(state1, method1, chord_body1); chord(state2, method2, chord_body2); ... In constructor, we can init object state by calling state1(); To

A comparison of Java/C#'s synchronization model and Join's model may help a little. Both models use a object-wise lock. However the lock is used differently. Java/C#'s model is based on "monitor", the whole object state (all application data too) is the critical region protected by this lock, if a synchronized method is called, the lock is hold during the execution of method body, the callings of all other synchronized methods will be blocked till the first calling returns. In Join, the object-wise lock is only used to protect the synchronization state of the object, embedded in actor<> / async<> / synch<> members. When a async / synch method is invoked, the lock is only hold for buffering messages and checking if any chords are ready to fire (all its messages have arrived) and then it is released. When chord bodies execute (either in calling thread of a synch<> method or a task in thread pool), this lock is not held anymore. We can explore the implications of this difference in the following directions: 1> Join's object-wise lock is not used to synchronize access to application code, instead this synchronization should be specified explicitly in chords or join-patterns. For example, if two methods may access / modify an internal data (data_A) concurrently, we could define an async method data_A_lock() to synchronize the access: chord(method1, data_A_lock, chord_body1); chord(method2, data_A_lock, chord_body2); By calling data_A_lock(), data_A is unlocked. Then the calling of method1/chord_body1 and method2/chord_body2 are synchronized regarding to data_A. 2> Join's synchronization is more fine-grained. In Java/C# model, calling a synchronized method will lock the whole object. For some object, its synchronized methods could be divided into diff groups because they depends on diff resources or states. Theoretically, one method from each of these diff groups should be able to run concurrently without interfering. In Java we cannot do it since the whole object is locked. To do it we need to split the original object into smaller objects, one for each group, to use different locks. This issue can be easily resolve in Join (with one lock) by defining a separate async<> method for each group and diff methods can join with a proper async<> method to acquire the exclusive access to the resource it needs. 3> Join's model can help avoiding some important cases of dead-locks. Some actions need exclusive access to multiple resources. Traditionally we need first lock all these resources one by one and then perform the action. This is problematic design, since some other actions may need exclusive access to (some of) these resources too. We have to make sure all these resources / locks are acquired in the same order otherwise dead-lock will occur. In Join, we can resolve this issue by defining an async method (lock1(), lock2(),...) for each resource and defining chord to join the action method with the set of async methods represents the set of resources it requires: chord(action1, lock1, lock2, lock3,..., chord_body); Please note that when message arrive, Join will check the availablity of all resources (lock1, lock2, ...) in one "atomic" transaction, so the order of how lock1(), lock2(),... are called are not relevant or important anymore. My interest in Join arises from a perceived overlap of concurrency and transition to state2 from inside a chord_body1, we can call state2(). Please refer to the active_object tutorial for a sample. Also i found Join is a close match to the "reactive" model we use to design network servers. Async<> methods can be used to represent incoming requests and chords defining the reaction rules about how to handle requests. By properly choosing synch<> / asynch<> to define the process method, we can achieve different server designs such as "iterative server" or "a task per request"/thread-pool design. Thanks Yigong

Hello, On 6/13/07, Mathias Gaunard <mathias.gaunard@etu.u-bordeaux1.fr> wrote:

That would probably impose the use of dynamic allocation of each channel, which would require memory management. Following RAII, the vector should therefore own the pointees, so ptr_vector should be used.

but vector doesn't support that anyway). But still, shouldn't channels be movable anyway?

By "movable", are you referring to the semantics similar to std::auto_ptr?

I have been trying to avoid dynamic memory allocation, since async<> / synch<> methods are kind of message queues using STL containers and STL is value-semantics oriented. Inside Join's "base" framework, dynamic memory allocation is only used for chord creations, which is really dynamic, and which is owned by the parent actor<> thru a vector of shared_ptr. For creating a bunch of "anonymous" async<> / synch<> methods or data channels, i have been using vector<async<>/synch<> >, till we hit the handling of copying. Thanks for pointing out ptr_vector, i'll look into it. Copying, or rather moving, is only needed when growing (or shrinking, the transfer of ownership? If so, async<> / synch<> methods can not or difficult to be movable. Since if we "move" a async/synch method from one actor to another, we need to destroy / cleanup all chords in original actor which the moved async/synch participate in and which will never become ready to fire now since the "moved" channel will never send messages again. Otherwise message leakage will happen. Also in the original join-calculus, the channels and the reaction rules to handle messages at these channels are defined in the same place: join definitions. We are trying to use a class (inheriting actor<>) to simulate the join definition. It seems to me that active classes (inheriting actor<>) should be the owner of their async / synch methods and these methods are not copyable/assignable/ movable. Thanks Yigong