TPL 學習日記(7): Thread-Safe Collections

Parallel library 是一個多執行緒的一套 API，因此在使用時，也需要遵守多執行緒程式的規則。

以下，是一個「找出3 到 5,00,000 之間有多少個質數」的解法。

單一執行緒

首先，我們當然要寫出單一執行緒的作法，再寫成多執行緒的作法。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading.Tasks;
using System.Collections.Concurrent;

namespace TPL_1 {
  class Program {
    static void Main(string[] args) {
      //單一執行緒
      Console.WriteLine(Time(
    () =>
    {
      List<int> primes = new List<int>();
      for (int i = 0; i < 2000000; i++)
      {
        if (IsPrime(i)) primes.Add(i);
      }
      Console.WriteLine("Count = " + primes.Count);
    }
  ));
    }
    /// <summary>
    /// 是否為質數
    /// </summary>
    /// <param name="input"></param>
    /// <returns></returns>
    static bool IsPrime(int input) {
      int bound = (int)Math.Sqrt(input);
      for (int i = 2; i <= bound; i++)
      {
        if (input % i == 0) return false;
      }
      return true;
    }

    static TimeSpan Time(Action a) {
      Stopwatch w = Stopwatch.StartNew();
      a();
      return w.Elapsed;
    }
  }
}

程式碼很簡單，其實就是將所有的質數找出並加進到一個使用 List<int> 的 instant 中(即 primes)，並在最後算出總共有348515個質數。

使用 Parallel library (Wrong)

這次要使用 Parallel library。由之前的經驗，我們會寫成下面的程式碼。

static void Main(string[] args) {
      //單一執行緒
      Console.WriteLine(Time(
    () =>
    {
      List<int> primes = new List<int>();
      for (int i = 0; i < 5000000; i++) {
        if (IsPrime(i)) primes.Add(i);
      }
      Console.WriteLine("Count = " + primes.Count);
    }
  ));
      Console.WriteLine(Time(
          () =>
          {
            var primes = new List<int>();
            Parallel.For(0, 5000000, i =>
            {
              lock(primes) //Watch this line
                if (IsPrime(i)) primes.Add(i);
            });
            Console.WriteLine("Count = " + primes.Count);
          }
        ));
    }

注意到 //Watch this line 的那一行。由於在寫 multi thread 程式, concurrent 非常重要，我加了 lock(primes) 讓存取 primes 可避免掉一致性的問題。結果呢，Multithread 竟然比 Single thread 還慢！真不可思議。

使用 Parallel library (Correct)

不要自己發明輪子。上面例子的問題，是自行使用 lock 來解決 concurrency 的問題。如果是在 TPL 的世界中，該問題就應使用 System.Collection.Concurrent namespace 內的集合。以下範例加上新的解法 (BlockingCollection)

static void Main(string[] args) {
      //單一執行緒
      Console.WriteLine(Time(
    () =>
    {
      List<int> primes = new List<int>();
      for (int i = 0; i < 5000000; i++) {
        if (IsPrime(i)) primes.Add(i);
      }
      Console.WriteLine("Count = " + primes.Count);
    }
  ));
      Console.WriteLine(Time(
          () =>
          {
            var primes = new List<int>();
            Parallel.For(0, 5000000, i =>
            {
              lock(primes)
                if (IsPrime(i)) primes.Add(i);
            });
            Console.WriteLine("Count = " + primes.Count);
          }
        ));
      Console.WriteLine(Time(
          () =>
          {
            var primes = new BlockingCollection<int>();
            Parallel.For(0, 5000000, i =>
            {
              if (IsPrime(i)) primes.Add(i);
            });
            Console.WriteLine("Count = " + primes.Count);
          }
        ));
    }

程式執行結果如下

結論

TPL 的程式已經很棒了，但有些細節的部份仍然要相當小心，否則甚至比不用還差。