Problem with Random and Threads in .NET

Question

I'm having trouble with the Random class in .NET, I'm implementing a threaded collection which is working fine, except for one smaller detail. The collection is a Skip list and those of you familiar with it know that for every node inserted I need to generate a new height that is <= CurrentMaxHeight+1, here's the code that I'm using to do that (I know it's very inefficient, but it works and thats my main priority now)

int randomLevel()
{
  int height = 1;

  while(rnd.NextDouble() >= 0.5 && height < MaxHeight)
    ++height;

  return height;
}

My problem here is that sometimes I keep getting only 1 back from this for several thousand elements in a row which kills the performance of the skip list. The chance for 10.000 elements to generate only 1 from this method in a row, seems very slim (happens pretty consistently).

So I'm assuming (guessing) that there is a problem with the Random object in some way, but I don't really know where to start digging around. So I turn to stackoverflow to see if anyone has an idea?

Edit

The rnd-variable is declared in the class SkipList<T>, and it is accessed from several threads (each thread calls .Add on the collection and Add calls .randomLevel)

Answer 1

Try locking the Random object.

int RandomLevel()
{
    int height = 1;

    lock(rnd)
    {
        while(rnd.NextDouble >= 0.5 && height < MaxHeight) height++;
    }

    return height;
}

There may be an issue with collisions when multiple threads access the Random object at the same time, and the seed might be getting corrupted. I can't offer any insight into what might be specifically happening, but according to MSDN, instance members of the Random type are not guaranteed to be thread-safe, so a lock seems called for in any event.

Answer 2

I wouldn't lock the entire while loop. Just lock the rnd.NextDouble() calls.

int RandomLevel()
{
  int height = 1;
  double newRand;

  lock(rnd) { newRand = rnd.NextDouble(); }

  while(newRand >= 0.5 && height < MaxHeight)
  {
    height++;
    lock(rnd) { newRand = rnd.NextDouble(); }
  }

  return height;
}

Although if performance is a consideration, I would certainly compare both solutions, as there might be a difference in single threaded vs. multithreaded performance.