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

It looks as though your loop runs less than half the time it's called - is that what you're looking for (when a random number between 0 and 1 is > 0.5? This could explain why you're getting "1" more often than you'd expect - at least half the time, it's not even running the loop that increments height - it just sets the height to 1, doesn't change it, and then returns "1". I'm not familiar with skip lists, so this might be intentional, but I thought I'd ask.

I'm not too familiar with working with random numbers, but is it possible that you've got a seeding problem? If you're not randomizing the Random object when you instantiate it, it may return a predictable stream of numbers, instead of ones that are truly random. Perhaps not causing the behavior you're seeing here, but something to consider moving forward.

Answer 3

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.