woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

Ragel State Machine Compiler 的速度测试

据说Ragel生成的自动机程序,速度飞快,特地测试了一下,所得结果如下。

 

测试环境:      VC6 + Release下编译

测试规模:      一亿次

测试用例:      Ragel编译r_atoi.rl文件 vs crt lib atoi函数

测试结果:

Ragel的编译选项

时间(毫秒)

crt lib atoi

5218

-T0

31500

-T1

26328

-F0

17797

-F1

13578

-G0

13203

-G1

10531

-G2

5422

-G2选项编译后生成的代码,速度确实强大,基本上和atoi库函数没有多少差别,要知道atoi可是crt lib里的啊,已经精到不能再精,优化到不能再优化了。

PS:很久前,我曾用汇编写了个my_memcpy,然后和crt libmemcpy比速度,结果只有它的一半效率,然后用C写个再比,下滑到了1/6,从此以后我再也不怀疑crt lib的效率了,取而代之的是异常崇拜。

 

l        Ragel的编译选项

clip_image002

 

l        测试程序如下

 

#include <windows.h>

int main()

{

    char* p_sz = "784215491\n";

    long val = 0;

    long tick = GetTickCount();

    for (int i = 0; i < 100000000; ++i)

    {

       val = atoi(p_sz);

       //val = r_atoi(p_sz);//---- Ragel生成的状态机

    }

    tick = GetTickCount() - tick;

    printf("%ld\n", tick);

    return 0;

}

 

l        r_atoi.rl如下

/*

 * Convert a string to an integer.

 */

 

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

 

%%{

    machine r_atoi;

    write data;

}%%

 

long r_atoi( char *str )

{

    char *p = str, *pe = str + strlen( str );

    int cs;

    long val = 0;

    bool neg = false;

 

    %%{

       action see_neg {

           neg = true;

       }

 

       action add_digit {

           val = val * 10 + (fc - '0');

       }

 

       main :=

           ( '-'@see_neg | '+' )? ( digit @add_digit )+

           '\n';

 

       # Initialize and execute.

       write init;

       write exec;

    }%%

 

    if ( neg )

       val = -1 * val;

 

    if ( neg )

       val = -1 * val;

 

    if ( cs < r_atoi_first_final )

       fprintf( stderr, "r_atoi: there was an error\n" );

 

    return val;

};

 

 

#define BUFSIZE 1024

/*

 

int main()

{

    char buf[BUFSIZE];

    while ( fgets( buf, sizeof(buf), stdin ) != 0 ) {

       long value = r_atoi( buf );

       printf( "%lld\n", value );

    }

    return 0;

}

*/

#include <windows.h>

#include <limits.h>

int main()

{

    char* p_sz = "784215491\n";

    long val = 0;

    long tick = GetTickCount();

    for (int i = 0; i < 100000000; ++i)

    {

       val = r_atoi(p_sz);

    }

    tick = GetTickCount() - tick;

    printf("%ld\n", tick);

    return 0;

}

 

自动 生成的自动机图形

 testRagel

posted on 2009-01-02 00:09 肥仔 阅读(5662) 评论(7)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言

评论

# re: Ragel State Machine Compiler 的速度测试  回复  更多评论   

刚刚自己再手写了一个my_atoi,同等规模下测试,时间为:13536 ms
为什么差距就这么大涅?

long my_atoi(const char *str)
{
long val = 0;
bool b_neg = ('-' == *str);
if(*str == '-' || *str == '+')++str;
while(1)
switch(*str++)
{
case 0:
return b_neg?-val:val;
case '0':
val = val*10 + 0;
break;
case '1':
val = val*10 + 1;
break;
case '2':
val = val*10 + 2;
break;
case '3':
val = val*10 + 3;
break;
case '4':
val = val*10 + 4;
break;
case '5':
val = val*10 + 5;
break;
case '6':
val = val*10 + 6;
break;
case '7':
val = val*10 + 7;
break;
case '8':
val = val*10 + 8;
break;
case '9':
val = val*10 + 9;
break;
default:
return 0;
}
return 0;
};
2009-01-02 01:00 | 肥仔

# re: Ragel State Machine Compiler 的速度测试  回复  更多评论   

改善了一下my_atoi, 同等规模下测试,时间为:3468 ms
这一下心里平衡了,可以安稳睡一个觉了

long my_atoi(const char *str)
{
long val = 0;
bool b_neg = ('-' == *str);
if(*str == '-' || *str == '+')++str;
while(*str)
{
if(('0' - 1) < *str && *str < ('9' + 1))
val = val*10 + *str++ - '0';
else
break;
}
return b_neg?-val:val;
}
2009-01-02 01:09 | 肥仔

# re: Ragel State Machine Compiler 的速度测试  回复  更多评论   

再次改善了一下,加了一个inline,时间变为 2562 ms了,因为去掉了函数调用开销

inline long my_atoi(const char *str)
{
long val = 0;
bool b_neg = ('-' == *str);
if(*str == '-' || *str == '+')++str;
while(*str)
{
if(('0' - 1) < *str && *str < ('9' + 1))
val = val*10 + *str++ - '0';
else
break;
}
return b_neg?-val:val;
}
2009-01-02 01:16 | 肥仔

# re: Ragel State Machine Compiler 的速度测试  回复  更多评论   

DFA使用二维数组存放之后,快是必然的结果。

以前自己写过一个动态而不是生成代码的词法分析器,都能有1秒钟44万token的吞吐量。倘若是生成,不更快也说不过去。
2009-01-02 12:57 | 陈梓瀚(vczh)

# re: Ragel State Machine Compiler 的速度测试  回复  更多评论   

@陈梓瀚(vczh)
我知你对这类东西蛮有研究的,介绍Ragel,你不妨去弄弄,据我现在所得结果,虽然都是自动机识别,但他比Lex要快,尤其-G2选项之后,函数全部内联,统统goto,没有用数组,速度快到无法形容。

另外还可以生成dot文件,调用Graphviz画出自动机的图形,这个很爽啊(我把ragel生成的r_atoi自动机图补到上面了,翻上去找找...)

不知谁有闲时间去翻译一下它的man page,我想去翻译,无奈真是太忙了,生活所迫啊。
2009-01-02 13:29 | 肥仔

# re: Ragel State Machine Compiler 的速度测试  回复  更多评论   

Ragel用来解析协议是很棒,很快的东西。
Ruby的若干个http服务器,是使用Ragel生成http_parser的。还有解析html,xml的,等等。
做网络或者Web数据抓取的,也有空的兄弟,可以研究下,无奈中文资料基本没有,国外使用的人也不是太多。
2009-01-02 13:45 | 肥仔

# re: Ragel State Machine Compiler 的速度测试  回复  更多评论   

这个我也写过80-110W(token)/s, 在HP3906上跑的,这个转到二维矩阵后速度基本都定在那里了,瓶颈都是在内存传输的速度上了。

我当时自己写的regexp engine,跑C语言的文法。
2009-03-22 17:31 | baikaishiuc

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理