Roc Tops Java, Go in Quicksort via Opportunistic In-Place Mutation

Roc凭借机会性就地变异在快速排序中超越Java与Go 编译器可通过静态别名分析在不违背纯函数不可变性的前提下执行内存就地更新，从而在重度变异工作负载上超越命令式语言。 Feldman对纯函数式编程本质上慢于命令式编程的传统观念提出质疑，认为运行时执行模型、编译策略和装箱开销对实际性能的影响远大于范式差异。他指出，通过非装箱闭包和去函数化可以使托管副作用的成本几乎降为零，而不可变性既能实现快速的结构检查，也能被完全编译消除。聚焦于受Elm启发的原生语言Roc，Feldman解释了如何通过Morphic求解器进行编译期静态别名分析以实现机会性就地变异。这种编译器优化使快速排序的纯函数式实现能够在底层执行就地交换，性能超越了JavaScript、Java和Go的命令式实现，并紧跟C++之后。 语言的基础机制往往比范式差异影响更大；将NoRedInk的主要后端服务从Ruby on Rails重写为编译型Haskell带来了10倍的性能提升。 (2:08) Roc利用LLVM编译为原生二进制文件，消除了装箱开销，并使用编译期静态引用计数来回收内存，避免了垃圾回收暂停。 (5:04) 纯函数式语言通过保持任务和闭包为非装箱状态，并应用去函数化以直接调用取代动态函数指针，从而消除了托管副作用带来的性能损耗。 (10:21) 通过借助Morphic别名分析求解器应用机会性就地变异，Roc的纯函数式快速排序运行速度超过了Java、JavaScript、Go和Haskell，仅次于C++。 (28:43)

Richard Feldman argues that pure functional languages can rival or exceed imperative performance by eliminating baseline runtime overhead and using static analysis to turn safe, immutable code into in-place machine operations. Runtime Execution Models and Baseline Overhead (2:08) Language overhead frequently eclipses differences in programming paradigms. Feldman highlights production metrics from NoRedInk, where migrating the primary backend service from Ruby on Rails to Haskell produced an approximate 10x performance improvement. This speedup did not stem from intrinsic properties of functional code, but from Haskell's compiled execution model outpacing Ruby's interpreted abstract syntax tree. Execution speed follows a continuum from interpreted ASTs and bytecode virtual machines up to LLVM-optimized native binaries. Language runtimes further compound overhead through boxing, which forces values into heap-allocated pointers rather than hardware registers or the stack. To strip away these baseline penalties, Feldman designed the pure functional language Roc to compile via LLVM, aggressively unbox values, and rely on static reference counting informed by research papers like *Counting Immutable Beans* and *Perseus*. Managed Effects Without Closure Penalties (8:03) Pure functional programming prohibits side effects, relying instead on managed effects where code builds an inert data structure that the language runtime executes. Skeptics often question whether wrapping operations inside task data structures degrades throughput, as seen with asynchronous Promises in imperative environments. Because managed effects fundamentally wrap functions within closures, their performance cost equals the overhead of closure allocation. In Roc, this overhead is minimized at compile time: tasks and closures remain unboxed on the stack, and the compiler applies defunctionalization to transform dynamic function pointers into enumerated direct calls. Feldman concludes that this compilation strategy renders the execution penalty of wrapping effects negligible. Opportunistic In-Place Mutation and Quicksort (21:14) While immutability provides performance wins in UI rendering by replacing deep object traversals with single-instruction pointer equality checks, it presents severe challenges for low-level algorithms like Quicksort. A pure implementation that allocates fresh memory buffers on every swap cannot match imperative memory locality. Historically, functional languages tackled this by either accepting performance losses or dropping into imperative escape hatches, such as Haskell using `Data.Vector.Generic.Mutable` with unsafe functions that sacrifice memory safety. Roc resolves this conflict through opportunistic in-place mutation. If the compiler proves that a data structure is never referenced again, modifying its memory directly preserves semantic referential transparency to the rest of the program. While dynamic reference counting can trigger in-place updates when an object's reference count is one, Roc uses static alias analysis via the Berkeley-developed Morphic solver to detect uniqueness at compile time, eliminating runtime branching. Benchmark Outcomes and Implementation Maturity (28:43) In a benchmark sorting 10 million numbers across 100 iterations, Roc's purely functional Quicksort implementation outperformed JavaScript, Java, Go, and the unsafe imperative Haskell implementation, placing second only to C++. The functional code expressed loops through tail-recursive helpers and swaps through immutable record returns, but static alias analysis paired with LLVM lowered those pure semantics into the exact in-place mutations executed by imperative systems. Feldman emphasizes that pure functional performance advantages arise from three avenues: alignment with specific problem domains like UI rendering, lower baseline runtime overhead compared to dynamic languages, and aggressive compiler optimizations. However, he acknowledges that Roc remains an active work in progress without large production codebases deployed, meaning the long-term behavior of its static reference counting at scale remains to be validated. Feldman demonstrates that pure functional programming can match imperative speed when compilers bridge the gap through unboxing, tail-call optimization, and opportunistic in-place mutation. However, because Roc has not yet been deployed in large-scale production environments, the practical reliability and scalability of its static reference counting system remain unverified.

Richard Feldman 认为，纯函数式语言在性能上不必劣于命令式语言；只要大幅削减语言底层的运行时开销，并结合基于静态分析的“适时就地变异”等编译器优化技术，纯函数式代码在很多场景下能够媲美甚至超越主流命令式语言。 范式差异与语言运行时开销的本质辨析 (2:08) 许多开发者习惯将性能瓶颈归咎于纯函数式范式本身，但 Feldman 指出，实际执行效率往往更多取决于语言自身的底层运行时开销，而非命令式与纯函数式的范式差别。例如，NoRedInk 将每年处理数十亿学生答题的高流量后端核心服务从 Ruby on Rails 重写为纯函数式语言 Haskell 后，观察到了约 10 倍的性能提升。Feldman 明确说明，这种大幅提升并非源于纯函数式代码具有某种与生俱来的速度，而是因为静态编译生成的原生二进制文件摆脱了解释型抽象语法树（AST）的巨大开销。在执行模型层级中，从解释型 AST、字节码虚拟机，再到直接生成二进制乃至基于 LLVM 优化的原生二进制，各层级开销差异显著。此外，像 Python 等语言中将数值和记录普遍进行堆分配的装箱（boxing）操作，也会产生大量的指针间接寻址与内存压力，严重拖累性能。 Roc 降低底层开销的架构设计 (5:04) 为了在浏览器之外复现 Elm 语言的开发体验，Feldman 主导设计了纯函数式语言 Roc，并将其定位为直译为本地独立二进制的高性能系统。在内存管理方面，相较于会引发停顿的追踪式垃圾回收（Tracing GC）以及具有精细控制力但依赖手工管理的机制，Roc 采用了静态引用计数。该方案参考了学术论文《Counting Immutable Beans》与《Perseus》，由编译器在编译阶段推断引用计数的增减，若发现相互抵消便直接在生成的机器代码中消除相应指令；在特定场景下，Roc 还能无缝切换为运行速度极高的区域分配（arena/bump allocation）。结合 LLVM 后端深度优化、对基本数据类型与记录的全面去装箱（unboxing）处理，Roc 在语言底层最大程度规避了运行时的间接开销。 托管效应与纯不可变性的性能权衡 (8:03) 纯函数式编程禁止任意副作用和就地变异，但这并不意味着程序无法进行真实 I/O。在 Roc 与 Elm 中，所有副作用均转化为受运行时控制的“托管效应（Managed Effects）”。与 JavaScript 中立即触发网络请求的 Promise 机制不同，托管效应只是在组装无副作用的任务描述结构，交由入口统一执行。针对将所有任务包装为闭包可能导致的性能退化，Roc 通过未装箱的任务结构与去功能化（defunctionalization）技术，将动态函数指针调用转化为枚举直接调用，使抽象层包装成本降至微乎其微。而在不可变性方面，纯函数式的内存分配确实在低级算法中存在劣势，但在 UI 渲染等特定场景下，不可变数据结构允许通过单指令指针比较（oldState === newState）快速完成等价性检验，跳过整个渲染子树的深层比对，从而在整体架构上产生超越可变更新的净收益。 适时就地变异与纯函数式快速排序 (15:51) 对于快速排序（Quicksort）等重度依赖内存就地交换的算法，传统纯函数式实现若频繁克隆数组便会导致性能急剧恶化。Haskell 社区常借助包含 unsafeRead 与 unsafeSwap 的可变向量模块或外部函数接口（FFI）来实现快速排序，但这打破了引用透明性并失去了内存边界安全。Roc 则采取了编译器层面的“适时就地变异（opportunistic in-place mutation）”策略：如果编译器检测到某个数据结构在更新后不再被后续代码引用（即引用计数为 1），便可在不破坏外部纯粹性语义的前提下，直接在原内存缓冲区执行物理就地变异。Roc 最初由 Folkert de Vries 尝试使用基于 Clean 语言的唯一性类型进行分析，后迁移至加利福尼亚大学伯克利分校本科研究团队构建的 Morphic 求解器，通过静态别名分析在编译期锁定变异机会，避免了运行时分支判断。 千万级数据基准测试表现与突破 在对 1000 万个数值执行 100 次快速排序的跨语言基准测试中，Roc 采用完全纯粹的尾递归函数与不可变语义实现，借助 Morphic 别名分析和 LLVM 优化降维，生成了与命令式算法完全一致的底层就地交换指令。测试结果显示，Roc 的纯函数式快速排序耗时低于 JavaScript、使用原生 int[] 数组的 Java、Go，甚至超越了利用 unsafe 内部可变特性的 Haskell，在测试阵列中仅次于默认跳过边界检查的 C++。Feldman 坦承该测试并非绝对严苛的科研定论，但它印证了结合尾调用优化（TCO）、未装箱内存布局、静态引用计数以及适时就地变异后，纯函数式语言在传统病态算法中同样能够跑赢大部分主流垃圾回收型命令式语言。 Feldman 总结指出，纯函数式语言超越命令式语言的路径主要有三条：利用不可变性天然契合的特定领域优势、消除动态运行时的基线语言开销，以及依靠高级编译器优化将纯语义转化为底层就地操作。然而他也坦白承认，由于 Roc 目前仍处于活跃开发阶段，尚未在超大规模的严肃生产环境中长期部署，其静态引用计数和各项机制在极端复杂工程规模下的实际表现仍有待后续验证。

