Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / C++ Новый топик    Ответить
 оптимизировать доступ к массиву для многопоточного приложения  [new]
baden_baden
Member

Откуда:
Сообщений: 48
Есть массив int, разные потоки считывают или записывают информацию.
Запись происходит в 3-8 раз реже, чем считывание.
Можно ли, исходя из такого соотношения для чтения и записи сделать что-то более быстрое, чем, например, блокировка с помощью mutex, atomic или spinlock?
18 май 17, 23:07    [20494418]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 43647

Можно вообще забить на синхронизацию. Выравненный int читается и пишется современными
процессорами атомарно. Чтобы компилятор не умничал - объявить этот массив volatile.

Posted via ActualForum NNTP Server 1.5

19 май 17, 00:03    [20494496]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
baden_baden
Member

Откуда:
Сообщений: 48
Dimitry Sibiryakov,

Нет никакой необходимости писать
std::atomic_int ai[10];
, достаточно лишь написать
volatile int ai[10];
и всё будет автоматически синхронизировано?

А как поступать, если это не массив, а
std::map<std::string, int> msi;
19 май 17, 00:58    [20494554]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
CEMb
Member

Откуда: public T{};
Сообщений: 1647
а если так:
std::map<std::string, std::atomic<int>> msi;
?
19 май 17, 05:08    [20494606]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
m_Sla
Member

Откуда:
Сообщений: 2696
посмотри https://github.com/khizmax/libcds
её разрабатывает один местный дядька

З.Ы. тема неоднократно поднималась, например http://www.sql.ru/forum/1253390/kakuu-biblioteku-posovetuete-s-potokobezopasnymi-konteynerami
19 май 17, 05:42    [20494612]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
Dima T
Member

Откуда:
Сообщений: 11302
baden_baden
всё будет автоматически синхронизировано?

Ты бы поподробней описал что конкретно понимаешь под "синхронизировано".

volatile гарантирует только что в итоге что-то будет записано и в случае с int это "что-то" будет из одного потока, т.е. если два потока сделают одновременно
a[0] = x;

то в итоге в a[0] запишется x одного из двух потоков, неизвестно какого, но итого точно не будет смесью значений x разных потоков.

Атомарность - это еще изменение, т.е. "прочитать-изменить-записать" это единая операция, которую volatile не гарантирует.

Если два потока выполнят
a[0]++;

в результате при std::atomic_int гарантированно будет +2, а с volatile может оказаться +1

В этой книге есть пара глав разъясняющих разницу между volatile и std::atomic

baden_baden
А как поступать, если это не массив, а
std::map<std::string, int> msi;

Чтение/запись элементов std::map можно делать одновременно с разных потоков, но добавление/удаление элементов только под блокировкой, в т.ч. запрещающей чтение/запись.

Для read-write блокировок есть std::shared_mutex, правда не везде.
19 май 17, 07:47    [20494655]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 2127
baden_baden
Есть массив int, разные потоки считывают или записывают информацию.
Запись происходит в 3-8 раз реже, чем считывание.
Можно ли, исходя из такого соотношения для чтения и записи сделать что-то более быстрое, чем, например, блокировка с помощью mutex, atomic или spinlock?


ReadWriteLock C++
19 май 17, 09:18    [20494870]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
Dima T
Member

Откуда:
Сообщений: 11302
kealon(Ruslan)
ReadWriteLock C++

Где-то читал почему std::shared_mutex только в С++17 решили добавить: оказывается это не панацея при коротких блокировках на чтение, т.к. постоянное изменение счетчика читающих само по себе тормоз, плюс усложнение логики. В таких ситуациях std::mutex может выигрывать по скорости.
19 май 17, 10:03    [20495028]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
baden_baden
Member

Откуда:
Сообщений: 48
Dima T
Для read-write блокировок есть std::shared_mutex, правда не везде.

Он эффективнее, чем
std::atomic<int>
?

