1

私は自分のラップトップのパフォーマンスを比較するための小さなプログラムを書きました。プログラムをCPUに集中させるために、いくつかのマルチスレッドコード（Parallel APIを介して実装）を使用してRabin-Karpパターンマッチングアルゴリズムを実装しました。

コンパイラ最適化フラグをオフにしてプログラムを実行すると、最適化フラグをオンにして実行するよりもかなり時間がかかることに気づきました。

例えば：

  • 所要時間（最適化フラグがオフの場合）：40秒（約）
  • 所要時間（最適化フラグがオンの場合）：18秒（約）

コンパイラによってどのような最適化が適用されているのかを知りたいのですが、これによりパフォーマンスが大幅に向上します。このフラグをオン/オフにしてコードを実行したときに何が起こっているのかを理解する方法についてのポインタは、非常に役立ちます。

コード

void Main()
{
    Dictionary<string,bool> collection = new Dictionary<string,bool>();
    IEnumerable<string> commonWords = File.ReadAllLines(@"G:\LINQPad4\words.txt")
        .Where(x => !string.IsNullOrEmpty(x)).Select(t => t.Trim());

    string magna_carta = File.ReadAllText(@"G:\LINQPad4\magna-carta.txt");

    Parallel.ForEach(commonWords,
    () => new Dictionary<string,bool>(),
    (word, loopState, localState) =>
    {
        RabinKarpAlgo rbAlgo = new RabinKarpAlgo(magna_carta,word);
        localState.Add(word,rbAlgo.Match());
        return localState;
    },
    (localState) =>
    {
        lock(collection){
            foreach(var item in localState)
            {
                collection.Add(item.Key, item.Value);
            }
        }
    });

    collection.Dump();
}

public class RabinKarpAlgo
{
    private readonly string inputString;
    private readonly string pattern;
    private ulong siga = 0;
    private ulong sigb = 0;
    private readonly ulong Q = 100007;
    private readonly ulong D = 256;

    public RabinKarpAlgo(string inputString, string pattern)
    {
        this.inputString = inputString;
        this.pattern = pattern;
    }

    public bool Match()
    {
        for (int i = 0; i < pattern.Length; i++)
        {
            siga = (siga * D + (ulong)inputString[i]) % Q;
            sigb = (sigb * D + (ulong)pattern[i]) % Q;
        }

        if(siga == sigb)
            return true;

        ulong pow = 1;
        for (int k = 1; k <= pattern.Length - 1; k++)
            pow = (pow * D) % Q;

        for (int j = 1; j <= inputString.Length - pattern.Length; j++)
        {
            siga = (siga + Q - pow * (ulong)inputString[j - 1] %Q) % Q;
            siga = (siga * D + (ulong)inputString[j + pattern.Length - 1]) % Q;

            if (siga == sigb)
            {
                if (inputString.Substring(j, pattern.Length) == pattern)
                {
                    return true;
                }
            }
        }

        return false;
    }
}

関連ファイルは、次のgitHubリポジトリからダウンロードできます。Rabin - KarpTest

記事：パフォーマンステスト

4

1 に答える 1

3

あなたの特別なケースでは、並列 foreach 内にある 3 つの for ループがあります。ほとんどの最適化は、動的ループ変換、そしてもちろん数学部分を通じて行われると強く信じています。

ループでできることの例を次に示します。ループ変換

C# コンパイラ チームの Eric Lippert は、これに関するブログ エントリを持って います。

于 2012-06-12T06:06:58.847 に答える