Вопрос о использовании Random в многопоточном приложении

← →
31512 © (2009-10-09 21:25) [0]

Здравствуйте, Уважаемые.
Меня интересует опыт использования функции Random в многопоточных приложениях при интенсивном её использовании.
Краткое описание проблемы.
Имеется статистическая модель, использующая метод Монте-Карло и реализованная на языке Delphi. При некоторых конфигурациях модели требуется (для получения хорошей статистики) колоссальное количество экспериментов. Речь идёт о миллиардах испытаний, что, разумеется, не обходится без солидных временных затрат. 3 млд. испытаний занимает в среднем 1 час 25 минут. Таких конфигураций нужно насчитать много. Однако, итоговые статистические матрицы обладают свойством аддитивности, что позволяет накапливать статистику частями. Т.е., если имеется двухпроцессорная машина с Xeon по 4 ядра, то запускаем 8 потоков по 375 млн. испытаний, а потом складываем результат и нормируем на общее число испытаний.
Эксперимент показал, что при таком подходе 3 млд. испытаний накапливается всего за полчаса. Однако расчёт, по полученным таким образом статданным, поплыл. Для одного объекта дал завышенный результат, для другого заниженный. И в общем физически ничем не обоснованный. Считая всё это в одном, главном, потоке приложения результат великолепный.
Тут я вспомним свою битву, когда переписывал модель на С++ для Linux. Копаясь в дебрях документации gcc обнаружил, что генератор случайных чисел в Linux очень навороченный. Там есть функции для получения случайных чисел в разных потоках отдельно (суффикс _r) и в "однопоточных" приложениях отдельно.

Всё тщательно проверено и грешить остаётся только на "проседание" Random при её интенсивном использовании из нескольких потоков.

Randomize вызывается 1 раз при старте программы.

Отсюда и возникают вопросы.
1. Есть ли подводные камни при использовании Random из нескольких потоков одновременно?
2. Нет ли в Windows API "потокобезопастного" Random?

← →
KilkennyCat © (2009-10-09 21:39) [1]

Random можно считать генератором случайности с большой натяжкой. Для серъезных опытов используют внешние генераторы.

← →
palva © (2009-10-09 21:40) [2]

1. Конечно есть. Обычно используется конгруэнтный метод, а он предполагает хранение предыдущего выработанного случайного числа. Если вам нужен потокобезопасный метод, то храните это число для каждого потока свое. То есть напишите свою функцию с использованием слова threadvar

← →
DVM © (2009-10-09 21:44) [3]

> 2. Нет ли в Windows API "потокобезопастного" Random?

GetTickCount + QueryPerfomanceCounter + Загрузка ЦП + свободная память + Количество потоков + Трафик + Движения мыши + Нажатые клавиши + Количество окон и т.д. продолдать можно бесконечно. Берешь все вместе, к этому применяешь что-то вроде синуса и оборачиваешь критической секцией.

← →
31512 © (2009-10-09 21:50) [4]

> KilkennyCat © (09.10.09 21:39) [1]

Сейчас экспериментирую с этим.

> palva © (09.10.09 21:40) [2]

threadvar тут не причём. У меня описан класс потока статистики и использую я не переменные, а поля класса.
Вопрос в другом. Если я использую Random во множестве потоков и каждый из потоков интенсивно использует это функцию, то не происходит ли того, то Random начинает выдавать в разных потоках одно и то же число. Именно так это описано в документации Linux.
Как я понял (если всё правильно понял), из своего маленького исследования, Random в Delphi использует CoCreateGUID. B если кванты времени между двумя вызовами Random очень малы, то он генерит число близкое к предыдущему.
Пытаюсь разобраться.

← →
DVM © (2009-10-09 21:53) [5]

> Random в Delphi использует CoCreateGUID. B если кванты времени
> между двумя вызовами Random очень малы, то он генерит число
> близкое к предыдущему.

CoCreateGUID использует время потому что

← →
31512 © (2009-10-09 22:00) [6]

С двумя потоками получилось 42 минуты на 3 млд. экспериментов.
8 потоков давали полчаса. Интересный результат.

← →
palva © (2009-10-09 22:07) [7]

> не происходит ли того, то Random начинает выдавать в разных потоках одно и то же число

Теоретически это вполне возможно.

> threadvar тут не причём

