8

forこのようにループを分割する際のオーバーヘッドは何ですか、

int i;

for (i = 0; i < exchanges; i++)
{
    // some code
    // some more code
    // even more code
}

このような複数のforループに？

int i;

for (i = 0; i < exchanges; i++)
{
    // some code
}

for (i = 0; i < exchanges; i++)
{
    // some more code
}

for (i = 0; i < exchanges; i++)
{
    // even more code
}

コードはパフォーマンスに敏感ですが、後者を実行すると読みやすさが大幅に向上します。（重要な場合は、各ループ内にいくつかのアクセサーを除いて、他のループ、変数宣言、または関数呼び出しはありません。）

私は厳密には低レベルのプログラミングの第一人者ではないので、誰かが基本的な操作と比較してパフォーマンスの低下を測定できればさらに良いでしょう。たとえば、 「ループを追加するたびに、2つの割り当てforに相当するコストがかかります」。intしかし、それがそれほど単純でなければ、私は理解しています（そして驚かないでしょう）。

よろしくお願いします。

4

4 に答える 4

14

多くの場合、あまりにも多くの要因が関係しています...そして、両方の方法を示すのは簡単です。

たとえば、次のループを分割すると、ほぼ2倍の速度低下が発生します（下部に完全なテストコードがあります）。

for (int c = 0; c < size; c++){
    data[c] *= 10;
    data[c] += 7;
    data[c] &= 15;
}

そして、これは、1回ではなく3回ループする必要があり、1回ではなくアレイ全体を3回パスする必要があるため、ほぼ明白です。

一方、この質問を見ると、要素ごとの追加が、結合されたループよりも個別のループではるかに高速であるのはなぜですか？

for(int j=0;j<n;j++){
    a1[j] += b1[j];
    c1[j] += d1[j];
}

メモリアライメントのために、逆のことが時々当てはまります。

これから何を取る？

ほとんど何でも起こり得ます。どちらの方法も常に高速であるとは限らず、ループ内の内容に大きく依存します。

そのため、このような最適化によってパフォーマンスが向上するかどうかを判断することは、通常、試行錯誤です。十分な経験があれば、かなり自信を持って（知識に基づいて）推測することができます。しかし、一般的に、何かを期待してください。

「追加のforループごとに、2つのint割り当てに相当するコストがかかります。」

あなたはそれがそれほど単純ではないということは正しいです。実際、それは非常に複雑なので、数字はあまり意味がありません。ループの反復は、あるコンテキストではXサイクルかかる場合がありますが、アウトオブオーダー実行やデータの依存関係などの多数の要因により、別のコンテキストではYサイクルかかります。

パフォーマンスはコンテキストに依存するだけでなく、プロセッサによっても異なります。

テストコードは次のとおりです。

#include <time.h>
#include <iostream>
using namespace std;

int main(){

    int size = 10000;
    int *data = new int[size];


    clock_t start = clock();

    for (int i = 0; i < 1000000; i++){
#ifdef TOGETHER
        for (int c = 0; c < size; c++){
            data[c] *= 10;
            data[c] += 7;
            data[c] &= 15;
        }
#else
        for (int c = 0; c < size; c++){
            data[c] *= 10;
        }
        for (int c = 0; c < size; c++){
            data[c] += 7;
        }
        for (int c = 0; c < size; c++){
            data[c] &= 15;
        }
#endif
    }

    clock_t end = clock();
    cout << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
}

出力（1ループ）： 4.08秒
出力（3ループ）： 7.17秒

于 2012-12-13T20:00:12.733 に答える
4

プロセッサは、ジャンプ命令に対するデータ命令の比率を高くすることを好みます。
分岐命令は、プロセッサに命令パイプラインをクリアしてリロードさせる場合があります。

命令パイプラインのリロードに基づいて、最初の方法はより高速になりますが、それほど大きくはありません。分割して、少なくとも2つの新しい分岐命令を追加します。

より高速な最適化は、ループを展開することです。ループを展開すると、ループの先頭に分岐する前にループ内でより多くの命令を実行することにより、データ命令と分岐命令の比率を改善しようとします。

もう1つの重要なパフォーマンスの最適化は、データがプロセッサのキャッシュラインの1つに収まるようにデータを整理することです。したがって、たとえば、データの単一のキャッシュを処理する内部ループを分割し、外部ループが新しいアイテムをキャッシュにロードすることができます。

この最適化は、プログラムが正しく堅牢に実行され、環境でより高いパフォーマンスが要求された後にのみ適用する必要があります。オブザーバー（アニメーション/映画）、ユーザー（応答を待つ）、またはハードウェア（クリティカルタイムイベントの前に操作を実行する）として定義される環境。OS（同時プログラムの実行）とストレージアクセスがプログラムのパフォーマンスの問題にさらに寄与するため、他の目的は時間の無駄です。

于 2012-12-13T19:48:51.680 に答える
2

これにより、あるバージョンが別のバージョンよりも高速であるかどうかがわかります。

#include <array>
#include <chrono>
#include <iostream>
#include <numeric>
#include <string>

const int iterations = 100;

namespace
{
    const int exchanges = 200;

    template<typename TTest>
    void Test(const std::string &name, TTest &&test)
    {
        typedef std::chrono::high_resolution_clock Clock;
        typedef std::chrono::duration<float, std::milli> ms;

        std::array<float, iterations> timings;

        for (auto i = 0; i != iterations; ++i)
        {
            auto t0 = Clock::now();

            test();

            timings[i] = ms(Clock::now() - t0).count();
        }

        auto avg = std::accumulate(timings.begin(), timings.end(), 0) / iterations;
        std::cout << "Average time, " << name << ": " << avg << std::endl;
    }
}

int main()
{
    Test("single loop",
        []()
        {
            for (auto i = 0; i < exchanges; ++i)
            {
                // some code
                // some more code
                // even more code
            }
        });

    Test("separated loops",
        []()
        {
            for (auto i = 0; i < exchanges; ++i)
            {
                // some code
            }

            for (auto i = 0; i < exchanges; ++i)
            {
                // some more code
            }

            for (auto i = 0; i < exchanges; ++i)
            {
                // even more code
            }
        });
}
于 2012-12-13T21:23:31.940 に答える
-3

物事は非常に簡単です。最初のコードはレーストラックで1周するようなもので、他のコードは完全な3周のレースをするようなものです。そのため、1周ではなく3周するのに時間がかかります。ただし、ループが順番に実行する必要のある処理を実行していて、それらが相互に依存している場合は、2番目のコードが処理を実行します。たとえば、最初のループがいくつかの計算を実行し、2番目のループがそれらの計算でいくつかの作業を実行している場合、両方のループを順番に実行する必要があります。そうでない場合は...

于 2012-12-13T19:51:05.803 に答える