CODEWITHSUNDEEP
c++multithreadingmutexconcurrent-vector
omarekik
omarekik

Reputation: 31

Lock based concurrent vector

I am starting with designing thread safe data structure and looking to implement a concurrent vector that hides multi-threading complexity for the user and that offers thread safe clear function (which is not offered by Intel TBB::ConcurrentVector) . Considering a concurrent vector which is based on std::vector and locking a mutex for each call of clear or push_back functions of std::vector, how to iterate thread safely through the concurrent vector using for loop? in other terms, how to make iterate_thread in this minimal reproducible example thread safe?

#include <bits/stdc++.h> 
using namespace std; // for the sake of minimal reproducible example
template<class T> 
class ConcurrentVector {
public: 
    ConcurrentVector() : mMutex{} 
                  , mVector{} 
    {}
    auto begin(){
        scoped_lock lk(mMutex);
        return mVector.begin(); 
    }
    auto end(){
        scoped_lock lk(mMutex);
        return mVector.end(); 
    }
    T& push_back(T t) {
        scoped_lock lk(mMutex);
        mVector.push_back(move(t)); 
        return mVector.back();
    }
    void clear() {
        scoped_lock lk(mMutex);
        mVector.clear(); 
    }
private: 
    mutex mMutex; 
    vector<T> mVector; 
}; 

int main(){
    ConcurrentVector<int> vec{};
    atomic_bool terminate_flag = false;
    jthread fill_thread{[&](){
        static int i = 0;
        while(!terminate_flag){
            this_thread::sleep_for(10ms);
            vec.push_back(++i);
        }
    }};
    jthread clear_thread{[&](){
        while(!terminate_flag){
            this_thread::sleep_for(1s);
            vec.clear();
        }
    }};
    jthread iterate_thread{[&](){
        while(!terminate_flag){
            this_thread::sleep_for(400ms);
            for(auto i : vec){
                cout << i << ", ";
            }
            cout << '\n';
        }
    }};
    
    this_thread::sleep_for(3s);
    terminate_flag = true;
    return 0;
}

Calling clear function in iterate_thread will invalidate iterator and actually, I am thinking of these two options:

Are there other alternatives or could any of the two mentioned improved?

Upvotes: -1

Views: 150

Answers (4)

omarekik
omarekik

Reputation: 31

Thanks @MikeVine, this concurrent_vector is based on a monitor that protects std::vector from data race:

template<class t_container>
class monitor{
public:
    template<typename ...Args>
    monitor(Args&&... args) : m_container(std::forward<Args>(args)...){}

    struct monitor_helper{//The time of locking is the life time of monitor_helper
        monitor_helper(monitor* mon) : m_monitor(mon), m_unique_lock(mon->m_mutex) {}
        t_container* operator->(){ return &m_monitor->m_container; }
        t_container& operator*(){ return m_monitor->m_container; } // for accessing using a manually locked object
        monitor* m_monitor;
        std::unique_lock<std::mutex> m_unique_lock;
    };

    monitor_helper operator->(){ return monitor_helper(this); }
    monitor_helper manually_lock(){ return monitor_helper(this); }
private:
    t_container m_container;
    std::mutex  m_mutex;
};

template<typename t_element> 
requires copyable<t_element>   
class concurrent_vector {
public: 
    void push_back(t_element t) {
        m_monitored_vector->push_back(move(t)); 
    }
    void clear() {
        m_monitored_vector->clear(); 
    }
    vector<t_element> get_data(){
        {//scope for manually_lock
            auto vector_lock_handler = m_monitored_vector.manually_lock();
            return *vector_lock_handler;
        }
    }
private: 
    monitor<vector<t_element>> m_monitored_vector; 
};

Upvotes: 0

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

Do not export any vector-like functions from your class. Only export a function that returns an object acting as a scoped lock, and make that object export vector-like functions, which in turn won't need any locking. Something like:

ConcurrentVector<int> v; 
...
{
  auto vv = v.open(); // vv locks 
  for (auto& i: vv) {  // and presents vector-like functionality
    i = 2*i+3;
  }
  // vv's destructor unlocks
}

Upvotes: 3

Aykhan Hagverdili
Aykhan Hagverdili

Reputation: 29985

Making a ConcurrentVector that wraps std::vector and locks on all public function calls is probably a bad idea. It will lead to an unnecessary number of lock/unlock calls, and it's generally undesirable to let other threads interleave between your calls. What I would recommend doing is to have one mutex for the entire vector, lock it with an RAII based lock class, perform all your actions and then let the destructor unlock the mutex at the end of the function. This generally achieves good performance and more predictable behavior.

Upvotes: 1

MSalters
MSalters

Reputation: 179907

A range-based loop still uses iterators, even if not visible in code. That iterator has to cooperate. You can't just use std::vector::iterator for this, because the lock has to be released when the iterator goes out of scope.

The naïve implementation linked to only locks the mutex in .begin() when the iterator is created, which is way too short.

Locking the mutex while an iterator exists also prevents the problem of two iterators existing, causing write clashes. However, .end() does need to return a sentinel iterator even when there's another outstanding iterator.

Where things really break down is .end()-1. This needs to lock the vector, as the last element of the vector is definitely writeable.

And don't expect this to magically solve all your problems. Code like if (v.begin()!=v.end()) auto last = *(v.end()-1) breaks when another thread calls v.clear() at the wrong moment.

Upvotes: 1

Related Questions