C++ Low level performance optimize

C++ Low level performance optimize

 

1.  May I have 1 bit ?

下面两段代码,哪一个占用空间更少,那个速度更快?思考10秒再继续往下看:)

C++ Low level performance optimize
//v1
struct BitBool
{
         bool b0 :1;
         bool b1 :1;
         bool b2 :1;
}
BitBool bb;
bb.b1 = true;

 //v2
struct NormalBool
{
         bool b0;
         bool b1;
         bool b2;    
}

NormalBool nb;
nb.b1 = true;
C++ Low level performance optimize

 

第一种通常被认为是优化的版本,甚至UE3里都有很多类似代码,但实际上却在两方面都不占优,why?原因是现代大部分cpu都没有指令能直接访问1bit数据,而

bb.b1 = true

相当于

bb.b1 |= (1<<xxxx); 相应汇编代码可能为(实际汇编根据编译器可能会不同):

shl         cl,2 
xor         cl,al 
and         cl,4 
xor         al,cl

nb.b1 = true;只需要
mov BYTE PTR [rcx+2], dl

        当考虑空间优化时一般只考虑到了数据占用空间,而没有考虑代码所占用的内存。因此虽然sizeof(BitBool)==1==8bit (默认8bit对齐的系统),但访问b1的指令所占空间却需要8~11byte! 考虑到访问成员的代码通常会成为内联函数,因此BitBool所占空间为 1 + 11 * n ,n为代码中需要访问数据的次数! 而NormalBool虽然需要3byte,但其访问代码只需要3byte机器码,所占空间为3 + 3 * n。因此无论在性能还是空间性,NormalBool均更好!

 

 2  Cache missing is killer!!!

     把一个随机数列依次插入list和vector,保持两个新数列从小到大排序:7,5,2,7,9,3  ===>   2,3,5,7,7,9 ,下面是代码,对于不同的数据量n,哪一种方法更好?

C++ Low level performance optimize
std::list<int> myList;
std::vector<int> myVec;

//create a random number array
const int size = 50000;
std::array<int, size> myArr;
for(int i = 0; i < size; i++)
{
       myArr[i] = rand() % 2000;
}

//pre-allocate memory
myVec.reserve(size);
myList.resize(size,65535);

//fill vector
for(int i = 0; i < size; i++)
{
    int value = myArr[i];
    auto it = myVec.begin();
    for(; it != myVec.end(); it++)
    {
        if(*it > value)
        {
            it = myVec.insert(it, value);
            break;
        }
    }
    if(it == myVec.end())
        myVec.push_back(value);
}

//fill list
for(int i = 0; i < size; i++)
{
    int value = myArr[i];
    auto it = myList.begin();
    for(; it != myList.end(); it++)
    {
        if(*it > value)
        {
            it = myList.insert(it, value);
            break;
        }
    }
    if(it == myList.end())
        myList.push_back(value);
}
C++ Low level performance optimize

 

    两段代码几乎相同从算法分析的角度看,频繁插入操作是vector的灾难,但实际测试结论是无论size为多大,vector总是比list快,并且size越大,差距越明显,在我的机器上当size=50k时快了近10倍!!why?首先list需要占用更多内存,其次vector总是保证元素位于连续的内存,这是最重要的!Cache missing导致的性能损失甚至比复制元素还严重。对现代CPU来说,运算速度已经非常快,一次cache missing就会浪费n个cpu周期,合理组织数据,让cpu减少等待时间是现代cpu非常重要的优化手段。

    注意,上面的演示代码只是为了展示cache missing的重要性,并不是完成这个任务的最优方法,另外实际情况下对于复杂类型来说,随着复制代价的提高,vector未必就能总胜出了:)。

 

 3. False Sharing(cache-line ping-ponging)

      大部分程序员都听说过cache missing,但知道false sharing的就不那么多了。为了讨论false sharing,首先要介绍cache line. 就像CPU不能读取1bit一样,cpu访问cache时通常也会多读取一些额外数据,同时读取的这一段数据就称为一条cache line。每一级cache都由n条cache line组成,对于intel i级的cpu来说cache line大小为64byte。假设cpu需要访问变量v时, v地址附近的数据都被读入cache中。对于单核的世界来说,一切都很好,但对于多核心下的多线程设计来说,问题就来了,假设v被加载到了第一个核的cache中,此时另一个核心需要访问临近v的变量v1怎么办? 如果都是只读操作,那么每个核心可以各保存一份cache line v的副本,不会有冲突。但如果线程1需要修改v,线程2需要修改v2怎么办呢,显然会导致不同核心的cache line状态不一致。为了解决这个问题,整个cache line都要被来回重新加载。比如:线程1从主内存加载cache line v,修改v,把整个cache line回写到主线程,线程2再重复这个过程修改v1,这种情况就称为false sharing,显然如果在平行运行的核心代码中出现这种的情况,性能是非常糟糕的,而这样的代码通常又不太容易发现

下面是wiki上false sharing的一个例子:

C++ Low level performance optimize
struct foo 
{
    int x;
    int y; 
};
 
static struct foo f;
 
int sum_a(void)
{
    int s = 0;
    for (int i = 0; i < 1000000; ++i)
        s += f.x;
    return s;
}
 
void inc_b(void)
{
    int i;
    for (i = 0; i < 1000000; ++i)
        ++f.y;
}
C++ Low level performance optimize

     假设sum_a和inc_b两个函数同事运行在不同核心的不同线程上,f的所有成员都在同一条cache line,inc_b在不听修改内存中的值,因此导致false sharing。

 

  在做性能优化前,一定要先profile,profile,profile!!!很多情况下,问题所在的位置和程序员所预期的都不一样,盲目修改代码甚至有可能降低程序性能!!!

ps:最悲剧的情况就是没有任何可靠的profile工具,还必须做性能优化,我目前的情况就是这样,怎一个惨字了得....

 

more refereence:
Modern C++: What You Need to Know 
Native Code Performance on Modern CPUs: A Changing Landscape
Native Code Performance and Memory: The Elephant in the CPU

 

C++ Low level performance optimize,布布扣,bubuko.com

C++ Low level performance optimize

上一篇:<修练8年C++面向对象程序设计之体会>


下一篇:C++中lower_bound函数和upper_bound函数