threadvar один из способов решить проблему. У вас генератор внутри класса? Как я понимаю это в разы снижает производительность. Если для такой пустяковой функции, как выработка очередного, числа требуется обратиться к свойству, то это ухудшит производительность раза в два... Но это так, замечание в сторону. Вопрос в том как хранить предыдущее выработанное число свое для каждого потока. Если treadvar не подходит храните его не внутри функции, а вместе с переменными потока. У вас же есть такие переменные (всякие счетчики), которые свои для каждого потока. Вот вместе с ними и храните. И передавайте как дополнительный параметр функции random. Хотя на вашем месте я и функцию такую не писал бы, а прямо вставил формулу в код. Время бы сэкономил.

← →
palva © (2009-10-09 22:11) [8]

> Random в Delphi использует CoCreateGUID

Если так (с удивлением об этом узнал), то откажитесь от Random Delphi, - сэкономите время. Есть много других отличных и простых генераторов.

← →
palva © (2009-10-09 22:15) [9]

> Random в Delphi использует CoCreateGUID

Может, Randomize использует? Тогда другое дело.

← →
31512 © (2009-10-09 22:57) [10]

> palva © (09.10.09 22:11) [8]

Скорее я чего-то неправильно понял.

← →
TUser © (2009-10-09 23:01) [11]

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

К каким общим ресурсам еще обращаются потоки?

← →
31512 © (2009-10-09 23:07) [12]

> palva © (09.10.09 22:07) [7]

В внутри класса у меня нет генератора случайных чисел. Я использую Random.
В том-то всё и дело. Сейчас изучаю генераторы случайных чисел, которые смог найти в сети. Но все они так или иначе в итоге используют Random.
Или такой вот эксклюзив:
procedure TMaster.DoGenerate(Sender:TObject); var i:Integer; g:array[0..4] of TGUID; b:array[0..63] of Byte absolute g; AList:TStrings; procedure FillRandBools; var j,k:Integer; begin with lbBool do begin Clear; AList:=Items; end; for j:=Low(b) to High(b) do for k:=0 to 7 do AList.Add(TrueFalse[b[j] and (1 shl k) > 0]); end; procedure FillRandInts; var j:Integer; begin with lbInt do begin Clear; AList:=Items; end; for j:=Low(b) to High(b) do AList.Add(IntToStr(b[j])); end; begin for i:=Low(g) to High(g) do CreateGUID(g[i]); FillRandBools; FillRandInts; end;

> TUser © (09.10.09 23:01) [11]

Потоки абсолютно независимы.
> то етсь если ситуация заывисит от порядка работы потоков

Никак не зависит. Это просто n независимых задач. По окончании работы потоков матрицы суммируются.
На двух потоках отклонение существенно меньше, чем на восьми.

Идеально только в одном потоке.

> результата должен быть б.м. случаен.

Результат совершенно не должен быть случаен, поскольку оцениваются математические ожидания физических величин.
Вспомни дифракцию электронов на решётке.

Я посмотрел в System.pas, как всё это устроено.
Промежуточное значение хранится в переменной
RandSeed: longint
и хранится не потокобезопасно.
Вы можете хранить ее в своих переменных потока и перед обращением к Random войти в критическую секцию, переменную RandSeed записать из своей переменной, а после обращения снова сохранить у себя и выйти из критической секции. Так будет потокобезопасно. Но насколько это скажется на производительности - не знаю.

> Но все они так или иначе в итоге используют Random.

Это вы зря. Ищите сишную реализацию и переделывайте на паскале. А зачем вам это нужно? Вас что, не устраивает линейный конгруэнтный метод?

Вот здесь интересные примеры:
http://www.gnu.org/software/gsl/manual/html_node/Random-number-generator-algorithms.html
Но найдете еще, если не будете ограничиваться паскалем.

> palva © (09.10.09 23:25) [14]

Ок. Вот что я сделал. Я перенёс всю логику в поток. Загнал туда же генератор случайных чисел из ALGLIB. В принципе это дало больший квант времени между обращениями к Random.
Результат: теперь 3 млд. на восьми ядрах считается не за полчаса, а за 14 минут.
Сходимость результатов:

1.45337418476940E+0002 (8 потоков)/1.45362162532453E+0002 (0 потоков) = 99.982977650385824621397117929928%

Твой подход спытаю непременно чуть позже.

> Твой подход спытаю непременно чуть позже.

И не надо. Наверняка медленнее будет.

> palva © (09.10.09 23:54)
Это будет не наверняка, а точно медленнее, поскольку каждому потоку придётся ждать, когда любой другой потока не "освободит Random". Поэкспериментировать, однако, тоже полезно будет.

Вопрос о использовании Random в многопоточном приложении Найти похожие ветки