当前位置: 首页>前端>正文

lua ffi string 0字符 lua string.format

大家直觉地认为".."操作符比string.format慢,这是个误解,实际上从连接字符串的效率来说".."比string.format快多了。先看看实验结果
10000000次实验,基础字符串11个字符
每次连接2个基础字符串 string.format 9秒; ".." 3秒
每次连接3个基础字符串 string.format 12秒; ".." 3秒
1000000次实验,基础字符串11个字符
每次连接10个基础字符串 string.format 4秒; ".." 1秒
10000000次实验,基础字符串59个字符
每次连接2个基础字符串 string.format 16秒; ".." 6秒
每次连接3个基础字符串 string.format 23秒; ".." 7秒
1000000次实验,基础字符串59个字符
每次连接10个基础字符串 string.format 7秒; ".." 2秒
一句话总结,".."比string.format平均快3-4倍,下面是实验的代码

local Beg = os.time()
 --local str = "hello world"
 local str = "hello world hello world hello world hello world hello world"
 --[[
 for i = 1, 10000000 do
 local res = str .. str
 --local res = string.format("%s%s", str, str)
 --3s 9s
 --6s 16s
 end
 for i = 1, 10000000 do
 --local res = str .. str .. str
 local res = string.format("%s%s%s", str, str, str)
 --3s 12s
 --7s 23s
 end
 for i = 1, 1000000 do
 local res = str .. str .. str .. str .. str .. str .. str .. str .. str .. str
 --local res = string.format("%s%s%s%s%s%s%s%s%s%s", str, str, str, str, str, str, str, str, str, str)
 --1s 4s
 --2s 7s
 end
 ]]
 print(os.time() - Beg)


为什么呢?看源码就知道了。".."被解释为OP_CONCAT,最终调用的是luaV_concat。string.format被注册为string库的一个函数,调用的时候要触发一个C函数调用,最终是调用str_format。直接贴源码:

void luaV_concat (lua_State *L, int total, int last) {
 do {
 StkId top = L->base + last + 1;
 int n = 2;  /* number of elements handled in this pass (at least 2) */
 if (!(ttisstring(top-2) || ttisnumber(top-2)) || !tostring(L, top-1)) {
 if (!call_binTM(L, top-2, top-1, top-2, TM_CONCAT))
 luaG_concaterror(L, top-2, top-1);
 } else if (tsvalue(top-1)->len == 0)  /* second op is empty? */
 (void)tostring(L, top - 2);  /* result is first op (as string) */
 else {
 /* at least two string values; get as many as possible */
 size_t tl = tsvalue(top-1)->len;
 char *buffer;
 int i;
 /* collect total length */
 for (n = 1; n < total && tostring(L, top-n-1); n++) {
 size_t l = tsvalue(top-n-1)->len;
 if (l >= MAX_SIZET - tl) luaG_runerror(L, "string length overflow");
 tl += l;
 }   
 buffer = luaZ_openspace(L, &G(L)->buff, tl);
 tl = 0;
 for (i=n; i>0; i--) {  /* concat all strings */
 size_t l = tsvalue(top-i)->len;
 memcpy(buffer+tl, svalue(top-i), l); 
 tl += l;
 }   
 setsvalue2s(L, top-n, luaS_newlstr(L, buffer, tl));
 }   
 total -= n-1;  /* got `n' strings to create 1 new */
 last -= n-1;
 } while (total > 1);  /* repeat until only 1 result left */
 }


首先看的是".."的实现,首先".."本身不是一个函数调用,仅仅是一个操作符。它的原理就是最直接的,就是把要连接的字符串全部找出来然后memcpy到新字符串上。之所以会有".."比较慢的误解,可能是源自于认为a .. b .. c需要先执行tmp = a .. b,再执行tmp = tmp .. c的操作,这样的拼接同一行如果出现很多次的话,memcpy的时间复杂度就会平方增长。但是看lua的源码就知道,它实际上并不是只连接两个字符串,它是会把所有需要连接的字符串都收集起来一起连接的。看以下例子

str = "a" .. "b"


以上语句的lua中间码如下

1       [1]     LOADK           0 -2    ; "a"
 2       [1]     LOADK           1 -3    ; "b"
 3       [1]     CONCAT          0 0 1
 4       [1]     SETGLOBAL       0 -1    ; str
 5       [1]     RETURN          0 1
 str = "a" .. "b" .. "c"


以上语句的lua中间码如下

1       [1]     LOADK           0 -2    ; "a"
 2       [1]     LOADK           1 -3    ; "b"
 3       [1]     LOADK           2 -4    ; "c"
 4       [1]     CONCAT          0 0 2
 5       [1]     SETGLOBAL       0 -1    ; str
 6       [1]     RETURN          0 1


首先可以看到,无论".."连接了多少个字符串,CONCAT都只会执行一次。其次,需要连接的字符串数量其实是记录在CONCAT指令的第三个参数里面。依然从源码可以看出来

case OP_CONCAT: {
 int b = GETARG_B(i);
 int c = GETARG_C(i);
 Protect(luaV_concat(L, c-b+1, c); luaC_checkGC(L));
 setobjs2s(L, RA(i), base+b);
 continue;
 }


OP_CONCAT的第一个参数是没用的,第二个参数是其实字符串在栈里的位置,第三个参数总共需要连接多少个字符串。需要连接的字符串会在栈里顺序排列下来。
也就是说,lua的实现没有想象中那么傻逼,这个连接字符串的算法从时间复杂度来说是O(n),我反正是想不到更快的算法了。
下面看string.format的源码:

