Сортировка вектора с использованием потоков

Question

Векторы, определенные в C ++ STL, являются реентерабельными или потокобезопасными? Могу ли я использовать два потока и работать (в данном случае сортировку) на двух половинах вектора, не используя мьютекс? Например:

int size = (Data_List.size())/2;

Thread A()
{

................ // Do we need to lock Data_list with a mutex
 sort(Data_List.begin(),Data_List.begin()+size,cmp);
}

Thread B()
{
....// Do we need to lock Data_list with a mutex
sort(Data_List.begin()+(size+1),Data_List.end(),cmp);
}

Мой вопрос: нужно ли блокировать доступ к Data_List с помощью мьютекса?

Примечание: функция cmp является обычной функцией сравнения int.

Answer 1

Пока потоки работают в разных областях памяти и ваша функция сравнения работает только с этой памятью и локальными переменными, у вас все должно быть в порядке. По сути, вы «блокируете» каждую половину таблицы, разделяя работу между потоками и позволяя потоку работать только со своей половиной данных.

Answer 2

Почти, но не совсем. Этот код, как правило, не является потокобезопасным, даже если предположить, что реализация дает разумные гарантии безопасности потока вектора.

Предположим, Data_List::value_type - это тип, для которого ваша архитектура не обеспечивает атомарный доступ. Например, в x86 байтовые записи и выровненные записи слов и слов являются атомарными, а короткие записи - нет, а записи пользовательских типов - нет, если они не имеют хорошего размера и выравнивания. Если ваш UDT имеет размер 3, у вас может быть проблема.

Чтобы выполнить неатомарную короткую запись, реализация может выполнить двухбайтовую запись. Или он может загрузить слово, изменить два байта и записать слово обратно. На архитектурах, где запись байтов стоит дорого, последняя вполне вероятна.

Теперь предположим, что ваша реализация выполняет последнее. Предположим далее, что ваше деление вектора оставляет первую половину слова в одной части, а вторую половину слова - в другой. Наконец, предположим, что оба потока пытаются изменить это слово одновременно. Это может пойти не так - они могут оба прочитать одно и то же значение, оба изменить его, но тогда одна запись произойдет раньше другой, поэтому одна из модификаций будет перезаписана и потеряна.

Атомный байтовый доступ по умолчанию не универсален, и я сомневаюсь, что любая реализация делает атомарный битовый доступ по умолчанию. Таким образом, vector<bool> является возможной проблемой, даже если другие типы векторов безопасны: ваше деление вектора может быть меньше середины байта. Не то, чтобы вы обычно сортировали по-другому, но есть другие операции, в которых вы можете попытаться разделить векторы, или ваш код может быть универсальным.

Обычно можно ожидать, что доступ к словам будет атомарным (и в C или C ++, int доступ). Но это не гарантируется стандартом языка, поэтому sig_atomic_t. Вы говорите, что cmp - это функция сравнения int, которая предполагает, что, возможно, ваш вектор содержит целые числа. Но вы можете сравнивать шорты с помощью функции сравнения int, так что я не знаю.

Что вам действительно нужно сделать, так это тщательно проверить вашу реализацию / платформу и посмотреть, что она говорит о безопасном доступе к памяти из нескольких потоков. Это, вероятно, хорошо для вектора int.

Answer 3

технически стандарт говорит, что эти классы не являются потокобезопасными, поэтому, если вы устанавливаете данные из таких вещей, как оператор [], то технически это множественные записи в один объект. С другой стороны, безопасно работать с отдельными частями массива c ... так что, похоже, здесь есть конфликт. Если вы хотите быть чистым, берите адрес первого элемента и рассматривайте его как c-массив. Многие ответы здесь говорят, что это нормально, если вы находитесь в отдельных частях массива, и хотя это, вероятно, верно для многих реализаций

-> Я думаю, важно отметить, что реализация бесплатна, не делайте это безопасным.

Answer 4

Вы можете использовать параллельный режим GCC (если вы используете GCC) для многопоточных версий различных алгоритмов. http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html

Answer 5

У вас не должно быть проблем, если потоки работают с непересекающимися частями вектора.