之前还在读研的时候有一个图论课，课上主要用 Python 写图算法。
但是数据集一大 Python 的性能你们懂的，到后面测试一次就要一分多钟。
有点受不了就用 C# 和 Rust 各写了一个，理清算法之后再照搬到 Python 。
当时最大的数据集下，一样的算法一样的机器，用 hyperfine 测试启动到结束的时间，性能大概是这样的
- Python 3.11: 30s
- C# (.NET7 AOT): 1.5s
- Rust: 750ms
毕业之后这段代码就搁我电脑里没怎么动过，但是每年 .NET 版本更新我都会拿出来再跑一下看看性能，去年 .NET 8 更新之后 C# 版本的运行时间降低到了 1s ，Rust 没什么变化。
今年 .NET 9 更新了我就又拿出来跑了一下，Rust 没变，C# 版时间降低到了 660ms ，超越了 Rust ，让我非常不解，按理说一个带运行时的 GC 语言无论如何性能都不会比跑在裸机上的 Rust 快。
问了几个群友，有人说 Rust 的默认 HashMap 性能不行，但是换 ahash 之后也没什么变化。
代码在这里： https://gist.github.com/Xerxes-2/4c73294601dca27d3d6dc7eeecc78ba1
请问 Rust 版哪里写的有问题还能优化吗
但是数据集一大 Python 的性能你们懂的，到后面测试一次就要一分多钟。
有点受不了就用 C# 和 Rust 各写了一个，理清算法之后再照搬到 Python 。
当时最大的数据集下，一样的算法一样的机器，用 hyperfine 测试启动到结束的时间，性能大概是这样的
- Python 3.11: 30s
- C# (.NET7 AOT): 1.5s
- Rust: 750ms
毕业之后这段代码就搁我电脑里没怎么动过，但是每年 .NET 版本更新我都会拿出来再跑一下看看性能，去年 .NET 8 更新之后 C# 版本的运行时间降低到了 1s ，Rust 没什么变化。
今年 .NET 9 更新了我就又拿出来跑了一下，Rust 没变，C# 版时间降低到了 660ms ，超越了 Rust ，让我非常不解，按理说一个带运行时的 GC 语言无论如何性能都不会比跑在裸机上的 Rust 快。
问了几个群友，有人说 Rust 的默认 HashMap 性能不行，但是换 ahash 之后也没什么变化。
代码在这里： https://gist.github.com/Xerxes-2/4c73294601dca27d3d6dc7eeecc78ba1
请问 Rust 版哪里写的有问题还能优化吗
第 1 条附言 · 19 天前
测试数据集： https://drive.google.com/file/d/1UbvxrefGh4L1qiHiMpQiLiwtb5VYWn-3/view?usp=drive_link
依次传入 graph 和 answer 即可
依次传入 graph 和 answer 即可
13 条回复 • 2024-12-04 05:41:46 +08:00
 |
1
oksbsb 19 天前
1. 没给测试数据集
2. 里面大量的内存分配，换 mimalloc 之类的库 |
 |
3
Xerxes2 OP @oksbsb 测试数据上传了
用 mimalloc 试了一下，没有变化 但是给 .NET AOT 开了<OptimizationPreference>Speed</OptimizationPreference>之后时间直接下降到了 610ms |
|
4
oksbsb 19 天前
热点函数是 shr 函数，使用 FxHashMap 我本机时间可以 590-600ms
use rustc_hash::FxHashMap as HashMap; |
|
6
oksbsb 19 天前
刚刚的结果是 opt-level = "s" 的结果，使用 opt-level = 2 或者 3.
结果在 440ms 左右 |
|
7
oksbsb 19 天前
没安装 dotnet9 。但使用 rust 默认的 std::collections::HashMap 耗时在 990ms 左右
|
|
9
Xerxes2 OP 发现 Rust 实现有一段没给节点更新信息导致重复计算，加上之后 280ms 了
|
 |
10
Donaldo 19 天前
换成 fxhash 会更快，ahash 在我的机器上是 600ms ，fxhash 对于 kv 是 u32 和 u64 表现更好，能到 300 多。
|
|
13
Xerxes2 OP 修复了，用时也降低到 370ms
|
Select Language