Rust让科学计算速度提升200倍

因果推断需要庞大的计算量

在因果推断中，有2个关键步骤：

1. 因果发现
2. 因果效用评估

1. 因果发现

因果发现问题可以简单理解为，首先我们有一组变量，然后在这些变量能组成的 所有 图中，找到一个最能够正确描述这些变量之间因果关系的图。那到底要搜索多少图呢？给大家看一组直观数据：

从上面表格中的数据可以不难发现，随着变量数量的增加，有向无环图（DAG）数量呈指数级爆发增长。当变量数达到10个时（10个变量在实际问题中并不算多，很常见），DAG解空间将膨胀到 $10^{18}$ 量级!!

尽管很多精妙的搜索算法会用大量技巧避免搜索整个DAG解空间，但是优化后的搜索空间依然十分巨大。如何高效求解是因果发现领域的研究热点。2018年以来发布的NoTears系列算法是该领域的核心创新，它将离散的DAG空间转换为平滑函数，将搜索问题转变成计算邻接矩阵的“DAG度（DAG-ness）”。但NoTears算法的复杂度依然是$O(d^3)$级。

2. 因果效用评估

因果发现只能带给我们定性的信息，它回答变量之间的因果关系，但不会定量地告诉我们他们之间的因果效用有多大。此时就需要因果效用评估算法。

因果效用评估常用的方法是结构方程模型，这里的结构方程模型既可以是标准的线性结构方程模型也可以是广义的非线性结构方程模型。以线性结构方程模型为例，线性模型意味着变量间的关系可以用线性方程描述。例如，假设我们有关系 $\mathit{X \rarr Y \larr Z}$，我们可以将其描述为标准参数化结构方程模型：

$$ \begin{aligned} &\mathit{X = \epsilon_1}\\ &\mathit{Z = \epsilon_2}\\ &\mathit{Y = \alpha X + \beta Z + \epsilon_3} \end{aligned} $$

其中$\epsilon_1, \epsilon_2, \epsilon_3$是满足高斯分布的独立随机变量。

结构方程需要根据样本数据对参数 $\mathit{\alpha, \beta}$ 赋值，同时给出误差项 $\mathit{\epsilon}$ 的均值$\mu$和方差$\sigma$。

当因果图中的关系比较多时，结构方程模型会非常复杂。理论上，无论是Gauss消元法还是LU分解法在直接求解线性方程组问题上的复杂度都是$O(d^3)$。

Rust让计算效率提升200倍

近年来，人们逐渐意识到对于一些复杂的情况，潜变量之间的非线性关系对于建立更有意义和正确的模型非常重要。由于潜变量非线性项对应的分布非常复杂，因此分析非线性结构方程模型更加困难。马尔可夫链蒙特卡罗（MCMC）估计方法在包含潜变量的结构方程模型（SEM）中迅速流行。简单地说马尔可夫链蒙特卡罗方法对潜变量假定先验，然后用MCMC直接对潜变量进行抽样，潜变量的样本有了，结构方程模型也就退化成了回归问题。

根据《结构方程模型：贝叶斯方法》一书中的算法理论，我用Python+numpy独立实现了MCMC方法。整体算法采用Gibbs采样，对800个样本采样10,000次，最终模型稳定收敛。用时553秒（9分多钟）。对比《结构方程模型：贝叶斯方法》一书的译者蔡敬衡教授和潘俊豪教授的C语言实现版本只需要14.7秒，python实现版本慢了40倍！根本无法达到生产使用要求。

最近我用Rust重新实现了MCMC方法，在相同运行环境下，只需要3.1秒！是Python的178倍，比C语言实现还快5倍！

图1. Python vs. C vs. Rust (数值越小速度越快)
运行环境：Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz 8G内存

为了更细致、客观地比较3个语言在科学计算上的性能，我将MCMC方法实现中用的最多的计算操作单独抽取出来，做了横向比较。

在MCMC算法中，用的最多的操作有：

• 矩阵点乘
• 矩阵求逆
• 解线性方程组
• Cholesky分解
• 高斯分布随机采样
• Gamma分布随机采样

