8

アプリケーションのプロファイリング中に、パターン マッチの関数チェックが非常に遅いことがわかりました。LINQ を使用して記述されています。この LINQ 式をループに単純に置き換えるだけで、大きな違いが生まれます。それは何ですか？LINQ は本当に悪いことで動作が遅いのでしょうか、それとも何か誤解しているのでしょうか?

private static bool PatternMatch1(byte[] buffer, int position, string pattern)
{
    int i = 0;

    foreach (char c in pattern)
    {
        if (buffer[position + i++] != c)
        {
            return false;
        }
    }

    return true;
}

LINQ を使用したバージョン 2 (Resharper が推奨)

private static bool PatternMatch2(byte[] buffer, int position, string pattern)
{
    int i = 0;
    return pattern.All(c => buffer[position + i++] == c);
}

LINQ を使用したバージョン 3

private static bool PatternMatch3(byte[] buffer, int position, string pattern)
{
    return !pattern.Where((t, i) => buffer[position + i] != t).Any();
}

ラムダを使用したバージョン 4

private static bool PatternMatch4(byte[] buffer, int position, string pattern, Func<char, byte, bool> predicate)
{
    int i = 0;

    foreach (char c in pattern)
    {
        if (predicate(c, buffer[position + i++]))
        {
            return false;
        }
    }

    return true;
}

これが大きなバッファでの使用法です

const int SIZE = 1024 * 1024 * 50;

byte[] buffer = new byte[SIZE];

for (int i = 0; i < SIZE - 3; ++i)
{
    if (PatternMatch1(buffer, i, "xxx"))
    {
        Console.WriteLine(i);
    }
}

PatternMatch2orの呼び出しPatternMatch3は非常に遅いです。は約 8 秒、 はPatternMatch3約 4 秒かかりますがPatternMatch2、呼び出しPatternMatch1には約 0.6 秒かかります。私が理解している限り、それは同じコードであり、違いはありません。何か案は？

4

4 に答える 4

7

Mark Byers と Marco Mp は、余分な呼び出しのオーバーヘッドについては正しいです。ただし、ここには別の理由があります。閉鎖による多くのオブジェクトの割り当てです。

コンパイラは、反復ごとに新しいオブジェクトを作成し、述語が使用できるとの現在の値bufferを格納します。これを示すdotTrace スナップショットを次に示します。コンパイラによって生成されたクラスです。positioniPatternMatch2<>c_DisplayClass1

(オーバーヘッドを追加するトレース プロファイリングを使用しているため、数値が非常に大きいことに注意してください。ただし、呼び出しごとのオーバーヘッドは同じであるため、全体的なパーセンテージは正しいです)。

ここに画像の説明を入力

于 2012-10-10T13:14:09.477 に答える
6

違いは、LINQ バージョンには追加の関数呼び出しがあることです。LINQ の内部では、ラムダ関数がループで呼び出されます。

余分な呼び出しはJIT コンパイラによって最適化される可能性がありますが、保証されているわけではなく、わずかなオーバーヘッドが追加される可能性があります。ほとんどの場合、追加のオーバーヘッドは問題になりませんが、関数が非常に単純で非常に多くの回数が呼び出されるため、わずかなオーバーヘッドでもすぐに加算されます。私の経験では、LINQ コードは通常、同等のループよりも少し遅くなります。これは、より高レベルの構文に対して頻繁に支払うパフォーマンスの代償です。for

この状況では、明示的なループに固執することをお勧めします。

コードのこのセクションを最適化している間に、より効率的な検索アルゴリズムを検討することもできます。あなたのアルゴリズムは最悪の場合 O(n*m) ですが、より良いアルゴリズムが存在します。

于 2012-10-10T12:54:41.097 に答える
6

さて、Where 演算子を見てみましょう。

その実装はほぼ(*)のようです:

public IEnumerable<T> Where(this IEnumerable<T> input, Func<T, bool> fn)
{
    foreach(T i in input) 
        if (fn(i))
            yield return i;
}

つまり、IEnumerable のループごとにイテレータ オブジェクトが作成されます。多くの LINQ クエリを実行するため、これらの割り当ての SIZE - n があることに注意してください。

次に、パターン内の各文字に対して次のことを行います。

  1. 列挙子への関数呼び出し
  2. 述語への関数呼び出し

2 つ目はデリゲートの呼び出しで、典型的な仮想呼び出しの呼び出しコストの約 2 倍のコストがかかります (最初のバージョンでは、配列のインデックス解除以外に余分な呼び出しはありません。

本当に野蛮なパフォーマンスが必要な場合は、可能な限り「古いスタイル」のコードを取得することをお勧めします。この場合、メソッド 1 の foreach を単純な for に置き換えます (少なくとも、最適化に役立たない場合は、とにかくインデックスを追跡しているため、読みやすくなります)。

この場合も読みやすく、Resharper の提案が議論の余地があることを示しています。

(*) プロキシ メソッドを使用して、入力列挙型が null でないことを確認し、コレクションが列挙される前に例外をスローするため、ほぼ述べました。これは、以前に書いたものを無効にしない小さな詳細です。完全性のために。

于 2012-10-10T13:06:53.930 に答える
1

コレクションに適用する場合の LINQ の主な目標は、その単純さです。パフォーマンスが必要な場合は、LINQ を完全に避ける必要があります。また、配列を列挙するにはインデックス変数をインクリメントするだけですが、LINQ では列挙子オブジェクト全体を設定する必要があります。

于 2012-10-10T12:56:27.423 に答える