Improving "shuffle" efficiency

Question

Right now, I am using the following code to create a Shuffle extension:

public static class SiteItemExtensions
{
    public static void Shuffle<T>(this IList<T> list)
    {
        var rng = new Random();
        int n = list.Count;
        while (n > 1)
        {
            n--;
            int k = rng.Next(n + 1);
            T value = list[k];
            list[k] = list[n];
            list[n] = value;
        }
    }
}

I am looking for a way more faster and efficient way to do this. Right now, using the Stopwatch class, it is taking about 20 seconds to shuffle 100,000,000 items. Does anyone have any ideas to make this faster?

Answer 1

This highlights an aspect of modern computer design that's often overlooked. It can be made over 3 times faster by a silly change:

            int k = 0; rng.Next(n + 1);  // silly change

There are now more statements in the inner loop but it is much faster. What you are seeing is the effect of the CPU cache. This algorithm has very poor cache locality, the odds that the next element to be read from the array is already in the cache is very low. Which takes an expensive trip to the slower outer caches and the dead-slow memory bus. The odds that elements from the array needed later are loaded into the cache is very high. But the odds that they are still there when needed is very low, your list is simply too large the fit the cache.

Nothing can be done to fix this, it is inherent in the algorithm design. Using realistic list sizes is however an obvious solution. Running it 100,000 times on a list with a 1000 elements is 3 times as fast.