обновить целочисленные элементы массива C ++ - PullRequest
Новая
       68

обновить целочисленные элементы массива C ++

0 голосов
/ 05 февраля 2019

Учитывая общий массив счетчиков целых чисел, мне интересно знать, может ли поток атомарно извлечь и добавить элемент массива, не блокируя весь массив?

Вот иллюстрация рабочей модели, которая использует мьютекс для блокировкидоступ ко всему массиву. 

// thread-shared class members
std::mutex count_array_mutex_;
std::vector<int> counter_array_( 100ish );

// Thread critical section
int counter_index = ... // unpredictable index
int current_count;
{
  std::lock_guard<std::mutex> lock(count_array_mutex_);
  current_count = counter_array_[counter_index] ++;
}
// ... do stuff using current_count.

Мне бы хотелось, чтобы несколько потоков могли одновременно извлекать и добавлять отдельные элементы массива.

Пока что в моем исследовании std::atomic<int> IСкинул, что при построении атомного объекта также конструирует защищенный член.(И множество ответов, объясняющих, почему вы не можете сделать std::vector<std::atomic<int> >)

Ответы [ 2 ]

0 голосов
/ 06 февраля 2019

C ++ 20 / C ++ 2a (или как вы хотите это называть) добавит std::atomic_ref<T>, что позволит вам выполнять атомарные операции над объектом, который не был atomic<T> для начала.

недоступно пока как часть стандартной библиотеки для большинства компиляторов, но есть рабочая реализация для gcc / clang/ ICC / другие компиляторы с расширениями GNU.

Раньше атомарный доступ к «простым» данным был доступен только с некоторыми специфичными для платформы функциями, такими как Microsoft LONG InterlockedExchange(LONG volatile *Target, LONG Value); или GNU C / C ++
type __atomic_add_fetch (type *ptr, type val, int memorder) (те же встроенные функции, которые библиотеки C ++ для компиляторов GNU используют для реализации std::atomic<T>.)

http://www.open -std.org / jtc1 / sc22 /wg21 / docs /apers / 2018 / p0019r8.html содержит некоторые вводные материалы о мотивации.Процессоры могут легко это сделать, компиляторы уже могут это сделать, и досадно, что C ++ не предоставляет эту возможность переносимым образом.

Поэтому вместо того, чтобы бороться с C ++, чтобы получить все неатомарное распределение и initСделано в конструкторе, вы можете просто при каждом доступе создавать atomic_ref для элемента, к которому вы хотите получить доступ.(Создавать его как локальный экземпляр можно, по крайней мере, когда он не блокируется, в любых «обычных» реализациях C ++).

Это даже позволит вам делать такие вещи, как изменение размера std::vector<int> после того, как вы обеспечитедругие потоки не обращаются к элементам вектора или к самому блоку управления vector.И тогда вы можете просигнализировать другим потокам о возобновлении.

Это еще не реализовано в libstdc ++ или libc ++ для gcc / clang. 

#include <vector>
#include <atomic>

#define Foo std   // this atomic_ref.hpp puts it in namespace Foo, not std.
// current raw url for https://github.com/ORNL/cpp-proposals-pub/blob/master/P0019/atomic_ref.hpp
#include "https://raw.githubusercontent.com/ORNL/cpp-proposals-pub/580934e3b8cf886e09accedbb25e8be2d83304ae/P0019/atomic_ref.hpp"


void inc_element(std::vector<int> &v, size_t idx)
{
    v[idx]++;
}

void atomic_inc_element(std::vector<int> &v, size_t idx)
{
    std::atomic_ref<int> elem(v[idx]);
    static_assert(decltype(elem)::is_always_lock_free,
           "performance is going to suck without lock-free atomic_ref<T>");

    elem.fetch_add(1, std::memory_order_relaxed);  // take your pick of memory order here
}

Для x86-64,они компилируются точно так, как мы надеемся с GCC, используя пример реализации (для компиляторов, реализующих расширения GNU), связанный в предложении рабочей группы C ++.https://github.com/ORNL/cpp-proposals-pub/blob/master/P0019/atomic_ref.hpp

Из проводника компилятора Godbolt с g ++ 8.2 -Wall -O3 -std=gnu++2a: 

inc_element(std::vector<int, std::allocator<int> >&, unsigned long):
    mov       rax, QWORD PTR [rdi]          # load the pointer member of std::vector
    add       DWORD PTR [rax+rsi*4], 1      # and index it as a memory destination
    ret

atomic_inc_element(std::vector<int, std::allocator<int> >&, unsigned long):
    mov       rax, QWORD PTR [rdi]
    lock add  DWORD PTR [rax+rsi*4], 1     # same but atomic RMW
    ret

Атомная версия идентична, за исключениемон использует префикс lock, чтобы сделать чтение-изменение-запись атомарным, , убедившись, что никакое другое ядро ​​не может прочитать или записать строку кэша, пока это ядро ​​находится в процессе атомарной модификации. Просто вЕсли вам интересно, как атомы работают в asm.

Большинство ISA, отличных от x86, таких как AArch64, конечно, требуют цикла повторения LL / SC для реализации атомарного RMW, даже с ослабленным порядком памяти.

Суть в том, что создание / уничтожение atomic_ref ничего не стоит. Его указатель на член полностью оптимизируется.Так что это ровно так же дешево, как и vector<atomic<int>>, но без головной боли.

Пока вы осторожны, не создавайте UB для гонки данных, изменяя размер вектора или получая доступэлемент без , проходящий через atomic_ref.(Это потенциально может проявиться как использование после освобождения во многих реальных реализациях, если std :: vector перераспределяет память параллельно с другим потоком, индексирующим в нем, и, конечно, вы бы атомарно модифицировали устаревшую копию.)

Это, безусловно, дает вам возможность повеситься, если вы не будете уважать тот факт, что сам объект std::vector не является атомарным, а также что компилятор не помешает вам сделать неатомарный доступ к основномуv[idx] после того, как другие потоки начали использовать его.

0 голосов
/ 05 февраля 2019

В одну сторону: 

// Create.
std::vector<std::atomic<int>> v(100);
// Initialize.
for(auto& e : v)
    e.store(0, std::memory_order_relaxed);

// Atomically increment.
auto unpredictable_index = std::rand() % v.size();
int old = v[unpredictable_index].fetch_add(1, std::memory_order_relaxed);

Обратите внимание, что std::atomic<> конструктор копирования удаляется, поэтому вектор нельзя изменить в размере и его необходимо инициализировать с помощью окончательного числа элементов.

Поскольку функция изменения размера std::vector потеряна, вместо std::vector вы также можете использовать std::unique_ptr<std::atomic<int>[]>, например: 

// Create.
unsigned const N = 100;
std::unique_ptr<std::atomic<int>[]> p(new std::atomic<int>[N]);
// Initialize.
for(unsigned i = 0; i < N; ++i)
    p[i].store(0, std::memory_order_relaxed);

// Atomically increment.
auto unpredictable_index = std::rand() % N;
int old = p[unpredictable_index].fetch_add(1, std::memory_order_relaxed);
...