## Background 本内容由 Strange Loop Conference 官方频道于 2021 年 10 月 20 日在 YouTube 发布，主讲人为 NoRedInk 软件工程师、Elm 社区知名成员 Richard Feldman。视频页面简介指出，许多人认为函数式编程易于维护但运行缓慢，而演讲者通过自身深入纯函数式语言的经验，从网络层剖析至 CPU 指令级，揭示纯函数式语言如何在性能上超越命令式对手。 ## TL;DR Richard Feldman 探讨了纯函数式编程语言如何打破“运行缓慢”的固有偏见，并在性能基准测试中超越主流命令式语言。他以正在开发的 Roc 语言为例，剖析了底层语言开销、未装箱值（Unboxed Values）、托管副作用（Managed Effects）以及基于 LLVM 的原生编译对性能的决定性影响。针对纯函数式语言缺乏就地变异（In-place Mutation）的致命弱点，演讲详细阐释了如何通过静态引用计数分析与 Morphic 求解器实现“机会性就地变异”。最终在极度依赖就地置换的快速排序（Quicksort）测试中，完全纯函数式的 Roc 成功击败了 JavaScript、Java、Go 以及采用危险变异的 Haskell，仅次于硬件直连的 C++，证明了现代优化编译器足以让纯函数式程序兼具极致的人机工效与机器性能。 ## Atmosphere & style 演讲节奏明快、条理极其严密，洋溢着工程实践与编译理论交织的技术兴奋感。Richard Feldman 语言风趣且坦率诚恳，既不回避纯函数式快排“代码更冗长、表象像在做无用功”的客观局限，又犀利调侃了传统 Haskell 使用 `unsafe` 作弊的危险现状。现场氛围从起初对语言开销的理性推导，逐步推进到公布纯函数式快排跑赢各大命令式语言基准测试的高潮，观众能深切感受到主讲人那种用严谨编译器架构打破行业偏见时的欣喜与自豪。 ## Bulletin - [00:06](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=6s) Richard Feldman 介绍了旨在继承 Elm 优良开发体验并编译为原生二进制的新纯函数式语言 Roc，致力于打破纯函数式编程运行缓慢的刻板印象。 - [02:13](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=133s) NoRedInk 将核心生产服务从 Ruby 迁移到 Haskell 后获得了约 10 倍的性能提升，说明底层的执行模型与语言运行时开销往往比编程范式本身更具决定性。 - [23:58](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1438s) Roc 引入了基于加州大学伯克利分校 Morphic 求解器的静态别名分析与静态引用计数，使编译器能在保持外部不可变语义的同时，静默执行底层的机会性就地变异。 - [26:35](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1595s) 在 1000 万个数字的快速排序极限基准测试中，完全遵循纯函数式编写的 Roc 成功击败了 JavaScript、Java、Go 以及采用 unsafe 就地修改的 Haskell，性能仅次于 C++。 ## Key takeaways - [03:24](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=204s) 编程语言的执行模型层级（动态解释、字节码虚拟机、原生二进制、LLVM 原生编译）和装箱开销对最终性能起着决定性作用。 - [05:04](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=304s) 追踪式垃圾回收器（Tracing GC）不可避免地伴随 GC 停顿，而 Roc 通过 LLVM 优化后端、全场景未装箱数值以及静态引用计数来抹平底层运行时开销。 - [08:03](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=483s) 纯函数式语言并非不做实际工作，而是通过类型系统将副作用转变为由运行时统一调度的托管副作用（Managed Effects）。 - [10:04](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=604s) Roc 借助未装箱闭包、未装箱 Task 以及去函数化（Defunctionalization）的枚举式直接调用，将托管副作用带来的包装抽象损耗降到了最低。 - [11:47](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=707s) 不可变性在底层硬件视角可能带来额外内存分配负担，但在高层架构（如前端虚拟 DOM 渲染）中能通过常数级的引用相等性检查跳过海量冗余计算，反直觉地提升总体性能。 - [14:16](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=856s) 快速排序（Quicksort）的性能核心高度依赖内存元素的就地置换，这使其成为检验纯函数式语言性能极限的最严苛基准算法。 - [15:51](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=951s) 教科书版纯函数式快速排序并非真正的原地快排；而 Haskell 虽可借助 Data.Vector.Generic.Mutable 和 unsafe 操作实现就地变异，但代价是彻底破坏引用透明性与内存安全。 - [21:15](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1275s) 正如尾调用优化（TCO）将递归无损转换为循环一样，如果编译器静态推导出数组在后续不再被引用，便可在硬件层面触发“机会性就地变异”（Opportunistic In-place Mutation）。 - [23:58](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1438s) 当目标对象在写入前其唯一性能够被编译期别名分析静态判定或运行时引用计数确认为 1 时，编译器可以直接覆写原内存而绝不破坏纯函数语言的语义。 - [25:31](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1531s) Clean 语言基于独占类型（Uniqueness Types）的第一代静态检测方案过于脆弱，Roc 转向了结合 UC Berkeley 研发的 Morphic 别名分析求解器，实现了稳健的可插拔检测。 - [26:35](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1595s) Roc 在纯函数式快速排序中不仅击败了命令式 JavaScript，还超越了 Java、Go 和开了 unsafe 外挂的 Haskell，证明了纯函数式在依赖就地突变的算法上同样具备极强竞争力。 - [33:23](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=2003s) 纯函数式超越命令式主要依托三条路径：特定高层场景的范式契合红利、消除基线语言开销的编译模型差距、以及编译期激进优化的力量。 ## Detailed walkthrough ### [00:06](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=6s) 从 Elm 到 Roc：纯函数式语言的性能探索 讲者 Richard Feldman 介绍了本次演讲的主题——纯函数式语言如何超越命令式语言。在过去的几年里，他一直致力于打造一门名为 Roc 的编程语言。Roc 的直接灵感来源和前身是他多年来最喜爱的语言 Elm。Elm 带来了极佳的开发者体验和愉悦感，作为一门编译为 JavaScript 的纯函数式语言，它非常适合构建基于浏览器的用户界面。然而，Richard 希望将这种愉悦的纯函数式体验带到浏览器 UI 之外的其他领域，因此 Roc 沿用了 Elm 的核心理念，但选择直接编译为原生二进制文件，以支持更广泛的使用场景。 Richard 回忆起自己最初接触 Elm 是在 2014 年读到的一篇名为《Blazing Fast HTML in Elm》的博客文章。当时他正在构建对性能敏感的 UI，那篇基准测试文章给了他极大的信心，确保他在获得舒适开发体验的同时，应用程序最终也能跑得飞快。在设计 Roc 时，他也希望延续这一价值取向，让这门语言能够极其高速地运行程序。但纯函数式语言面临着一个固有的技术挑战：纯函数意味着没有副作用、没有突变（In-place Mutation）。然而现实中部分经典算法（例如快速排序 Quicksort）高度依赖就地突变来换取高性能，这看似是纯函数式编程无法避免的性能硬伤。 ```mermaid flowchart LR accTitle: 从 Elm 到 Roc 的演进对比 accDescr: 展示 Elm 与 Roc 在语言范式、编译目标和应用场景上的异同 subgraph Elm["Elm"] E1["纯函数式语言"] --> E2["编译到 JavaScript"] E2 --> E3["浏览器 UI 界面"] end subgraph Roc["Roc"] R1["纯函数式语言"] --> R2["编译到原生二进制 (LLVM)"] R2 --> R3["通用计算 / 命令行 / 后端服务"] end ``` - Richard Feldman 指出开发纯函数式算法的核心矛盾：“The fact of the matter is some algorithms just require in-place mutation to run fast.” - 对于就地突变重度依赖的场景，纯函数式语言常常面临质疑：“Like for example how competitive could a pure functional language possibly be at a mutation-heavy algorithm like quicksort?” --- ### [02:13](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=133s) 语言运行时开销与 NoRedInk 的迁移案例 要分析纯函数式语言能否胜过命令式语言，首先必须剖析“语言开销”（Language Overhead），即一门语言本身会引入多少额外开销、能否充分发挥底层硬件的全部性能。Richard 以自己工作的公司 NoRedInk 为例进行了说明。NoRedInk 是一个面向英语教师和学生的教育平台，每年学生要在上面回答数十亿道题目。他们的后端架构原本使用非常普遍的 Ruby on Rails，但近年来逐步将后端迁移至著名的纯函数式语言 Haskell。 在迁移过程中，他们把公司内部流量最高、最核心、对性能最关键的服务从 Ruby 迁移到了 Haskell。该服务在重构前后承担的功能几乎完全一致，但性能测试结果显示，Haskell 版本的运行速度比 Ruby 版本快了整整 10 倍左右。Richard 坦言，这绝不是因为纯函数式编程具备某种让一切自动加速的“魔法配方”，而是因为执行模型和语言开销方面的差异完全主导了这场对比：Ruby 解释执行且开销巨大，而 Haskell 是静态编译为二进制运行的。 - NoRedInk 迁移的核心服务每年处理学生提交的数十亿道练习题目。 - Ruby 迁移到 Haskell 后带来了约 10 倍（10x）的性能提升。 - Richard Feldman 解释性能提升的真相：“Now this we're well aware was not because like pure functional programming is like oh that that's it's this magic sauce that just makes everything run faster.” --- ### [03:24](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=204s) 执行模型分级与装箱开销 Richard 将主流编程语言的执行模型从高开销到低开销进行了梯队划分。处于最高开销层级的是将源码解析为抽象语法树（AST）后直接动态解释执行的语言（如 Python、Ruby、JavaScript，尽管部分带 JIT）；其次是编译为字节码并由虚拟机解释执行的语言（如 Java、C# 以及编译为 BEAM 字节码的 Elixir）；最快的类别则是直接编译为独立原生二进制文件的语言（如 Go、Swift 和 Haskell）。在原生编译的梯队中，LLVM 编译更是一个独特且强大的存在，C++、Rust、Zig 等语言均借助 LLVM 获得极致的优化与硬件贴合度，这也是 Roc 选择 LLVM 的原因。 除了执行模型外，另一个拖慢性能的关键因素是装箱（Boxing），即把数据分配在堆（Heap）上，其访问与分配速度远慢于栈（Stack）或 CPU 寄存器。在很多语言中，基本数字、对象/记录、函数及闭包都会被默认装箱。例如 Python 中的数字默认是装箱的，进行数值计算极其缓慢，开发者不得不借助 NumPy 等 C 扩展库来进行加速。 | 执行模型类别 | 代表语言 | 性能与开销特征 | |:--- |:--- |:--- | | **源码动态解释执行 (Interpreted)** | Python, Ruby, JavaScript (部分带 JIT) | 开销最高，依靠运行时解析 AST 或 JIT 优化热点循环 | | **虚拟机字节码 (Interpreted Bytecode)** | Java, C#, Elixir (BEAM) | 开销居中，平台无关性强，通过虚拟机调度运行 | | **编译为原生二进制 (Compile to Binary)** | Go, Swift, Haskell | 开销很低，生成独立机器码直接执行 | | **LLVM 优化原生二进制** | C++, Rust, Zig, **Roc** | 黄金标准，底层极致优化，最大限度贴近硬件极限性能 | - 装箱不仅发生在复合数据结构中，在 Python 这类语言中连基础数值也是堆分配装箱的。 - Roc 致力于全场景消灭不必要的装箱：“We're using unboxed values basically everywhere we possibly can there aren't any values that I know of that are boxed unnecessarily.” --- ### [05:04](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=304s) 内存管理策略与 Roc 的无停顿优化 在内存管理方面，Richard 梳理了三种主流机制： 1. **手动或半自动的单次申请与释放**：C 语言需要手动调用 `malloc` 和 `free`；而 C++、Rust 和 Zig 提供了现代化工具协助管理，但底层依然遵循逐个对象分配与释放的模式，兼具低延迟与高性能。 2. **追踪式垃圾回收（Tracing GC）**：Java、JavaScript、Go、Haskell 等语言广泛采用。其最大痛点在于无法避免垃圾回收暂停（GC Pauses），程序会在特定时间段被冻结以清理内存。 3. **自动引用计数（Automatic Reference Counting, ARC）**：Python、Swift 和 Roc 使用此方式。虽然它消除了全局 GC 暂停，但运行时的引用计数更新带来了整体开销，常规吞吐量（Throughput）往往低于追踪式 GC。 为了解决引用计数的吞吐量短板，Roc 引入了“静态引用计数”（Static Reference Counting）技术。通过实现学术论文《Counting Immutable Beans》和《Perseus》中的理念，编译器能够在编译期推导引用计数的增减，并直接将能够相互抵消的操作剔除，从而大幅减少运行时实际执行的引用计数指令。此外，Roc 还实现了一种对应用程序开发者完全透明的内存技术——Arena 分配（Bump Allocation）。这种机制在特定场景下速度甚至快于 Tracing GC 和单独的手动内存管理。凭借 LLVM 优化、全面去装箱（Unboxed Values）以及静态引用计数与 Arena 分配，Roc 在语言底层开销的控制上打下了坚实基础。 - 传统的追踪式 GC 存在普遍的性能卡顿：“Big downside of tracing garbage collectors compared to individual allocations and deallocations is that you get garbage collection pauses.” - Roc 采用的两篇核心编译期引用计数优化论文为《Counting Immutable Beans》和《Perseus》。 - 总结 Roc 在消除语言开销方面的三大支柱：LLVM 编译后端、全局去装箱、以及静态引用计数加透明的 Arena/Bump 内存分配机制。 ### [08:03](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=483s) 无副作用与托管副作用（Managed Effects） 纯函数式语言在性能竞争中面临两大严苛约束：不允许副作用、不允许就地可变性（Mutation）。很多人会误以为纯函数式语言因为“没有副作用”就无法做实际工作。正如 Richard Feldman 所说：“A common question that I hear asked of people who talk about pure functional programming languages is are you just heating the CPU up? Side effects are like everything.” 甚至有人怀疑像 Haskell 这样的语言怎么可能支撑起巨大的线上生产流量、难道它从不读写数据库吗？事实并非如此，程序依旧在执行所有必要的效果，只不过它们不是任性的“副作用”，而是被纳入类型系统监管的“托管副作用”（Managed Effects）。 性能层面的权衡，归根结底是“副作用与托管副作用”之间的对比。在 JavaScript 等命令式环境中，异步副作用通常借助 Promise 实现：调用 `fetch(url)` 发起请求，再链式调用 `.then(callback)` 处理下一个 Promise。而在 Elm 这样的纯函数式语言中，代码结构几乎完全一样，只是语法形式改为了管道操作符 `|> Task.andThen`。两者的核心差异在于执行时机：在 JavaScript 中，Promise 一旦实例化，`fetch` 立即在底层发出 HTTP 请求；而纯函数式语言的 Managed Effects 只是纯粹的数据结构拼接，它在构建阶段绝不触发实际 IO，必须层层包装后交给 `main` 入口，由语言的运行时系统在程序真正启动时负责调度与执行。 ```mermaid flowchart TD accTitle: Side Effects vs Managed Effects Execution Flow accDescr: Comparison showing imperative promises executing immediately while managed effects execute via runtime subgraph Imperative["命令式: JavaScript Promise"] P1["创建 Promise / fetch(url)"] -->|"立即触发"| E1["发送网络 HTTP 请求"] E1 --> P2[".then(callback) 链式回调"] end subgraph PureFunctional["纯函数式: Managed Effects (Elm / Roc)"] T1["构建 Task 数据结构"] -->|"组合"| T2["Task.andThen 拼接逻辑"] T2 -->|"移交"| M["传递给 main 入口"] M -->|"运行时统一调度"| E2["执行底层 IO / 实际效果"] end ``` ### [10:04](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=604s) 托管效果的抽象开销与去函数化（Defunctionalization） 既然 Managed Effects 必须将所有效果层层包裹在类似 Promise 或 Task 的结构中，那么它在全系统范围内强加的包装开销究竟有多大？从底层实现来看，无论是 Promise 还是 Task，本质上都是闭包（Closures）——即捕获了外层词法作用域的环境，并在内部嵌套了其他闭包。因此，包裹效果的运行时代价，等同于该语言运行闭包的代价。 在常规的高级语言运行时中，闭包通常需要装箱（Boxing），这意味着大量的堆内存分配，耗时极长。但在 Roc 语言的设计中，这一痛点得到了解决： - Roc 的闭包完全不需要装箱（Unboxed），不会产生堆分配压力。 - 借助去函数化（Defunctionalization）技术，编译器能通过枚举直接调用（Enumerated Direct Calls）代替昂贵的间接函数指针查找。 - 这种机制让 Task 及其嵌套的闭包都能保持未装箱状态，使得全局采用 Managed Effects 所带来的开销极其微小。 对此，Richard Feldman 总结道：“Task itself is unboxed... and we have these enumerated direct calls with defunctionalization, which all of which basically means that the overhead of this these like wrapped effects that we have to do everywhere it's so minimal that it's honestly not something we're even worried about.” 简而言之，无副作用带来的包装开销根本构不成性能瓶颈。 ### [11:47](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=707s) 内存突变与不可变性的性能拉锯 相较于副作用，不可变性（Immutability）才是纯函数式编程面临的真正严峻挑战。在常规性能优化中，禁止可变性往往会让问题变得复杂棘手。以数组元素翻倍为例： - 命令式的 `for` 循环可以直接修改内存索引：`array[i] *= 2`。该操作完全就地完成（In-place），不仅省去了重复分配，而且数据大概率命中 CPU 高速缓存。 - 不可变风格的 `array.map(x => x * 2)` 则必须分配一个全新数组并逐个写入数值。由于多出了堆内存分配与冷缓存写入的开销，在底层硬件视角下，非可变版本的执行速度天然逊于就地修改。 然而，在宏观架构层面，不可变性有时反而能带来反直觉的性能反超。Richard Feldman 提到了当年吸引他深入 Elm 的基准测试：在 UI 渲染性能对比中，处于榜单前列、速度最快的框架无一例外全都依赖不可变数据。其核心原因在于，不可变性赋予了系统进行极快浅比较（Reference Equality Check）的能力——通过单纯比对新旧状态的对象指针，就能瞬时跳过整个组件子树的渲染。如果到处都是就地突变，这种优化将彻底失效。 这一突破最早由 David Nolan 在 ClojureScript 中提出，随后 Elm 的作者 Evan Czaplicki 将其发扬光大。Richard Feldman 强调：“So basically when the cost of immutability, which is a cost in this case, is less than the sort of like cost of rendering, it can actually end up working out to be a net performance improvement.” 尽管如此，这也仅仅是不可变性在特定领域恰好带来的红利；在许多偏底层的硬核算法中，就地修改仍然是无可替代的性能基石。 ### [14:16](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=856s) 快速排序（Quicksort）与就地置换的挑战 不可变语言究竟能否在高度依赖突变的算法上保持竞争力？为了探究这一极限，Richard Feldman 选取了经典的快速排序（Quicksort）作为检验样本。快速排序虽然在日常业务中很少由工程师手动重写，但它是绝佳的原型代表，其性能灵魂完全维系在高频的内存元素就地置换（In-place Swap）上。 快速排序在执行分区（Partitioning）时，虽然早期的数值比较可以勉强采用不可变的形式表达，但将左右两侧的元素就地交换位置是不可避免的；若每次交换都重新构建数组拷贝，算法的效率将彻底崩溃。针对这一点，Richard Feldman 直言：“There's just no substitute for doing that in place if you want Quicksort to basically be Quicksort and run fast.” 典型的 JavaScript 快速排序实现中充斥着命令式要素：嵌套循环、自增索引、直接修改指针与数组槽位的 `swap` 函数。这一标准教科书级的实现，正是纯函数式语言在追求极致底层性能时必须正面击败的假想敌。 ### [15:51](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=951s) Haskell 的快速排序：优雅的表象与“作弊”的就地修改 提到纯函数式语言中的快速排序（Quicksort），人们往往会想到 Haskell 教科书上那段仅有几行、极其优雅简洁的声明式实现。然而，社区对此一直存在一个完全合情合理的批评：“这根本就不能算作快速排序。”正如某篇著名博文所指出的，快速排序之所以快，核心就在于其“就地变异”（In-place mutation）的分区算法；而 Haskell 那段简洁的代码背后却在频繁克隆、分配新列表，它既不快，也违背了快排的初衷。面对这种质疑，有人发起了“接受挑战”的尝试，硬是在 Haskell 中写出了真正的就地修改版快速排序。然而，代码不仅失去了原有的优雅，其画风更是变得诡异而危险。 ```mermaid flowchart TD accTitle: Haskell 快速排序的两种实现对比 accDescr: 对比传统简洁纯函数快排与引入 unsafe 操作的就地变异快排 subgraph Pure["教科书版（纯函数式）"] P1["简洁的声明式语法"] --> P2["递归生成新列表"] P2 --> P3["大量内存分配与克隆<br/>（性能低下，非真正快排）"] end subgraph Imperative["命令式 Haskell（Data.Vector.Generic.Mutable）"] I1["unsafeRead / unsafeSwap / unsafeSlice"] --> I2["直接修改底层连续内存"] I2 --> I3["丧失引用透明性与越界检查<br/>（接近 C/C++ 的未定义行为风险）"] end ``` 在这段所谓的“高性能 Haskell 快排”中，充斥着诸如 `unsafeRead`、`unsafeSwap` 以及 `unsafeSlice` 这类令人心惊肉跳的函数调用。Richard Feldman 调侃道，光看名字就知道问题很大：“基于它们的名字，你就能猜出为什么我会感到担忧了。”因为这段代码本质上是在使用 `Data.Vector.Generic.Mutable` 进行纯正的命令式编程——程序员在理论上的纯函数语言里直接做内存就地覆写，心存侥幸地假装“没人会发现，一切都安好”。根据官方文档，`unsafeSlice` 会在不发生拷贝的情况下直接截取可变向量的一部分，如果此时有其他地方对其修改，当前视图的数据也会随之突变，纯函数世界赖以生存的“引用透明性”（Referential Transparency）彻底荡然无存；更严重的是，它完全不做边界检查，安全性甚至低于 Rust，直接跌落至 C 和 C++ 的危险泥潭，可能遭遇段错误（Segmentation fault）、脏内存读取乃至安全漏洞。Richard 坦言，这根本就是作弊，因为此时你早已不再是在写函数式程序了。 - 纯函数式简易快排的缺陷：通过列表推导式或过滤拼接产生大量副本，时间与空间开销巨大，并非原地排序。 - 危险的可变向量 API：`Data.Vector.Generic.Mutable` 提供了就地修改能力，但带 `unsafe` 前缀的函数会完全绕过边界检查与只读保护。 - 引用透明性破裂：共享同一块可变内存意味着外部修改会破坏函数输出的确定性，引发难以排查的并发或逻辑缺陷。 --- ### [18:09](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1089s) 基准测试的真相：各语言开销与公平性权衡 既然 Haskell 通过这种“超规格作弊”引入了就地修改，它的实际运行表现究竟如何？Richard 在同一台机器上对 1000 万个数字进行了快速排序基准测试，每个语言运行 100 次取平均值。结果显示，未经特殊深度调优的教科书实现下，JavaScript 耗时略低于 1.4 秒；而使用了 unsafe 黑魔法的 Haskell 居然比 JavaScript 略微快了一点点。在它们之上，Java 比 Haskell 更快，Go 又优于 Java，而没有任何运行时包袱的 C++ 则不出所料地拔得头筹。这证明纯函数式语言在极端情况下确实能达到与命令式相抗衡的速度，但代价极其惨重。正如 Richard Feldman 严肃指出的：“这不是通过使用函数式编程来实现的，这纯粹是通过作弊，做一些我认为任何 Haskell 开发者都不会建议你在生产代码中尝试的极其危险的事情。” ```mermaid flowchart LR accTitle: 1000万个数字快速排序相对速度对比 accDescr: 展示 JavaScript、Haskell、Java、Go 和 C++ 的运行速度递进关系 JS["JavaScript<br/>(~1.4s)"] --> HSK["Haskell (Unsafe)"] HSK --> JAV["Java"] JAV --> GO["Go"] GO --> CPP["C++ (最快)"] ``` 然而，Richard 特别强调，切忌把这个测试当成绝对的语言性能排名。虽然算法在渐进复杂度（Big-O）上完全一致，但各语言特有的运行时开销（Language Overheads）会对微基准测试产生剧烈干扰。只要稍微调整一下实现细节，数字就会天差地别： 1. **Java 的数据结构差异**：起初团队使用的是 `ArrayList`，当有人提醒替换为原生的 Java `array` 后，性能立刻大幅提升； 2. **JavaScript 的数值类型陷阱**：最初测试排的是 64 位整数，虽然现代 JavaScript 拥有 `BigInt`，但其性能远不如作为 JS 底层看家本领的 `Double`（双精度浮点数），为了不让 JS 处于劣势，团队将基准类型统一切换为双精度浮点； 3. **C++ 的边界检查机制**：C++ 默认直接跳过边界检查，这在内存上是不安全的，但既然这就是惯用的 C++ 风格，测试便保留了这种写法。 面对这种性能死结，工业界通常不会在 Haskell 内部硬写 unsafe 代码，更现实的做法是通过语言互操作（Interop/FFI）调用 C、C++、Rust 或 Zig 等底层系统语言，就像 Python 将沉重的矩阵运算交给用 C 语言编写的 NumPy 一样。 --- ### [21:15](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1275s) 编译优化的魔力：从尾调用消除到机会性就地变异 如果既不想使用危险的 unsafe 技巧破坏语言纯洁性，又不想依赖外部语言的 FFI，编译器优化（Optimizers）能否充当救世主？历史证明，优化编译器的潜力常常超出人类直觉。在 Fortran 问世之初，许多程序员惊讶地发现，优化编译器生成的机器码在实际运行中往往比人类手工编写的汇编语言还要快。就像如今在国际象棋和围棋领域人类已无法战胜 AI 一样，未来终有一天人类手写优化的极限也会被编译器全面超越。而在函数式编程中，最经典的优化莫过于“尾调用优化”（Tail Call Optimization, TCO）：任何命令式的 `while` 或 `for` 循环在表达能力上都与递归函数等价，TCO 能够准确识别特定形式的递归，并将其编译成与命令式循环在机器指令级别完全一模一样的汇编代码。 ```mermaid flowchart TD accTitle: 机会性就地变异机制 accDescr: 编译器判断输入数组在后续代码中是否被引用，若无引用则复用原内存进行就地修改 A["调用 array.map(fn)"] --> B{"原数组在后续程序中<br/>是否还会被引用？"} B -- "存在后续引用" --> C["分配新内存空间<br/>（完全防御性拷贝，保障纯不可变性）"] B -- "绝无后续引用" --> D["触发机会性就地变异<br/>（直接在原内存上覆写）"] D --> E["对外维持语义不可变与引用透明<br/>对内获得命令式就地变异的极致性能"] ``` 既然递归能够无损转换为循环，那么内存操作是否也能依法炮制？比如将高阶函数 `array.map` 优化成与命令式 `for` 循环就地修改数组相同的机器码。答案是肯定的，但这需要极为苛刻的前提条件：如果盲目在原内存上原地改写，数据的不可变性就会荡然无存。然而，存在一种绝妙的特殊场景——如果编译器经过静态分析后确认，被映射的原始数组在接下来的程序生命周期中再也不会被引用，那么直接复用这块内存进行覆写便不会产生任何副作用。Richard Feldman 解释道，在这种情况下没有任何坏处，因为“是的，我们确实在原地进行了变异，但没有任何人能看得到”。 - 语义不可变与机器性能的统一：从外部视角看，数据依然符合引用透明性与纯函数规则；从硬件视角看，它完全消除了内存分配与垃圾回收开销，榨取出了命令式就地修改的极致性能。 - 机会性就地变异（Opportunistic In-Place Mutation）：编译器自主探测对象的生命周期与独占性，在不牺牲高级语言安全抽象的前提下，让纯函数式代码跨越性能鸿沟。 ### [23:58](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1438s) 自动就地变异：从运行时引用计数到编译期静态检测 Richard Feldman 深入阐释了让纯函数式程序变快的最关键技术——只要程序的语义不受影响、外部观察不到副作用，编译器就可以像执行尾调用优化一样，将本应发生的“不可变复制”（immutable clone）静默转换为“就地变异”（in-place mutation）。在底层实现上，一种方式是依赖引用计数（Reference Counting，这也是 Roc 采用的方案）：当代码即将执行一次克隆时，如果检查到目标对象的引用计数恰好为 1，便意味着全程序再无其他人持有该引用，此时直接覆写原内存绝对安全。这也决定了该优化必须搭配引用计数，而无法在追踪式垃圾回收器（Tracing GC）下生效，因为追踪式 GC 根本不会在运行时记录精确的引用计数值。 然而，更进一步的突破在于：许多时候根本不需要等到运行时再去检查引用计数。编译器通过对程序其余部分的数据流分析，完全能够在编译期静态检测出“该变量在此时此地引用计数必然为 1 且后续绝不再被引用”。这种静态判定不仅完全抹除了运行时的分支判断开销（无需做额外的 `rc == 1` 比较），还能直接惠及无法被引用计数的无装箱值（Unboxed Values，例如扁平的结构体 Record），甚至能与 Roc 拥有的其他各种内存管理策略无缝兼容。 ```mermaid flowchart TD accTitle: 编译期与运行时就地变异决策流程 accDescr: 纯函数式数据结构在执行写入前，通过静态别名分析或运行时引用计数判断是否转为就地内存变异。 A["代码执行数据写入/更新"] --> B{"编译期静态分析<br/>后续是否无别名引用？"} B -- "是（静态确定唯一）" --> C["直接执行就地变异<br/>(无运行时检查开销)"] B -- "否 / 无法静态确定" --> D{"运行时引用计数检查<br/>RC 是否等于 1？"} D -- "RC == 1 (唯一引用)" --> E["就地变异 (In-place Mutation)"] D -- "RC > 1 (存在共享)" --> F["内存分配并复制 (Immutable Clone)"] ``` - 静态优化消除了运行时的条件判断指令，使得非装箱的 Record 也能直接就地更新。 - 追踪式垃圾回收器（Tracing GC）缺乏局部精确的即时引用计数信息，因而无法直接以这种方式进行动态就地变异优化。 --- ### [25:31](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1531s) 从独占类型到 Morphic 求解器：静态变异检测的演进之路 谈及技术的演进过程，Richard 回忆道，Roc 的第一版静态检测是由 Folkert de Vries 在内梅亨大学（Radboud University）攻读硕士学位期间实现的（Richard 在此还打趣向荷兰观众致歉，笑称自己可能读不准校名）。该版本借鉴了 Clean 语言的独占类型（Uniqueness Types），虽然确实能在编译期成功检测出就地变异的机会，但在实际工程中却暴露出致命缺陷——它非常脆弱（brittle）。开发者哪怕在程序的某个不起眼位置做了一点细微改动，就极易破坏类型推导，导致整个编译优化被莫名降级（de-optimized）。 为了解决这一痛点，Roc 转向了基于别名分析（Alias Analysis）的第二代方案——引入了由加州大学伯克利分校（UC Berkeley）团队研发的 Morphic 求解器。Richard 不禁赞叹道：“我在读本科的时候净打电子游戏了，而这帮伯克利的本科生却用 Rust 写出了一个可插拔的静态就地变异检测优化库。”目前 Roc 编译器正是首个接入 Morphic 库的先锋项目，正是这种产学研的紧密协作，奠定了 Roc 迈向极致性能的基础。 - 第一代方案：基于 Clean 语言启发的不变/独占类型系统（Uniqueness Types），缺陷是容易发生非预期的优化失效（de-optimization）。 - 第二代方案：基于 Rust 开发的 Morphic 别名分析求解器，作为独立可插拔模块嵌入 Roc 编译器。 --- ### [26:35](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1595s) 纯函数式快速排序：最严苛测试下的性能奇迹 为了检验所有底层的优化组合拳，Richard 挑选了一个对纯函数式编程而言最为严苛、甚至堪称“病态”（pathological）的基准测试——快速排序（Quicksort）。标准的快速排序为了达到极致性能，高度依赖 `for` 循环、下标递增和直接的原地元素交换（in-place swap），而纯函数式代码必须将循环改写为尾递归，并将原地交换写成返回新列表与新索引的记录（Record）。Richard 直言不讳地指着 Roc 实现的 `partition` 代码坦白道，它比命令式代码明显要长得多，表面上看是在疯狂做无用功：不仅递归调用辅助函数 `partitionHelp`，还不断打包和返回带有新状态的 Record。 “纯函数式编程在快速排序上根本没有占便宜的道理，”Richard 坦陈这绝对是纯函数式编程的“最坏情况”（worst-case scenario）。然而，在没有任何作弊手段、不调用命令式逃逸舱（Escape Hatch）、不搞任何底层语言 FFI 互操作的前提下，基准测试的结果却震惊了全场：Roc 的纯函数式快速排序不仅远远把 JavaScript 甩在身后，更是击败了开了命令式“外挂”的 Haskell，连 Java 和 Go 也纷纷落败，全场仅次于 C++！Richard 兴奋地透露，这个基准测试其实在演讲前两天才刚刚跑通，“我们当时花了一两个小时就在琢磨：到底怎样才能把跟 C++ 之间仅剩的那点差距也彻底抹平？” Richard Feldman 坚定地总结道： > “本质上，我们现在在渐进复杂度上使用的是完全相同的算法，只要把语言层面的额外开销尽可能压到最低，就意味着——即便面对这种必须依赖就地变异才能跑得快的问题，纯函数式编程如今也完全能够胜任。” | 语言实现形态 | 快速排序运行时表现与机制 | |:--- |:--- | | **JavaScript** | 命令式 `for` 循环与原生就地数组交换，受限于引擎动态开销与 JIT 边界 | | **Haskell (ST/IO)** | 借助命令式逃逸舱（例如 `STUArray`）强行进行就地变异，性能良好但脱离了纯函数式范畴 | | **Java / Go** | 原生命令式变异与静态类型，但受 GC 与运行时开销约束，速度慢于经过深度优化的 Roc | | **Roc (纯函数式)** | **语义上完全纯函数式**；经由 LLVM、静态别名分析、尾调用优化及就地更新直接击溃绝大多数命令式对手，紧咬 C++ | | **C++** | 零抽象开销的硬件直连级就地变异，当前基准测试中的性能天花板 | --- ### [29:47](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1787s) 性能基石与 Roc 语言的宏伟蓝图 Richard 归纳了帮助 Roc 逆袭的五大核心优化支柱： 1. **LLVM 优化后端**：与 C++、Rust、Zig 站在同一起跑线上，完成了海量底层的指令级重塑。 2. **无装箱值（Unboxed Values）**：杜绝无意义的堆内存分配与指针解引用，极大减轻了 LLVM 的内联与优化负担。 3. **静态引用计数管理**：在保持内存全自动安全管理的前提下，零运行时垃圾回收暂停。 4. **尾调用消除（Tail Call Optimization）**：对于递归实现的快速排序不可或缺；团队曾测试过关闭该优化的后果——程序卡死半天，最终以调用栈溢出（Stack Overflow）悲惨收场。 5. **按需就地变异（Opportunistic In-place Mutation）**：真正逆转战局的关键法宝。Richard 指出，据他所知，Roc 是目前唯一一个致力于工业级实际落地、而非仅仅停留在学术研究象牙塔中实现该技术的纯函数式语言。 在演讲的收尾段落，Richard 梳理了 Roc 的设计初衷与愿景。Roc 是纯函数式前端语言 Elm 的直系精神继承者。Elm 在浏览器端 UI 构建上带来了无与伦比的愉悦开发体验，而 Roc 则希望将这份纯函数式的优雅、严谨和极致体验带出浏览器，直接编译成操作系统原生的二进制可执行文件。面对“纯函数式不能产生副作用、不能随心所欲就地修改数据”的双重枷锁，Roc 通过压倒性的全系统底层减负，证明了纯函数式语言不仅能提供顶级的工效学体验，更拥有在性能角斗场上正面超越主流命令式语言的强悍底气。 ### [31:47](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1907s) 生产环境迁移经验与 Roc 的底层性能设计 Richard Feldman 分享了 NoRedInk 公司的后端工程实践：团队正在将核心系统从 Ruby 迁移到 Haskell。目前公司大部分线上流量已经交由 Haskell 处理，整体性能带来了大约 10 倍的提升。借此机会，他还顺便打了个招聘广告，欢迎对 Haskell、Elm 以及未来的 Roc 感兴趣的工程师加入团队。 回到 Roc 语言的设计上，团队通过一系列底层架构选择，将这门纯函数式语言的运行时开销压到了最低。Roc 采用 LLVM 作为编译后端，在整个语言运行时中尽可能普遍采用非装箱（unboxed）值，并依托静态引用计数（static reference counting）实现极低开销的内存管理。Richard Feldman 坦诚地指出，目前尚无法确切断言静态引用计数在大规模真实业务场景下的表现：“我们其实还不知道静态引用计数在规模化场景下的实际表现到底有多好，因为 Roc 目前仍然是一个处于早期阶段的语言，还没有用于任何严肃的生产环境，也没有足够大的 Roc 程序来验证这一点；但至少到目前为止，我们对当前探索的技术路线感到非常乐观。” ```mermaid flowchart TD accTitle: Roc Low Overhead Architecture accDescr: 展现 Roc 语言通过 LLVM 后端、未装箱值与静态引用计数实现超低运行时开销的架构设计 subgraph Frontend["语言语义层"] A["纯函数式代码"] B["托管副作用 (Managed Effects / Tasks)"] end subgraph Compiler["编译与运行时优化"] C["未装箱闭包与未装箱 Task"] D["枚举式直接调用 (Direct Calls)"] E["静态引用计数 (Static Ref Counting)"] F["LLVM 编译后端 (原生代码生成)"] end Frontend --> Compiler Compiler --> G["超低开销的机器执行性能"] ``` - **架构选型关键**：使用 LLVM 生成紧凑高效的机器码，消除了传统解释器或厚重虚拟机的运行负担。 - **内存布局策略**：核心数据结构和基本类型全面默认使用未装箱（unboxed）表示，避免无谓的指针解引用与堆分配。 - **内存清理机制**：依赖编译期分析辅助的静态引用计数，配合其他低开销创新内存手段，避免运行时出现长延迟的垃圾回收停顿。 --- ### [32:32](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=1952s) 托管副作用与不可变性的性能平衡 在副作用处理方面，Roc 彻底杜绝了任意的隐式副作用（side effects），转而全面依赖托管副作用（managed effects）。从开发者的人机交互体感来看，这与 JavaScript 中使用 Promise 类似，唯一的硬性区别在于：在 Roc 中没有任何绕过 Promise 或 Task 的隐式“后门”，所有 I/O 和状态交互必须通过 Task 完成。 针对这种全量封装是否会拖慢运行速度的疑虑，Richard Feldman 解释道，Roc 通过未装箱任务（unboxed tasks）、未装箱闭包（unboxed closures）以及枚举式直接函数调用（enumerated direct calls）等底层优化，彻底消除了抽象层的多余损耗：“幸运的是，当我们采用未装箱的任务、未装箱的闭包以及这些枚举式直接调用后，运行速度变得极快，以至于在工程实践中我们完全不必担心这会成为语言的主要开销来源。” 关于不可变性（immutability），业内通常认为它在默认情况下是一种性能负担，因为每次更新都需要分配新对象。但 Richard Feldman 指出，在很多实际应用场景中——例如浏览器的虚拟 DOM 渲染——运行时的不可变性反而可以成为一种激进的性能优化策略。由于数据引用的不变性，UI 框架能够以常数级别的时间复杂度检查引用相等性，进而直接跳过大量冗余的脏检查和 DOM 重绘工作。 --- ### [33:23](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=2003s) 克服原地异变限制：纯函数式快排超越命令式 当算法本身极度依赖原地异变（in-place mutation）才能发挥极致性能时（如快速排序），单纯依赖逻辑上的不可变性就会陷入被动。为了攻克这一瓶颈，Roc 团队引入了长串的编译期重写与优化管线，使其在纯函数式表达下也能生成就地修改的机器指令。 这一努力最令人振奋的成果体现在快速排序（Quicksort）的基准测试中。对于纯函数式编程而言，快速排序向来是“病态式艰难且糟糕”的典型任务，但完全采用纯函数式风格编写的 Roc 实现，最终成功超越了处于自身舒适区的命令式语言实现。 Richard Feldman 总结了纯函数式编程超越命令式编程的三大核心路径： 1. **范式天然契合**：某些场景下，纯函数式编程的引用透明性和不可变性能够赋能高层优化（如浏览器 UI 快速跳过计算）。 2. **基线语言开销差距**：性能领先有时单纯源自底层实现的高效，而与编程范式本身无关，正如工程团队在服务端用 Haskell 替换 Ruby 换来 10 倍提速。 3. **编译期暴力优化（Sheer Force of Optimizations）**：即使面对天然不适合纯函数式的任务，编译器也能化解性能劣势。 Richard Feldman 总结道：“即使这项任务本质上并不适合纯函数式编程，我们也能做到让它的唯一劣势仅仅停留于代码不够简练、需要阅读更多内容，而不是运行速度变慢；事实上，它依然完全有能力跑赢其他带垃圾回收的编程语言。”这场演讲最终有力地证明了，纯函数式语言不仅能让代码更易维护，同样具备在性能层面彻底击败传统命令式系统的实力。 ## Notable quotes > [00:06](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=6s) The fact of the matter is some algorithms just require in-place mutation to run fast. — Richard Feldman > [05:04](https://www.youtube.com/watch?v=vzfy4EKwG_Y&t=304s) Big downside of tracing garbage collectors compared to individual allocations and deallocations is that you get garbage collection pauses. — Richard Feldman ## Mentioned Richard Feldman, Roc, Elm, NoRedInk, Ruby, Ruby on Rails, Haskell, Python, JavaScript, NumPy, Java, C#, Elixir, BEAM, Go, Swift, LLVM, C++, Rust, Zig, Counting Immutable Beans, Perseus, David Nolan, ClojureScript, Evan Czaplicki, Folkert de Vries, Radboud University, Clean, UC Berkeley, Morphic ## Video description Like many, I once thought that functional programming makes programs easier to maintain, but slower to run. After all, that had been my experience; when I wrote JavaScript in a functional style, my code got easier to maintain - but it no longer ran as fast. Once I got deeper into functional languages, including pure functional ones, I was surprised to discover that they could actually outperform imperative languages - not just in tasks generally considered "well-suited" to functional programming, but sometimes even in cases considered well-suited for imperative programming! This talk examines performance from the network level all the way down to individual CPU instructions to show how and when pure functional programming languages can outperform their imperative counterparts. Come see just how fast functional programming can be! Richard Feldman NoRedInk @rtfeldman Richard Feldman is a software engineer at NoRedInk and a well-known member of the Elm community. Recorded at Strange Loop 2021 https://thestrangeloop.com [Source](https://www.youtube.com/watch?v=vzfy4EKwG_Y)

