многопоточность

Question

Я пишу числовую программу, которая должна быть несколько быстрой, а также многопоточной. У меня есть класс, который представляет число, и я хочу использовать в нем генератор случайных чисел. Теперь мне не нужно, чтобы мой ГСЧ был истинным ГСЧ, мне просто нужно, чтобы он генерировал целые числа с равномерным распределением между 0 и NMAX.

Итак, у меня есть в классе:

// use just an int here and forget about multithreading.
static uint32 rand = NMAX/4; 
// this will be called multithreadedly
static uint32 GetRand() { return rand = ( rand + 1 ) % NMAX; }

Теперь, в однопоточном мире, это совершенно нормально для моих целей.

Поскольку это многопоточность, я предполагаю , что единственно возможная плохая вещь, которая может произойти, это то, что время от времени (например, <1% времени) обновление сбрасывается. Это означает, что два потока читают rand, обновляют его в регистре, возвращают обновленное значение, а затем записывают его дважды с одним и тем же значением. Это совершенно нормально. </p>

Мой вопрос: может ли быть что-нибудь хуже этого? Я полностью согласен с каждым потоком, использующим собственную переменную rand, но это просто огромная боль, чтобы это произошло. Что я определенно не могу сделать, так это сделать так, чтобы каждый экземпляр класса использовал свою собственную переменную rand, поскольку это потребовало бы слишком много памяти.

UPDATE:

Итак, почему я хочу это сделать? Полная история - это класс с плавающей запятой, который использует 1 или 2 байта. Так что это должно быть быстро и так, и это кажется лучшим способом. На самом деле, я думаю, что я обновлю его с ( rand + 1 ) % NMAX до чего-то вроде ( rand + [some prime] ) % NMAX, так как он, кажется, работает лучше. Это пример одного из тех случаев, когда более надежное решение потребовало бы большего количества кода, сделало бы вещи менее общими и более зависимыми, сделало бы код менее понятным и легче разбить, и все для идеи, что «должна использоваться правильная синхронизация» ,

В основном меня беспокоит какая-то странная оптимизация, которую может выполнить компилятор, чтобы обновление rand не просто сбрасывалось, а rand становилось полным мусором. Теперь, когда я думаю об этом, , даже если будет в порядке (способ использования этого числа), так как при следующем использовании GetRand все равно будет% NMAX, ошибка будет вызывать не более одного использования GetRand находиться вне заданного диапазона [0, NMAX). Спасибо за любые ответы.

Answer 1

1. Вы можете использовать TLS, чтобы у каждого потока была «своя» переменная.

__declspec(thread) static uint32 rand = NMAX/4; 
// this will be called multithreadedly
static uint32 GetRand() { return rand = ( rand + 1 ) % NMAX; }

2. В вашем конкретном случае очень легко исправить код, чтобы сделать его поточно-ориентированным.

:

static long rand = NMAX/4; 
// this will be called multithreadedly
static uint32 GetRand() { return InterlockedIncrement(&rand) % NMAX; }

Answer 2

В целях обсуждения давайте предположим следующую реализацию:

• Используется Twister Mersenne (mt19937), который генерирует пакеты по 624 случайных числа на вызов.
• КаждыйЭкземпляр вашего класса (который используется исключительно внутри одного потока) считывает число из пакета и увеличивает счетчик глобального индекса, чтобы следующий вызов (из любого экземпляра) извлек следующий номер в пакете.Когда глобальный индекс достигнет конца массива, ГСЧ будет заблокирован, и будет сгенерирована новая партия из 624 случайных чисел, после чего глобальный индекс будет сброшен.

Мое предложение по улучшению предназначено длякаждый экземпляр для получения, скажем, 16 номеров одновременно.16 чисел не нужно хранить (копировать) внутри экземпляра: вы просто увеличиваете глобальный индекс на 16 (делая их недоступными для других экземпляров), чтобы экземпляр мог использовать их по одному.

Answer 3

У меня все в порядке с каждой нитью используя собственную переменную rand, но это просто огромная боль, чтобы это произошло.

Не обязательно так сложно сделать это таким образом. Некоторые компиляторы (например, GCC) поддерживают локальное хранилище потока , что позволяет каждому потоку иметь собственную копию данной переменной.

Сказав это, я могу подумать только об одной проблеме - mdash; кроме того, который вы упомянули & mdash; с вашим текущим способом сделать это. Если каждый поток запускается на отдельном ядре, а случайное значение сохраняется в нераспространенном кеше каждого ядра, обновления могут не распространяться среди ядер в течение неопределенного периода времени. Вы можете избежать этого, используя барьер памяти (который может быть создан с помощью блокировок), но это, вероятно, ухудшит производительность.

Answer 4

Если два потока вызывают GetRand одновременно, может произойти классическая несинхронизированная ошибка. Например, rand = 10. После того, как два потока вызывают GetRand, ожидается, что rand будет 12, но на самом деле это может быть 11. Если это нормально, вы можете оставить этот код без изменений. Но я думаю, что лучше использовать синхронизацию, потому что без нее и код, и его результат выглядят немного странно. Другое программирование может подумать, что это ошибка.

Редактировать.

rand = ( rand + 1 ) % NMAX;

В худшем случае: два или более потоков читают одну и ту же переменную rand из памяти. Каждый поток локально производит расчет (rand + 1)% NMAX. Затем все потоки возвращают один и тот же результат обратно в память. Это не повреждает значение переменной rand, это не приводит к тому, что эта переменная выходит за пределы области видимости, и генератор чисел продолжит вычислять действительные числа.