2

I'm looking for a lock-free data structure in C++ to replace the following:

pthread_mutex_lock(plock);
set.insert(element);
pthread_mutex_unlock(plock);

The set should support .insert() and .size() with at most O(logN) complexity, has an iterator, and should be able to keep its order with a custom comparator. Basically something that does the same as the ConcurrentSkipListSet in Java. Ideally, it should be platform independent.

I am looking at CDS: http://libcds.sourceforge.net/doc/cds-api/modules.html but not sure which data structure can achieve the goal. The doc does not really have complexity for some of the data structures.

Any suggestion would be great, thanks!

Fenwick
  • 1,061
  • 2
  • 15
  • 28
  • what's your platform ? If it's windows you could explore PPL ( http://msdn.microsoft.com/en-us/library/dd504906.aspx ). – Jagannath Nov 05 '14 at 00:33
  • I have to ask what the real problem you're trying to solve is here? It's possible that you could find such a lockfree container...and then have it turn out to be slower than strategically using locks on a normal set. – Mark B Nov 05 '14 at 01:52
  • Are you sure that `ConcurrentSkipListSet` is lock-free? – Siyuan Ren Nov 05 '14 at 02:32
  • @Jagannath Linux, Mac OS and Windows are our targets. – Fenwick Nov 05 '14 at 03:15
  • @MarkB I have a large graph of millions of integers represented as edge lists, in the format of `sourceNode(int) targetNode(int)`. Given a list of nodes, I need to get all their unique neighbors with multithreading. The neighbor nodes should be kept in the order of the nodes in the list. – Fenwick Nov 05 '14 at 03:29
  • @SiyuanRen I'm pretty sure. The ConcurrentSkipListSet is the alternative of TreeSet for concurrent code – Fenwick Nov 05 '14 at 03:31
  • @Fenwick "Concurrent" is not the same thing as "lock-free". – Siyuan Ren Nov 05 '14 at 03:33
  • @SiyuanRen Of course "concurrent" does not mean "lock-free". I meant CSLSet is designed for concurrent situations to have similar behavior as TreeSet but being lock-free. – Fenwick Nov 05 '14 at 03:57
  • 1
    @Fenwick In that case, Intel's TBB can help you here. https://software.intel.com/en-us/node/506181 -- The link gives you information about concurrent_unordered_set. Like PPL, they don't support concurrent_set. If you don't require ordering, then this could help you. – Jagannath Nov 05 '14 at 21:11

1 Answers1

1

With C++11, it's pretty easy to write your own:

template <typename T, typename Compare = std::less<T>>
class concurrent_set
{
private:
    set::set<T, Compare> set_;
    std::mutex mutex_;

public:
    typedef typename std::set<T, Compare>::iterator iterator;
    // etc.

    std::pair<iterator, bool>
    insert(const T& val) {
        std::unique_lock<std::mutex> lock(mutex_);
        return set_.insert(val);
    }

    size_type size() const {
        std::unique_lock<std::mutex> lock(mutex_);
        return set_.size();
    }
    // same idea with other functions
};

Without C++11, there's boost::mutex too.

Barry
  • 286,269
  • 29
  • 621
  • 977
  • 7
    Concurrent, perhaps. Lock-free? Now that's the important bit, and as you can see from your code above, std::unique_lock is ... a lock.The whole point of a lock-free data structure is to avoid locking. Yes, I'm a proud member of Tautology Club. – George Nov 05 '14 at 01:34
  • Clearly missed that part. – Barry Nov 05 '14 at 01:57