<p>Most of your poor performance is because you're creating a new random number generator for every random number.  I got a 7x speed increase by only creating one.  I also merged all the code into a single function to maximize the optimization from .net.  The final result is just under 10x faster (117 seconds to 12 for 80,000,000 items on my 32-bit Win7 virtual machine).  </p>

<pre><code>Friend Sub Shuffle(ByRef Buffer As Integer())
    Dim _random As New System.Random
    For max As Integer = Buffer.Length - 1 To 1 Step -1
        Dim random As Integer = _random.Next(1, max)
        Dim temp As Integer = Buffer(max)
        Buffer(max) = Buffer(random)
        Buffer(random) = temp
    Next
End Sub
</code></pre>

<p>Note a lock is not needed for the random number generator because each call to Shuffle has its own copy and isn't shared across threads.</p>

<p>70% of the time is spent reading the value from Buffer(random).  This is because it's likely not in the CPU cache and has to hit main memory whereas reading Buffer(max) is only .5% because it's being read sequentially descending and the CPU can pre-read it into cache.  20% is in calculating the random number so with a faster generator, you can save a little more time but not much.</p>

<p>The big win would be an algorithm that didn't randomly access the array for every element.  I followed the advice of Hans Passant in the question comments and googled <a href="https://arxiv.org/pdf/1508.03167.pdf" rel="nofollow noreferrer">MergeShuffle</a>.  It seems to be just such an algorithm (multiple sequential accesses instead of a random single pass).  And in addition to allowing partitioning, it does not require more RAM.</p>

<p>I prototyped it and I saw a 20% speed up with 80M items switching to Fisher-Yates at 2.5M items.</p>
Faster Scramble Millions Numbers
<p>I need to scramble HUGE integer arrays (from 1,000,000 to 80,000,000 elements).</p>

<p>These arrays are sequential created (1 to n step 1) and I need to ensure that no one sequential number is lost - and because of it I cannot create "random numbers" arrays.</p>

<p>So, I create them using a single FOR-NEXT (it takes very low time, about 2ms) and I utilize the Fisher-Yates-Durnstenfeld shuffle algorithm, as follows.</p>

<p>First I create the array:</p>

<pre><code> dim Huge(0 to 80,000,000) as Integer
 For x as integer = 1 to 79,999,999
     Huge(x) = x
 Next
</code></pre>

<p>It takes really few miliseconds to be created...</p>

<p>After, I scramble the numbers:</p>

<pre><code>    Shuffle(Huge)
</code></pre>

<p>where Shuffle is <strong>a routine called in a Parallel/Multitasking environment</strong>. Because of this, I need to LOCK the RANDOM function (to provide good entropy in swaping values and locations) utilized in Fisher-Yates-Durstenfeld routine :</p>

<h1>The Fisher-Yates Shuffle</h1>

<pre class="lang-vb prettyprint-override"><code>Friend Sub Shuffle(ByRef Buffer As Integer())
  For max As Integer = Buffer.Length - 1 To 1 Step -1
      ExtractRandomItem(Buffer, max)
  Next
End Sub

Friend Sub ExtractRandomItem(ByRef buffer As Integer(), max As Integer)
  Dim random As Integer = GetRandomNumber(max + 1)
  If random = max Then
     random -= 1
  End If

  Dim temp As Integer = buffer(max)
  buffer(max) = buffer(random)
  buffer(random) = temp
End Sub

Friend Function GetRandomNumber(max As Integer) As Integer
  Dim _random As New System.Random
  SyncLock _random
      Return _random.Next(1,max)
  End SyncLock
End Function
</code></pre>

<h2>My problem</h2>

<p>This shuffle routine is pretty good to scramble randomly the array, but, if it takes only 2ms to scramble 8192 elements, for <strong>24,000,000 elements it takes 32 seconds</strong> - too much time for my needs. </p>

<p><strong>Do you know any way to enhance this process and make it faster?</strong></p>

<p><strong>Or do you know another non-deterministic shuffle algorithm to work faster than that I have?</strong></p>

<p>Note: <em>I had already tried PARALLEL.FOR and I had no expressive gain anyway (just few miliseconds in fact)</em>.</p>

<p>And I don't really need "random-like" shuffle but just a non-deterministic  ordering.</p>

<p>Thanks for any help</p>

<p><strong>UPDATE</strong></p>

<p>Due to relevant comments of Jdweng and Hans, I feel it's interesting to make an appointment:</p>

<ul>
<li><p>The routine works with 2 arrays at same time (an input and an output) and each of them may have until 32 mega-elements (> 33 millions each one), which cause .NET to allocate almost 1Gb of RAM. It's not my choice, but the system requirement, sometimes. </p></li>
<li><p>So, I need avoid to create a new array to substitute the SWAP operation to an  in -> out operation...</p></li>
</ul>

<p><strong>UPDATE II</strong></p>

<p>Some guys had recommended good practices, but they are not eligible to solve the problem. Let me discuss each of them:</p>

<ul>
<li><p><strong>Using different arrays</strong>: this procedure may save some clocks-by-operation avoiding swap (3 ops) for using move between array A and B. But it will require to double the RAM request (two identical matrices). It's not an option using huge matrix over NET-Framework memory allocation schema (which require free consecutive blocks of memory).</p></li>
<li><p><strong>Using MergedShuffle algorithm</strong>: it seems to be the most desirable solution but I'm affraid of having the shuffle separated "by pieces of the matrix", since this schema works on pieces of the matrix based on their middle points. I need to study it deeper to understand the whole process.</p></li>
<li><p><strong>Using parallel on pieces of the main array</strong>: it is not an option since the shuffle will comply only the imposed range - in other words, I won't have the last elements shuffled with the initial elements of the array. It can be seen as a kind of deterministic schema (not an option).</p></li>
</ul>