casuale genera numero 1 oltre il 90% di volte in parallelo

Question

consideri il seguente programma:

public class Program 
{ 
    private static Random _rnd = new Random(); 
    private static readonly int ITERATIONS = 5000000; 
    private static readonly int RANDOM_MAX = 101; 

    public static void Main(string[] args) 
    { 
      ConcurrentDictionary<int,int> dic = new ConcurrentDictionary<int,int>(); 

      Parallel.For(0, ITERATIONS, _ => dic.AddOrUpdate(_rnd.Next(1, RANDOM_MAX), 1, (k, v) => v + 1)); 

      foreach(var kv in dic) 
      Console.WriteLine("{0} -> {1:0.00}%", kv.Key, ((double)kv.Value/ITERATIONS) * 100); 
    } 
} 

Ciò stamperà il seguente output:

(nota che l'uscita varierà ogni esecuzione)

> 1 -> 97,38% 
> 2 -> 0,03% 
> 3 -> 0,03% 
> 4 -> 0,03% 
... 
> 99 -> 0,03% 
> 100 -> 0,03% 

Perché il numero 1 generato con tale frequenza?

Answer 1

Random è non thread safe.

Next non fa nulla di speciale per garantire la sicurezza del filo.

Non utilizzare Random come questo. E non prendere in considerazione l'utilizzo della durata di archiviazione locale del thread, altrimenti si rovinano le proprietà statistiche del generatore: È necessario utilizzare solo un'istanza Random. Un approccio sarà quello di utilizzare lock(_global) e disegnare un numero in quella regione bloccata.

I pensare cosa sta succedendo qui è che il primo filo di raggiungere il generatore ottiene i suoi numeri casuali generati correttamente, e tutte le discussioni successive ricevono 0 per ogni disegno. Con un pool di thread di "parallelizzazione" di 32 thread, i rapporti che citi sopra sono approssimativamente stimati; supponendo che i risultati per i 31 thread siano posizionati nel primo bucket.

Answer 2

Beh, Random classe non è thread-safe uno, il modo più semplice fuori è quello di rendere filo locale (ogni thread ha proprioRandom esempio):

private static ThreadLocal<Random> m_rnd = new ThreadLocal<Random>(() => new Random()); 

private static Random _rnd { 
    get { 
    return m_rnd.Value; 
    } 
} 

https://msdn.microsoft.com/en-us/library/system.random(v=vs.110).aspx#ThreadSafety

Answer 3

Facendo un passo avanti rispetto alla soluzione di archiviazione locale del thread e cercando di evitare il problema statistico, suggerisco di utilizzare un seme casuale generato da RNGCryptoServiceProvider:

using System; 
using System.Collections.Concurrent; 
using System.Threading; 
using System.Threading.Tasks; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 

     private static readonly int ITERATIONS = 5000000; 
     private static readonly int RANDOM_MAX = 101; 

     private static int GetCriptoRandom() 
     { 
      using (var rng = new System.Security.Cryptography.RNGCryptoServiceProvider()) 
      { 
       byte[] bytes = new byte[4]; 
       rng.GetBytes(bytes); 
       return BitConverter.ToInt32(bytes, 0); 
      } 
     } 

     private static ThreadLocal<Random> m_rnd = new ThreadLocal<Random>(() => new Random(GetCryptoRandom())); 

     private static Random _rnd 
     { 
      get 
      { 
       return m_rnd.Value; 
      } 
     } 

     static void Main(string[] args) 
     { 
      ConcurrentDictionary<int, int> dic = new ConcurrentDictionary<int, int>(); 
      Parallel.For(1, ITERATIONS, _ => dic.AddOrUpdate(_rnd.Next(1, RANDOM_MAX), 1, (k, v) => v + 1)); 
      foreach (var kv in dic) 
       Console.WriteLine("{0} -> {1:0.00}%", kv.Key, ((double)kv.Value/ITERATIONS) * 100); 

     } 
    } 
} 

Sembra statisticamente corretto, i risultati vanno dallo 0,99% all'1,01%.

Answer 4

Random non è thread-safe - non è necessario utilizzare la stessa istanza Random da più thread senza sincronizzazione.

Perché stai ricevendo 1 in particolare? Bene, il modo in cui funziona Random (in 4.5.2) consiste nel mantenere un array di seed e due indexer. Quando lo usi simultaneamente da più thread, il tuo seed array si incasina e quasi sempre ottieni valori identici in più slot. L'operazione di base fa qualcosa come seed[a] - seed[b] e quando questi valori sono uguali, si ottiene lo zero indietro. Dal momento che hai chiesto 1 come minimo, questo zero è spostato su uno - e c'è la tua anomalia. Ciò avviene molto rapidamente in un ambiente multi-core, dal momento che c'è un bel po 'di stato interdipendente che viene aggiornato su ogni chiamata Next.

Ci sono molti modi per risolvere questo problema. Uno è quello di sincronizzare l'accesso a un'istanza comune Random - ha senso solo se stai facendo relativamente pochi randoms, però, nel qual caso non useresti comunque lo Parallel. Se le prestazioni sono un problema, è necessario aggiungere qualche forma di pre-recupero (ad esempio, preparare i numeri casuali in batch, per thread o utilizzando una coda concorrente) o utilizzare qualche altro metodo.

Un altro modo è mantenere un'istanza separata Random per ogni thread. Ciò richiede di selezionare attentamente un seme per ognuna delle istanze, tuttavia, altrimenti i numeri casuali potrebbero non essere casuali. L'approccio utilizzato in .NET stesso (ancora, usando il codice 4.5.2 come riferimento) è quello di utilizzare Thread.CurrentThread.ManagedThreadId come seed, che funziona piuttosto bene. Un altro approccio comune consiste nell'utilizzare una singola istanza globale (sincronizzata) Random per inizializzare i semi degli altri Random s, ma a seconda delle esigenze, potrebbe essere necessario assicurarsi che non vengano prodotti semi duplicati.

Naturalmente, è possibile utilizzare anche un altro generatore di numeri casuali. Tuttavia, i generatori pseudo casuali di solito richiedono gli stessi approcci di Random - dipendono fortemente dal loro stato; questo è ciò che li rende pseudo-casuali in primo luogo. Un generatore di crittografia potrebbe funzionare meglio, ma quelli tendono ad essere molto lenti e possono comunque ricorrere all'approccio sincronizzato, specialmente se non c'è supporto hardware.

In alcuni casi, ha senso distribuire i lavori di generazione secondo alcune regole ragionevoli. Ad esempio, se si utilizza la generazione procedurale pseudo-casuale per le risorse di gioco, può essere opportuno stabilire regole esplicite su come i generatori diversi vengono seminati, in modo ripetibile - naturalmente, questo significa anche che non si può realmente usare Parallel entrambi, e dovrai essere un po 'più esplicito.