Are there any plans to extend the intrusive library with lock-free data structures (stacks, FIFO queues)? I'm about to start writing my own lock-free classes and have thought that it'd be nice to include them in the intrusive library, if possible [I've gotten used to the interface, and I don't want to have different interfaces in my code]. My goals: - lock-free stack and queue - SMR (both described in "Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes" by Maged M. Michael) - target platform: Solaris using atomic_ops (3C); possibly also inline ASM for SunCC I don't have neither time nor resources (nor will, for that matter) to make a full implementation that works on all platforms supported by Boost. Also, I do *not* want to use Boost.Thread. The code is parametrized by the following (all related to SMR): - number of participating threads (every "thread" must be associated with a unique integer starting from 0) - number of hazard pointers - batch size SMR also needs static storage accessed by all threads. Any suggestions are welcome.
Hi, Zeljko Vrba wrote:
Are there any plans to extend the intrusive library with lock-free data structures (stacks, FIFO queues)?
I haven't thought about this, but it sounds interesting. But lock-free is far beyond by possibilities.
I'm about to start writing my own lock-free classes and have thought that it'd be nice to include them in the intrusive library, if possible [I've gotten used to the interface, and I don't want to have different interfaces in my code]. My goals:
Are you sure these new containers fit in Intrusive? Maybe a new, lock-free containers library is what we need.
- target platform: Solaris using atomic_ops (3C); possibly also inline ASM for SunCC
This is a big problem. First, Intrusive does not support (for the moment) SunCC. Second, we will need portable containers to admit them in Intrusive.
I don't have neither time nor resources (nor will, for that matter) to make a full implementation that works on all platforms supported by Boost. Also, I do *not* want to use Boost.Thread.
Maybe you could join with other lock-free experts to develop the library. Just curious: Do you support all the Intrusive interface? What thread-safety do you achieve with containers, hooks, and algorithms? Regards, Ion
On Wed, Jun 13, 2007 at 08:11:45AM +0200, Ion Gaztañaga wrote:
I haven't thought about this, but it sounds interesting. But lock-free is far beyond by possibilities.
It's not _that_ hard; good papers have all algorithms in pseudo-code which is mostly enough :)
Are you sure these new containers fit in Intrusive? Maybe a new, lock-free containers library is what we need.
Actually, I'm not sure. Lock-free objects support a very limited set of operations..
This is a big problem. First, Intrusive does not support (for the moment) SunCC. Second, we will need portable containers to admit them in Intrusive.
BTW, SunCC works fine with base hooks. Code like namespace detail { struct uproc_chan_list_tag; struct uproc_sched_list_tag; } class user_process : public bvt_acct, public boost::intrusive::list_base_hookdetail::uproc_chan_list_tag, public boost::intrusive::list_base_hookdetail::uproc_sched_list_tag { ... }; works for me with no problems! Now that you've mentioned it, did you come a bit further with debugging member hooks under SunCC?
Maybe you could join with other lock-free experts to develop the library. Just curious: Do you support all the Intrusive interface? What thread-safety do you achieve with containers, hooks, and algorithms?
I didn't yet design the classes, but:
- stack: push_front, pop_front
- queue: push_back, pop_front
These are pretty much the only safe operations that do not require locks.
Plus, some trickery with either SMR or double-wide CAS, but this is just
an implementation detail. As for hooks, my own doubly-linked list class
had an interface like:
template<typename NodeT>
struct list_node_traits {
/* Get prev/next values in the node. */
static NodeT *prev(const NodeT&) { THROW("list_node_traits"); }
static NodeT *next(const NodeT&) { THROW("list_node_traits"); }
/* Set prev/next values in the node. */
static void prev(NodeT&, NodeT*) { THROW("list_node_traits"); }
static void next(NodeT&, NodeT*) { THROW("list_node_traits"); }
};
Instead of inventing "hook classes", I let the user allocate hooks manually,
and specialize as many traits classes as he needs. (One traits class per hook
in the "target" structure). If the user is consistent in naming of the links
(e.g. next/prev), one traits class can be reused for many node types.
A design question for you: Why did you introduce explicit hook classes which
hide this machinery from the user instead of letting the traits be a part of
the public interface?
In my case, automatic hooks (like yours) would be kinda "over-engineering"
(besides, I do not know how to do it myself in reasonable time...)
The design space I have in mind is something as follows:
- implementation of atomic instructions (external function, inline ASM)
- optional locking atomic operations (think x86 LOCK prefix; it is not
needed if it can be assured that the data structure will NOT be accessed
by multiple CPUs)
- safety level (more safety = increasing overhead: CAS, CAS2, SMR)
The instantiation would be like
lf_fifo
Zeljko Vrba wrote:
This is a big problem. First, Intrusive does not support (for the moment) SunCC. Second, we will need portable containers to admit them in Intrusive. ... works for me with no problems! Now that you've mentioned it, did you come a bit further with debugging member hooks under SunCC?
I've installed Solaris Express Developer in a virtual machine and I'm able to compile all perfectly with GCC + Sun linker. However the Sun compiler (SunStudio 11, with 5.8 compiler version) does not compile the latest Intrusive CVS saying that std::iterator_traits is not in std namespace. I've just put SunCC in the low-priority queue, because I can't spend more time investigating this issue. I might be configuring something wrong, though. Ion
On Wed, Jun 13, 2007 at 05:46:25PM +0200, Ion Gaztañaga wrote:
I've installed Solaris Express Developer in a virtual machine and I'm able to compile all perfectly with GCC + Sun linker. However the Sun compiler (SunStudio 11, with 5.8 compiler version) does not compile the latest Intrusive CVS saying that std::iterator_traits is not in std namespace. I've just put SunCC in the low-priority queue, because I can't spend more time investigating this issue. I might be configuring something wrong, though.
Ah, you need to tell it to use stlport. My set of C++ compiler flags is as follows: +w -g -xdebugformat=stabs -D_XOPEN_SOURCE=500 -library=stlport4 (SunCC 5.9 switched to generate DWARF debug information by default, but it generates it wrongly.. or dbx interprets it wrongly; it manifests in that dbx is not able to find source files in certain cases.. The issue is fixed by reverting to STABS format.) (I need _XOPEN_SOURCE for extended POSIX functionality; you can probably leave it out). Best regards, Zeljko.
Ion Gaztañaga wrote:
I've installed Solaris Express Developer in a virtual machine and I'm able to compile all perfectly with GCC + Sun linker. However the Sun compiler (SunStudio 11, with 5.8 compiler version) does not compile the latest Intrusive CVS saying that std::iterator_traits is not in std namespace. I've just put SunCC in the low-priority queue, because I can't spend more time investigating this issue. I might be configuring something wrong, though.
I've just found this to help me: http://blogs.sun.com/sga/category/Boost and http://developers.sun.com/sunstudio/documentation/ss11/mr/READMEs/c++_faq.ht... It seems that I should try with STLport instead of the default standard library. I'll try it again. Regards, Ion
participants (2)
-
Ion Gaztañaga -
Zeljko Vrba