std::map<std::string, std::atomic<int>> msi;

Про него я в курсе, только вопрос в том, есть ли что-то более быстрое.

ReadWriteLock C++
https://github.com/khizmax/libcds

Спасибо, посмотрю.
19 май 17, 10:23    [20495171]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
Dima T
Member

Откуда:
Сообщений: 11302
baden_baden
Dima T
Для read-write блокировок есть std::shared_mutex, правда не везде.

Он эффективнее, чем
std::atomic<int>
?

Зависит от задачи, которую ты не описал. ОС тоже не указал. Поэтому обсуждаем скорость сферических коней в вакууме.
19 май 17, 10:32    [20495219]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
Dima T
Member

Откуда:
Сообщений: 11302
std::unordered_map быстрее чем std::map

PS Ты бы привел простенький пример кода, который ускоряешь. Тогда можно будет подсказывать что лучше использовать. Есть еще другие ньюансы влияющие на скорость, например выравнивание по кэшлинии проца. Тут замеры делал.
19 май 17, 10:39    [20495252]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
baden_baden
Member

Откуда:
Сообщений: 48
автор
Зависит от задачи, которую ты не описал. ОС тоже не указал. Поэтому обсуждаем скорость сферических коней в вакууме.

Интересует именно "скорость сферических коней в вакууме".
std::unordered_map быстрее чем std::map

Хорошо, контейнер заменили. А как уже в нём увеличить скорость при наличии только операций чтения и записи (чтение встречается чаще)?

P.S. Посмотрю ссылки.
19 май 17, 10:53    [20495352]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
Dima T
Member

Откуда:
Сообщений: 11302
baden_baden
Интересует именно "скорость сферических коней в вакууме".

Если бы был один универсальный способ, то все им бы и пользовались. Но его нет, поэтому надо рассматривать конкретный случай.
baden_baden
Хорошо, контейнер заменили. А как уже в нём увеличить скорость при наличии только операций чтения и записи (чтение встречается чаще)?

Если нет добавления и удаления элементов контейнера, не надо атомарного изменения значений, то быстрее всего
std::unordered_map<std::string, int> msi;
19 май 17, 11:27    [20495563]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 2127
Dima T
kealon(Ruslan)
ReadWriteLock C++

Где-то читал почему std::shared_mutex только в С++17 решили добавить: оказывается это не панацея при коротких блокировках на чтение, т.к. постоянное изменение счетчика читающих само по себе тормоз, плюс усложнение логики. В таких ситуациях std::mutex может выигрывать по скорости.


хм, не учёл что у него запись чтение в массив, которые очень быстрые операции - ReadWriteLock действительно излишен наверное, std::mutex или критической секции за глаза хватит.

Если недостаточно текущего технического предела - 40 млн локов/c, то как вариант можно предложить сделать блокировки на отдельные куски массива. Но опять же если будут частые обращения в один и тот же кусок, упрёмся в тех предел
19 май 17, 11:57    [20495705]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
ну я
Member

Откуда: Stalingrad
Сообщений: 1102
Dimitry Sibiryakov
Можно вообще забить на синхронизацию. Выравненный int читается и пишется современными
процессорами атомарно. Чтобы компилятор не умничал - объявить этот массив volatile.

Если записывается значение, вычисленное на основании этого же или других значений - то забить нельзя, и нужны либо блокировки либо доступ через interlocked функции (или примитивы компилятора). А технически, собсно сама запись - так оно конечно, вот только ТС не указал, в чем причина блокировки.
19 май 17, 12:22    [20495822]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 33435
Dimitry Sibiryakov
Чтобы компилятор не умничал - объявить этот массив volatile.


Не поможет
19 май 17, 14:59    [20496713]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 33435
baden_baden
Есть массив int, разные потоки считывают или записывают информацию.
Запись происходит в 3-8 раз реже, чем считывание.
Можно ли, исходя из такого соотношения для чтения и записи сделать что-то более быстрое, чем, например, блокировка с помощью mutex, atomic или spinlock?


