C# - 設定Queue Capacity提升使用效率

Queue(佇列)是C#提供的FIFO(First In First Out)的Collection，最先進入的元素會最先被取出，Queue最基本的使用為Enqueue與Dequeue的Function，Enqueue為將資料塞入Queue中，Dequeue則從Queue中取出資料，另外，.Net還提供了Count, Contains, Peek...等Queue相關的屬性與操作讓開發者更容易使用。但這篇重點不是要來推銷Queue有多好用，這篇限量是要告訴大家一個提升Queue使用效率的小方法。

仔細到MSDN看看Queue Class的定義會發現到Queue的Constructor中，除了一般預設的無引數Constructor(Queue())外，和傳入集合的Constructor(Queue(ICollection))，另外還有一個傳入Capacity的Constructor(Queue(Int32))，與GrowFactor的Constructor(Queue(Int32, Single))，(備註：在泛型的Queue<T>中沒有GrowFactor的Constructor(Queue(Int32, Single)))。
一般來說，大家宣告Queue時都選擇使用預設的Constructor，往往不太清楚傳入Capacity的Constructor和預設的差異在哪，限量一開始以為Capacity為設定Queue的最大容量，可是每次測試超過最大容量時都會發現Queue的Size還是會動態成長，經過一番深究後，終於了解Capacity果然是容量沒錯，但它代表的不是最大容量，而是初始容量，限量使用.Net Reflector神器進入看Queue的Source Code，發現Queue Size是會動態增加的(詳見底下Queue.cs)。
一開始用預設Constructor時，Capacity預設為32，GrowFactor預設為2f，
Queue會產生一個長度為32的Array，在Enqueue時如果剛好Array滿了就會SetCapacity Function裡進行動態增加Size的動作，讓我們再進去SetCapacity Function裡面看看，它動態增加的方式是產生一個更大Size的Array，再把原本的Array用Copy的方式複製過去，這樣子複製的效能其實是不太好的，所以如果能夠在預先知道資料的最大數量，限量建議使用傳入Capacity的Constructor搭配GrowFactor，一來當Size小於Capacity時不會進行Array.Copy的動作，二來使用GrowFactor在增加Array Size時會以設定的GrowFactor倍數成長，大幅增加了執行的效能。

Queue.cs

[TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")]
public Queue() : this(0x20, 2f)
{
}


[TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")]
public Queue(int capacity) : this(capacity, 2f)
{
}

public Queue(int capacity, float growFactor)
{
 if (capacity < 0)
 {
  throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
 }
 if ((growFactor < 1.0) || (growFactor > 10.0))
 {
  throw new ArgumentOutOfRangeException("growFactor", Environment.GetResourceString("ArgumentOutOfRange_QueueGrowFactor", new object[] { 1, 10 }));
 }
 this._array = new object[capacity];
 this._head = 0;
 this._tail = 0;
 this._size = 0;
 this._growFactor = (int) (growFactor * 100f);
}

…

public virtual void Enqueue(object obj)
{
 if (this._size == this._array.Length)
 {
  int capacity = (int) ((this._array.Length * this._growFactor) / 100L);
  if (capacity < (this._array.Length + 4))
  {
   capacity = this._array.Length + 4;
  }
  this.SetCapacity(capacity);
 }
 this._array[this._tail] = obj;
 this._tail = (this._tail + 1) % this._array.Length;
 this._size++;
 this._version++;
}

…

private void SetCapacity(int capacity)
{
 object[] destinationArray = new object[capacity];
 if (this._size > 0)
 {
  if (this._head < this._tail)
  {
   Array.Copy(this._array, this._head, destinationArray, 0, this._size);
  }
  else
  {
   Array.Copy(this._array, this._head, destinationArray, 0, this._array.Length - this._head);
   Array.Copy(this._array, 0, destinationArray, this._array.Length - this._head, this._tail);
  }
 }
 this._array = destinationArray;
 this._head = 0;
 this._tail = (this._size == capacity) ? 0 : this._size;
 this._version++;
}

接著限量要發揮研究生的實驗與驗證的精神，看測試看看Queue使用預設Constructor與Capacity的效能差異，以下為比較效能的Code：

QueueCompare.cs

using System;
using System.Collections;
using System.Diagnostics;

namespace ConsoleTest
{
 class Program
 {
  static void Main( String[] args )
  {
   for ( var i = 1 ; i <= 10 ; i++ )
   {
    Console.WriteLine( String.Format( "Round {0}", i ) );
    Round( 5000000, 10000000, 8f );
    Console.WriteLine();
   }

   Console.ReadLine();
  }

  static void Round( Int32 count, Int32 capacity, Single growFactor )
  {
   var watch = new Stopwatch();
   var queue = new Queue();
   watch.Start();
   for ( var i = 0 ; i < count ; i++ )
   {
    queue.Enqueue( i );
   }
   watch.Stop();
   Console.WriteLine( String.Format( "Queue: {0} ms", watch.ElapsedMilliseconds ) );

   watch.Reset();

   var queue2 = new Queue( capacity, growFactor );
   watch.Start();
   for ( var i = 0 ; i < count ; i++ )
   {
    queue2.Enqueue( i );
   }
   watch.Stop();
   Console.WriteLine( String.Format( "Queue with initial capacity: {0} ms", watch.ElapsedMilliseconds ) );
  }
 }
}

QueueCompare中，限量寫了一個Round Function，使用Stopwatch測試兩種Queue在多次Enqueue完後的時間差異，每次實驗跑10 Round，讓我們看看實驗結果：

實驗一描述: 測試當Enqueue數量小於Capacity時兩個Queue的效能差異

實驗一參數設定: 

1. Count: 5000000

2. Capacity: 10000000

3. GrowFactor: 8f
實驗結果:

實驗二描述: 測試當Enqueue數量大於Capacity時兩個Queue的效能差異

實驗二參數設定: 

1. Count: 5000000

2. Capacity: 1000000

3. GrowFactor: 8f
實驗結果:

實驗一的結果可以清楚的看到使用Capacity的Queue效能會比預設的還要好，而實驗二因為Size已經超過Capacity所以兩個Queue的效能差異時好時壞，所以實驗證明使用Capacity時效能會較好。

另外提一點，Queue又可分為一般Queue(針對Object為對象)與泛型Queue<T>(針對T為對象)，在測試的時候，限量有使用過Queue<T>執行測試，發現使用Queue<T>執行動作會比一般的Queue還來的快，其中運作限量還沒仔細看清楚，所以就..............つづく  (続く)。

參考來源：
MSDN - Queue類別