When shuffling large arrays, how much time can be attributed to random number generation?

It is well known that contemporary computers don't like to randomly access data in an unpredictible manner in memory. However, not all forms of random accesses are equally harmful. Suppose that the array is large. Take an array made of 100 million elements. It far exceeds the CPU cache on the machines I own.