5

私は関数を最適化しています。私はすべての方法と sse を試し、別の位置から戻るようにコードを修正してタイムスパンの計算を確認しましたが、最終的にほとんどの時間が bool の判断に費やされていることがわかりました。if ステートメントのすべてのコードを単純な追加操作に置き換えても、それでも 6000 ミリ秒かかります。

私のプラットフォームは gcc 4.7.1 e5506 cpu です。その入力 'a' と 'b' は 1000 サイズの int 配列で、'asize' と 'bsize' は対応する配列サイズです。MATCH_MASK = 16383、タイムスパンを統計するために関数を 100000 回実行します。問題に良い考えはありますか。ありがとうございました！

   if (aoffsets[i] && boffsets[i])  // this line costs most time

コード：

uint16_t aoffsets[DOUBLE_MATCH_MASK] = {0}; // important! or it will only be right on the first time
uint16_t* boffsets = aoffsets + MATCH_MASK;
uint8_t* seen = (uint8_t *)aoffsets;
auto fn_init_offsets = [](const int32_t* x, int n_size, uint16_t offsets[])->void
{
    for (int i = 0; i < n_size; ++i)
        offsets[MATCH_STRIP(x[i])] = i;
};
fn_init_offsets(a, asize, aoffsets);
fn_init_offsets(b, bsize, boffsets);

uint8_t topcount = 0;
int topoffset = 0;
{
    std::vector<uint8_t> count_vec(asize + bsize + 1, 0);   // it's the fastest way already, very near to tls
    uint8_t* counts = &(count_vec[0]);
            //return aoffsets[0];   // cost 1375 ms
    for (int i = 0; i < MATCH_MASK; ++i)
    {
        if (aoffsets[i] && boffsets[i])  // this line costs most time
        {
                            //++affsets[i];  // for test
            int offset = (aoffsets[i] -= boffsets[i]);
            if ((-n_maxoffset <= offset && offset <= n_maxoffset))
            {
                offset += bsize;
                uint8_t n_cur_count = ++counts[offset];
                if (n_cur_count > topcount)
                {
                    topcount = n_cur_count;
                    topoffset = offset;
                }
            }
        }
    }
}
    return aoffsets[0];   // cost 6000ms
4

2 に答える 2

4

まず、memset(count_vec,0, N);memaligned バッファーが std::vector を 30% 上回っています。

分岐のない式 (aoffsets[i] * boffsets[i]) を使用して、使用しない式を同時に計算することができますoffset = aoffset[i]-boffset[i]; offset+bsize; offset+n_maxoffset;。

offsetの典型的な範囲に応じて、(offset+bsize) の最小/最大を計算して、次の反復で必要な memset(count_vec) を制限したくなるかもしれません: すでにゼロの値をクリアする必要はありません。

philipp が指摘したように、操作をインターリーブするのは良いことです。また、uint32_t aboffset[N]; から aoffset[i] と boffset[i] の両方を同時に読み取ることができます。巧妙なビット マスキング (aoffset[i]、aoffset[i+1] の変更マスクを生成する) を使用すると、純粋な c で 64 ビットのシミュレートされた SIMD を使用して (ヒストグラム累積部分まで) 2 つのセットを並列に処理できる可能性があります。

于 2012-11-22T07:47:58.657 に答える
3

キャッシュミスを減らすことでプログラムの速度を上げることができます：aoffsets[i]そしてboffsets[i]メモリ内で互いに比較的遠くにあります。それらを並べて配置することで、プログラムを大幅に高速化できます。私のマシン（e5400 cpu、VS2012）では、実行時間が3.0秒から2.3秒に短縮されました。

#include <vector>

#include <windows.h> 
#include <iostream> 


typedef unsigned short uint16_t;
typedef int int32_t;
typedef unsigned int uint32_t;
typedef unsigned char uint8_t;

#define MATCH_MASK 16383
#define DOUBLE_MATCH_MASK (MATCH_MASK*2)
static const int MATCH_BITS = 14; 
static const int MATCH_LEFT = (32 - MATCH_BITS); 
#define MATCH_STRIP(x) ((uint32_t)(x) >> MATCH_LEFT)

static const int n_maxoffset = 1000;

