关于GHC实施的好介绍性文字?

在Haskell编程时(特别是在解决Project Euler问题时,其中次优解决方案倾向于强调CPU或内存需求)时,我经常困惑为什么程序行为如此。 我看着简介,尝试引入一些严格性,选择另一种数据结构,但大多数情况下它是在黑暗中摸索,因为我缺乏良好的直觉。

另外,虽然我知道Lisp,Prolog和命令式语言通常如何实现,但我不知道如何实现懒惰语言。 我也有点好奇。

因此,我想更多地了解从程序源到执行模型的整个链。

我想知道的事情:

  • 典型的优化应用了什么?

  • 当有多个候选人进行评估时,执行顺序是什么(虽然我知道它是由所需产出驱动的,但在首先评估A和然后评估B或首先评估B以检测您不需要评估之间仍然存在很大的性能差异A)

  • thunk代表了什么?

  • 如何使用堆栈和堆?

  • 什么是CAF? (分析表明有时热点在那里,但我不知道)


  • 关于GHC系统架构和方法的大部分技术信息都在他们的wiki中。 我会链接到关键部分,以及一些人们可能不知道的相关文章。

    什么典型的优化应用?

    关键的论文是:基于转换的优化器Haskell,SL Peyton Jones和A Santos,1998,描述了GHC模型应用类型保留转换(重构)核心类Haskell语言来改进时间和内存使用。 这个过程被称为“简化”。

    在Haskell编译器中完成的典型事情包括:

  • 内联;
  • Beta降低;
  • 死码消除;
  • 条件转变:案例,案例消除。
  • 拆箱;
  • 构建产品退货;
  • 完全懒惰转化;
  • 专业化;
  • Eta扩张;
  • Lambda提升;
  • 严格分析。
  • 有时:

  • 静态参数转换;
  • 构建/折叠或流式融合;
  • 常见的子表达式消除;
  • 构造函数专业化。
  • 上述论文是开始了解大多数优化的关键。 在前面的书中,实现函数式语言Simon Peyton Jones和David Lester给出了一些较简单的例子。

    当有多个候选人进行评估时,执行顺序是什么?

    假设你使用的是单处理器,那么答案是“编译器根据启发式和程序的需求模式静态选择的一些命令”。 如果您通过火花使用投机评估,那么“一些非确定性,乱序执行模式”。

    一般来说,要查看执行顺序是什么,请查看核心,例如ghc-core工具。 Core介绍在RWH关于优化的章节中。

    thunk代表了什么?

    Thunk用代码指针表示为堆分配数据。

    查看堆对象的布局。 具体来说,看看thunk是如何表现的。

    堆栈和堆是如何使用的?

    正如Spineless Tagless G-machine的设计所确定的那样,特别是自该论文发布以来进行了许多修改。 广义而言,执行模式:

  • (盒装)对象分配在全局堆上;
  • 每个线程对象都有一个堆栈,由与堆对象具有相同布局的框架组成;
  • 当你进行函数调用时,你将值推入堆栈并跳转到该函数;
  • 如果代码需要分配一个构造函数,那么这些数据将被放置在堆上。
  • 要深入了解堆栈使用模型,请参阅“推/输入与评估/应用”。

    什么是CAF?

    “恒定适用表格”。 例如,在您的程序执行期间分配的顶层常量。 由于它们是静态分配的,因此必须由垃圾收集器专门处理。


    参考和进一步阅读:

  • GHC评论
  • 无旋式Tagless G-machine
  • 通过转换编译
  • 推/输入与评估/应用
  • 作为一流公民的无箱价值
  • 内衬的秘密
  • 运行时支持多核Haskell

  • 在介绍性文本中,这可能不是您想到的,但杨德昌博士正在进行一系列的博客文章,讨论Haskell堆,如何实施Thunk等。

    这是有趣的,既有插图,也有对事物的解释,而没有深入研究Haskell新手的太多细节。 该系列涵盖了您的许多问题:

  • Haskell堆和thunk如何存储 - 系列中的第一篇文章
  • 绑定和CAF
  • IO monad如何被转换为原语
  • 在技​​术层面上,有很多论文涵盖(与其他内容一致),以及你想知道的部分内容。

  • SPJ撰写的一篇论文,Simon Marlow等人在Haskell的GC上 - 我没有读过它,但是由于GC经常代表Haskell所做工作的良好端口,所以它应该提供洞察力。
  • Haskell 2010年报告 - 我确信你会听说过这个,但它不好链接。 可以在地方进行干读,但最好的方法之一是了解Haskell是什么样的方式,至少是我读过的部分。
  • Haskell的历史 - 比名字所暗示的更具技术性,并且提供了一些对Haskell设计非常有趣的观点以及设计背后的决定。 读完之后,你不禁会更好地理解Haskell的实现。
  • 链接地址: http://www.djcxy.com/p/43179.html

    上一篇: Good introductory text about GHC implementation?

    下一篇: Performance Analysis via Core