static int str_format (lua_State *L) {
 int arg = 1;
 size_t sfl;
 const char *strfrmt = luaL_checklstring(L, arg, &sfl);
 const char *strfrmt_end = strfrmt+sfl;
 luaL_Buffer b;
 luaL_buffinit(L, &b);
 while (strfrmt < strfrmt_end) {
 if (*strfrmt != L_ESC)
 luaL_addchar(&b, *strfrmt++);
 else if (*++strfrmt == L_ESC)
 luaL_addchar(&b, *strfrmt++);  /* %% */
 else { /* format item */
 char form[MAX_FORMAT];  /* to store the format (`%...') */
 char buff[MAX_ITEM];  /* to store the formatted item */
 arg++;
 strfrmt = scanformat(L, strfrmt, form);
 switch (*strfrmt++) {
 case 'c': {
 sprintf(buff, form, (int)luaL_checknumber(L, arg));
 break;
 }   
 case 'd':  case 'i': {
 addintlen(form);
 sprintf(buff, form, (LUA_INTFRM_T)luaL_checknumber(L, arg));
 break;
 }   
 case 'o':  case 'u':  case 'x':  case 'X': {
 addintlen(form);
 sprintf(buff, form, (unsigned LUA_INTFRM_T)luaL_checknumber(L, arg));
 break;
 }   
 case 'e':  case 'E': case 'f':
 case 'g': case 'G': {
 sprintf(buff, form, (double)luaL_checknumber(L, arg));
 break;
 }   
 case 'q': {
 addquoted(L, &b, arg);
 continue;  /* skip the 'addsize' at the end */
 }   
 case 's': {
 size_t l;
 const char *s = luaL_checklstring(L, arg, &l);
 if (!strchr(form, '.') && l >= 100) {
 /* no precision and string is too long to be formatted;
 keep original string */
 lua_pushvalue(L, arg);
 luaL_addvalue(&b);
 continue;  /* skip the `addsize' at the end */
 }  
 else {
 sprintf(buff, form, s);
 break;
 }
 }
 default: {  /* also treat cases `pnLlh' */
 return luaL_error(L, "invalid option " LUA_QL("%%%c") " to "
 LUA_QL("format"), *(strfrmt - 1));
 }
 }
 luaL_addlstring(&b, buff, strlen(buff));
 }
 }
 luaL_pushresult(&b);
 return 1;
 }


string.format本身是一个函数调用,这就会有函数调用的消耗,不过我们暂时先忽略这种消耗。光看string.format本身也比".."的实现复杂不少。整个算法的思路是这样的:
循环地从格式字符串strfrmt找出有%的部分,每一次循环只处理从上次处理过的%的下一个字符到这次找到的%的这一部分的格式字符串。举个例子,假如strfrmt原本是"a%sb%s"。那么第一次循环就处理"a%s",第二次循环处理"b%s"。
每次循环所需要处理的那一部分格式字符串存储在format字符串里,根据这个format字符串和当前栈的参数可以生成这一部分格式化之后的结果,这个结果存储在buff里面。每次循环结束的时候,会把buff添加到最终结果b上。
对于%s来说,会有一个优化,如果字符串的长度大于100,不把中间结果存储在buff上,而是直接把这部分字符串连接到最终结果b上。
由此可以看到,string.format比起"..",如果纯粹讨论字符串拼接,如果需要拼接的内容本身不多,其复杂的地方主要是在于它需要扫描,复制格式字符串;复制中间字符串以及一些函数调用方面的消耗。
以10000000次实验,基础字符串11个字符,每次连接2个基础字符串的实验为基础,我尝试修改了lua的源码再次做了一下实验
首先,原版lua中,这个实验里string.format耗时9秒; ".."耗时3秒
当我把if (!strchr(form, '.') && l >= 100)这个条件去掉,也就是说无论何时都使用优化方案的话,string.format耗时5秒,快了一倍。这是合理的,因为没有这个优化,最终拼接结果的每一个字符,都要先存储在中间变量buff上,当然会慢一倍。
然后,为了模拟string.format的函数调用消耗,我把".."封装成一个函数来调用

local function concat(str1, str2)
 return str1 .. str2
 end


用concat替换".."之后,".."的耗时变成了4秒,和string.format已经很接近了。
为了模拟扫描和复制格式字符串的过程,我把concat再改一下,把string.format的格式字符串也加进去(根据luaV_concat的实现,增加在".."后面的字符串会被直接memcpy到最终结果后面),修改后的concat如下

local function concat(str1, str2)
 return str1 .. str2 .. "%s%s"
 end


用这个concat替换".."之后,".."的耗时变成了5秒,和string.format一样。下面贴出完整的代码

//lstrlib.c
 if (true/*!strchr(form, '.') && l >= 100*/) {
 --test.lua
 local Beg = os.time()
 local str = "hello world"
 local function concat(str1, str2)
 return str1 .. str2 .. "%s%s"
 end
 for i = 1, 10000000 do
 --local res = str .. str
 local res = concat(str, str)
 --local res = string.format("%s%s", str, str)
 end
 print(os.time() - Beg)


这个实验虽然不算很严谨,但是还是能说明问题。string.format如果仅仅用来拼字符串的话,和".."相比主要的消耗用在中间字符串的复制上,函数调用本身也有部分消耗,格式字符串的扫描和复制也占了一部分,这部分消耗取决于格式字符串的长度。
由此可知,如果不影响代码可读性的话,".."是肯定优于string.format的


https://www.xamrdz.com/web/2dh1942903.html

相关文章: