位运算补课：快速判断一个数是不是2的幂

int a = 1024;
if ( (a & (a-1)) == 0)
{
    printf("是2的幂\n");
}

转：各种操作的延迟时间

下图来自此页面：http://blog.hesey.net/2012/06/evolution-of-large-website-architecture.html

另有一张同事贴的页面：http://www.eecs.berkeley.edu/~rcs/research/interactive_latency.html
比较有趣，每年的变化都能看见，不知道是如何预测出来的。

protocol buffers and thrift：当心类型暴涨

最近在阅读另一个部门交接的代码。
尝试增加一个小小的新功能，然后编译、链接……这个过程相当痛苦。
这个部门在数据传输协议上，采用了类似于protocol buffers或thrift类似的技术：用中间语言定义类型，然后用工具编译成C++代码。

这样做无可厚非。但我在阅读代码和编译链接的时候，非常痛苦：
1、 类型实在太多了，类型套类型，分散在很多个不同的目录中；
2、编译不通过，必须把所有引用到的类型的头文件都include进去；链接也不通过，必须把类型的encode/decode库链接进去。

因此，使用protocol buffers and thrift类似的技术初看很好，随着业务的发展，类型越来越多，代码就变得越来越臃肿，越来越难以维护。

我建议，这样去避免类型暴涨：
1. 采用自动编译，把中间的定义文件放在某个目录下，自动生成各种语言需要的代码；
2. 所有的类型放在一起，甚至可以把所有的类型包含在一个all_types.h中；后续的代码要引用类型，包含这一个头文件即可。怕影响编译速度？可以用预编译头文件解决；
3. 所有的类型的encode/decode代码，全部编译后，打包到一个大的all_types.a中，到时候链接一个库即可；
4. 定期清理，不要的类型丢弃。

试验：多线程竞争写

下面一段代码将试验不同条件下多线程竞争对变量进行累加的效果：

#include <stdio.h>
#include <pthread.h>

#define MAX_NUM 5000000

int num = 0;

void* thread_func(void* param)
{
for (int i=0; i<MAX_NUM; ++i)
{
++num;
}
return NULL;
}

int main()
{
pthread_t t1, t2;
pthread_create(&t1, NULL, thread_func, NULL);
pthread_create(&t2, NULL, thread_func, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("%d\n", num);
return 1;
}

假设没有竞争，则num最终输出的结果应该是10000000

试验一：执行上面的代码输出5315953

试验二：将蓝色的这行的定义修改为：volatile int num = 0;

        执行后输出5431651。

        虽然没有得到正确的结果，但从数值上看出，volatile对数据同步还是有一些效果的。

试验三：在红色的行前增加一行代码：__sync_synchronize();

        执行后输出7443185

        试验说明，内存屏障能够进一步加快多核间的内存数据同步。

试验四：将红色的这行修改为__sync_add_and_fetch(&num, 1);

        执行后得到了正确结果10000000

        由此说明，多核条件下并发累加，只有原子操作才能得到正确的结果。volatile关键字和内存屏障都不能解决。

==============================================

进一步思考：如下是CPU的结构图

线程在操作num这个数的时候，都会把num载入自己的 L1 cache line

当CPU0上的线程1改写了num的值，L1 cache line为标示为脏。然后，CPU0上的cache line会同步到CPU 1上的cache line，然后CPU1读取数据的时候，就会是最新的数据。

如果按照这种数据同步原理，则试验一应该得到正确的结果。但为什么结果又不正确呢？

CPU， L1 CACHE， 内存，这三者之间的数据同步机制究竟是如何进行的？希望有大虾予以指教。

一个失败的经验：把内存映射文件当成共享内存用

服务器开发中常常采用共享内存来存储数据，好处有：
1. 预分配空间，性能高；
2. 服务器崩溃后，共享内存的数据还在，进程重启后可快速回复服务。（这点尤其重要）

但是，共享内存也有比较麻烦的问题：
1. 增加容量很麻烦：要先dump出数据，然后删除共享内存，再重新分配，再写入；
2. local cache带来了单点问题，机器死机或者掉电后，必然丢失数据。

于是，在某次服务器开发的时候，我尝试用内存映射文件来代替共享内存。因为内存映射文件有这样一些好处：
1. 与共享内存一样，进程重启后，数据得以保留；
2. 扩容方便：如果内存允许，我映射更大的一个内存区域就好；
3. 迁移方便：停止进程，然后把映射文件复制到另一个机器，再启动进程即可。

愿望总是美好的！使用内存映射文件后，系统常常莫名其妙地IO猛烈飚高，都是映射文件惹的祸。
首先，内存映射文件分配的是虚拟内存，等到程序访问这个区域后，发现没有对应的物理内存，会引起一个缺页中断，然后操作系统从文件对应的区域中，加载4KB的数据到page cache中。
然后，如果对这一内存区域执行写操作，数据并不立即被写往磁盘，而仅仅只是把这个page标记为脏页。当整个操作系统的脏页达到一定比例后，操作系统就会把这些脏页的数据写往磁盘，由此也就引起了IO突然飚高。


因此，当采用local cache的存储方案的时候，性能是第一个考虑点，其次才是方便进程快速恢复服务。而使用内存映射文件，必然增加了系统的IO，降低了性能，这与服务器开发的目的是违背的。

学到两个新词：NOR和NAND

在看GCC原子操作函数的时候发现有个：__sync_nand_and_fetch
什么是nand操作？

找了半天终于找到：
位操作里除了创建的 and, or, xor, not
还有not or和not and
not or等价于： not (a or b)
not and等价于： not (a and b)

VC++里面貌似已经支持两个新的操作符来代表nor和nand： ~|  ~&

搜索到的相关帖子在这里：http://forums.codeguru.com/showthread.php?420830-bitwise-nor-operator

测试伪共享对性能的影响

伪共享(false sharing)的知识需要了解的话，请google之。
下面是测试代码：两个线程分别计算5亿次累加两个相邻变量的时间消耗。
//test_false_sharing_1.cpp

#include <stdio.h>
#include <sys/time.h>
#include <time.h>
#include <pthread.h>

#define PACK  __attribute__  ((packed))
typedef int cache_line_int __attribute__((aligned(LEVEL1_DCACHE_LINESIZE)));

struct data
{
    int a;
    int b;
};

#define MAX_NUM 500000000

void* thread_func_1(void* param)
{
    timeval start, end;
    gettimeofday(&start, NULL);
    data* d = (data*)param;
    for (int i=0; i<MAX_NUM; ++i)
    {
        ++d->a;
    }
    gettimeofday(&end, NULL);
    printf("thread 1, time=%d\n", (int)(end.tv_sec-start.tv_sec)*1000000+(int)(end.tv_usec-start.tv_usec));
    return NULL;
}

void* thread_func_2(void* param)
{
    timeval start, end;
    gettimeofday(&start, NULL);
    data* d = (data*)param;
    for (int i=0; i<MAX_NUM; ++i)
    {
        ++d->b;
    }
    gettimeofday(&end, NULL);
    printf("thread 2, time=%d\n", (int)(end.tv_sec-start.tv_sec)*1000000+(int)(end.tv_usec-start.tv_usec));
    return NULL;
}

int main()
{
    data d = {a:0, b:0};
    pthread_t t1, t2;
    pthread_create(&t1, NULL, thread_func_1, &d);
    pthread_create(&t2, NULL, thread_func_2, &d);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("end, a=%d,b=%d\n", d.a, d.b);
    return 0;
}

/*
g++ -o test_false_sharing_1 test_false_sharing_1.cpp -g -Wall -O2
*/

----------------------------------------------

执行后输出：

thread 1, time=4121562
thread 2, time=4329193 

把以上程序稍稍修改：

struct data

{

    cache_line_int a;

    cache_line_int b;

};

//struct中的int修改为按照cache_line对齐的int

然后酱紫编译：

 g++ -o test_false_sharing_2 test_false_sharing_2.cpp -g -Wall -lpthread -DLEVEL1_DCACHE_LINESIZE=`getconf LEVEL1_DCACHE_LINESIZE` 

执行后输出：

thread 1, time=1607430
thread 2, time=1629508 

性能提高了2.5倍。

-------------------------------------------------

测试中注意两点：

1. int重新对齐的定义后，在struct中不要在定义对齐的属性，否则之前的对齐属性会失效；

2. 采用getconf LEVEL1_DCACHE_LINESIZE这样的命令获得cache line的大小；
3. 编译中不能加上-O2，否则编译器计算会导致瞬间出结果；（这个优化真是强大啊）

刚刚知道了一个牛叉的工具：Google App Inventor

同事在群里贴了这张图，顿时觉得很震撼：

居然还可以画出这么漂亮的程序流程图。

更牛叉的是，这个工具是google用于生成ANDROID APP的。可以一行代码都不写就创建应用。