uint16_t test(int32_t* a, int asize, int32_t* b, int bsize)
{
    uint16_t offsets[DOUBLE_MATCH_MASK] = {0}; 

    auto fn_init_offsets = [](const int32_t* x, int n_size, uint16_t offsets[])->void
    {
        for (int i = 0; i < n_size; ++i)
            offsets[MATCH_STRIP(x[i])*2 /*important. leave space for other offsets*/] = i;
    };
    fn_init_offsets(a, asize, offsets);
    fn_init_offsets(b, bsize, offsets+1);

    uint8_t topcount = 0;
    int topoffset = 0;
    {
        std::vector<uint8_t> count_vec(asize + bsize + 1, 0);   
        uint8_t* counts = &(count_vec[0]);
        for (int i = 0; i < MATCH_MASK; i+=2)
        {
            if (offsets[i] && offsets[i+1])  
            {
                int offset = (offsets[i] - offsets[i+1]); //NOTE: I removed 
                if ((-n_maxoffset <= offset && offset <= n_maxoffset))
                {
                    offset += bsize;
                    uint8_t n_cur_count = ++counts[offset];
                    if (n_cur_count > topcount)
                    {
                        topcount = n_cur_count;
                        topoffset = offset;
                    }
                }
            }
        }
    }
    return offsets[0];   
}


int main(int argc, char* argv[])
{
    const int sizes = 1000;
    int32_t* a = new int32_t[sizes];
    int32_t* b = new int32_t[sizes];
    for (int i=0;i<sizes;i++)
    {
        a[i] = rand()*rand();
        b[i] = rand()*rand();
    }

    //Variablen 
    LONGLONG g_Frequency, g_CurentCount, g_LastCount; 

    QueryPerformanceFrequency((LARGE_INTEGER*)&g_Frequency);
    QueryPerformanceCounter((LARGE_INTEGER*)&g_CurentCount); 

    int sum = 0;

    for (int i=0;i<100000;i++)
    {
        sum += test(a,sizes,b,sizes);
    }

    QueryPerformanceCounter((LARGE_INTEGER*)&g_LastCount); 
    double dTimeDiff = (((double)(g_LastCount-g_CurentCount))/((double)g_Frequency)); 

    std::cout << "Result: " << sum << std::endl <<"time: " << dTimeDiff << std::endl; 


    delete[] a;
    delete[] b;
    return 0;
}

のバージョンと比較してtest()。

#include <vector>

#include <windows.h> 
#include <iostream> 


typedef unsigned short uint16_t;
typedef int int32_t;
typedef unsigned int uint32_t;
typedef unsigned char uint8_t;

#define MATCH_MASK 16383
#define DOUBLE_MATCH_MASK (MATCH_MASK*2)
static const int MATCH_BITS = 14; 
static const int MATCH_LEFT = (32 - MATCH_BITS); 
#define MATCH_STRIP(x) ((uint32_t)(x) >> MATCH_LEFT)
static const int n_maxoffset = 1000;

uint16_t test(int32_t* a, int asize, int32_t* b, int bsize)
{
    uint16_t aoffsets[DOUBLE_MATCH_MASK] = {0}; // important! or it will only be right on the first time
    uint16_t* boffsets = aoffsets + MATCH_MASK;

    auto fn_init_offsets = [](const int32_t* x, int n_size, uint16_t offsets[])->void
    {
        for (int i = 0; i < n_size; ++i)
            offsets[MATCH_STRIP(x[i])] = i;
    };
    fn_init_offsets(a, asize, aoffsets);
    fn_init_offsets(b, bsize, boffsets);

    uint8_t topcount = 0;
    int topoffset = 0;
    {
        std::vector<uint8_t> count_vec(asize + bsize + 1, 0);   
        uint8_t* counts = &(count_vec[0]);

        for (int i = 0; i < MATCH_MASK; ++i)
        {
            if (aoffsets[i] && boffsets[i]) 
            {

                int offset = (aoffsets[i] - boffsets[i]); //NOTE: I removed the -= because otherwise offset would always be positive!
                if ((-n_maxoffset <= offset && offset <= n_maxoffset))
                {
                    offset += bsize;
                    uint8_t n_cur_count = ++counts[offset];
                    if (n_cur_count > topcount)
                    {
                        topcount = n_cur_count;
                        topoffset = offset;
                    }
                }
            }
        }
    }
    return aoffsets[0];   
}


int main(int argc, char* argv[])
{
    const int sizes = 1000;
    int32_t* a = new int32_t[sizes];
    int32_t* b = new int32_t[sizes];
    for (int i=0;i<sizes;i++)
    {
        a[i] = rand()*rand();
        b[i] = rand()*rand();
    }

    LONGLONG g_Frequency, g_CurentCount, g_LastCount; 
    QueryPerformanceFrequency((LARGE_INTEGER*)&g_Frequency);
    QueryPerformanceCounter((LARGE_INTEGER*)&g_CurentCount); 

    int sum = 0;

    for (int i=0;i<100000;i++)
    {
        sum += test(a,sizes,b,sizes);
    }

    QueryPerformanceCounter((LARGE_INTEGER*)&g_LastCount); 

    double dTimeDiff = (((double)(g_LastCount-g_CurentCount))/((double)g_Frequency)); 

    std::cout << "Result: " << sum << std::endl <<"time: " << dTimeDiff << std::endl; 


    delete[] a;
    delete[] b;
    return 0;
}
于 2012-11-22T09:21:48.670 に答える