Home

mroutine库

15 Dec 2012 by LelouchHe

介绍

这篇文章的主要目的就是描述我准备实现的cotoutine库,具体的要求见设计一套cotoutine库,简而言之就是:

  1. asymmetric的coroutine库
  2. 结合pthread库,实现多线程和cotoutine
  3. 实现类似Go的channel
  4. 匿名函数和闭包

平台选择

在这里,我没有很关心可移植性,我觉得这个问题可以延后考虑,目前是要开发一套可在我机器上跑的库即可,即x86-64,最多再支持下x86系统即可,别的平台不管了

编译器的话,应该是gcc,版本是4以上(因为公司的gcc很老,貌似是4.1好像)

实现样版

经过一定时间的考察和研究,仅仅关于coroutine这部分,我觉得LuaJit的Coco非常的不错,有很多借鉴的地方,比如routine的状态保存这部分,我觉得完全可以使用修改之后的Coco版本,在此感谢SuperMike带给我们的如此精彩的实现

实现第一步

目前已经实现了第一步,即简单coroutine的实现,这部分是利用ucontext的,不过确实如众人所言,ucontext确实很慢,也就是每秒百万级别的切换率(一开始测试错了,所以得到了惊人的结果..哎..)

代码参见mroutine

目前有这样一个疑问没有解决,即routine的提前结束,比如:

void test_2(struct mroutine_t *mr, int para)
{
    int i = 0;
    while (i++ < 5)
        mr_yield(mr, para + i);
}

void test_1(struct mroutine_t *mr)
{
    mid_t mid = mr_create(mr, test_2);
    int para = 100;
    mr_resume(mr, mid, para);
}

当test_2yield的时候,test_2其实没有结束,但是回到test_1之后,test_1立即结束了,而且test_2这个routine对外面是透明的,test_1的调用者无法得知test_2的存在,那么这样,test_2就泄露了.

当然,最后mr_fini的时候肯定会回收的,但是1.如果这是服务器程序,很久才fini;2.test_2动态分配的资源在fini的时候都不会收回(仅有程序结束的时候才会)

目前的解决办法只有避免这种情况的发生,一定要保证上层一定比下层执行的长,而且如果要动态分配资源,一定要保证释放

(额..要不要再做个C版的GC呢..这个就一下全解决了..)

实现第二步

现在要做的是提高下性能,准备把ucontext替换成汇编代码,如果有超过5~10倍的提升,就加入主干代码,并给出相应编译选项来

ps: 其实还很想实现可变参数,不过感觉有点难,va能解析的只有int,double而已,指针什么的都是利用两个int模拟出来的(64/32不同),如果都传入的只有指针的话还是可以一试的.恩,等搞定汇编就来做这个.我还很想尝试下多值返回的实现,不过这个在编译器端应该很好弄,在C上的话,可能还得弄清栈结构来进行汇编.好吧,也尝试下吧,不过这就得改变熟悉的调用语法了.

汇编的问题

汇编固然会快点,因为测试了下切换需要的空间,目前的ucontext大概一个需要936B,然后每个上下文包含两个ucontext(一个是当前,一个是前一个,这个后面另说),还有些辅助的,下来就1928B,接近2K了.每次切换都要用2K,显然不论cache还是真的切,都非常慢.

可是看了很多人实现的汇编,都没有很好的解决这个问题(或者这个对其他实现来说不是问题?).libtask模拟实现的ucontext,没有返回值的概念,return address直接就是0,那么一旦coroutine正常运行结束,那么该线程(如果单线程,就意味着整个程序)退出,虽然可能这是好的设计,不过不满足我的需求.Coco的实现里同样有这个问题,不过他的那个在Lua虚拟机里运行,估计没有大的问题(我不确定,最近正在学习Lua),而另一个要命的缺点是状态保存不全,比如在i386下,就保存3个寄存器(eip, esp, ebp),虽然这样非常快(额,应该是ucontext的2%,提速肯定大),但是其他的状态就全部丢失了,包括可能的中间变量(很有可能保存到寄存器里了),我想这个也不是很好的方案.