[0:06] Richard Feldman: The fact of the matter is some algorithms just require in-place mutation to run fast. [5:04] Richard Feldman: Big downside of tracing garbage collectors compared to individual allocations and deallocations is that you get garbage collection pauses.

[0:06] Richard Feldman: The fact of the matter is some algorithms just require in-place mutation to run fast.

[0:06] this is outperforming imperative with [0:07] pure functional languages i'm richard [0:09] feldman so for the past couple years [0:11] i've been working on building a [0:12] programming language called rock and [0:14] rock is inspired by and a direct [0:15] descendant of my what has been my [0:17] favorite programming language for [0:18] several years now which is l [0:20] um elm is one of the things that i love [0:22] about it is it's got this really [0:23] delightful user experience it really [0:24] gives me joy to program in it [0:26] it's a pure functional language and it's [0:28] compiled to javascript so it's really [0:29] good for making browser-based uis but [0:32] i've wanted sort of like an like [0:33] experience in other domains besides [0:34] browser-based uis and so rock has [0:37] similar goals to album of having like a [0:38] delightful user experience and it's a [0:40] pure functional programming language [0:42] like elm but it's compiled to binary so [0:44] it's sort of for other use cases that [0:46] elm is not meant for at the moment [0:48] um so i first got into elm based on this [0:50] blog post blazing fast html and elm [0:52] which came out in 2014 [0:54] and one of the things that i appreciated [0:55] about elm was i had a relatively [0:57] performance sensitive ui that i was [0:58] building and i really like to see this [0:59] benchmark that sort of gave me [1:01] confidence that i was gonna have a fast [1:02] experience when i was building my apps [1:04] in element i wasn't gonna have a nice [1:05] experience building it and then have [1:06] things run slowly when i got done [1:09] um so i wanna sort of keep that value in [1:11] rock like it's really important to me [1:12] that like hey let's go fast let's let's [1:13] build a programming language that runs [1:14] programs really fast [1:16] of course the trouble with that is that [1:17] this is a pure functional programming [1:19] language and pure functional programming [1:21] languages are all about pure functions [1:23] as in like every function is pure and [1:25] that means [1:26] no side effects and no mutation which [1:29] can be a bit of a challenge when it [1:30] comes to performance if you're trying to [1:31] go really fast because [1:33] the fact of the matter is some [1:34] algorithms just require in-place [1:36] mutation to run fast [1:38] um like for example how competitive [1:39] could a pure functional language [1:40] possibly be at a mutation-heavy [1:42] algorithm like quicksort this seems like [1:44] somewhat of an intractable unavoidable [1:46] downside [1:47] so fortunately though there are several [1:49] different considerations to performance [1:50] like for example the language overhead [1:52] like how much overhead does the language [1:53] introduce sort of how close can it get [1:55] you to what the hardware is capable of [1:56] and that can be sort of balanced against [1:58] you know there's no side effects there's [1:59] no mutation so when you put all those [2:01] things together how well can we come out [2:04] when compared to imperative languages [2:06] well let's let's kind of look through [2:07] these and just talk through them so [2:08] first going to talk about language [2:10] overhead like in general and also as it [2:11] pertains to rock [2:13] um so [2:14] haskell is a very well known probably [2:15] the most well known uh pure functional [2:17] programming language um and we actually [2:19] use it at work where i work at no red [2:20] ink so our back end for many years was [2:23] ruby on rails which is a pretty common [2:25] tech stack uh and then in recent years [2:27] we've actually been migrating our our [2:29] back end from ruby to haskell and so in [2:32] particular we migrated one of our [2:33] services actually our most high traffic [2:35] performance critical service to haskell [2:37] this is serving billions of questions [2:39] every year we make software for english [2:41] teachers so students are answering [2:42] billions of questions on our site um all [2:45] going through this haskell service [2:46] and what we found was that when we [2:48] migrated this from ruby and rails to [2:50] haskell and service basically doing the [2:52] same job as it was doing before slightly [2:54] different but not really that meaningful [2:55] from a performance perspective um the [2:57] delta was quite large in terms of [2:59] performance it was about 10x faster [3:02] now this we're well aware was not [3:04] because like pure functional programming [3:05] is like oh that that's it's this magic [3:06] sauce that just makes everything run [3:08] faster um no it's definitely wasn't that [3:10] it's just because some [3:14] imperative versus uh pure functional but [3:16] they just sort of dominated in this case [3:18] which led to haskell being a lot more uh [3:20] performance in practice than ruby was [3:23] um [3:24] so let's talk about that execution model [3:25] a little bit i mentioned that ruby's [3:26] interpreted um there's quite a few [3:28] languages that we'll do interpreted [3:30] basically like interpreting the source [3:31] code into parsing it into an ast and [3:33] then interpreting that on the fly so [3:35] python ruby javascript i'll do this may [3:37] or may not have jit which is a [3:38] just-in-time compilation which can speed [3:40] that up in like really uh tight loops [3:42] things like that um some languages do [3:44] interpreted by codes so like java [3:45] c-sharp elixir compiling to beam by code [3:50] other languages go straight to a binary [3:52] like a [3:53] just an individual stand-alone binary so [3:55] go does this swift does this haskell [3:57] also does this [3:59] these are generally the fastest category [4:01] of things like these are pretty much [4:02] sorted from sort of highest overhead to [4:05] least overhead [4:06] but there's something that's worth [4:07] calling out as almost a different [4:08] category onto its own which is llvm [4:10] compiled to binary so llvm is basically [4:13] a library that's for optimizing uh [4:15] compiled binaries um it's not like llvm [4:18] is like the only way to get this uh this [4:19] extra speed bump but um languages like c [4:22] plus plus and rust and zig all use this [4:24] to get like really really exceptionally [4:25] great performance out of their binaries [4:27] and of course that's what we want for [4:28] rock too so that's what we've been using [4:31] um i mentioned boxing so boxing [4:33] basically referring to things being [4:34] allocated on the heap which generally is [4:36] a lot slower than allocating them on the [4:38] stack or in registers [4:40] some things that can be boxed include [4:41] numbers so like in python numbers are [4:43] boxed for example um that means that [4:45] doing number stuff in python is [4:46] generally a lot slower and why you have [4:48] libraries like numpy and stuff to speed [4:50] that back up um objects and records also [4:53] very commonly boxed depending on the [4:54] language [4:55] functions and closures also potentially [4:57] box depending on the language [4:59] basically uh you know that that's just [5:01] sort of another source of potential [5:02] slowness [5:04] memory management lots of different [5:05] memory management strategies a really [5:06] common one sort of the old school way [5:08] was like individual allocations and d [5:09] allocations like c c plus plus rust and [5:12] zig these languages will help you out [5:14] with this they're not going to make you [5:15] do it by hand like you had to and see [5:16] like every single allocation [5:18] specifically call malik and then call [5:20] free again um but at the end of the day [5:22] like that is how the memory is being [5:23] managed it's sort of like one allocation [5:24] at a time um then you also have tracing [5:27] garbage collectors which is a very very [5:29] popular strategy these days so like go [5:31] javascript haskell also like java and [5:33] the list goes on and on for tracing gcs [5:35] um big downside of tracing garbage [5:37] collectors compared to individual [5:39] allocations and d allocations is that [5:40] you get garbage collection pauses so [5:42] this is all something that we're [5:44] probably familiar with um you know the [5:46] program just locks up for for some [5:47] period of time while it's doing this [5:49] garbage collection there's another [5:50] memory management strategy that does not [5:52] have garbage collection pauses which is [5:54] quite nice um which is automatic [5:55] reference counting so python swift and [5:57] rock all do this and the usual downside [6:00] there is just that the reference [6:01] counting sort of has more overall [6:03] overhead typically so that sort of the [6:05] throughput is less compared to tracing [6:07] garbage collector even though you don't [6:08] have the gc pauses [6:10] um one of the things that you can do to [6:12] sort of reduce that downside and make it [6:14] so that it has higher throughput without [6:16] reintroducing gc pauses is what's known [6:18] as static reference counting i know that [6:20] swift does this in some form but i'm not [6:22] a swift programmer not sure exactly how [6:23] it works um but i know what we did in [6:25] rock to do this uh was there these two [6:27] papers that we implemented one is called [6:29] counting immutable beans the other is [6:30] called perseus and basically these are [6:32] two ways of among other things [6:34] optimizing it so that you don't need to [6:36] do as many reference checks at runtime [6:38] as many reference count operations at [6:39] runtime because we're able to sort of [6:41] detect at compile time where they would [6:43] be happening and cancel each other out [6:45] and we can just kind of throw them [6:46] away um one other thing i want to note i [6:49] don't have time to get all the way into [6:51] it for this talk but um there's another [6:52] thing that rock does that's a pretty [6:54] novel in terms of memory management the [6:56] upshot of it is that instead of using [6:58] automatic reference counting you can [6:59] completely transparently to the [7:01] application author in some situations uh [7:03] do arena allocation bump allocation [7:05] which are just way faster than any of [7:07] these other strategies including tracing [7:08] gc including even like individual [7:10] allocations and deallocations um i gave [7:13] a whole talk about this uh so if you're [7:14] curious about that you can you can check [7:15] it out later but suffice it to say um [7:17] this is one of the things that i think [7:18] is going to be most promising for rock's [7:21] long-term memory management even though [7:22] for the rest of this talk i'm not going [7:23] to be using it [7:24] um okay so to sum up when it comes to [7:26] language overhead we've basically tried [7:28] to do as good of a job when we can of [7:30] minimizing the language overhead of rock [7:33] so we're using llvm that's like [7:34] basically sort of the gold standard for [7:36] high performance compiling to binaries [7:38] today [7:39] we're using unboxed values basically [7:41] everywhere we possibly can there aren't [7:43] any values that i know of that are boxed [7:45] unnecessarily [7:46] and when it comes to memory management [7:48] we're doing static reference counting [7:49] along with uh some more exotic stuff [7:51] like arena allocation behind the scenes [7:54] um [7:55] so overall i'm like feeling pretty good [7:56] about this like okay i think we're doing [7:58] a good job here um good start but uh [8:00] that's that was sort of the upside [8:02] section right now we have these two [8:03] things we have to deal with which is [8:05] we're not allowed to do side effects [8:06] we're not allowed to do mutation so how [8:08] do we compete when those are our [8:10] restrictions so let's talk about the no [8:11] side effects thing well unfortunately of [8:13] the two this one turns out to not be as [8:15] big of a deal as you might guess [8:17] a common question that i hear asked of [8:19] people who talk about pure functional [8:20] programming languages is are you just [8:22] heating the cpu up [8:24] side effects are like everything so i [8:26] mean like what are you doing um pascal [8:28] doesn't do side effects like how is most [8:30] of our production traffic running on [8:31] haskell is it just like not doing any [8:32] effects is it never talking to database [8:34] no of course not it's doing all those [8:35] effects they're just not side effects [8:37] still effects but they are now managed [8:39] effects [8:40] so side effects versus managed effects [8:42] that's really the trade-off we're [8:44] talking about here when it comes to [8:45] performance [8:46] so here's an example of something that [8:48] does side effects this is javascript uh [8:50] doing using promises so we're setting [8:52] promise one equals fetch some url [8:54] promise two is fetch the url dot then [8:56] and then there's some callback which is [8:58] gonna return another promise you could [8:59] chain these together et cetera et cetera [9:01] promises are a super common thing in [9:02] javascript they're nice for modeling [9:04] asynchronous tasks that can sort of be [9:06] chained together and it's something that [9:09] is done all over the imperative world [9:10] managed effects now hold on because this [9:12] is going to look extremely different [9:14] as you can see this is super different [9:16] and weird and alien um no it's the same [9:18] thing [9:19] it's basically just promises the only [9:21] the only difference is like this is an [9:22] elm syntax so it's a little bit [9:23] different instead of a dot then you have [9:25] a pipe to and then but same basic thing [9:27] um so if you ever look at a like large [9:29] pure functional program structurally [9:31] it's very very similar to promises um [9:33] the only difference is that with [9:35] promises [9:36] right when you instantiate the promise [9:37] it runs the effect like as soon as you [9:39] call fetch boom it does the http request [9:41] right then and there whereas with [9:42] managed effects it's basically you're [9:43] building up the same structure but it [9:45] doesn't get executed right away instead [9:48] you build up this big sort of chain [9:49] together task you hand that off to main [9:51] and then the the language run time will [9:53] actually execute that when you start the [9:55] program [9:56] that's the only difference so it's [9:57] nothing mysterious it doesn't feel like [9:59] a totally different you know way of [10:00] doing effects it's just like kind of [10:02] like promises but you do that everywhere [10:04] now one important difference when it [10:05] comes to performance is that you do have [10:07] to do this for all effects so in a [10:09] language that supports side effects uh [10:10] you don't have to have promise for [10:11] everything sometimes you can just have a [10:13] normal function call that does side [10:14] effects whereas in the language with [10:16] managed effects every single effect is [10:18] done in this way with sort of this like [10:20] promise like wrapper [10:21] so really kind of the question comes [10:23] down to what is that overhead like we if [10:25] we have to have this sort of wrapper [10:26] around all of our effects like promise [10:28] or task whatever the case may be um how [10:30] significant of an overhead is that for [10:32] the language so basically what it boils [10:34] down to is that for both promise and [10:36] task they're essentially closures that [10:37] is to say functions that can sort of [10:39] capture the enclosing scope a little bit [10:41] um and then they have other closures [10:43] inside that's really all there is to it [10:45] they're basically just closures which is [10:46] to say that the overhead of wrapped [10:48] effects is pretty much just whatever the [10:50] cost of closures is in your particular [10:52] language now the thing is that overhead [10:54] can vary pretty dramatically like i [10:56] mentioned earlier one of the things that [10:58] can be potentially boxed which is to say [11:00] heap allocated which is to say taking a [11:01] lot longer than things that aren't boxed [11:03] um our functions or closures um [11:06] fortunately in the case of rock we were [11:08] able to do this um we don't box them [11:10] this is one of the many things that we [11:11] don't box [11:12] there's a whole you know topic of [11:14] de-functionalization and how we're able [11:15] to do that with direct calls instead of [11:16] function pointers which is really cool [11:18] but uh not the subject of this talk um [11:20] so to sum up in terms of managed effects [11:22] and the overhead that they have on the [11:23] language um task itself is unboxed the [11:26] unboxed task is essentially just a bunch [11:27] of closures inside other closures which [11:29] are also unboxed um and we have these [11:31] enumerated direct calls with [11:32] defunctionalization which all of which [11:34] basically means that the overhead of [11:36] this these like wrapped effects that we [11:38] have to do everywhere it's so minimal [11:39] that it's honestly not something we're [11:41] even worried about [11:42] now [11:43] that's when it comes to no side effects [11:45] so small in terms of overhead that we're [11:46] not worried about it [11:47] different story when it comes to [11:48] mutation [11:49] uh this is this is sort of the big one [11:51] like this is this is like the big [11:52] downside of pure functional programming [11:54] um is that um that this makes [11:57] performance optimization in some [11:58] scenarios a lot harder um so let's just [12:01] uh compare a mutation and non-mutation [12:03] version of something to sort of get an [12:04] idea for why this might be [12:06] so here is an imperative for loop so [12:08] we're saying that i equals zero i is [12:09] less than ray.length i plus plus and [12:10] then inside the body of the for loop [12:12] basically what we're doing is we're [12:13] saying every element of this array we're [12:15] just going to double it right there in [12:16] place [12:17] pretty simple operation here's what it [12:19] looks like if you don't have access to [12:20] mutation you're basically going to do a [12:22] map so a ray.map and then this is also [12:25] in javascript syntax [12:26] and then each element in the array we're [12:28] going to double it now this is going to [12:29] make an entirely new array so this sort [12:31] of no mutation version is definitely not [12:34] going to run as fast as the mutation [12:35] version mutation is going to be a lot [12:36] faster because it doesn't have to [12:38] allocate an entirely new array and write [12:40] all these values into this new array [12:41] that's maybe not in your memory cache [12:43] instead it's able to do everything in [12:44] place everything's going to probably be [12:46] in the cache already [12:47] it's just going to go faster so if you [12:49] have this use case where you're like [12:51] that's what i need for performance [12:53] there's really no substitute for [12:54] mutation in cases like this [12:57] um having said that it's worth noting [12:59] that there are some cases where actually [13:00] making the new array can net become a [13:02] performance optimization so i mentioned [13:04] that this was the sort of benchmark from [13:06] that sort of got me into elm in this [13:07] blog post and one of the things that [13:09] it's comparing here is essentially what [13:11] how how are these different frameworks [13:13] and languages able to optimize rendering [13:16] and as it turns out as you can see on [13:18] this chart like lower is better so the [13:19] smaller bars are running faster [13:22] all the ones at the bottom actually [13:23] require immutability for rendering and [13:26] they're able to be much faster than the [13:28] alternatives in large part because this [13:30] enables a very quick comparison check [13:32] between the old and the new state [13:34] and it's only able to do that because [13:36] you're actually making a new one if [13:37] there if you were doing in-place [13:38] mutation in place direct updates this [13:41] optimization would not work and these [13:42] things would be a lot slower in practice [13:44] than they actually are [13:46] so basically when the cost of [13:47] immutability which is a cost in this [13:49] case um is less than the sort of like [13:51] cost of rendering it can actually end up [13:53] working out to be a net performance [13:55] improvement uh which is exactly how [13:57] these [13:58] libraries and languages are able to win [14:00] at this benchmark um as far as i know [14:02] the first person to come up with this [14:03] like observation that this could be used [14:05] for performance optimization was uh [14:06] david nolan for closure script and then [14:08] evan shaflicky who made elm built on [14:10] that to basically produce the results of [14:12] that um that performance benchmark uh [14:14] that i showed a second ago okay now this [14:16] is a case where [14:18] by coincidence pure functional [14:19] programming just happens to nicely work [14:22] out to be a performance optimization [14:23] despite the fact that immutability is [14:25] all else being equal at cost but like i [14:27] said earlier some algorithms require [14:29] in-place mutation to run fast we cannot [14:31] get away from this there's just no [14:33] substitute for it if we want to to make [14:35] them run fast um and you know i asked [14:37] this question like how competitive can a [14:38] pure function language be at a mutation [14:41] heavy algorithm like quick sort [14:43] well let's let's actually look at [14:44] quicksort itself um so i'm choosing this [14:46] because it's a relatively well-known [14:48] algorithm not that it's the thing that [14:49] people are writing all the time but you [14:50] know we can kind of use it as a proxy [14:52] for uh like mutation-heavy algorithms in [14:54] general um so this is a very brief [14:56] animation of how quicksort works you [14:58] definitely don't need to remember how [15:00] all this works but the important part is [15:02] it's doing all these comparisons and [15:03] then at some point this is the key it [15:05] does this swap so it actually swaps in [15:07] place inside the array those two [15:09] elements and again there it's doing it [15:11] again so all the other comparisons kind [15:14] of could be fine in a pure functional [15:15] sense it's all you know relatively [15:16] immutable but that swap there's just no [15:18] substitute for doing that in place if [15:20] you want quick sort to basically be [15:22] quick sort and run fast [15:24] okay so here's an implementation of um [15:27] quicksort in javascript it's actually [15:28] just one part of it the partitioning [15:29] function i just want to look at this [15:30] real quick [15:31] we can kind of see all sorts of [15:32] imperative stuff happening here right [15:34] here's a for loop um it's calling this [15:35] swap function which is swapping things [15:37] in place it's incrementing something [15:38] mutating that doing another swap there's [15:40] just imperative stuff all over the place [15:42] in this uh implementation um this is [15:44] kind of like a textbook quick sort this [15:46] is not hand optimized like for [15:48] all of the quicksort examples i'm going [15:49] to talk through in this section none of [15:51] these are optimized at all it's all just [15:52] going to be like take quicksort out of a [15:54] textbook implement it done [15:56] okay [15:58] so uh talking about quicksort in a pure [16:00] functional language like haskell which [16:01] we saw earlier earlier is capable on its [16:03] own just because the overhead is so much [16:04] lower than something like ruby is [16:06] capable of outperforming um imperative [16:08] languages at some tasks like we saw at [16:10] work but how does it do in quicksort [16:12] well one of the things that haskell is [16:13] known for is this very concise quick [16:16] sort implementation [16:17] this is cool it's neat that you can [16:19] implement something that is [16:20] quick sortie um in this way but a pretty [16:23] reasonable objection to this is that [16:25] this is in no way shape or form [16:26] quicksort um so there's a whole blog [16:28] blog post about this where it's [16:29] basically like yeah the whole point of [16:30] quicksort is that it's fast because of [16:32] in place mutation this is just doing a [16:34] bunch of cloning it's not fast it's not [16:36] quick [16:37] so why are we considering this to be [16:39] quicksort which i think is a valid [16:41] criticism [16:42] but the blog post also goes on to say [16:44] okay challenge accepted let's try to [16:46] make one that does in place mutation in [16:48] haskell um so that one is slightly less [16:51] concise um here it is [16:55] but beyond the conciseness delta um [16:56] there's a much more concerning issue [16:58] which is that i'm just going to [16:59] highlight a couple of function calls we [17:00] have in here based on their names you [17:02] can guess why i might be concerned [17:03] unsafe read unsafe swap an unsafe slice [17:07] those don't sound safe [17:09] based on the names and indeed if you [17:11] look at the uh [17:12] what they're actually doing [17:14] this is imperative haskell we are [17:15] actually literally doing a [17:17] data.vector.generic.mutable [17:20] and we're in a pure functional language [17:21] or theoretically pure functional [17:23] we're actually doing like direct [17:25] in-place mutation and just hoping no no [17:28] no nobody notices it's going to be fine [17:29] everything's fine [17:31] so here's the the docs for unsafe slice [17:34] says like yield a part of the mutable [17:36] vector without copying it meaning if [17:38] somebody else mutates it it's going to [17:39] mutate my copy so referential [17:40] transparency is now gone no bounce [17:42] checks are performed so we're actually [17:43] now less safe than something like rust [17:45] we're in like c and c plus plus [17:46] territory where we might get [17:47] segmentation faults if we try to read [17:49] off the end of the array we might get [17:50] garbage memory [17:52] security problems uh this function's all [17:54] kinds of unsafe so it's a good thing [17:56] they put on safe in the title i [17:57] appreciate that [17:59] so this is uh [18:00] kind of cheating um we're it's actually [18:02] super cheating like we're just not doing [18:04] functional programming anymore um [18:06] but having said that okay okay fair [18:08] enough but [18:09] how does it perform [18:11] well [18:12] uh so i ran this against a number of uh [18:14] other programming languages and uh quick [18:16] sorting 10 million numbers um and also [18:19] doing running that 100 different times [18:21] and then sort of taking the average just [18:22] so we can kind of see how things look [18:24] all done on the same machine um so [18:26] javascript clocked in a little under 1.4 [18:29] seconds haskell was actually slightly [18:31] faster than javascript which is [18:33] impressive [18:34] java was faster than haskell go was [18:36] faster than java and then c plus [18:38] unsurprisingly was the fastest so this [18:40] is all again just sort of textbook you [18:41] know unoptimized just writing out [18:43] quicksort according to the textbook or [18:45] in the haskell case doing this kind of [18:46] weird unsafe thing um but it does show [18:48] that it is it is possible for haskell to [18:51] beat these languages but again [18:53] not by using functional programming this [18:55] is just by sort of cheating and uh and [18:57] doing really dangerous things that i [18:59] don't think any hassler would recommend [19:00] that you do in production code unless [19:01] there's really absolutely no other [19:02] alternative having said that [19:05] it is good to know that if you need it [19:06] if you really need to do an imperative [19:08] algorithm like that you do have access [19:10] to that in haskell like you're not going [19:11] to be blocked you're not going to be [19:12] like oh i guess we got to rewrite in c [19:14] plus plus no you actually can do it and [19:16] it can be competitive in performance [19:18] with languages that are 100 imperative [19:20] that are imperative all the time not [19:21] just when you're sort of doing this [19:22] carve out um [19:24] the deltas that you see here like the [19:26] reason that some of these languages are [19:27] different is basically though although [19:29] there is the same algorithm you know [19:30] behind the scenes they're all doing [19:31] asymptotically the same thing there's [19:33] different language overheads that are [19:34] sort of accounting for these differences [19:36] um [19:37] worth noting that in this benchmark we [19:39] found that tweaks affect the overhead a [19:41] lot so i really don't want anyone to [19:42] look at that and be like oh java is [19:44] faster than javascript no this is not a [19:46] reasonable conclusion to take away [19:48] for example originally we had when we [19:50] did this we used java arraylist and [19:51] someone pointed out hey java array is [19:53] like much faster it's something like [19:54] this sure enough that was true that [19:55] really brought brought things down for [19:57] java we didn't consider that to be [19:59] really a performance optimization [20:00] because it's like either was a [20:01] reasonable choice [20:02] javascript originally we were sorting [20:04] 64-bit integers and even though java has [20:06] like a javascript has a big num thing [20:07] now it turns out it's just still way [20:09] slower than double which is sort of [20:10] java's javascript's red and butter so go [20:13] figure we switched everything to double [20:14] so so is not to disadvantage javascript [20:17] and c plus is skipping bounce checks [20:19] maybe that's unfair to the other [20:20] language that's definitely memory unsafe [20:22] but that is kind of idiomatic c plus [20:24] plus so we figured well we're trying to [20:25] just do a straightforward implementation [20:26] here so that seemed fair again can't [20:29] emphasize this enough this is not a [20:30] rigorous comparison [20:31] this is really just to talk about you [20:33] know performance optimization and uh [20:34] pure functional languages [20:36] um [20:37] okay also note worth noting that um [20:39] interop is a much more common way to [20:41] solve like uncommon performance problems [20:43] like this like if i were writing haskell [20:44] and i found some algorithm that like [20:46] really really needed to be performance [20:47] optimized like they really needed that [20:49] in-place mutation i probably would not [20:50] go into this like mutable like let's [20:52] just throw all our guarantees out the [20:53] window land or if i if i have to then [20:56] i'm probably just going to do it by [20:57] doing interop with a much faster [20:58] imperative language like a low-level [20:59] systems level language c plus rust zig [21:02] something like that and this is what [21:03] most languages do i mentioned numpy [21:04] earlier in python the whole point of [21:06] that is it just goes down and talks to [21:07] like i think numpy is written in c um [21:10] but you know basically a lower level [21:11] language that's capable of you know [21:12] running as fast as you need [21:14] okay but what if we could do it with [21:17] optimizers instead instead of you know [21:20] cheating instead of like throwing all of [21:21] our guarantees out the window is there [21:22] some way that we can optimize our way [21:24] into getting that same level of [21:25] performance because optimizers are [21:27] pretty amazing things like um the the [21:28] first optimizing compilers included uh [21:31] fortran and apparently so i've told [21:33] people were actually surprised to find [21:35] that the code written through the [21:36] optimizing compiler actually ended up in [21:38] practice being faster typically than [21:41] code written by hand like an assembly [21:43] language people were really surprised by [21:45] this um there may come someday be a day [21:47] where you know much like with games like [21:49] chess and now go um humans are just [21:51] incapable of beating optimizers we're [21:53] definitely not there yet but it's [21:54] theoretically possible that we could get [21:55] there where you know you just can't [21:56] really catch up and also in the typical [21:58] case it's way faster let the optimizer [21:59] do it so if we can we would like to not [22:02] have to resort to things like interop or [22:04] you know these uh secret mutation you [22:06] know unsafe things um [22:08] so one example of a good optimization [22:10] that's really common and important in [22:12] functional languages is tail call [22:13] optimization this is something where we [22:15] don't need to drop down into other [22:16] languages we don't need to do unsafe [22:17] things we can just let the compiler sort [22:20] of translate pure functional code into [22:22] code that is equivalent to the [22:24] imperative counterpart so uh basically [22:27] any imperative loop like a while or a [22:29] four or anything like that [22:30] can be expressed this is there's a proof [22:32] somewhere i forget what it's called um [22:33] as a recursive function instead they're [22:35] both they're both like equivalent in [22:36] terms of expressive power um the [22:38] recursive function by default it has [22:40] very different runtime characteristics [22:42] but tail call optimization can detect [22:44] when it's possible to optimize that into [22:47] just the same thing in other words like [22:48] the exact machine instructions that you [22:50] get out the other side are going to be [22:51] identical whether you wrote a while loop [22:54] or you wrote a recursive function [22:56] so that's cool and that's sort of [22:57] promising [22:59] could we do the same thing here could we [23:01] make it so that we could take this [23:03] imperative for loop where we did [23:05] mutation in place for this array example [23:07] and make it so that the array.map [23:09] version optimizes to exactly the same [23:12] thing like same runtime characteristics [23:14] and the answer is yes but [23:16] you've got to be careful with that [23:18] because if we're doing things in place [23:19] it's not really immutable anymore [23:22] except it can be in one situation [23:25] like if those compile to the same [23:26] machine code and [23:28] we have to happen to be in the situation [23:30] where the thing that we're mapping over [23:32] is never referenced again for the rest [23:33] of the program [23:35] there's no downside it's never [23:36] referenced again yeah we're mutating in [23:38] place but no one ever sees that [23:40] like we're just reusing the same memory [23:41] and so it's still semantically immutable [23:43] we've still preserved all of our [23:44] guarantees everything's still [23:45] referentially transparent [23:47] but we're getting the runtime [23:48] performance of imperative in place [23:50] mutation [23:53] interesting interesting so this is the [23:54] idea of opportunistic in-place mutation [23:56] basically the compiler figuring out when [23:58] it's unobservable to change to in-place [24:00] mutation and then just doing that [24:02] similar to tail call optimization um so [24:05] this absolutely can be done [24:06] automatically one way to do it is by [24:08] using reference counting like we are [24:09] using in rock so basically the trick is [24:11] just reference count counts how many [24:12] times the thing is referenced if you're [24:14] about to do something that would [24:15] ordinarily be in [24:17] immutable clone and you realize wait a [24:19] minute the reference count is one that [24:20] means nobody else is referencing it so [24:23] let's go ahead and do it in place you [24:24] can totally do that um this does mean [24:26] that you need to be doing reference [24:27] counting instead of a tracing garbage [24:28] collector because the tracing garbage [24:29] collector doesn't have that information [24:31] it doesn't know how many uh references [24:32] you have to something so um that this [24:34] optimization when done in this way sort [24:36] of relies on that [24:38] as it turns out um very very often like [24:40] a whole lot of the time though um you [24:42] can actually do this statically like you [24:44] can detect [24:45] that the reference is going to be won at [24:47] this exact point because you can see [24:49] it's just never referenced for the rest [24:50] of the program [24:51] so this is basically a way to detect [24:53] many but not quite all but many very [24:54] many of the these in-place mutation [24:56] optimization opportunities at compile [24:59] time now this means that you don't [25:01] actually need to do the runtime [25:02] reference count checks which is good [25:03] because it works with all of the [25:04] different ways that rock can manage [25:06] memory not just reference counting [25:08] and it also means that we can do it for [25:09] unboxed values so only box values are [25:11] reference counted and which means that [25:13] you know if we're doing this the static [25:15] detection we can do it for any kind of [25:16] record for example [25:18] um [25:18] this also reduces runtime overhead in [25:20] general because it means we just don't [25:21] need to do this extra comparison to this [25:23] extra check at runtime to see if the [25:24] reference count is one we just already [25:26] know that it's safe to do it in place we [25:27] can just remove that conditional [25:28] altogether [25:30] um [25:31] the first version of this that we had [25:32] going uh was made by folk devries as [25:34] part of his um master's thesis at [25:36] radballer university sorry dutch people [25:38] i know it's pronounced differently [25:39] but he used uniqueness types and [25:41] inspired by the clean programming [25:42] language um and this worked this [25:44] actually was able to do the in-place [25:46] detection at compile time but uh we [25:48] found that it was kind of brittle and it [25:49] was actually like unfortunately easy to [25:52] de-optimize it and like make a change [25:53] somewhere in your program that caused [25:54] the optimization to no longer be able to [25:56] apply um so version two which is what [25:59] we're using today is based on alias [26:00] analysis using the morphic solver this [26:03] is a really cool library especially [26:04] academic folks you should check this out [26:06] these uc berkeley folks they did this in [26:08] undergrad [26:09] i played video games in undergrad uh [26:10] they've made a static in place mutation [26:13] detection optimization library and rust [26:15] that's like plugable into multiple [26:16] compilers one of which is the rock [26:18] compiler now i guess the first of which [26:19] is the rocking pile we've been sort of [26:20] collaborating with them um so really [26:22] appreciate all their hard work on this [26:24] um it's really cool and really is [26:25] helping out uh rock to achieve its goals [26:27] and performance um and uh so if you if [26:30] you're interested in that here's some [26:31] contact info to follow up with them um [26:34] cool so [26:35] pulling all this together i'm talking [26:37] about a lot of optimizations here a lot [26:38] of like you know overhead reduction um [26:41] how competitive can a pure function [26:42] language be at quicksort um well uh so [26:46] in terms of rock uh let's let's actually [26:48] implement quicksort in a pure functional [26:51] style like not cheating not resorting to [26:53] imperative stuff this is actually pure [26:54] functional quick sort for real [26:57] so we saw in the javascript version um [26:59] there was all these imperative stuff [27:00] there was like a for loop and there was [27:01] a swap in place and partitioning index [27:03] being incremented um but through the [27:05] stuff we've just talked about like tail [27:06] call elimination we can say okay we [27:08] don't actually need to do a for loop we [27:09] can just do a recursive function and [27:11] instead of doing this swap in place [27:12] maybe we can just do a swap that's [27:14] semantically immutable but hopefully can [27:15] get compiled to in-place mutation in [27:18] practice um so here's what partition [27:20] looks like in rock it is definitely [27:22] longer than the imperative version i'm [27:23] not gonna lie [27:24] um and it's also doing what appears to [27:26] be a lot more work like we're instead of [27:27] incrementing that thing with plus plus [27:29] we're actually returning a record that [27:30] has like the new index plus one the list [27:32] is doing a full swap which is you know [27:34] semantically is uh is immutable [27:36] returning a new list um we're returning [27:38] another record here um we're calling [27:40] this partition help function which is a [27:41] whole nother function um which is also [27:44] returning records and calling itself so [27:45] it's recursive um really just like [27:47] looking at these two side by side it's [27:49] clear that like yeah okay quick sort [27:51] this is not where functional programming [27:52] shines this is not where like like yeah [27:54] i can't wait to like write quicksort in [27:55] a pure functional style it's gonna be [27:57] really beautiful and elegant and concise [27:58] now this is actually pretty much a [28:00] pathological algorithm for pure [28:01] functional programming like it requires [28:03] in-place mutation um [28:05] to be fast and that's just like not [28:06] something that pure fp excels at it's [28:08] great at plenty of other things but this [28:09] is not it this is we're really at the [28:12] worst case scenario pretty much for for [28:14] pure functional programming but [28:16] we have this question where we saw in [28:18] the in the benchmark with haskell [28:20] haskell using imperative stuff was able [28:22] to [28:23] you know be competitive with these [28:24] imperative languages basically because [28:26] haskell has pretty low overhead overall [28:28] in fact it was even able to be slightly [28:29] faster than javascript um [28:32] where does rock end up when we're using [28:33] no no tricks no like secretly imperative [28:36] stuff no [28:37] interop just [28:39] pure functional programming [28:41] and a bunch of optimizations [28:43] turns out [28:45] really really fast [28:51] so this is pure functional programming [28:52] language it has no business being fast [28:53] at quicksort [28:55] and yet because of all these [28:57] optimizations that we're doing and like [28:58] all the low overhead that we've like [28:59] really been careful to bake in the [29:01] language um granted like i said this is [29:03] a pretty silly benchmark but um it's [29:05] real i mean this this actually we got it [29:06] to be faster than javascript haskell [29:09] haskell using cheats [29:11] java go and basically everything but c [29:14] plus plus um not gonna lie we just got [29:16] all of this working like two days ago [29:18] and uh like within an hour or two we [29:20] were like okay well like how do we close [29:21] that gap with c plus plus [29:23] uh [29:24] that'll be another talk hopefully that'd [29:26] be really cool but um but yeah i mean [29:27] basically the the way that we were able [29:29] to do this was by just optimizations um [29:32] which to me is like uh very exciting you [29:34] know it's fundamentally now we have the [29:36] same algorithm in terms of asymptotics [29:37] and just that difference in overhead we [29:39] were able to sort of bring that down as [29:40] well as possible meant that yeah i mean [29:42] even for problems like this where you [29:43] need in place mutation to be fast that's [29:45] achievable now [29:47] okay so to sum up all the optimizations [29:49] we sort of talked about here we have the [29:50] lvm optimizer this is doing all like [29:52] really low level stuff same thing that c [29:54] plus plus and rust in them and zig use [29:56] um that's doing a lot of heavy lifting [29:58] here for sure um unboxed values really [30:00] helps out the llcm optimizer um just not [30:02] doing these like heap allocations that [30:04] we don't need to um static reference [30:06] counting that was in use there so that [30:07] was all automatically memory managed [30:09] code [30:09] we can do even better with other memory [30:11] management strategies but it seemed like [30:12] for a fair comparison we shouldn't use [30:14] those here um tail call optimization [30:16] absolutely essential for quick sort [30:18] we tried actually doing it without tail [30:20] call optimization just to see what [30:21] happens and the answer is you just sit [30:23] and watch the computer do nothing for a [30:24] while and then eventually stack overflow [30:25] so don't recognize don't recommend that [30:27] um but uh but fortunately when you do [30:29] have it it's quite fast um and then [30:31] finally the real key that you know [30:33] without which this is just uh totally [30:34] hopeless is the opportunistic in-place [30:36] mutation now that's one of the things [30:37] that as far as i know rock is the only [30:39] functional programming language that's [30:41] sort of aimed at being like a real used [30:43] in industry language that's doing this i [30:44] think all the other languages that are [30:45] doing it are like academic research [30:47] languages [30:48] so we're excited to see what it can do [30:50] okay so let's summarize all the things [30:52] we talked about um so first you know [30:54] this this is a language that comes [30:55] directly from elm this is a direct [30:56] descendant of elm i've had this really [30:58] delightful experience using elm it's a [30:59] pure functional language that compiles [31:00] to javascript really great for [31:02] browser-based uis but i wanted to be [31:03] able to do sort of other things than [31:04] just browser-based uis with a similar [31:06] kind of feel of language um so those are [31:08] all the goals of rock uh you know [31:10] delightful experience i mean i didn't [31:11] talk about any experience stuff but i've [31:13] given some other talks on you know user [31:14] experience and uh ergonomics of rock [31:17] pure functional compiled binary um and [31:20] yet we still want to go fast you know [31:22] even though we're compiling to you know [31:23] binaries and competing with all the [31:24] other imperative languages that would do [31:26] that you know we'd really like to be uh [31:27] as as fast or faster than uh than sort [31:29] of our our contemporaries [31:31] there's three major performance [31:32] considerations to this so one is overall [31:34] language overhead and then there are [31:35] these sort of drawbacks to try and work [31:36] around like we can't have side effects [31:38] can't have mutation um so talked about [31:40] how you know overall language overhead [31:42] can sometimes just dominate and it [31:43] doesn't those other considerations just [31:45] don't matter like at work you know we [31:47] are migrating uh from ruby to haskell uh [31:49] most of our traffic now goes through [31:50] haskell and we saw about a 10x [31:52] improvement by the way uh we're hiring [31:54] if you're interested in working in [31:55] technologies like haskell and elm maybe [31:56] someday rock who knows um [31:59] and uh and so uh what we saw is that [32:01] we're able to sort of uh get language [32:03] overhead for rock as low as possible by [32:04] using lvm as our compilation back end um [32:07] using unboxed values basically [32:09] everywhere and by doing memory [32:11] management uh in these really low [32:12] overhead ways with static reference [32:13] counting um as well as these other novel [32:16] things that i mentioned in other talks [32:18] um we don't actually know to be fair [32:20] like how how well the static reference [32:21] counting is going to work at scale [32:22] because rock is a very work in progress [32:24] language it's like not really being used [32:25] for anything serious yet there are no [32:27] sufficiently big rock programs to say [32:28] that but so far we're feeling pretty [32:30] good about about the direction we're [32:31] going [32:32] um talked about side effects versus [32:33] managed effects so rock can't do side [32:35] effects but it does manage effects which [32:37] in practice feels about the same as [32:38] using promises [32:40] the only difference is that you know you [32:41] sort of have to use them everywhere for [32:42] every possible effect there is no like [32:44] non-promise or non-task way of doing [32:46] effects so really that comes down to [32:48] okay how efficient are those effects and [32:50] fortunately when we're doing unboxed [32:52] tasks unboxed closures and these [32:53] enumerated direct calls it turns out to [32:55] be so fast that in practice we're just [32:57] not worried about this being a [32:58] significant source of overhead for the [32:59] language [33:00] um on the other hand uh we talked about [33:02] immutability and so normally [33:03] immutability is by default a cost but we [33:05] have seen use cases some scenarios where [33:08] immutability at runtime like actually [33:10] you know creating new versions of values [33:12] can end up being a performance [33:13] optimization depending on the libraries [33:15] you're using and how quickly they can [33:16] potentially skip doing other work [33:18] so this is a good example in the browser [33:22] but we also talked about how that's it's [33:23] not always that convenient sometimes you [33:25] have algorithms that require in-place [33:26] mutation to run fast um and this is [33:28] where this sort of long list of [33:30] optimizations that we've got going on [33:31] enables us to compete with those um all [33:34] of this sort of culminating in in our [33:36] exciting results of actually being able [33:37] to be faster at quick sort which is [33:39] pathologically hard and bad for pure [33:41] functional programming um written in a [33:43] pure functional style and actually out [33:44] competing successfully um these [33:46] imperative languages that are sort of in [33:48] their wheelhouse [33:49] um [33:50] so hopefully we've now seen a couple [33:51] different examples of ways that pure [33:53] functional programming actually can out [33:54] compete outperform imperative at various [33:57] different tasks in some cases like with [33:59] the the rendering in the browser it's [34:00] just because pure functional programming [34:02] happens to be well suited to doing that [34:03] in a high performance way in other cases [34:05] it's just because of baseline language [34:07] overhead has nothing to do with paradigm [34:08] like our haskell outperforming ruby at [34:10] work um and in some cases it's just [34:12] through sort of a sheer force of [34:14] optimizations that we're able to say [34:16] yeah even though this task is not [34:17] innately well suited to pure functional [34:18] programming we can make the downside be [34:20] just that it's less concise and you know [34:23] more to read but not that it's slower in [34:25] fact it can actually still be capable of [34:27] outperforming other garbage collected [34:29] languages [34:30] and hopefully now you have an idea of [34:32] how you actually can outperform [34:34] imperative with pure functional [34:35] languages thanks very much [34:39] [Music] [34:54] you