На самом деле если это так, то и один мьютекс только на запись уже будет достаточно быстр.
Т.е. если сделать разделяемое чтение и блокирующую чтение запись. Как -- прямо сейчас не соображу, но можно.
Семафор там или что...

Если массив маленький, скажем, несколько тысяч, можно его перезаписывать целиком, а не поэлементно, может тоже дать прирост.
19 май 17, 15:02    [20496731]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
mayton
Member

Откуда: loopback
Сообщений: 35512
baden_baden
Есть массив int, разные потоки считывают или записывают информацию.
Запись происходит в 3-8 раз реже, чем считывание.
Можно ли, исходя из такого соотношения для чтения и записи сделать что-то более быстрое, чем, например, блокировка с помощью mutex, atomic или spinlock?

Тут все очень сильно зависит от смысла задачи.
Действительно ли потокам нужно видеть синхронное изменнение разделяемого ресурса?

Если каждому потоку дать копию своего массивчика но организовать между ними
протокол обновления (по времени) или по событию (наполнение очереди)
то можно снизить накладные расходы на мутексы и все прочие
"прямые" решения.
19 май 17, 18:32    [20497405]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
Bred eFeM
Member

Откуда:
Сообщений: 519
baden_baden
Запись происходит в 3-8 раз реже, чем считывание.
реже - это частота, а для понимания сути происходящего нужен коэффициент заполнения.

Можно ли, исходя из такого соотношения для чтения и записи
соотношения - это, возможно, скважность.

1/8 .. 1/3 времени уходит на саму запись - ускоряйте запись.
А если на ожидание доступа к записи - SRW lock вкупе с ограничением единичного чтения/записи в алгоритме.

что-то более быстрое
быстее atomic не будет.
19 май 17, 19:14    [20497462]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
Common Lisp
Member

Откуда:
Сообщений: 68
Dima T
volatile гарантирует только что в итоге что-то будет записано
volatile гарантирует только то, что сайд-эффекты от вычислений будут происходить в строгом соответствии с абстрактной машиной из стандарта.
20 май 17, 14:41    [20498379]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
Common Lisp
Member

Откуда:
Сообщений: 68
Лучшая оптимизация доступа к общему ресурсу из многопоточного приложения это отсутствие такого общего ресурса.
20 май 17, 14:47    [20498383]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
CEMb
Member

Откуда: public T{};
Сообщений: 1647
Common Lisp
Лучшая оптимизация доступа к общему ресурсу из многопоточного приложения это отсутствие такого общего ресурса.
А если у меня несколько массивов данных динамической длины, которые надо обрабатывать в реалтайме, и при этом показывать 30 кадров в секунду во весь экран? о_о
22 май 17, 05:24    [20500103]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
Изопропил
Member

Откуда:
Сообщений: 30305
CEMb
Common Lisp
Лучшая оптимизация доступа к общему ресурсу из многопоточного приложения это отсутствие такого общего ресурса.
А если у меня несколько массивов данных динамической длины, которые надо обрабатывать в реалтайме, и при этом показывать 30 кадров в секунду во весь экран? о_о


что за обработка и что рисовать нужно?
22 май 17, 08:48    [20500221]     Ответить | Цитировать Сообщить модератору
 Re: оптимизировать доступ к массиву для многопоточного приложения  [new]
CEMb
Member

Откуда: public T{};
Сообщений: 1647
Изопропил
что за обработка и что рисовать нужно?
10K окружностей с физическими свойствами соударяются в 2-мерном пространстве, в зависимости от силы удара или разлетаются, или слепляются в одну или разбиваются на две. Один поток считает, второй рисует.
22 май 17, 11:21    [20500730]     Ответить | Цитировать Сообщить модератору
Все форумы / C++ Ответить