调度问题

总的说来,routine有两种调度方式,一种是我目前实现的方式,yield返回调用resume的地方,这种调度方式应该就是合作的形式,调用者和被调用者应该都是非常熟悉的(废话,都是自己写的),二者协同完成任务;另一种则是回到总的调度器那里(可以参看风云coroutine),然后由调度器来决定那个routine应该再次resume了,这样是方便以后扩展到和pthread交互,不过缺点就是很不明显,让coroutine完全没了调用的感觉了,依赖关系也需要显示的保存在调度器里了.

其实两种方式都有可取的地方,为了以后的扩展,mroutine可能会增加一个接口用来直接返回调度器,比如yield_up之类的,这样程序员可以自己来选择怎么使用.比如调度器可能仅仅关心一些全局方面的,比如是不是要增加线程(比如都block了),而其余的则还是维持调用的语义

这方面的知识还要继续学习,争取不要增加太大复杂度的完成问题.

重大挫折

汇编好难啊,尤其是各种调用各种寄存器绕来绕去一下子就晕了,整了一天,才只能做到简单的切换,还不能做到函数返回后继续运行.

好吧,我准备抄glibc的实现呀(不过..我不想..)

其实怎么说呢,汇编其实也不好,因为升了很多状态量,很容易引起莫名其妙的bug的,要不我就先ucontext的吧..

好吧

好吧,不得不认输了.今天准备了个多线程的例子准备好好展示下高超的性能,结果发现多线程的性能好的一塌糊涂,0.5billion/s数量级,超出mroutine的500倍,下面就是二者的性能测试例程:

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

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
int num = 0;
int i = 0;

void *test(void *argc)
{
    while (1) 
    {   
        pthread_mutex_lock(&mutex);
        i++;
        if (i > num)
        {   
            pthread_mutex_unlock(&mutex);
            return NULL;
        }   
        pthread_mutex_unlock(&mutex);
    }  
}

int main(int argc, char *argv[])
{
    num = atoi(argv[1]);

    pthread_t pid_1, pid_2;
    pthread_create(&pid_1, NULL, test, NULL);
    pthread_create(&pid_2, NULL, test, NULL);

    struct timeval start, end;

    gettimeofday(&start, NULL);
    pthread_join(pid_1, NULL);
    pthread_join(pid_2, NULL);
    gettimeofday(&end, NULL);

    printf("num: %d\n", num);
    printf("cost: %d(us)\n", (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec));

    return 0;
}

mroutine版本:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>

#include "mroutine.h"

void test_fun(struct mroutine_t *mr, int a)
{
    while (1) 
    {   
        a = mr_yield(mr, a + 1); 
    }   
}

void test(struct mroutine_t *mr, int num)
{
    int a = 1;
    mid_t a_mid = mr_create(mr, test_fun);
    int b = 1;
    mid_t b_mid = mr_create(mr, test_fun);
    
    int i = 0;
    while (i++ < num)
    {   
        mr_resume(mr, a_mid, a++);
        mr_resume(mr, b_mid, b++);
    }   
}

int main(int argc, char *argv[])
{
    int num = atoi(argv[1]);
    struct mroutine_t *mr = mr_ini(0, 0); 

    struct timeval start, end;
    gettimeofday(&start, NULL);
    test(mr, num);
    gettimeofday(&end, NULL);

    printf("num: %d\n", num);
    printf("cost: %d(us)\n", (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec));
    
    mr_fini(mr);

    return 0;
}

mroutine的上下文切换的大小其实和线程调度类似,但从性能来看,远远不如,怪不得人们在推荐使用使用pthread,而不是各种协程库

总结

现在正式的冻结mroutine的开发,等到日后有精力再来搞吧

这是一段很赞的经历