Примеры использования и тестирования потокобезопасного указателя и неконкурентного общего мьютекса В этой статье мы покажем: дополнительные оптимизации, варианты использования и тестирование разработанного нами поточно-ориентированного указателя с оптимизированным общим мьютексом.
contfree_safe_ptr - это эквивалент Safe_ptr > В конце мы покажем сравнительные графики тестов нашего поточно-ориентированного указателя и некоторых лучших lock-free алгоритмов из libCDS на процессорах Intel Core i5/i7, Xeon, 2 x Xeon. Три похожие статьи:
- Обеспечение потокобезопасности любого объекта
- Ускорение std::shared_mutex в 10 раз
- Потокобезопасный std::map с производительностью карты без блокировок
Различная степень детализации замка
Сначала покажем, как оптимально использовать Shared-Mutex, на примере работы с таблицей (массивом структур).Обратимся к опыту промышленных СУБД.
Например, в СУБД MSSQL используются блокировки различной детализации – блокировка: одной или нескольких строк, страницы, экстента, одного раздела таблицы, индекса, всей таблицы, всей базы данных.
https://technet.microsoft.com/en-us/library/ms189849(v=sql.105).
aspx Действительно, если мы долго работаем с одной строкой и нам важно, чтобы строка не была изменена в это время другим потоком, то нет необходимости все это время блокировать всю таблицу - достаточно заблокировать только 1 ряд.
- Заблокируйте всю таблицу с помощью общей блокировки
- Ищем нужную строку или несколько строк
- Затем блокируем найденную строку
- Разблокировать стол
- И мы работаем с заблокированной линией
До сих пор мы использовали только блокировку на уровне таблицы, т. е.
блокировали одну или несколько таблиц.
Или все таблицы, использованные в выражении, были автоматически заблокированы до его завершения.
В других случаях мы вручную блокировали одну или несколько таблиц с помощью объектов блокировки RAII до истечения срока действия ( область действия блока ) этих замков (пока они не будут уничтожены):(*safe_map_1)["apple"].first = "fruit"; // locked Table-1 (safe_map_1) // unlocked Table-1 safe_map_1->at("apple").
second = safe_map_1->at("apple").
second * 2; // locked Table-1 (safe_map_1) // unlocked Table-1 safe_map_1->at("apple").
second = safe_map_2->at("apple").
second*2; // locked Table-1(safe_map_1) and Table-2(safe_map_2) // unlocked Table-1 and Table-2
{
std::lock_guard<decltype(safe_map_1)> lock(safe_map_1); // locked Table-1 (safe_map_1)
(*safe_map_1)["apple"].
first = "fruit";
safe_map_1->at("apple").
second =
safe_map_1->at("apple").
second * 2;
// unlocked Table-1
}
{
lock_timed_any_infinity lock_all(safe_map_1, safe_map_2);
// locked Table-1(safe_map_1) and Table-2(safe_map_2)
safe_map_1->at("apple").
second =
safe_map_2->at("apple").
second*2; //locked Table-1(safe_map_1) and Table-2(safe_map_2)
safe_map_1->at("potato").
second =
safe_map_2->at("potato").
second*2; //locked Table-1(safe_map_1) and Table-2(safe_map_2)
// unlocked Table-1 and Table-2
}
Давайте рассмотрим пример, в котором мы случайным образом выбираем индекс для вставки, затем случайным образом выбираем одну из четырех операций (вставка, удаление, обновление, чтение) и выполняем ее с потокобезопасным объектом типа contfree_safe_ptr .
Пример: [37] coliru.stacked-crooked.com/a/5b68b65bf2c5abeb В этом случае мы наложим на таблицу следующие блокировки:
- Вставка – эксклюзивный замок
- Удалить – эксклюзивная блокировка
- Обновление – эксклюзивный замок
- Чтение – Общая блокировка
- Заблокировать всю таблицу (xlock для обновления, slock для чтения)
- Ищем нужную строку, читаем или меняем ее
- Разблокировать стол
int const rnd_index = index_distribution(generator); // 0 - container_size
int const num_op = operation_distribution(generator);// insert_op, update_op, delete_op, read_op
switch (num_op) {
case insert_op: {
safe_map->emplace(rnd_index, (field_t(rnd_index, rnd_index))); // insert with X-lock on Table
break;
}
case delete_op: {
size_t erased_elements = safe_map->erase(rnd_index); // erase with X-lock on Table
}
break;
case update_op: {
auto x_safe_map = xlock_safe_ptr(safe_map); // X-lock on Table
auto it = x_safe_map->find(rnd_index);
if (it != x_safe_map->cend()) {
it->second.money += rnd_index; // still X-lock on Table (must necessarily be)
}
}
break;
case read_op: {
auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table
auto it = s_safe_map->find(rnd_index);
if (it != s_safe_map->cend()) {
volatile int money = it->second.money; // still S-lock on Table (must necessarily be)
// volatile here only to avoid optimization for unused money-variable
}
}
break;
default: std::cout << "\n wrong way! \n"; break;
}Теперь мы убедимся, что во время операции обновления таблица блокируется блокировкой чтения (общей), а не блокировкой изменения (эксклюзивной).
Это значительно ускорит операции обновления при использовании нашего «общего мьютекса без конфликтов записи», который мы разработали ранее.
В этом случае несколько потоков смогут одновременно выполнять операции обновления и чтения в одной таблице.
Например, один поток читает одну строку, а другой поток изменяет другую строку.
Но если один поток пытается изменить ту же строку, которую читает другой поток, то во избежание гонок за данными мы должны блокировать саму строку при ее чтении и при ее изменении.
Пример: [38] coliru.stacked-crooked.com/a/89f5ebd2d96296d3 Теперь для операций обновления или чтения мы делаем:
- Заблокируйте всю таблицу с помощью общей блокировки
- Ищем нужную строку или несколько строк
- Затем блокируем найденную строку (xlock для Update, slock для Read)
- И работаем с заблокированной строкой (X/S-lock) и заблокированной таблицей (S-lock)
- Разблокировать линию
- Разблокировать стол
Код для одной итерации нашего примера-2:
int const rnd_index = index_distribution(generator); // 0 - container_size
int const num_op = operation_distribution(generator);// insert_op, update_op, delete_op, read_op
switch (num_op) {
case insert_op: {
safe_map->emplace(rnd_index, (field_t(rnd_index, rnd_index))); // insert with X-lock on Table
break;
}
case delete_op: {
size_t erased_elements = safe_map->erase(rnd_index); // erase with X-lock on Table
}
break;
case update_op: {
auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table
auto it = s_safe_map->find(rnd_index);
if (it != s_safe_map->cend()) {
auto x_field = xlock_safe_ptr(it->second);
x_field->money += rnd_index; // X-lock on field, still S-lock on Table (must necessarily be)
}
}
break;
case read_op: {
auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table
auto it = s_safe_map->find(rnd_index);
if (it != s_safe_map->cend()) {
auto s_field = slock_safe_ptr(it->second);
volatile int money = s_field->money; // S-lock on field, still S-lock on Table (must necessarily be)
// volatile here only to avoid optimization for unused money-variable
}
}
break;
default: std::cout << "\n wrong way! \n"; break;
}Здесь для потокобезопасной работы со строкой мы использовали Safe_obj. безопасный_объект содержит объект типа T, а не указатель на него, как в Safe_ptr .
Поэтому при использовании Safe_obj нет необходимости отдельно выделять память под сам объект и менять атомарный счетчик ссылок, как это требуется в Safe_ptr. Таким образом, операции вставки и удаления при использовании Safe_obj выполняются намного быстрее, чем при использовании Safe_ptr. Стоит отметить, что при копировании Safe_obj копируется не указатель на объект, а сам объект, предварительно заблокировав источник и место назначения Safe_obj. Примечание.
Строго говоря, мы блокируем не всю строку, а все поля строки, за исключением индекса строки, по которому мы ищем.
Вот почему мы назвали наш объект полем, а не строкой.
А также подчеркнуть, что таким образом мы можем заблокировать не только одну строку, но даже отдельные поля в одной строке, если поместим их в отдельные объекты Safe_obj. Это позволит различным потокам блокировать разные поля и работать над ними параллельно.
Теперь мы используем следующие блокировки для разных операций: 
Этот пример очень быстр для большого количества кратковременных операций.
Но мы по-прежнему удерживаем блокировку чтения (общую) для таблицы при изменении или чтении строки (поля).
А если у нас будут редкие, но очень длительные операции над строками таблицы, то блокировка будет держаться на всей таблице долгое время.
Однако если по логике вашей задачи не важно, чтобы строка могла быть удалена одним потоком, пока другой поток читает или модифицирует эту же строку, то нам достаточно заблокировать таблицу на время поиска строки.
И чтобы избежать доступа к освобожденной памяти, когда другой поток удалил строку, нам нужно использовать std::shared_ptr. — указатель с атомарным потокобезопасным счетчиком ссылок.
В этом случае память будет освобождена только тогда, когда ни один поток не имеет указателей на эту строку.
Вместо Safe_obj мы будем использовать Safe_ptr для защиты строки.
Это позволит нам скопировать указатель на строку и использовать потокобезопасный счетчик ссылок в std::shared_ptr. который содержится в Safe_ptr. Пример: [39] coliru.stacked-crooked.com/a/f2a051abfbfd2716 Теперь для операций обновления или чтения мы делаем:
- Заблокируйте всю таблицу с помощью общей блокировки
- Ищем нужную строку или несколько строк
- Затем блокируем найденную строку (xlock для Update, slock для Read)
- Разблокировать стол
- И работаем с заблокированной линией (X/S-lock) столько времени, сколько потребуется.
- Разблокировать линию
Пример-3:
int const rnd_index = index_distribution(generator); // 0 - container_size
int const num_op = operation_distribution(generator);// insert_op, update_op, delete_op, read_op
safe_ptr_field_t safe_nullptr;
switch (num_op) {
case insert_op: {
safe_map->emplace(rnd_index, (field_t(rnd_index, rnd_index))); // insert with X-lock on Table
break;
}
case delete_op: {
size_t erased_elements = safe_map->erase(rnd_index); // erase with X-lock on Table
}
break;
case update_op: {
auto pair_result = [&]() {
auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table
auto it = s_safe_map->find(rnd_index);
if (it != s_safe_map->cend()) return std::make_pair(it->second, true); // found
else return std::make_pair(safe_nullptr, false); // null-value
}(); // unlock Table
if(pair_result.second) {
auto x_field = xlock_safe_ptr(pair_result.first); // X-lock on field
x_field->money += rnd_index; // if a long time is read
} // unlock field
}
break;
case read_op: {
auto pair_result = [&]() {
auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table
auto it = s_safe_map->find(rnd_index);
if (it != s_safe_map->cend()) return std::make_pair(it->second, true); // found
else return std::make_pair(safe_nullptr, false); // null-value
}(); // unlock Table
if(pair_result.second) {
auto s_field = slock_safe_ptr(pair_result.first); // S-lock on field
volatile int money = s_field->money; // if a long time is read
// volatile here only to avoid optimization for unused money-variable
} // unlock field
}
break;
default: std::cout << "\n wrong way! \n"; break;
}Хорошо спроектированные многопоточные программы используют короткие доступы к разделяемым объектам, поэтому в дальнейшем мы будем использовать не последний, а предпоследний пример для коротких операций чтения.
Недостатки выполнения вокруг идиомы
Давайте посмотрим на возможные проблемы и покритикуем наш код. В предыдущей главе мы рассмотрели достаточно удобный и высокопроизводительный пример, явно задающий тип блокировки для операций Update и Read с помощью функций:- slock_safe_ptr() - только для чтения
- xlock_safe_ptr() – для чтения и изменения
Пример: [40] coliru.stacked-crooked.com/a/89f5ebd2d96296d3 Но вы можете забыть использовать явные блокировки для операций обновления и чтения.
В этом случае Safe_ptr будет разблокирован сразу после завершения операции поиска, после чего вы продолжите использовать:
- найден итератор, который может быть признан недействительным другим потоком
- или найденный элемент, который может быть удален другим потоком
safe_hide_obj<field_t, spinlock_t> field_hide_tmp;
//safe_obj<field_t, spinlock_t> &field_tmp = field_hide_tmp; // conversion denied - compile-time error
//field_hide_tmp->money = 10; // access denied - compile-time error
auto x_field = xlock_safe_ptr(field_hide_tmp); // locked until x_field is alive
x_field->money = 10; // access grantedПример: [41] coliru.stacked-crooked.com/a/d65deacecfe2636b Если бы раньше вы могли ошибиться и написать следующее - ошибочный код:
auto it = safe_map->find(rnd_index); // X-lock, find(), X-unlock
if (it != s_safe_map->cend())
volatile int money = it->second ->money; // X-lock, operator=(), X-unlockТеперь такой вызов не будет компилироваться и потребует явной блокировки объектов — правильный код:
auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table
auto it = s_safe_map->find(rnd_index);
if (it != s_safe_map->cend()) {
auto s_field = slock_safe_ptr(it->second);
volatile int money = s_field->money; // S-lock on field, still S-lock on Table
// volatile here only to avoid optimization for unused money-variable
} // S-unlock Table, S-unlock fieldОднако у вас все еще есть опасность использовать замки как временные объекты — неправильный :
auto it = slock_safe_ptr(safe_map)->find(rnd_index); // S-lock, find(), S-unlock
if (it != s_safe_map->cend()) {
volatile int money = slock_safe_ptr(it->second)->money; // S-lock, =, S-unlock
}У вас есть выбор:
- Использовать Safe_ptr И безопасный_объект для возможности явно или автоматически (Executearound Idiom) заблокировать ваш объект
- Или используйте Safe_hide_ptr И Safe_hide_obj оставив только возможность явно заблокировать ваш объект
- используйте удобную автоматическую блокировку (Executearound Idiom)
- или немного снизить вероятность ошибки, обязав объект явно блокироваться
- вставить_или_назначить() — если элемент есть, то назначаем его, если нет, то вставляем
- try_emplace() — если элемента нет, то создать элемент
- слияние() - объединить 2 карты в 1
- извлекать() – получить элемент и удалить его с карты
В общем, отказ от итераторов для всех контейнеров (кроме std::array и std::vector) очень помогает при создании многопоточных программ.
Чем реже вы используете итераторы, тем меньше вероятность, что вы получите доступ к итератору, признанному недействительным тем или иным потоком.
Но сама идея итераторов не противоречит идее многопоточности, например поддержка СУБД (Oracle, MSSQL).
курсоры (аналоги итераторов) и разные уровни изоляции транзакций (разная многопоточность).
Но что бы вы ни выбрали: используйте «Выполнение вокруг идиомы», используйте явные блокировки для Safe_hide_ptr , откажитесь от них и используйте стандартные блокировки std::mutex. или даже напишите свои собственные алгоритмы без блокировок — у вас всегда есть много возможностей ошибиться.
Разделение таблицы еще больше повышает производительность.
Вернемся еще раз к опыту промышленных реляционных СУБД.
Например, СУБД может использовать секционирование таблиц для повышения производительности.
В этом случае вместо всей таблицы можно заблокировать только используемый раздел: https://technet.microsoft.com/en-us/library/ms187504(v=sql.105).
aspx Хотя в СУБД вся таблица обычно не блокируется для операций удаления и вставки, это всегда справедливо для операций удаления.
А вот для операций Insert можно выполнить очень быструю загрузку данных в таблицу, обязательным условием которой является монопольная блокировка таблицы:
- MS SQL (трассировка dbcc (610, -1)): INSERT INTO sales_hist With ( ТАБЛОКX )
- Oracle: ВСТАВИТЬ /*+ ДОБАВИТЬ */ INTO sales_hist https://docs.oracle.com/cd/E18283_01/server.112/e17120/tables004.htm#i1009887
Вопросы блокировки с помощью INSERT с прямым путем Во время INSERT по прямому пути база данных получает монопольные блокировки таблицы (или всех разделов секционированной таблицы).
В результате пользователи не могут выполнять какие-либо одновременные операции вставки, обновления или удаления в таблице, а одновременные операции создания и построения индекса не допускаются.
Однако параллельные запросы поддерживаются, но запрос вернет только информацию до операции вставки.
Но теперь попробуем заблокировать только часть нашего контейнера.
Попробуем реализовать собственный секционированный упорядоченный ассоциативный массив partsed_map и посмотрим, насколько увеличится производительность.
Мы заблокируем только тот раздел, который нужен в данный момент. Смысл: станд::карта< safe_ptr > > Вот первый станд::карта будет постоянным и будет содержать разделы (подтаблицы).
Это будет очень упрощенный пример, где количество секций задается в конструкторе и в дальнейшем не меняется.
Каждый раздел представляет собой потокобезопасный ассоциативный массив.
Safe_ptr > .
Для максимальной производительности количество разделов и их диапазоны должны быть такими, чтобы вероятность доступа к каждому разделу была одинаковой.
Если у вас диапазон ключей 0 - 1000000, и вероятность запросов на чтение/обновление/вставку/удаление до начала диапазона больше, чем до конца диапазона, то разделов с небольшим значением ключа должно быть больше , и их диапазоны должны быть меньше.
Например, 3 секции: [0 – 100000], [100001 – 400000], [400001 – 1000000].
Но в наших примерах мы будем предполагать, что ключи запроса имеют равномерное распределение.
Диапазоны разделов можно указать двумя способами:
- Safe_map_partitioned_t Safe_map { "а", "f", "k", "p", "u" };
программа будет работать корректно.
Пример: [42] coliru.stacked-crooked.com/a/fc148b08eb4b0580 Кроме того, для максимальной производительности вам необходимо использовать «бесконфликтный общий мьютекс», который мы ранее реализовали внутри.
Safe_ptr<> , то есть смысл такой: станд::карта< contfree_safe_ptr > > Давайте возьмем код из предыдущего примера и добавим код contfree_safe_ptr из предыдущей главы.
Заменить: Safe_map_partitioned_t > Включено: Safe_map_partitioned_t , contfree_safe_ptr > Пример: [43] coliru.stacked-crooked.com/a/23a1f7a3982063a1 Мы сделали это Safe_map_partitioned_t<> класс «Просто ради интереса», т.е.
в реальных программах его использовать не рекомендуется.
Мы только что показали пример того, как можно реализовать собственные алгоритмы на основе contfree_safe_ptr.<> указатель и contention_free_shared_mutex<> замок.
Как использовать
Сначала скачайте файл Safe_ptr.h из корня репозитория: github.com/AlexeyAB/object_threadsafe Затем включите этот файл в свой файл cpp: #include "safe_ptr.h" В качестве оптимального варианта использования мы остановимся на приведенном выше примере 2 — он прост и очень продуктивен: struct field_t {
int money, time;
field_t(int m, int t) : money(m), time(t) {}
field_t() : money(0), time(0) {}
};
typedef safe_obj<field_t, spinlock_t> safe_obj_field_t;
// thread-safe ordered std::map by using execute around pointer idiom with contention-free shared-lock
contfree_safe_ptr< std::map<int, safe_obj_field_t > > safe_map_contfree;
bool success_op;
switch (num_op) {
case insert_op:
slock_safe_ptr(test_map)->find(rnd_index); // find for pre-cache to L1 with temprorary S-lock
test_map->emplace(rnd_index, field_t(rnd_index, rnd_index));
break;
case delete_op:
slock_safe_ptr(test_map)->find(rnd_index); // find for pre-cache to L1 with temprorary S-lock
success_op = test_map->erase(rnd_index);
break;
case read_op: {
auto s_safe_map = slock_safe_ptr(test_map); // S-lock on Table (must necessarily be)
auto it = s_safe_map->find(rnd_index);
if (it != s_safe_map->cend()) {
auto x_field = xlock_safe_ptr(it->second);
volatile int money = x_field->money; // get value
x_field->money += 10; // update value
}
}
break;
default: std::cout << "\n wrong way! \n"; break;
}Вставка и удаление – изменение карты : Поскольку наша общая блокировка slock_safe_ptr() максимально быстрая, то еще до изменения (insert_op или delete_op) мы находим элемент, который нам нужно удалить, или ближайший к тому, который нам нужно вставить, с помощью slock_safe_ptr(), что разблокируется сразу после операции find().
Мы не используем результат этой операции напрямую, но эта операция простоя сообщает процессору, какие данные необходимо кэшировать в кэше L1 для последующих изменений карты.
Далее мы выполняем test_map-> emplace() для вставки или test_map-> erase() для удаления, и эти операции автоматически вызывают эксклюзивную блокировку на время их выполнения.
Вставка/удаление - происходит быстро, потому что почти все данные уже есть в кеше этого ядра, а еще есть большой плюс - нам не нужно постоянно поднимать Shared-lock до Exclusive-lock (это может сильно увеличить шанс тупик - вечное зависание программы).
Чтение и обновление — (чтение карты) и чтение или изменение одного элемента : То, что мы называем чтением (read_op) в нашем конкретном примере — это чтение и последующее изменение одного элемента с карты (одной строки с карты).
Перед чтением мы размещаем на карте общую блокировку slock_safe_ptr(), чтобы другие потоки не могли удалять или заменять какие-либо элементы на карте.
И, удерживая общую блокировку, пока существует объект s_safe_map, мы находим нужный элемент и применяем эксклюзивную блокировку xlock_safe_ptr() только к этому одному элементу, затем читаем его и изменяем.
После этого, когда мы выходим из области {}, сначала уничтожается объект x_field и с элемента снимается эксклюзивная блокировка, а затем уничтожается объект s_safe_map и снимается общая блокировка с карты.
Компилятор позволяет нам совершать любые операции с test_map — читать или изменять его и вызывать любые его методы — в этом случае автоматически применяется монопольная блокировка.
Но компилятор позволит вам читать только объект, объявленный как const или присвоенный константной ссылке.
auto const& some_ptr = test_map; например, вы можете позвонить some_ptr-> find(); и общая блокировка будет автоматически применена на всё время выполнения выражения, но для константной ссылки вы не сможете сделать следующее some_ptr-> emplace(); .
Соответственно, вы не сможете изменить объект, пока он автоматически защищен общей блокировкой.
Аналогичное поведение при явной блокировке slock_safe_ptr(test_map) , вы сможете выполнить slock_safe_ptr(test_map)-> find(); , но при попытке скомпилировать slock_safe_ptr(test_map)-> emplace(); - будет ошибка.
Все это гарантирует правильный автоматический выбор блокировок и корректную работу многопоточной программы.
Все это и даже больше описано в первой статье.
Сравнение производительности полученных реализаций Safe_ptr
Подведем промежуточные итоги.Давайте покажем, насколько улучшилась производительность благодаря нашим оптимизациям.
Приведем графики производительности – количества миллионов операций в секунду (МОпс) с разным процентом операций модификации 0 – 90%.
При модификации с равной вероятностью будет выполнена одна из трех операций: вставка, удаление, обновление (правда, операция Update не меняет само дерево std::map, а меняет только одну из его строк).
Например, при 15% модификаций это будут следующие операции: 5% вставка, 5% удаление, 5% обновление, 85% чтение.
Используемый компилятор: g++ 4.9.2 (Linux Ubuntu) x86_64. Вы можете скачать этот тест для Linux (GCC 4.9.2) и Windows (MSVS2015): github.com/AlexeyAB/object_threadsafe/tree/master/benchmark Для компиляции в Clang++ 3.8.0 в Linux вам необходимо изменить Makefile. Приведем пример тестирования на 16 потоках для одного серверного процессора Intel Xeon E5-2660 v3 2,6 ГГц.
Прежде всего нас интересует оранжевая линия: безопасный &rowlock .
Если у вас установлено более одного процессора, то командная строка для запуска: numactl --localalloc --cpunodebind=0 .
/benchmark 16 Если у вас установлен один процессор, просто запустите: .
/тест 
Заключение:
- Интересно, что наша общая блокировка contfree в contfree_safe_ptr значительно быстрее, чем стандартный std::shared_mutex в Safe_ptr
- Также интересно, что начиная с 15% изменений std::mutex быстрее, чем std::shared_mutex (а именно Safe_ptr быстрее, чем Safe_ptr
-
Rails 4. Гибкая Веб-Разработка
19 Oct, 24 -
Анализ Безопасности Маршрутизатора Smart Box
19 Oct, 24 -
Как Яд Закрывает Счета?
19 Oct, 24
