В частности, я ищу очередь блокировки. Есть ли такая вещь в С++ 11? Если нет, то каковы мои другие варианты? Я действительно не хочу больше спускаться на уровень потока. Слишком подвержен ошибкам.
Существуют ли параллельные контейнеры в С++ 11?
Ответы (6)
По словам Диего Дагума из группы Microsoft Visual C++:
Повторяющийся вопрос (ну, один из многих) касается контейнеров STL и того, являются ли они потокобезопасными.
Принимая здесь слова Стефана, реальность такова, что это не так, не как ошибка, а как функция: если каждая функция-член каждого контейнера STL получит внутреннюю блокировку, это сведет на нет производительность. Как библиотека общего назначения с широкими возможностями повторного использования, она также не обеспечит корректности: правильный уровень для размещения блокировок определяется тем, что делает программа. В этом смысле отдельные функции-члены, как правило, не имеют такого правильного уровня.
Библиотека параллельных шаблонов (PPL) включает несколько контейнеров, которые обеспечивают безопасный доступ к их элементам:
- класс concurrent_vector – это класс-контейнер последовательностей, обеспечивающий произвольный доступ к любому элемент. Он обеспечивает безопасное параллельное добавление, доступ к элементам, доступ к итератору и операции обхода итератора.
- класс concurrent_queue – это класс-контейнер последовательности, который позволяет первоочередной доступ к его элементам. Он включает ограниченный набор параллельных безопасных операций, таких как push и try_pop, и это лишь некоторые из них.
Несколько примеров здесь.
Также интересно: http://www.justsoftwaresolutions.co.uk/threading/implementing-a-thread-safe-queue-using-condition-variables.html.
С++ 11 не предоставляет параллельные контейнеры сам по себе. Тем не менее, есть варианты библиотеки. Помимо уже упомянутого PPL, не забудьте про библиотеку Intel TBB.
Он имеет параллельную реализацию queue
, hash_map
, set
и vector
. Но это не только потокобезопасная контейнерная библиотека, но и параллельная версия стандартных алгоритмов (цикл for, сокращение, сортировка и т. д.).
Я удивлен, что никто не упомянул moodycamel::ConcurrentQueue. Мы используем его уже довольно давно, и он работает очень хорошо. Характерно, что его реализация является lock-free, что сразу приносит колоссальную скорость. Другие причины его использования (цитата с официального сайта):
Полноценных lock-free очередей для C++ не так много. У Boost есть один, но он ограничен, например, объектами с тривиальными операторами присваивания и тривиальными деструкторами. Очередь Intel TBB не является свободной от блокировок и также требует тривиальных конструкторов. Есть много академических работ, в которых реализованы очереди без блокировок на C++, но трудно найти пригодный для использования исходный код, а тесты тем более.
Некоторые тесты и сравнения доступны здесь, здесь и здесь.
Предостережение: в случае нескольких производителей порядок извлеченных элементов не обязательно будет таким же, как порядок отправленных элементов (@IgorLevicki), поэтому, если вам нужна эта гарантия, ищите какой-то другой вариант.
Интерфейсы контейнеров просто не предназначены для этой цели. Для интерфейсов, которые они используют, блокировка, видимая для клиента, действительно единственный способ добиться этого, гарантируя правильность и предсказуемое поведение. Кроме того, это было бы ужасно неэффективно, потому что количество приобретений было бы очень большим (по сравнению с хорошей реализацией).
Решение 1
Передать по значению (где применимо).
Решение 2
Создайте набор простых дополнительных реализаций, которые вы можете использовать для передачи контейнеров, удерживая блокировку области видимости (считайте, что это псевдо C++):
template <typename TCollection>
class t_locked_collection {
public:
t_locked_collection(TCollection& inCollection, t_lock& lock) : collection(inCollection), d_lock(lock), d_nocopy() {
}
TCollection& collection;
// your convenience stuff
private:
t_scope_lock d_lock;
t_nocopy d_nocopy;
};
затем вызывающая сторона связывает блокировку с коллекцией, а затем вы обновляете свои интерфейсы, чтобы использовать (пропускать) тип контейнера, где это уместно. Это просто расширение класса для бедных.
Этот заблокированный контейнер является одним из простых примеров, и есть несколько других вариантов. Это путь, который я выбрал, потому что он действительно позволяет вам использовать уровень детализации, который идеально подходит для вашей программы, даже если он не так прозрачен (синтаксически), как заблокированные методы. Также относительно легко адаптировать существующие программы. По крайней мере, он ведет себя предсказуемо, в отличие от коллекций с внутренними блокировками.
Другой вариант:
template <typename TCollection>
class t_lockable_collection {
public:
// ...
private:
TCollection d_collection;
t_mutex d_mutex;
};
// example:
typedef t_lockable_collection<std::vector<int> > t_lockable_int_vector;
... где тип, подобный t_locked_collection
, может использоваться для предоставления базовой коллекции. Это не означает, что подход защищен от дурака, просто устойчив к дураку.
Моя версия одновременного параллелизма пространства имен неупорядоченной карты {
template<typename T,typename T1>
class unordered_bucket: private std::unordered_map<T,T1>
{
mutable std::recursive_mutex m_mutex;
public:
T1 &operator [](T a)
{
std::lock_guard<std::recursive_mutex> l(m_mutex);
return std::unordered_map<T,T1>::operator [](a);
}
size_t size() const noexcept {
std::lock_guard<std::recursive_mutex> l(m_mutex);
return std::unordered_map<T,T1>::size();
}
vector<pair<T,T1>> toVector() const
{
std::lock_guard<std::recursive_mutex> l(m_mutex);
vector<pair<T,T1>> ret;
for(const pair<T,T1> &p:*this)
{
ret.push_back(p);
}
return ret;
}
bool find(const T &t) const
{
std::lock_guard<std::recursive_mutex> l(m_mutex);
if(this->std::unordered_map<T,T1>::find(t) == this->end())
return false; //not found
return true;
}
void erase()
{
std::lock_guard<std::recursive_mutex> l(m_mutex);
this->unordered_map<T,T1>::erase(this->begin(),this->end());
}
void erase(const T &t)
{
std::lock_guard<std::recursive_mutex> l(m_mutex);
this->unordered_map<T,T1>::erase(t);
}
};
#define BUCKETCOUNT 10
template<typename T,typename T1>
class ConcurrentMap
{
std::vector<unordered_bucket<T,T1>> m_v;
public:
ConcurrentMap():m_v(BUCKETCOUNT){} //using 10 buckets
T1 &operator [](T a)
{
std::hash<T> h;
return m_v[h(a)%BUCKETCOUNT][a];
}
size_t size() const noexcept {
size_t cnt=0;
for(const unordered_bucket<T,T1> &ub:m_v)
cnt=cnt+ub.size();
return cnt;
}
vector<pair<T,T1>> toVector() const
{
vector<pair<T,T1>> ret;
for(const unordered_bucket<T,T1> &u:m_v)
{
const vector<pair<T,T1>> &data=u.toVector();
ret.insert(ret.end(),data.begin(),data.end());
}
return ret;
}
bool find(const T &t) const
{
for(const unordered_bucket<T,T1> &u:m_v)
if(true == u.find(t))
return true;
return false;
}
void erase()
{
for(unordered_bucket<T,T1> &u:m_v)
u.erase();
}
void erase(const T &t)
{
std::hash<T> h;
unordered_bucket<T,T1> &ub = m_v[h(t)%BUCKETCOUNT];
ub.erase(t);
}
};
}
В C++11 нет параллельных контейнеров.
Но следующий класс заголовков предоставляет параллельную очередь, стек и приоритетные контейнеры, используя std::deque.
BlockingCollection — это потокобезопасный класс коллекции C++11, созданный по образцу класса .NET BlockingCollection.