为了公平，我们设计了一个1000 * 1000的矩阵 $A$，矩阵中每个元素是用高斯分布随机采样或Gamma分布随机采样，然后计算矩阵点乘 $A \cdot A^T \quad A \sim N(0, 1)$, 矩阵求逆 $A^{-1} \quad A \sim N(0, 1)$ , 解线性方程组 $AX = b \quad A \sim \varGamma , b \sim N(0, 1)$ 和 Cholesky分解$A = I$。其中Python调用numpy库进行矩阵运算和随机采样，C采用Numerical Recipes中的算法实现矩阵运算和随机采样，Rust用ndarray-linalg进行矩阵运算，用rand_distr完成随机采样。运行结果如下：

图2. 高频科学计算任务性能对比

从上表可以看出，在矩阵运算上，Rust比C快30-50倍，比Python快200-500倍！在随机采样上，Rust比C快5-10倍，比Python快200倍。从图表上看，Rust快到看不见，性能确实强悍！

上面的运行结果让我着实吃了一惊。首先Python性能这么差出乎所有人意料，因为MCMC的python实现中主要用numpy和scipy进行科学计算，numpy和scipy背后是用C语言实现的，不应该跟C有如此大的差距；其次Rust性能比C还快5倍也是意外惊喜，理论上Rust语言的性能应该接近C语言，不应该有如此大的提升。

为了回答上述问题，我们深入到3种语言背后是用的库的实现。我们首先研究了C语言实现使用的Numerical Recipes, 这是一个非常古老的库，随着 Numerical Recipes 系列算法书籍发布，有多种语言实现。Numerical Recipes在矩阵运算上采用了多种技巧优化性能，比如对对角阵、对称矩阵等特殊形态的矩阵进行了特殊的优化，让计算量下降一个数量级。而MCMC中有大量的对称矩阵，这就解释了为什么C语言实现比numpy实现会快这么多。

我们又深入到Rust的ndarray和ndarray-linalg的实现。ndarray-linalg在矩阵计算时背后调用的是OpenBlas或Intel-MKL，在我们测试中用的是Intel-MKL。Intel-MKL是⼀套经过高度优化和广泛线程化的数学例程（Subprograms ），专为需要极致性能的科学、工程及金融等领域的应用而设计，并针对英特尔处理器提供特别的性能优化。这就解释了为什么Rust实现比C语言实现快这么多--不是语言上的优势，而是OpenBlas/Intel-MKL带来了性能上的提升。

Rust会成为未来科学计算的主流吗？

Rust性能这么强悍，那么Rust会取代Python成为科学计算和机器学习的主流语言吗？

我们认为不会。

编程语言只是一个工具，判断一个语言的是否流行或者是否适用，不是单纯比较性能（尽管性能非常重要），还应该考虑更多维度。其中语言的安全性、易用性、生态直接影响语言的流行程度。

图3. Python、C和Rust语言特性对比

Rust语言有其突出的优势，它诞生的背景和目标是为了在保证性能的前提下解决内存安全问题，Rust将自己定位为系统语言，目的是挑战C语言在系统编程领域的地位。所以如上图所见，Rust有着比拟C的性能，同时最大化了内存安全。然而获取内存安全的代价是提高了学习门槛和编程难度。Rust是公认的学习曲线最陡峭的编程语言之一。它开创性的所有权机制引入了大量新的概念和规则，需要开发者改变过去的编程习惯，重构心智模型。

而科学计算场景下编程语言的使用者多是科学家和分析师，他们往往缺乏计算机底层理论知识，需要的仅仅是一门简单易用、表达力强大的语言。这方面Python有着无可比拟的优势。同时Python有着丰富的第三方库，几乎涵盖所有编程领域的需求，这点C和Rust还有很长的路要走。

并且科学计算大多数情况是运行在实验室环境下，对于性能不敏感，所以C和Rust在性能上的优势在科学计算上加分不多，反而复杂的语法、陡峭的学习曲线、缺乏丰富的第三方库成为其在科学计算中流行的绊脚石。

因此我们认为Python在科学计算和人工智能领域的地位短时间还是无法撼动的，Rust由于其自身定位的原因，也很难在科学计算这一领域对Python构成威胁，但是在性能敏感的场景下，用Rust取代C作为Python的后端语言是不错的选择。事实上业界已经出现Weld等Rust项目为Python提速。

应该用Rust重构技术栈吗？

Rust 语言作为一门新生语言，目前倍受关注。不仅有诸多大佬站台宣传，网上对Rust也是一边倒地赞扬。开源界更是视Rust为解决安全问题的救命稻草，用Rust重构一切的呼声甚嚣尘上。是否应该用Rust重构技术栈成为开发界热议的话题。

