论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2009-07-20 21:15 |只看该作者 |倒序浏览

Linux内核源码中的“list.h”和FreeBSD源码中的"queue.h"中的STAILQ都可以被用来做FIFO的队列。
由于对程序的效率非常关心，因此我测试了这两个实现的性能：

在一次测试中，是将一个N=1000000个事先分配好的object进行如下操作：

将N个object依次添加到队列末尾
进行N次的删除队列首元素操作

除了list和STAILQ外，我还自己实现了一个MYQ。MYQ比起STAILQ所需要的内存更少，不过性能似乎还不如STAILQ。。。

原本以为list的效率应该和STAILQ差不多，结果却发现效率相差将近一倍。个人感觉STAILQ的效率应该几乎是最优的了。
下面是测试结果：

python timeit.py vs-LIST.exe
Testing LIST...
Time used: 10.703
python timeit.py vs-STAILQ.exe
Testing STAILQ...
Time used: 5.843
python timeit.py vs-MYQ.exe
Testing MYQ...
Time used: 5.937

程序如下：

#include <stdio.h>

#include "list.h"
#include "queue.h"

#define STAILQ_TEST (1)
#define LIST_TEST (2)
#define MYQ_TEST (3)

#ifndef TEST
#error TEST must be defined to STAILQ_TEST or LIST_TEST
#endif

#define REPEAT    (500)
#define NOBJECTS (1000000)

struct object{
char anything[7];
#if TEST == LIST_TEST
struct list_head list_entry;
#elif TEST == STAILQ_TEST
STAILQ_ENTRY(object) stailq_entry;
#elif TEST == MYQ_TEST
struct object *myq_next;
#endif
};

struct object objects[NOBJECTS]; // all objects

STAILQ_HEAD(__stailq, object) the_stailq = STAILQ_HEAD_INITIALIZER(the_stailq); // the stailq

LIST_HEAD(the_list);

#if TEST == STAILQ_TEST
static void test_stailq()
{
int t;
puts("Testing STAILQ...");
for (t = 0; t < REPEAT; t++) {
      int i;

      for (i = 0; i < NOBJECTS; i++) {
         STAILQ_INSERT_TAIL(&the_stailq, objects+i, stailq_entry);
      }
      for (i = 0; i < NOBJECTS; i++) {
         STAILQ_REMOVE_HEAD(&the_stailq, stailq_entry);
      }
}
}
#elif TEST == LIST_TEST
static void test_list()
{
int t;
puts("Testing LIST...");
for (t = 0; t < REPEAT; t++) {
      int i;

      for (i = 0; i < NOBJECTS; i++) {
         list_add_tail( (&(objects[i].list_entry)), (&the_list) );
      }
      for (i = 0; i < NOBJECTS; i++) {
         list_del( (the_list.next) );
      }
}
}
#elif TEST == MYQ_TEST

struct {
struct object *head;
struct object **lastp;
} the_myq = {
NULL, &(the_myq.head),
};

#define myq_push(new, q)          \
do {                         \
      *((q)->lastp) = new;       \
      (q)->lastp = &new->myq_next; \
} while(0)

#define myq_pop(q)  \
do { \
      if ((q)->lastp == &((q)->head->myq_next) ) { \
         (q)->lastp = &((q)->head);  \
      } \
      (q)->head = (q)->head->myq_next; \
} while(0)

static void test_myq()
{
int t;
puts("Testing MYQ...");
for (t = 0; t < REPEAT; t++) {
      int i;

      for (i = 0; i < NOBJECTS; i++) {
         myq_push( (&(objects[i])), (&the_myq) );
      }
      for (i = 0; i < NOBJECTS; i++) {
         myq_pop( &the_myq );
      }
}
}

#endif //TEST == STAILQ_TEST

int main()
{
#if TEST==LIST_TEST
test_list();
#elif TEST == STAILQ_TEST
test_stailq();
#elif TEST == MYQ_TEST
test_myq();
#else
#error TEST is wrong.
#endif
return 0;
}

我把程序放在附件里，有兴趣的人可以下载，呵呵。