C++ Low level performance optimize
1. May I have 1 bit ?
下面两段代码，哪一个占用空间更少，那个速度更快？思考10秒再继续往下看:)
//v1
struct BitBool
{
bool b0 :;
bool b1 :;
bool b2 :;
}
BitBool bb;
bb.b1 = true; //v2
struct NormalBool
{
bool b0;
bool b1;
bool b2;
} NormalBool nb;
nb.b1 = true;
第一种通常被认为是优化的版本，甚至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，哪一种方法更好？
std::list<int> myList;
std::vector<int> myVec; //create a random number array
const int size = ;
std::array<int, size> myArr;
for(int i = ; i < size; i++)
{
myArr[i] = rand() % ;
} //pre-allocate memory
myVec.reserve(size);
myList.resize(size,); //fill vector
for(int i = ; 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 = ; 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);
}
两段代码几乎相同从算法分析的角度看，频繁插入操作是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的一个例子:
struct foo
{
int x;
int y;
}; static struct foo f; int sum_a(void)
{
int s = ;
for (int i = ; i < ; ++i)
s += f.x;
return s;
} void inc_b(void)
{
int i;
for (i = ; i < ; ++i)
++f.y;
}
假设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