博尔的判断是如此之慢？

Question

我正在优化函数,我尝试各种方式甚至sse,并修改代码从不同的位置返回以查看计算时间跨度但最后我发现大部分时间花在bool判断上.即使我用if中的简单添加操作替换if语句中的所有代码,它仍然需要6000毫秒.

我的平台是gcc 4.7.1 e5506 cpu.它的输入'a'和'b'是一个1000size的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

Answer 1

您可以通过减少缓存未命中来提高程序的速度：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;
}