Scarpet的奇葩代码优化方法


  • TIS成员

    引言

    上一篇文章发布后,我主要做了两件事:一是写了个Heap数据结构;第二个就是明确了一下Carpet的脚本语言应该叫Scarpet。再有就是拿着一个测试时候发现的bug去小小的锤了一下作者,顺便学到了点优化。

    写出Heap算法以后,发生了一件奇妙的事情:同样是一万次的添加元素并排序,时间复杂度是O(log N)的堆竟然比O(N)慢了不少。后来在经由discord的Kayleigh大佬向gnembon交bug的时候,学到了优化方法:把return和if去掉

    heap_get(heap_name, index) -> return(element(var(heap_name), index));
    
    heap_get_left_index(index) -> return(index * 2 + 1);
    
    heap_get_right_index(index) -> return(index * 2 + 2);
    
    heap_get_parent_index(index) -> return(if (index == 0, null, floor((index - 1) / 2)));
    

    变成了这样的代码

    heap_get(heap_name, index) -> element(var(heap_name), index);
    
    heap_get_left_index(index) -> index * 2 + 1;
    
    heap_get_right_index(index) -> index * 2 + 2;
    
    heap_get_parent_index(index) -> if (index == 0, -1, floor((index - 1) / 2));
    

    关于var()的和特殊情况传引用的方法之后再说。这里只是把return语句去除,让函数自动返回最后一条语句的输出——效率真的提高了很多!

    猜测

    既然“万物皆函数”,那么有理由相信return()语句的也是函数,而且复杂度不一般。这种反直觉的特性应该还有许多,例如:

    • 自加语句:a += ba = a + b
    • 卫语句,例如 https://blog.csdn.net/jw903/article/details/45506777 这个例子
    • if内/外赋值的区别:a = if (x > y, 'yes', 'no')if (x > y, a = 'yes', a = 'no') 的区别
    • return 和 if 在加或不加的时的耗时影响
    • 几种迭代语句,loop, while, for
    • 整数和浮点数的运算
    • 预先声明变量
    • 变量类型的更改

    实验

    针对不同的测试内容设置两条略微不同的语句,每条语句实验三次,收集耗时数据

    自加自减

    /script run a = 0; loop (100000000, a += 1000); - 11s, 10s, 11s
    
    /script run a = 0; loop (100000000, a = a + 1000); - 18s, 19s, 18s
    

    卫语句

    /script run 
    equals(n1, n2) -> (
        if(n1 == n2, return(0)); 
        if(n1 < n2, return(-1)); 
        return(1)
    ); 
    loop (5000000, equals(floor(rand(2)), floor(rand(2)))); - 43s, 41s, 41s
    
    /script run 
    equals(n1, n2) -> (
        if(n1 == n2, 
            return(0), 
            if(n1 < n2, 
                return(-1), 
                return(1)
            )
        )
    ); 
    loop (5000000, equals(floor(rand(2)), floor(rand(2)))); - 34s, 37s, 37s
    

    赋值在if内和if外

    /script run a = ''; loop (100000000, a = if(floor(rand(2)) > 1, 'y', 'n')); - 42s, 43s, 43s
    
    /script run a = ''; loop (100000000, if(floor(rand(2)) > 1, 'a = y', a = 'n')); - 45s, 42s, 42s
    

    return和if

    /script run a() -> (return(rand(1000))); loop(1000000, a()); - 5.207s, 5.193s, 5.322s
    
    /script run a() -> (rand(1000));         loop(1000000, a()); - 0.153s, 0.137s, 0.146s
    
    /script run a() -> if (rand(2) - 1 > 0, 1, 0); loop (100000000, a()); - 44s, 45s, 42s
    
    /script run a() -> rand(2) - 1 > 0; loop (100000000, a()); - 38s, 39s, 39s
    

    几种迭代语句

    /script run loop (500000000, 0); - 27s, 25s, 26s
    
    /script run while (true, 500000000, 0); - 41s, 43s, 41s
    
    /script run for (range(500000000), 0);	- 38s, 39s, 42s
    

    整数与浮点数

    /script run global_l1 = l(); global_l2 = l(); loop (1000000, global_l1 += floor(rand(100)); global_l2 += rand(100)); 0;
    
    /script run loop(30, for (global_l1, a = _^_));	- 12s, 15s, 15s
    
    /script run loop(30, for (global_l2, a = _^_));	- 12s, 13s, 13s
    

    预先声明变量

    /script run loop(10000000, a = 0; a = 5; a = sqrt(a)) - 7.037s, 7.154s, 7.776s
    
    /script run loop(10000000, a = 5; a = sqrt(a)) - 4.539s, 5.270s, 5.040s
    

    变量类型更改

    /script run loop(20000000, a = l(); a = 10)	- 11s, 12s, 12s
    
    /script run loop(20000000, a = l(); b = 10) - 12s, 12s, 12s
    

    数据分析

    • 自加语句:a+=b的速度比a=a+b快将近一倍
    • 卫语句:不用卫语句稍微好一点,但是不明显
    • if内/外赋值:看不出明显区别
    • returnifreturn加了会多花不少时间,if添加前后差别不大
    • 几种迭代语句:loop最快,while只比for慢一点,后两者差别不大
    • 整数和浮点数的运算:整数反而慢一些,但是不明显
    • 预先声明变量:会花费和正常赋值差不多的时间,
    • 变量类型的更改:看不出明显区别

    总结

    能用a+=b的时候就不要手贱去写a=a+b;宁愿用麻烦的 if 嵌套也少用用 return 这一大公害;loop是个好东西,整数和浮点数也许不用那么担心了,没必要的预先声明变量就写在注释里吧……
    如有不满,欢迎自己测试以后锤作者



  • 我快速浏览了一下Scarpet的Interpreter,return慢的原因是因为return是通过throw ReturnStatement(val) 来实现让上层解释器中断控制流的,然后在解释器eval函数的那一层catchReturnStatement的值设置返回值。这是一个实现解释器时很常见的Trick,但是异常在Java里面是有比较大的Overhead,因为要保存stacktrace之类的……(话说不写return不才是函数式正统吗orz)
    其实这么说Scarpet的语言设计是稍微有点瑕疵的,包括list底层用ArrayList实现,那确实只能append不能insert了,不然开销太大了……


  • TIS成员

    @Alan20210202 之前写面向对象习惯了,满脑子都是引用对象;然后scarpet写了几天,回来写java的时候满脑子都是删return


 

友情链接

魔茶国际
Powered by TIS