特定範囲の素数の数を求める処理を、C#, .NET, 並列処理で高速化してみます。

ソースコード

Parallelization.zipダウンロード

ダウンロード後、zipファイルを展開し、slnx ファイルを Visual Studio 2026 以降で開いてください。

実行結果

探索範囲: 1-100,000,000

クラス名: SingleThread
分割数  : 1
素数の数: 5,761,455
実行時間: 17.403 秒
速度比  : 1.00

クラス名: UsingProcess
分割数  : 24
素数の数: 5,761,455
実行時間: 1.702 秒
速度比  : 10.22

クラス名: UsingThread
分割数  : 24
素数の数: 5,761,455
実行時間: 1.630 秒
速度比  : 10.68

クラス名: UsingThreadPool
分割数  : 73
素数の数: 5,761,455
実行時間: 1.560 秒
速度比  : 11.16

クラス名: UsingTask
分割数  : 73
素数の数: 5,761,455
実行時間: 1.586 秒
速度比  : 10.98

クラス名: UsingParallelFor
分割数  : 73
素数の数: 5,761,455
実行時間: 1.644 秒
速度比  : 10.59

クラス名: UsingParallelForEach
分割数  : 73
素数の数: 5,761,455
実行時間: 1.594 秒
速度比  : 10.92

クラス名: UsingPartitioner
分割数  : 73
素数の数: 5,761,455
実行時間: 1.538 秒
速度比  : 11.32

手持ちの環境で実行したときの様子です。並列化によって、約11倍の高速化が図れているのが分かると思います。

共通部分

Program.cs
using System.Diagnostics;

namespace Parallelization;

internal static class Program
{
    public static int Main(string[] args)
    {
        // 引数が2個あるとき、子プロセスの処理を実行
        if (args.Length == 2)
            return UsingProcess.ChildProcessMain(args);

        // 探索範囲をセット。引数が1個のときはその値、引数なしのときは1億。
        var searchLength = args.Length == 1 ? int.Parse(args[0]) : 100_000_000;
        Console.WriteLine($"探索範囲: 1-{searchLength:N0}");

        // 処理時間計測と結果出力
        var primes = new Prime[] {
            new SingleThread(),
            new UsingProcess(),
            new UsingThread(),
            new UsingThreadPool(),
            new UsingTask(),
            new UsingParallelFor(),
            new UsingParallelForEach(),
            new UsingPartitioner()
        };
        double? standardTime = null;
        foreach (var prime in primes)
        {
            Console.WriteLine();
            Console.WriteLine($"クラス名: {prime.GetType().Name}");
            var stopwatch = Stopwatch.StartNew();
            var result = prime.Count(searchLength);
            stopwatch.Stop();
            standardTime ??= stopwatch.Elapsed.TotalSeconds;
            Console.WriteLine($"分割数  : {result.Item1}");
            Console.WriteLine($"素数の数: {result.Item2:N0}");
            Console.WriteLine($"実行時間: {stopwatch.Elapsed.TotalSeconds:N3} 秒");
            Console.WriteLine($"速度比  : {standardTime / stopwatch.Elapsed.TotalSeconds:N2}");
        }

        return 0;
    }
}

メイン処理です。それぞれの方法で処理を行い、結果と時間を出力します。

Prime.cs
namespace Parallelization;

internal abstract class Prime
{
    // 素数をカウント
    public abstract (int, int) Count(int searchLength);

    // 範囲内の素数をカウント
    protected static int CountRange(int begin, int end)
    {
        var count = 0;
        for (var num = begin; num < end; num++)
            if (IsPrime(num)) count++;
        return count;
    }

    // 素数かどうか
    private static bool IsPrime(int n)
    {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (var i = 5; i * i <= n; i += 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        return true;
    }

    // 範囲分割
    protected record struct Range(int Begin, int End);

    protected static Range[] SplitRange(int begin, int end, int count)
    {
        // begin はその値を含む、end はその値を含まない。
        // begin = 0, end = 100, count = 3 の場合、戻り値は (0, 33), (33, 66), (66, 100)。
        var ranges = new Range[count];
        var step = (end - begin) / count;
        for (var index = 0; index < count; index++)
            ranges[index] = new Range(begin + index * step, index == count - 1 ? end : begin + (index + 1) * step);
        return ranges;
    }
}

ベースクラスです。範囲内の素数を求める、範囲分割するなどの共通処理が書かれています。

並列化なし

SingleThread.cs
namespace Parallelization;

internal class SingleThread : Prime
{
    public override (int, int) Count(int searchLength)
    {
        var result = CountRange(1, searchLength + 1);
        return (1, result);
    }
}

そのまま集計関数を呼び出しています。

Processクラスを利用

UsingProcess.cs
using System.Diagnostics;

namespace Parallelization;

internal class UsingProcess : Prime
{
    public override (int, int) Count(int searchLength)
    {
        // タスクを分割
        var ranges = SplitRange(1, searchLength + 1, Environment.ProcessorCount);

        // 子プロセスを開始
        var processes = new List<Process>();
        foreach (var range in ranges)
        {
            var process = Process.Start(Environment.ProcessPath!, $"{range.Begin} {range.End}");
            processes.Add(process!);
        }

        // 子プロセスが終了するのを待機し、結果を加算
        var sum = 0;
        foreach (var process in processes)
        {
            process.WaitForExit();
            sum += process.ExitCode;
        }

        // 合計を返す
        return (ranges.Length, sum);
    }

    // 子プロセスのMain
    public static int ChildProcessMain(string[] args)
    {
        return CountRange(int.Parse(args[0]), int.Parse(args[1]));
    }
}

マルチプロセスで並列処理を行っています。

Threadクラスを利用

UsingThread.cs
namespace Parallelization;

internal class UsingThread : Prime
{
    public override (int, int) Count(int searchLength)
    {
        // タスクを分割
        var ranges = SplitRange(1, searchLength + 1, Environment.ProcessorCount);

        // スレッドを開始
        var states = new List<State>();
        foreach (var range in ranges)
        {
            var state = new State(range.Begin, range.End);
            state.Thread = new Thread(state.Main);
            state.Thread.Start();
            states.Add(state);
        }

        // スレッドが終了するのを待機し、結果を加算
        var sum = 0;
        foreach (var state in states)
        {
            state.Thread!.Join();
            sum += state.Result;
        }

        // 合計を返す
        return (ranges.Length, sum);
    }

    private class State(int begin, int end)
    {
        public readonly int Begin = begin;
        public readonly int End = end;
        public Thread? Thread;
        public int Result;

        public void Main()
        {
            Result = CountRange(Begin, End);
        }
    }
}

マルチスレッドで並列処理を行っています。

ThreadPoolクラスを利用

UsingThreadPool.cs
namespace Parallelization;

internal class UsingThreadPool : Prime
{
    public override (int, int) Count(int searchLength)
    {
        // タスクを分割
        var ranges = SplitRange(1, searchLength + 1, Environment.ProcessorCount * 3 + 1);

        // タスクを開始
        var states = new List<State>();
        foreach (var range in ranges)
        {
            var state = new State(range.Begin, range.End);
            ThreadPool.QueueUserWorkItem(SetResult, state);
            states.Add(state);
        }

        // タスクが完了するのを待機し、結果を加算
        var sum = 0;
        foreach (var state in states)
        {
            state.Completion.Wait();
            sum += state.Result;
        }

        // 合計を返す
        return (ranges.Length, sum);
    }

    private class State(int begin, int end)
    {
        public readonly int Begin = begin;
        public readonly int End = end;
        public readonly ManualResetEventSlim Completion = new();
        public int Result;
    }

    private static void SetResult(object? state)
    {
        var s = (State)state!;
        s.Result = CountRange(s.Begin, s.End);
        s.Completion.Set();
    }
}

スレッドプールを利用して並列処理を行っています。Threadクラスは「スレッド」を直接扱っていましたが、ThreadPoolクラスは「タスク」を扱うのが特徴です。スレッドの起動・終了は自動で行われ、それらのスレッドを利用して効率よくタスクが実行されます。

Taskクラスを利用

UsingTask.cs
namespace Parallelization;

internal class UsingTask : Prime
{
    public override (int, int) Count(int searchLength)
    {
        // タスクを分割
        var ranges = SplitRange(1, searchLength + 1, Environment.ProcessorCount * 3 + 1);

        // タスクを開始
        var tasks = new List<Task<int>>();
        foreach (var range in ranges)
        {
            var task = new Task<int>(() => CountRange(range.Begin, range.End));
            task.Start();
            tasks.Add(task);
        }

        // タスクが完了するのを待機し、結果を加算
        var sum = 0;
        foreach (var task in tasks)
        {
            task.Wait();
            sum += task.Result;
        }

        // 合計を返す
        return (ranges.Length, sum);
    }
}

Task はスレッドプールの発展形で、処理完了待ちや結果の受け渡しなどの便利な機能が利用できます。

Parallel.Forを利用

UsingParallelFor.cs
using System.Collections.Concurrent;

namespace Parallelization;

internal class UsingParallelFor : Prime
{
    public override (int, int) Count(int searchLength)
    {
        // タスクを分割
        var ranges = SplitRange(1, searchLength + 1, Environment.ProcessorCount * 3 + 1);

        // 並列実行
        var results = new ConcurrentBag<int>();
        Parallel.For(0, ranges.Length, index =>
        {
            var range = ranges[index];
            var result = CountRange(range.Begin, range.End);
            results.Add(result);
        });

        // 合計を返す
        return (ranges.Length, results.Sum());
    }
}

Parallel はタスクの発展形で、タスクの開始と完了待ちを自動で行ってくれます。Forメソッドは並列化した for 文に相当します。

Parallel.ForEachを利用

UsingParallelForEach.cs
using System.Collections.Concurrent;

namespace Parallelization;

internal class UsingParallelForEach : Prime
{
    public override (int, int) Count(int searchLength)
    {
        // タスクを分割
        var ranges = SplitRange(1, searchLength + 1, Environment.ProcessorCount * 3 + 1);

        // 並列実行
        var results = new ConcurrentBag<int>();
        Parallel.ForEach(ranges, range =>
        {
            var result = CountRange(range.Begin, range.End);
            results.Add(result);
        });

        // 合計を返す
        return (ranges.Length, results.Sum());
    }
}

ForEachメソッドは、並列化した foreach 文に相当します。

Parallel.ForEachとPartitionerを利用

UsingPartitioner.cs
using System.Collections.Concurrent;

namespace Parallelization;

internal class UsingPartitioner : Prime
{
    public override (int, int) Count(int searchLength)
    {
        // タスクを分割
        var partitioner = Partitioner.Create(1, searchLength + 1);

        // 並列実行
        var results = new ConcurrentBag<int>();
        Parallel.ForEach(partitioner, range =>
        {
            var result = CountRange(range.Item1, range.Item2);
            results.Add(result);
        });

        // 合計を返す
        return (results.Count, results.Sum());
    }
}

Partitioner はタスクの分割を自動で行います。この方法が最も処理速度が速くなるようです。

結局どれを使えばいい？

Parallel と Task だけを使えば OK です。Process、Thread、ThreadPool は .NET Framework 3.5 以前から利用できる古い機能と考えてください。