如何编写慢速 Rust 代码

我如何尝试将 Lisp 代码移植到 Rust 并设法得到一个慢得多的程序……以及如何解决这个问题！我最近发表了一篇博文，正如我所料（实际上，希望如此，因为这会吸引人们为“研究”做出贡献），在互联网上引起了相当大的争论！这篇文章是关于 Lutz Prechelt 将 Java 与 C/C++ 进行比较的一项旧研究，以及一些将其他语言添加到比较中的后续论文，包括 Common Lisp 和一些脚本语言。我决定尝试看看那些 21 年前进行研究的论文的结果是否仍然有效，或者从那时起情况是否完全改变。我无法让一群学生，更不用说专业程序员，用多种语言为我的“学习”编写程序，所以我做了第二件最好的事情，并移植了可以说是最常见的解决问题的方法（基于 Peter Norvig 的代码） ，不少于）其他语言：Java、Rust，以及后来的 Julia 和 Dart。结果令人震惊：Rust 是最慢的语言之一！如果我只包含相同算法的实现，它的内存使用率最低，但也是最高的LOC（代码行）。今天，我想通过展示我的 Rust 代码为何如此缓慢，以及如何通过一些小的修复，至少在性能（和正如我发现的那样，仅适用于某些类型的输入）。

感谢 Rust 的粉丝们，他们花了很多空闲时间向我展示了为什么我的 Rust 代码如此缓慢以及如何修复它！在开始研究慢速 Rust 代码之前，让我们先看看原始的 Common Lisp 代码。这是 Peter Norvig 对 Prechelt 电话编码问题的 Lisp 解决方案的本质（为简洁起见已删除注释）：（ defun 打印翻译（ num 数字和可选（开始 0）（单词 nil））（如果（ >= 开始（长度数字）） ( format t "~a:~{ ~a~}~%" num ( reverse words)) ( let (( found-word nil) ( n 1)) ; 前导零问题（循环从下面开始（长度数字） ) do ( setf n ( + ( * 10 n) ( nth-digit digits i))) ( 循环词 in ( gethash n *dict*) do ( setf found-word t) ( print-translations num numbers ( + 1 i) ( cons word words)))) ( when ( and ( not found-word) ( not ( numberp ( first words)))) ( print-translations num numbers ( + start 1) ( cons ( nth-digit numbers start ) words)))))) 这是一个有趣而简短的解决方案，我自己也不会想出来的。第一个 Java 实现，而不是 JDK 1.0），但那是另一回事了。无论如何，将其移植到其他语言似乎非常容易和有趣，所以这就是我所做的。我的目的是检查一种语言到底有多大的不同，假设您可以使用相同的算法解决问题。论文（我可能在上一篇文章中没有说清楚）是，一旦您对算法的选择（有时可能是困难的部分）打折扣，语言差异就不会像您在考虑程序做完全不同的事情以达到相同的结果。最初的研究实际上有令人信服的证据表明程序员倾向于根据语言提出不同的算法：低级语言程序员倾向于使用低级结构，即使他们的语言允许更高级别的结构。我的理论是，这确实导致低级语言具有更高的 LOC 计数和更好的性能。一旦你控制了这一点，LOC 和性能应该会更接近，你使用哪种语言的意义就小得多（好吧，只要你可以让自己在你选择的语言中使用正确的抽象级别来解决问题）。

回到 Rust 代码……我试图让它尽可能接近原始 Lisp 代码，以便进行苹果对苹果的比较。所以我认为使用大数字来“关键”现有单词非常重要。很多人批评这个决定，因为他们“知道”BigInt 在许多语言中都很慢，而 Lisp 真的很擅长。好吧，我们很快就会看到，这不是 Rust 代码运行缓慢的原因。这是我编写的 Rust 代码的一部分，包括我使用的从 word 到 BigUInt 的转换： use lazy_static::lazy_static;使用 num_bigint::{BigUint, ToBigUint}; type Dictionary = HashMap <BigUint, Vec < String > >;lazy_static ！ { 静态引用一：BigUint = 1.to_biguint().unwrap();静态参考十：BigUint = 10.to_biguint().unwrap();} fn word_to_number(word: & str) -> BigUint { let mut n = ONE.clone(); for ch in word.chars() { if ch.is_alphabetic() { n = &n * ( & *TEN) + &char_to_digit(ch); } } n} 我使用了lazy_static，因为我想要一个ONE 和TEN 的全局常量，以避免为word_to_number 中显示的循环的每次迭代分配一个BigUint 实例。这不仅非常丑陋，而且完全没有必要和徒劳。我当时当然不知道。根据我以前在 Rust 中的经验，这似乎是这样做的方式（即需要非常量的全局状态，使用lazy_static）。

