草庐IT

go - 对于实现函数式语言的虚拟机，有哪些明显的优化？

coder 2023-05-01 原文

我正在研究一种中间语言和一个虚拟机来运行具有几个“有问题”属性的函数式语言:

  • 词法命名空间(闭包)
  • 动态增长的调用堆栈
  • 慢整数类型(bignums)

    • 中间语言是基于堆栈的，具有当前命名空间的简单哈希表。为了让您了解它的外观，这里是 McCarthy91功能:
    # McCarthy 91: M(n) = n - 10 if n > 100 else M(M(n + 11))
.sub M
    args
    sto n

    rcl n
    float 100
    gt
    .if
        .sub
            rcl n
            float 10
            sub
        .end
        .sub
            rcl n
            float 11
            add
            list 1
            rcl M
            call-fast
            list 1
            rcl M
            tail
        .end
    call-fast
.end

    “大循环”很简单:
  • 取指令
  • 增加指令指针(或程序计数器)
  • 评估指令

    • 随着sto , rcl还有更多，函数调用有三个指令:
  • call复制命名空间(深拷贝)并将指令指针压入调用栈
  • call-fast是一样的，只是创建了一个浅拷贝
  • tail基本上是一个“转到”

    • 实现非常简单。为了给你一个更好的主意，这里只是“大循环”中间的一个随机片段(更新，见下文)

        } else if inst == 2 /* STO */ {
        local[data] = stack[len(stack) - 1]
        if code[ip + 1][0] != 3 {
            stack = stack[:len(stack) - 1]
        } else {
            ip++
        }
    } else if inst == 3 /* RCL */ {
        stack = append(stack, local[data])
    } else if inst == 12 /* .END */ {
        outer = outer[:len(outer) - 1]
        ip = calls[len(calls) - 1]
        calls = calls[:len(calls) - 1]
    } else if inst == 20 /* CALL */ {
        calls = append(calls, ip)
        cp := make(Local, len(local))
        copy(cp, local)
        outer = append(outer, &cp)
        x := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        ip = x.(int)
    } else if inst == 21 /* TAIL */ {
        x := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        ip = x.(int)

    问题是这样的:用 -10000 的值调用 McCarthy91 16 次需要 3 秒，几乎没有区别(在优化掉深拷贝之后，增加了近一秒)。

    我的问题是:优化这种语言的解释有哪些常用技术？有没有低垂的果实？

    我在我的列表中使用了 slice (参数，各种堆栈，命名空间的映射 slice ，......)，所以我到处做这样的事情:call_stack[:len(call_stack) - 1] .现在，我真的不知道是什么代码段使这个程序变慢了。任何提示将不胜感激，但我主要是在寻找一般优化策略。

    旁白:

    通过绕过我的调用约定，我可以大大减少执行时间。 list <n>指令获取堆栈的 n 个参数并将它们的列表推回到堆栈中，args指令从该列表中弹出并将每个项目推回到堆栈中。这首先检查是否使用正确数量的参数调用函数，其次能够调用具有可变参数列表的函数(即 (defun f x:xs) )。删除它，并添加一条指令 sto* <x> , 替换 sto <x>; rcl <x> ，我可以把它缩短到 2 秒。仍然不精彩，我必须拥有这个 list/args反正生意。 :)

    另一边(我知道这是一个很长的问题，抱歉):

    用 pprof 分析程序告诉我的很少(我是 Go 的新手，以防万一):-)。这些是 pprof 报告的前 3 项:
      16   6.1%   6.1%       16   6.1% sweep               pkg/runtime/mgc0.c:745
   9   3.4%   9.5%        9   3.4% fmt.(*fmt).fmt_qc   pkg/fmt/format.go:323
   4   1.5%  13.0%        4   1.5% fmt.(*fmt).integer  pkg/fmt/format.go:248

    这些是我迄今为止所做的更改:
  • 我删除了哈希表。相反，我现在只传递指向数组的指针，并且只在必要时有效地复制本地范围。
  • 我用整数操作码替换了指令名称。之前，我浪费了相当多的时间来比较字符串。
  • call-fast指令消失了(在其他更改后加速不再可测量)
  • 我没有“int”、“float”和“str”指令，我只有一个 eval我在编译时评估常量(即字节码的编译)。然后eval只是推送对它们的引用。
  • 更改 .if 的语义后，我可以摆脱这些伪函数。现在是 .if , .else和 .endif , 带有类似于 .sub 的隐式 goto à 和块语义. ( some example code )

    • 实现了词法分析器、解析器和字节码编译器后，速度有所下降，但并没有那么严重。计算 MC(-10000) 16 次使其在 1.2 秒内评估 420 万条字节码指令。这是a sample of the code it generates (来自 this)。

    The whole thing is on github

    最佳答案

    有几十年的研究可以优化:

  • Implementing functional languages: a tutorial ，西蒙佩顿琼斯和大卫莱斯特。由 Prentice Hall 出版，1992 年。
  • Practical Foundations for Programming Languages , 罗伯特·哈珀

    • 关于go - 对于实现函数式语言的虚拟机，有哪些明显的优化？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10992852/

    的gocodestacklifunctional-programminginterpretervm-implementationintermediate-language

    有关go - 对于实现函数式语言的虚拟机，有哪些明显的优化？的更多相关文章

    1. ruby - 如何将脚本文件的末尾读取为数据文件(Perl 或任何其他语言) - 2

      我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚

    2. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

      我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

    3. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

      我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

    4. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

      我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

    5. ruby - 在 Ruby 中有条件地定义函数 - 2

      我有一些代码在几个不同的位置之一运行:作为具有调试输出的命令行工具，作为不接受任何输出的更大程序的一部分，以及在Rails环境中。有时我需要根据代码的位置对代码进行细微的更改，我意识到以下样式似乎可行:print"Testingnestedfunctionsdefined\n"CLI=trueifCLIdeftest_printprint"CommandLineVersion\n"endelsedeftest_printprint"ReleaseVersion\n"endendtest_print()这导致:TestingnestedfunctionsdefinedCommandLin

    6. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

      几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

    7. ruby - 在 Ruby 中按名称传递函数 - 2

      如何在Ruby中按名称传递函数？(我使用Ruby才几个小时，所以我还在想办法。)nums=[1,2,3,4]#Thisworks,butismoreverbosethanI'dlikenums.eachdo|i|putsiend#InJS,Icouldjustdosomethinglike:#nums.forEach(console.log)#InF#,itwouldbesomethinglike:#List.iternums(printf"%A")#InRuby,IwishIcoulddosomethinglike:nums.eachputs在Ruby中能不能做到类似的简洁？我可以只

    8. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

      华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

    9. Unity 热更新技术 | （三） Lua语言基本介绍及下载安装 - 2

      ?博客主页：https://xiaoy.blog.csdn.net?本文由呆呆敲代码的小Y原创，首发于CSDN??学习专栏推荐：Unity系统学习专栏?游戏制作专栏推荐：游戏制作?Unity实战100例专栏推荐：Unity实战100例教程?欢迎点赞?收藏⭐留言?如有错误敬请指正！?未来很长，值得我们全力奔赴更美好的生活✨------------------❤️分割线❤️-------------------------

    10. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

      嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

    随机推荐