要回答这个问题，光看语言特性是不够的，要考虑应用场景、组织发展和团队管理等一系列外部问题。我们需要一个更宏观的框架去思考Rust语言的现状和未来。一般我会从如下4个方面去考量一门语言：

图4. 编程语言评估框架

适用场景

一门语言的适用场景往往跟它的语言特性密切相关。Rust 语言定位为一门通用系统级编程语言，它无 GC ，在保持高性能的同时保证内存安全和并发安全。与其他语言相比，Rust有4大优势：

1. 高性能。Rust 速度惊人且内存利用率极高。由于没有运行时和垃圾回收，它能够胜任对性能要求特别高的服务，可以在嵌入式设备上运行，还能轻松和其他语言集成。
2. 可靠性。Rust 丰富的类型系统和所有权模型保证了内存安全和线程安全，让您在编译期就能够消除各种各样的错误。
3. 硬件直接抽象。Rust 和 C 都是直接对硬件的抽象，都可看作一种「可移植汇编程序」。Rust能控制数据结构的内存布局、整数大小、栈与堆内存分配、指针间接寻址等，所以Rust经常被视为C语言的安全替代。
4. 异步高并发编程。Rust 原生支持异步高并发编程，它自带的并发原语可以零成本实现异步编程，极大简化了异步开发。Rust 语言可能是首个支持异步编程的系统级语言。

Rust语言的特性使得Rust 的应用场景基本可以同时覆盖 C/C++/Java/Go/Python 的应用领域，大致可以分为如下场景：

1. 操作系统：如Rust for Linux，Redox，Tock等；
2. 数据库：如事务型分布式 Key-Value 数据库TiKV，新一代原生数仓Databend等；
3. 云原生：如微型无服务虚拟机Firecracker，k8s上的WASM运行时Krustlet等；
4. 区块链：如Facebook的Diem，区块链创新平台Substrate等；
5. 高性能网络：如异步框架tokio，高性能web服务框架Actix-Web等；
6. 机器学习：如HuggingFace的Tokenizers，对标sk-learn的linfa等；
7. 游戏引擎：如bevy、ggez等；
8. 工具类：如远程桌面rustdesk；
9. 其他语言运行时和WebAssembly：如JavaScript和TypeScript运行时Deno，WASM框架yew等；

总的来说Rust适合基础设施开发及对性能、安全敏感的领域，而事实上目前Rust在这些的应用也是最多的。

语言成熟度

一门不成熟的语言是不应该被用于生产环境的。不同语言的成熟度标准可能不太一样，我一般从语言自身成熟度、开发者基础、社区活跃性和应用广泛性4个方面衡量一门语言的成熟度。

自身成熟度

Rust语言自 2008 年开始由 Graydon Hoare 开始研发，2009 年得到 Mozilla 赞助，2010 年首次发布 0.1.0 版本。Rust坚持以6周为单位不断迭代新功能，每3年升级版次。自2015 年Rust发布 1.0 稳定版以来，已经连续发布了两大版次 2018 Edition 和 2021 Edition。每个版次都有明确的主题：

• 2015 Edition: Rust 0.1.0 ~ 1.0 稳定版，主题是 “稳定性”
• 2018 Edition: Rust 1.0 ~ 1.31.0 稳定版，主题是 “生产力”
• 2021 Edition: Rust 1.31.0 ~ 1.56.0 稳定版，主题是“成熟”

从Rust发版来看，Rust 语言已经足够成熟到能将其应用于生产环境。从新特性发布频率来看，Rust 早已稳定，且稳定版 API 基本不会更改，稳定版每六周发一个新版主要是解决现有问题和优化性能。

开发者基础

开发者基础是编程语言选型的重要考量指标之一，它关系到开发者的成熟度和招聘难易程度。尽管Rust 连续六年被Stack Overflow评为最受欢迎语言，但Rust的实际用户数并不多。在2022年10月之前，Rust在TIOBE 编程语言排行榜中一直在20名开外，这说明Rust 依旧属于小众语言。好消息是Rust的排名一直在稳步上升，截止2023年5月，Rust 排名 17 ，流行度 0.82%。我们可以认为Rust开始步入主流变成语言行列。

图5. 2023年5月TIOBE编程语言排名(1-20名)，Rust排名17。

社区活跃性

Rust社区目前呈现出贡献者社区和开发者社区活跃度两级分化的情况。

Rust贡献者社区十分活跃，目前有Rust贡献者多达3800人。对比Github上其他流行语言的贡献者，

图6. 流行编程语言贡献者数量对比

Rust的贡献者是其同时期诞生的Go语言的2倍。

并且Rust语言的迭代速度非常快。从 2010 年 6 月 17 号 Rust 创始人 Graydon 的第一个提交开始，Rust一共修复了 35,694 个issues 和 53,183 个 PR，12年间平均一天修复 8 个 issue，12 个 PR。这个速度在任何规模的开源项目中都是惊人的。

与贡献者社区的活跃项目，开发者社区就显得平淡许多。这与Rust目前开发者基础尚浅，依然属于小众语言有关。根据Stack Overflow的数据，Rust相关问题大约28,629个，平均每周 150 个问题左右，每天 20 个问题左右。相比其他语言，

图7. 主流编程语言Stack Overflow提问问题数对比

Rust的提问问题只有Go语言的一半不到。可见Rust开发者社区还有待进一步成长。

应用广泛性

编程语言在各领域中的重量级应用可以从侧面反映语言的成熟度。目前Rust在很多的领域都涌现出杀手级应用。其中最受关注的是Rust for Linux。

Rust for Linux 项目旨在推动 Rust 成为 Linux 内核编程语言的一等公民，目前已经在Linux社区获得广泛认同，连Linux创建者 Linus 在活动中支持Rust进入Linux。在2021开源峰会上，Linus表示：

... ... C 语言微妙的类型交互，并不总是合乎逻辑的，对几乎所有人来说都是陷阱，它们很容易被忽视，而在内核中，这并不总是一件好事。

Rust 语言是我看到的第一个看起来像是真的可以解决问题的语言。人们现在已经谈论 Rust 在内核中的应用很久了，但它还没有完成，可能在明年，我们会开始看到一些首次用 Rust 编写的无畏模块，也许会被整合到主线内核中。

在2021 年 9 月 的 Linux Plumbers 大会上， Linux社区再一次讨论了 Rust 进入 Linux 内核的进展，大会的结论有 2 点：

1. Rust 肯定会在 Linux 内核中进行一次具有时代意义的实验。
2. Rust 进入 Linux 内核，对推动 Rust 进化具有很重要的战略意义。

除了Rust for Linux外，Google的Fuchsia OS 内大约有 137 万行 Rust 代码，是目前出Rust自身外最大的Rust项目，并且 Google 极力支持 Rust for Linux 项目，还出资赞助了核心开发。

微软也在很多项目中使用了Rust。开发者经常使用的VS Code就使用ripgrep提升其搜索能力。

AWS也广泛使用Rust构筑其高性能、安全的基础设施级网络和其他系统软件。Amazon S3、Amazon EC2、Amazon CloudFront、Amazon Route 53等背后都是Rust在支撑着。

Facebook 内部 Rust 项目综合起来代码已超百万行，其中最著名的是加密货币项目 Diem（原Libra）。并且Facebook 目前有一个团队，专门为 Rust 编译器和库做贡献。

目前国内使用Rust的公司不多，用的最多的当属飞书团队。飞书团队在客户端跨平台组件中使用了 Rust，据不可靠消息，码量超过 55 万行。这直接反映出Rust在国内确实不火。

语言生产力

一门语言是否有生产力是软件工程中非常重要的考量指标。我会从学习曲线、工程能力、领域生态三方面去评估。

学习曲线

Rust 被公认是一门很难学的语言，学习曲线非常陡峭。

作为一门新兴的编程语言，Rust采百家之长，从 C++ 学习并强化了 move 语义和 RAII（资源获取即初始化），从 Cyclone 借鉴和发展了生命周期，从 Haskell 吸收了函数式编程和类型系统等。同时Rust又有着自己独特的思想，其所有权和生命周期机制，几乎是所有其他编程语言都未曾涉及的领域。这就要求开发者不但要学习掌握大量的概念，还需要转换编程思维--从命令式编程转换到函数式语言、从变量的可变性迁移到不可变性、从弱类型语言迁移到强类型语言，从手动或自动内存管理到通过生命周期来管理内存。这些转换都要求开发者重构心智模型，多种思维转换让难度是多重叠加。

