软件开发: 02 2011存档

代码小比较

By DongHao on 02 15, 2011 2:14 PM | | Comments (8) | TrackBacks (0)
判断上百万个4k的buffer是否为全0，我最先想到的办法是：
zero_buffer = malloc(4096);
memset(zero_buffer, 0, 4096);

/* 循环百万次读取buffer */
    if (!memcmp(zero_buffer, buffer)) {
        /* 全0 */
    }

做完以后跑了一下，速度凑合。由于好奇，看看shell工具cp的代码，它的解决办法是：

/* 循环百万次读取buffer */
    long *wp = buffer;
    while (*wp++ ==0 && wp<buffer + 4096)
        continue;

    if (wp >= buffer + 4096) {
        /* 全0 */
    }

cp的代码真称得上千锤百炼，这比我的方法要快，因为我的办法需要CPU访问两块内存（buffer和zero_buffer），而cp只问一块内存，CPU的cache会高效得多。
判断一块4k buffer当然看不出快慢，我们循环上百万次，立刻就能看出差别：cp的算法比我的快了3倍。


=== 2012.04.19 ===

首先感谢 bernie 的提问，我自己写了完整的代码来验证这个事儿：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define SIZE (1024*1024*1024)

void my_process(void *a, void *b)
{
if (memcmp(a, b, SIZE))
printf("wrong\n");
}

void cp_process(void *a)
{
long *wp = a;
while (*wp++ == 0 && wp < (long *)(a + SIZE))
continue;
}

int main(int argc ,char *argv[])
{
struct timeval start, end;

char * zero_buffer = (char*)malloc(SIZE);
memset(zero_buffer, 0, SIZE);
char * buffer = (char*)malloc(SIZE);
memset(buffer, 0, SIZE);

gettimeofday(&start, NULL);
my_process(buffer, zero_buffer);
gettimeofday(&end, NULL);
printf("my:%lu\n", (end.tv_sec * 1000000 + end.tv_usec) -
(start.tv_sec * 1000000 + start.tv_usec));

gettimeofday(&start, NULL);
cp_process(buffer);
gettimeofday(&end, NULL);
printf("my:%lu\n", (end.tv_sec * 1000000 + end.tv_usec) -
(start.tv_sec * 1000000 + start.tv_usec));
return 0;
}

绝对能编译，（大家注意，我只算内存比较的时间，什么malloc什么memset只是我的准备工作，不算在运行时间内的）我在一台开发机上跑了一下，结果是：

my:3428159
cp:611168

cp命令的算法显然比我的快。大家可以自己在机器上试试，如果结果不一样，咱们再研究研究 :)

另外，要注意那句
if (memcmp(a, b, SIZE))
printf("wrong\n");
不能直接写成
        memcmp(a,b,SIZE);
因为只写“memcp“的话my_process函数会被编译器优化掉（因为函数没有返回值，也没有改全局变量，也就是说，没有任何”输出“），我猜 bernie 遇到的就是这个问题

« 软件开发: 01 2011 | 主索引 | 存档 | 软件开发: 03 2011 »