fn word_to_number(word: & str) -> BigUint { let mut n = 1 u8.into();对于 word.chars().filter_map(char_to_digit) { n * = 10 u8; 中的数字n + = 数字； } n} 看到这让我大吃一惊。请注意，上面的所有操作仍然使用 BigUint，与原始操作一样！让 mut n = ONE.clone();让 mut found_word = false;对于 i 在 start..digits.len() { n = &n * ( & *TEN) + &nth_digit(digits, i); ...让 mut n = 1 u8.into();让 mut found_word = false;对于 i 在 start..digits.len() { n * = 10 u8; n + = nth_digit(digits, i); ...这也需要对 char_to_digit' 做一些小改动，如果您有兴趣，请查看完整的差异。仅仅通过这种可读性的改进，代码实际上已经运行得更快了（但不如 CL 快）！！下一步是为每个部分解决方案避免低效的列表副本（或 Rust Vec），我这样做是为了保持代码简单。

每次算法为潜在解决方案找到一个新词时，它都需要将该词累积到当前部分解决方案中进行递归。它需要对可能处于同一级别的多个单词执行此操作，因此我们不能只是改变列表并忘记它。这就是为什么我使用 Common Lisp 的方法，大约：这将返回一个新列表，其中包含单词的所有元素，加上单词，没有改变单词。您可能知道，Lisp 是围绕列表构建的，因此在 Lisp 中这样做非常高效。但等效的 Rust 不是。这会复制列表，然后在递归之前附加新单词。这意味着我们可以对每个单词重复这个操作，因为原始的 partial_solution 被保留了下来。此外，单词可以保持不变，作为函数式程序员，不变性很好！正如许多评论者指出的那样，从性能的角度来看这是愚蠢的。你知道一旦你递归，这个相同的代码将再次运行（或不），并且无论如何，我们可以弹出递归完成后原始列表中的单词以达到完全相同的结果！具有不可变结构的函数式编程可能很棒，但它需要不可变数据结构的“智能”实现，而仅仅克隆 Vec 不是这样！完成了，对吧？错了……我们现在必须处理借用检查器告诉我们我们不能仅仅获得一个全新的 String 实例并将其放入我们的 Vec<&String> 中，因为 Vec 不是其任何字符串的所有者。

我在 Rust 中见过很多次：我写了一大段代码，对生命周期有点粗心，然后不得不在我的程序中的任何地方更改我的变量和函数的类型，以避免在任何地方都必须 clone() 东西使其工作。这意味着，是的，在 Rust 中编写高效的代码需要很多深谋远虑。在这种情况下，我们使用可变 Vec 的微小修改实际上要求我们只处理生命周期匹配或超过我们的 Vec 的字符串。 fn print_translations < 'dict >( num: & str, numbers: & Vec <char >, start: usize, words: & mut Vec < & 'dict str>, dict: & 'dict Dictionary,) -​​> io::Result <()> 现在，我们有一个问题，并不是我们插入到 words 中的所有单词都来自 dict：有些单词将是问题允许我们在找不到单词时使用的替换数字。 ...62 | word.push(&digit); | -----------^^^^^^^- | | | | |借来的价值活得不够长|参数要求为 `'dict` 借用 `digit` 要解决这个问题，我们必须更改 nth_digit 以给我们一个寿命足够长的字符串！但是我们怎么做呢？嗯，在这种情况下，它实际上非常简单：只有 10 个可能的数字，所以我们可以有一个包含所有数字的静态列表！然后 nth_digit 将始终返回带有 'static 生命周期的东西，这应该可以工作，因为它肯定会比 'dict.

fn nth_digit(digits: & Vec <char >, i: usize) -> BigUint { let ch = digits.get(i).expect( "index out of bounds"); (( *ch as usize) - ( '0' as usize)).to_biguint().unwrap()} 这仍然有效，因为当我们做 n += nth_digit(digits, i); 时，即使 n 是一个大Uint！静态数字：[ & str; 10] = [ "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"];...让数字= nth_digit(digits, start); words.push(DIGITS[usize::from(digit)]);在这里，像我这样的 Rust 新手（我已经断断续续地使用 Rust 两年多了，但停止成为 Rust 的新手确实需要一些时间或大量的奉献）可能会说这变得有点太复杂了与 Java 或 Lisp 相比。一生会变得非常棘手。然而，在这种情况下，似乎拥有良好 Rustexpertise 的人会看到这一点，并且会从一开始就解决这个问题？！好吧，我很想与许多 Rust 程序员一起进行一项研究，看看它在实践中的实际情况:)。或许有一天。这是正确的！ Rust 代码现在在性能上几乎完全匹配 Common Lisp 代码！有时使用 if let Ok() 可能很诱人，但不要这样做：

很花哨吧？！这是其中一种习惯用法，如果您还不知道它，您会觉得自己以前写过那段可怕的代码是个白痴。我糟糕的方法（实际上我花了半个小时才决定如何做）： let mut args: Vec <_ > = args().skip( 1).collect(); let words_file: String = if !args.is_empty() { args.remove( 0) } else { "tests/words.txt".into() };让 input_file: String = if !args.is_empty() { args.remove( 0) } else { "tests/numbers.txt".into() };显然，您不需要将 args 收集到 Vec 中，然后将它们删除以获得所有权！在迭代器上使用 next() 您实际上正在消耗这些项目。因为 std::env::Args 实现了 Iterator<String>，而不是 Iterator<&str> 或其他东西，所以使用它会给你 args 的所有权（它是否克隆了 args？神奇地支持它返回的字符串与单个 &'static str不知何故？不知道......）。不幸的是，这些风格上的改进并没有给我们带来太多额外的性能，之前的图表仍然很好地反映了代码的当前性能。在这一点上，Rust 代码基本上是 @phillipc 的，而不是我的。请参阅他的 fork 以获取其他一些类似版本的代码。

在这一点上，Rust 开发人员可能会拍拍自己的后背回家与家人共度美好时光，在内部庆祝他们头脑中的小胜利。 @bugaevc 提出了一个摆脱 BigUint 并使用 Vec<u8> 代替（完整差异）的实现。作为他实现的一个小例子，这里是 word_to_number 函数，它看起来仍然很整洁。事实证明，此更改使 Rust 可以更快地查看电话号码！以下是最终结果，包括改进的 Java 版本（以下称为 Java3），它使用了与改进的 Rust 代码几乎相同的性能改进： 请注意，此图表仅包含上一节中的最终 BigUInt 版本和新版本。I由您来考虑@bugaevc 的解决方案是否仍然可以与原始的 Common Lisp 相媲美，而我们也没有挤压 Common Lisp 可能必须提供的最后一点汁液。如您所见，如果您真的需要最后一毫秒的性能，Rust 可以为您提供！

Java 现在似乎已经远远落后了（至少它的性能比原来的、性能错误缠身的 Rust 实现要好得多）。作为奖励，我认为使用更大的字典是个好主意，因为随着解决方案的组合空间爆炸，这使得运行时变得非常困难！这可能会让 Java 至少部分地自我救赎，并展示它的 JIT 是否可以创造 Java 人（像我一样！）所说的奇迹，如果有足够的时间和有关热代码路径的信息。非常适合让我们的程序出汗。我编辑了 benchmarkconfig 以在额外运行中使用它。经过一些实验，事实证明这太过分了，因为即使找到几个电话号码也需要几分钟......所以我不得不调整设置直到程序运行了合理的时间，但不要太长（我解决了大约一分钟最快的实现）。使用非常少量的电话号码，但允许每个号码的最大长度为 50，导致运行之间的可变性变得极端，因为这些号码是在每次基准测试中随机生成的（如果特定运行碰巧包含几个长数字，找到所有解决方案需要很长时间）。我通过将电话号码的长度限制为较低的上限并增加电话号码的数量来对此进行调整，这使运行更加稳定，使基准测试可重现。

多次运行基准测试表明存在差异，但在语言之间的相对性能上没有差异。左边的组是第一次运行，右边是第二次运行（使用相同的设置）。我还使用@phillipc 的 BigInt 最终解决方案运行了最后一个基准测试，令人惊讶的是，它几乎与最终的 Rust 实现一样长（前者为 32.93 秒，后者为 32.42 秒）。谁认为 Rust 的 num crate 很慢？这些实现都对基准设置非常敏感：增加最大电话号码长度，例如，从 12 到 16，对运行时间有巨大影响（从大约 20 秒到几分钟）。然而，电话号码的数量似乎足够大，以至于每次我运行基准测试时，语言之间的相对性能差异大致相同。话虽如此，Java 似乎在任何至少需要 20 秒的运行中领先（使用用 ByteBuffer 替换 BigInt 的实现，就像 Rust 版本所做的那样，而不是 Trie！），并且在此之后它的领先优势不断增加。正如预测的那样，JIT 开始发挥作用，使 Java 超越了其他语言，即使是我的企业级代码也是如此。 Rust 的人推测，打印到标准输出可能会在某个时候成为瓶颈……以我们现在获得的解决方案的数量来看，这肯定是真的！

所以我采用了@bugaevc 的建议之一来缓冲对标准输出的写入。当然，我在 Java 中也做了同样的事情！不知何故，这现在已经成为一场严肃的 Java VS Rust 竞赛。在我看来，删除对标准输出的写入会使练习变得毫无意义，因为目标显然是能够向用户显示结果。此外， benchmark_runner 会丢弃进程的标准输出，因此不会因标准输出消费者阻塞太长时间而导致延迟，我认为这足以使基准测试结果在使用缓冲区时有效。运行最后一个基准测试表明，Rust 和 Java 现在都可以在十几秒左右的时间内运行！惊人的！！！这是否会使我当前的结果无效？好吧，不……重新运行所有的基准测试表明，除了最后一个结果，所有之前的运行仍然显示大致相同的东西（即标准输出直到现在还不是瓶颈），结果随着更大的输入变得越来越不平衡（不足以大幅改变结果）。在我缓冲标准输出写入后的第一次运行时，Rust 似乎再次变得比 Java 快得多。然而，由于打印输出变得更快，程序只运行了几秒钟，不足以让 JVM 优化掉一些东西。果然，再次增加输入大小以使程序运行至少一分钟（这是我耐心等待结果的时间）表明 JVM 最终赶上了。使用了两种语言的默认缓冲区大小。似乎都选择了 8 KB 缓冲区。我决定有必要看看这里是否有趋势，所以我不得不回到折线图，但更长的运行时间不是输入的数量，而是用作输入的单个电话号码的长度。通过这种方式，我们知道每个程序可以为一个电话号码找到所有解决方案的时间（解决方案的数量随着电话号码的长度增长非常快）。

这表明 Rust 启动得更快，正如预期的那样，并且 JVM 最终赶上了！我在电话长度为 29 时停了下来，因为每次运行已经超过了我每次运行 1 分钟的限制……但是正如你所看到的，最后还不清楚 Java 是否最终能够超过 Rust（从技术上讲，它是由一个最后两次运行的利润率非常小）！出于这个原因，我认为确实需要最后一次长度为 30 的运行来决定判决，即使这需要更长的时间：D！如果我们交换 Rust HashMap 实现，正如他们所说，我使用的标准实现应用了 JVM 没有的加密安全哈希？！我们是否还允许将 Java 的 HashMap 与这样或这样的更快的实现交换？如果我们只是扔掉解决方案而不是打印它们会怎样？如果我们将解决方案并行化怎么办？人们提出了各种各样的建议，但我必须在某处划清界限。

我可能会让一些人生气，因为我没有使用这个或那个库，但我在这里的武断路线是不允许将库添加到混合中，因为它使语言比较比现在更难，而且，说实话，我已经筋疲力尽了试图达成共识。用 Rust 编写代码并不意味着你的代码会很快。很容易犯错误并且性能很慢。正如这篇博文所显示的那样，您甚至可能需要出很多汗才能击败 Common Lisp 和 Java。这篇博文陷入了 Java 和 Rust 之间的一场疯狂竞赛，看看哪个能跑得更快……这不是我的本意，我只想展示如何修复我糟糕的 Rust 代码，但要知道性能足够好，我不得不使用其他语言进行比较，事情很快就陷入了一场毫无意义的竞赛来解决一个没人关心的问题，只是为了找出哪种语言是最快的。好消息是，最后，最受关注的语言 Java 和 Rust 的性能非常接近，以至于我认为语言选择并不像人们认为的那么重要的观点得到了显着加强，我认为。有时，无论您使用哪种语言或您的程序员有多聪明，您的代码都会运行得如此之快，以至于您甚至不会考虑其他语言而不是您熟悉的语言。其他时候，我几乎总是会说，你需要......