Rust极高的学习门槛和陡峭的学习曲线让许多开发者望而却步或浅尝辄止。这最终导致前面提到的Rust开发者基础薄弱。当然学习门槛的高低，依个人水平不同而不同。顶尖的开发者可以较轻松地跨越学习门槛，成为Rust拥趸和贡献者，大部分普通开发者被拦在了入门之外。这就解释了为何Rust贡献者社区和开发者社区量级分化严重。

工程能力

Rust 已经为开发工业级产品做足了准备。

为了提供灵活的架构能力，Rust 使用特质（trait） 来作为零成本抽象的基础，让开发者可以灵活地架构紧耦合和松耦合的系统。Rust 也提供了泛型来表达类型抽象，结合 trait 特性，让 Rust 拥有静态多态和代码复用的能力。泛型和 trait 让开发者可以灵活使用各种设计模式来对系统架构进行重塑。

为了提供强大的语言扩展能力和开发效率，Rust 引入了基于宏的元编程机制。宏则让 Rust 拥有强大的代码复用、代码生成能力，极大提高了Rust的开发效率。

为了方便开发者相互协作，Rust 提供了非常好用的包管理器Cargo。Cargo天生拥抱开源社区和 Git，支持将写好的包一键发布到 crates.io，供其他人使用。

Rust在工程化上也存在一些不足：

首先，Rust 编译速度很慢，因为Rust在编译期要做大量编译期检查和编译期优化工作。虽然 Rust 官方也一直在改进 Rust 编译速度，包括增量编译支持，引入新的编译后端（ cranelift ），并行编译等措施，但还是慢。

其次，Rust还没有专属的IDE，尽管有很多插件能够提高Rust开发效率，但目前在宏代码的支持上不是很好，同时对 Rust 语言特有内存不安全问题的各种检测工具还很缺乏。

领域生态

软件开发中有句至理名言：“不要重复发明轮子”。现实开发工作为了平衡功能和效率，都会选择引入框架和第三方库。因此一门语言的库是否丰富对语言的生产力有至关重要的影响。

Rust的框架和库都已包（crate）的形式发布到crates.io。截止目前，crates.io 上面已经有 85,342 个 crate。这些库涵盖了命令行工具、no-std 库、开发工具、Web 编程、API 绑定、网络编程、数据结构 、嵌入式开发、加密技术、异步开发、算法、科学计算等日常常见使用场景。除此之外，Rust还在 WebAssembly 、编码、文本处理、并发、GUI、游戏引擎、可视化、模版引擎、解析器、操作系统绑定等领域有不少库。

Rust生态几乎能够覆盖所有开发场景的需要，但针对某些特殊场景、架构和硬件生态Rust的支持还不完善。这需要需要企业投入人力和硬件成本来支持，同时期待社区和生态共同努力将其完善。

可持续发展性

一门语言的可持续发展能力可以从开放性、核心团队、商业支持三方面来考量。

Rust 语言是完全开源的，它也是世界上最大的开源社区组织，有3800位贡献者，其开放性毋庸置疑。但如此庞大的开发社区给项目管理带来极大挑战。好在Rust核心团队在项目治理和协作上有清晰的分工和流程，由不同职责的团队和工作组各司其职。目前Rust项目有10个团队和8工作组，每个团队具体职能详见Rust项目。他们分工明确、协作顺畅，确保了每六周一次版本迭代，每3年一次版次升级。

2021 年 2 月 9 号，Rust 基金会宣布成立。华为、AWS、Google、微软、Mozilla、Facebook 等科技行业领军巨头加入 Rust 基金会，为 Rust 语言的开发者们也提供了强有力的资金后盾。随后，ARM 、丰田、动视、Automata、Sentry、Knóldus、Tangram 等各个领域的头部公司都加入了基金会，为推动 Rust 做贡献。可以说 Rust 语言的可持续发展前景非常广阔。

结语

Rust 语言自身相对已经成熟，生态也足够丰富，并且在很多应用领域崭露头角。但是Rust陡峭的学习曲线让Rust目前依然是小众语言，缺乏成熟的开发者基础，这是CTO在引入Rust到技术栈时要考虑的重要问题。如果团队人才密度足够高，可以比较轻松地转到Rust，否则将会面临市场人才紧缺，能力参差不齐等问题，最终导致技术选型灾难。