请问我这段 2-hop 算法的 Rust 实现还能怎么优化

[Xerxes2]

之前还在读研的时候有一个图论课，课上主要用 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 版哪里写的有问题还能优化吗

[oksbsb]

1. 没给测试数据集
2. 里面大量的内存分配，换 mimalloc 之类的库

[Xerxes2]

@oksbsb 1. 现在在下班路上，等会回家给
2. 等会我试试

[Xerxes2]

@oksbsb 测试数据上传了
用 mimalloc 试了一下，没有变化
但是给 .NET AOT 开了<OptimizationPreference>Speed</OptimizationPreference>之后时间直接下降到了 610ms

[oksbsb]

热点函数是 shr 函数，使用 FxHashMap 我本机时间可以 590-600ms

use rustc_hash::FxHashMap as HashMap;

[Xerxes2]

@oksbsb 您机器上 dotnet 9 的时间呢？

[oksbsb]

刚刚的结果是 opt-level = "s" 的结果，使用 opt-level = 2 或者 3.
结果在 440ms 左右

[oksbsb]

没安装 dotnet9 。但使用 rust 默认的 std::collections::HashMap 耗时在 990ms 左右

[Xerxes2]

@oksbsb 我换了 rustc_hash 之后和你几乎一样

[Xerxes2]

发现 Rust 实现有一段没给节点更新信息导致重复计算，加上之后 280ms 了

[Donaldo]

换成 fxhash 会更快，ahash 在我的机器上是 600ms ，fxhash 对于 kv 是 u32 和 u64 表现更好，能到 300 多。

[oksbsb]

@Xerxes2 加上后结果不太一致。

11233 != 11369

[Xerxes2]

@oksbsb 有点奇怪，C#上写法是差不多的，结果是对的

[Xerxes2]

修复了，用时也降低到 370ms