[boost][sync?] "Distributed" value (or something...)
I would like to ask Boost developers and users:
1. Am I the only one seeing the following pattern in my concurrent systems
code?
2. Is there already some tools available in Boost that does what I
describe here and that I am not aware of?
3. If not, would there be any interest in the tool I'm describing here or
not? Is it a dumb idea?
(I keep getting back to this idea but I'm surprised not finding anything
similar online)
The pattern that I am seeing occurs when:
1. I have a value or a set of values in an object or several objects which
value(s) describe some kind of configuration that several other systems
will read and use.
2. The object(s) will be updated only by one thread (at a time).
3. When the object's value is modified, all the systems that rely on the
object's value have to be notified
so that they update themselves using that value.
4. The systems I am refering to can use different threads for updating and
we can assume that they are running concurrently.
5. It is not important that the source object's value is synched with the
reader's values at all time,
however it is important that the sequence of changes to the source
object's value is signaled to the readers
exactly in the same order and "as fast as possible", but delay is ok.
The simplest solution to solve this is to have a mutex locking the value
and the systems checking the value
regularly. (that is, using syncrhonized_value for example)
However the locking and looping reads might not be necessary if it is done
in another way (if I am correct, I still lack experience in the domain).
The solution that I am thinking about would look like this.
/////////
// The object containing the value used by the other systems.
class System_A
{
distributed_source<int> m_foo_count; // changes to this object
will be sent to "readers"...
public:
System_A() : m_foo_count(42) ...
{}
//...
// thread-safe read-only access
distributed_value<int> make_foo_count_reader() const {
return distributed_value<int>{ m_foo_count };
}
};
/////////
// The different systems acquire a read access to the value.
class System_B
{
distributed_value<int> foo_count; // read-only value reflecting
System_A::m_foo_count's value since last update.
public:
SystemB( const System_A& system_a, ... )
: m_foo_count( system_a.make_foo_count_reader() )
{
// setup the initial config...
on_foo_count_changed( *m_foo_count );
// trigger some processing when SystemA::foo_count's value have
been changed:
m_foo_count.on_changed( [this]( int new_value ){ // called
after the value have been changed
m_work_queue.push( [=]{ // will be executed on the next
update cycle for this system...
on_foo_count_changed( new_value ); /
});
});
}
//...
private:
void update_cycle( const UpdateInfo& info )
{
// ...
// the following is just to clarify:
const int foo_before = *m_foo_count; // the value is not
updated yet, but we can still use it
m_work_queue.execute();
const int foo_after = *m_foo_count; // the value might have
been udpated
if( foo_before != foo_after )
{
// the value have been updated (though you don't need to do
this if you used the callback instead).
}
//...
};
};
////////
// At some point the value is changed by the system owning the source
object...
System_A::change_foo( int new_value )
{
m_work_queue.push( [=]{ // will be executed on the next update
cycle of this system...
// ...
*m_foo_count = new_value; // assign the new value then send the
new value to the readers...
});
}
System_A::something_complex( std::function
On 30/07/2014 07:44, Klaim - Joël Lamotte wrote:
I would like to ask Boost developers and users:
1. Am I the only one seeing the following pattern in my concurrent systems code? 2. Is there already some tools available in Boost that does what I describe here and that I am not aware of? 3. If not, would there be any interest in the tool I'm describing here or not? Is it a dumb idea? (I keep getting back to this idea but I'm surprised not finding anything similar online)
The pattern that I am seeing occurs when: 1. I have a value or a set of values in an object or several objects which value(s) describe some kind of configuration that several other systems will read and use. 2. The object(s) will be updated only by one thread (at a time). 3. When the object's value is modified, all the systems that rely on the object's value have to be notified so that they update themselves using that value. 4. The systems I am refering to can use different threads for updating and we can assume that they are running concurrently. 5. It is not important that the source object's value is synched with the reader's values at all time, however it is important that the sequence of changes to the source object's value is signaled to the readers exactly in the same order and "as fast as possible", but delay is ok.
This sort of thing is a publisher-subscriber model. There are lots of different implementations of it, depending on what each end "knows" (eg. push vs. pull) and who you want to have responsible for copying the data, whether you want lock-based or lock-free, etc. A really simple (albeit heavy-handed) way of doing this lock-free (or almost lock-free, depending on shared_ptr implementation) is to have your data in a shared_ptr; whenever something wants to act on the data it uses atomic_load to fetch it from some well-known location and can then do whatever read-only access it wishes; when it wants to change the data it first copies the entire object, makes the changes in the copy, and then uses atomic_compare_exchange to replace the "real" version. If the compare fails, it lost the race to a faster writer so must perform its updates again on the new data and try exchanging again. But that pattern is only good for fairly self-contained objects where reads are frequent and writes are rare, and where it's relatively easy to copy, throw away and recalculate (which also implies self-containment, because that gets more complex if you want to act on two or more such objects). In particular it is *not* suited to frequent concurrent writes because it's vulnerable to writer starvation (*some* writer will always succeed, but it's possible that one writer always fails because a faster one always beats it). There are other patterns that are better suited to other kinds of accesses; it's hard to find something generally applicable without making performance compromises.
On Wed, Jul 30, 2014 at 4:45 AM, Gavin Lambert
This sort of thing is a publisher-subscriber model. There are lots of different implementations of it, depending on what each end "knows" (eg. push vs. pull) and who you want to have responsible for copying the data, whether you want lock-based or lock-free, etc.
Thanks for the keywords.
A really simple (albeit heavy-handed) way of doing this lock-free (or almost lock-free, depending on shared_ptr implementation) is to have your data in a shared_ptr; whenever something wants to act on the data it uses atomic_load to fetch it from some well-known location and can then do whatever read-only access it wishes; when it wants to change the data it first copies the entire object, makes the changes in the copy, and then uses atomic_compare_exchange to replace the "real" version. If the compare fails, it lost the race to a faster writer so must perform its updates again on the new data and try exchanging again.
This would work I guess but not well with big values (like a big struct). Also, from my understanding, having one "copy" of the object for each subscriber seems to be potentially more efficient if you already know that each subscriber work with it's own thread (or set of threads). As I assumed and you are confirming, there is a lot of ways to do it depending on the actual context... I guess I should implement a solution with my current case before considering generalization.
But that pattern is only good for fairly self-contained objects where reads are frequent and writes are rare, and where it's relatively easy to copy, throw away and recalculate (which also implies self-containment, because that gets more complex if you want to act on two or more such objects). In particular it is *not* suited to frequent concurrent writes because it's vulnerable to writer starvation (*some* writer will always succeed, but it's possible that one writer always fails because a faster one always beats it).
Yes, it's exactly for this kind of case. In particular, values being considered as "global configuration", in my case. That is, they are read once from a file at startup, then put in some structs and separate objects. Then, if one is changed, a lot of things have to be updated, but in a lot of different systems running in different threads. So even if the config changes are rare, they might trigger a lot of reaction, and I want the reactions to be independant (which is why I was considering having a copy of the value for each subscriber).
There are other patterns that are better suited to other kinds of accesses; it's hard to find something generally applicable without making performance compromises.
Indeed. In my use case, performance manipulating that value is not really important except on the reactions of the subscriber. I will try some experimental implementations, see how it goes. However I have no experience in measuring speed of a concurrent system, so I'll focus first on interface.
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On 30/07/2014 20:35, Klaim - Joël Lamotte wrote:
A really simple (albeit heavy-handed) way of doing this lock-free (or almost lock-free, depending on shared_ptr implementation) is to have your data in a shared_ptr; whenever something wants to act on the data it uses atomic_load to fetch it from some well-known location and can then do whatever read-only access it wishes; when it wants to change the data it first copies the entire object, makes the changes in the copy, and then uses atomic_compare_exchange to replace the "real" version. If the compare fails, it lost the race to a faster writer so must perform its updates again on the new data and try exchanging again.
This would work I guess but not well with big values (like a big struct). Also, from my understanding, having one "copy" of the object for each subscriber seems to be potentially more efficient if you already know that each subscriber work with it's own thread (or set of threads).
Copies are not efficient for a big struct, but copies only occur on write so it's not a big deal if writes are rare. Having a separate copy for each subscriber is helpful to avoid write contention, but if everything is only reading from a single shared object that is seldom written to then I don't think it provides any benefit (but I'm not an expert on cache effects). My gut feeling is that which approach is "better" depends on the number of subscribers and the frequency of actions. You do pay a bit for an atomic load/exchange (it's not a lot, but it's still something you want to avoid doing in a tight loop), but it means you only need to copy once; conversely having copies for each subscriber lets you avoid the atomics but requires you to make N copies. There are other tradeoffs as well, of course -- the one I proposed above doesn't have notifications on change, it just lets existing operations continue using the old data while new operations silently pick up the new data (basically a pull model); while a push model explicitly notifies subscribers that new data is available and lets them potentially do something esoteric if required -- but if implemented naively may result in the subscribers all being called from the publisher's thread, which may introduce contention and cache fragmentation.
On Wed, Jul 30, 2014 at 11:39 AM, Gavin Lambert
On 30/07/2014 20:35, Klaim - Joël Lamotte wrote:
A really simple (albeit heavy-handed) way of doing this lock-free (or almost lock-free, depending on shared_ptr implementation) is to have your data in a shared_ptr; whenever something wants to act on the data it uses atomic_load to fetch it from some well-known location and can then do whatever read-only access it wishes; when it wants to change the data it first copies the entire object, makes the changes in the copy, and then uses atomic_compare_exchange to replace the "real" version. If the compare fails, it lost the race to a faster writer so must perform its updates again on the new data and try exchanging again.
This would work I guess but not well with big values (like a big struct). Also, from my understanding, having one "copy" of the object for each subscriber seems to be potentially more efficient if you already know that each subscriber work with it's own thread (or set of threads).
Copies are not efficient for a big struct, but copies only occur on write so it's not a big deal if writes are rare.
Yes I believe that at least in my use case it makes sense.
Having a separate copy for each subscriber is helpful to avoid write contention, but if everything is only reading from a single shared object that is seldom written to then I don't think it provides any benefit (but I'm not an expert on cache effects).
I'm not an expert either so I might be pessimizing that part. I started an implementation and will try to make the interface not impact the implementation so that I can try different things.
My gut feeling is that which approach is "better" depends on the number of subscribers and the frequency of actions. You do pay a bit for an atomic load/exchange (it's not a lot, but it's still something you want to avoid doing in a tight loop), but it means you only need to copy once; conversely having copies for each subscriber lets you avoid the atomics but requires you to make N copies.
In my case it's ok to have N copies, but yeah I have to make sure the user understand this cost.
There are other tradeoffs as well, of course -- the one I proposed above doesn't have notifications on change, it just lets existing operations continue using the old data while new operations silently pick up the new data (basically a pull model); while a push model explicitly notifies subscribers that new data is available and lets them potentially do something esoteric if required -- but if implemented naively may result in the subscribers all being called from the publisher's thread, which may introduce contention and cache fragmentation.
I'll try to make my implementation possible to use either with callbacks called using executors, or through an regular pull call. Both seems interesting in different cases and it don't seem to me (at the moment) that implementation of both would be mutually exclusive. I'll report here when I have something that I can at least use in my own project.
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (2)
-
Gavin Lambert -
Klaim - Joël Lamotte