为什么 Python 设置交集比 Rust HashSet 交集更快？

Question

这是我的 Python 代码：

len_sums = 0
for i in xrange(100000):
    set_1 = set(xrange(1000))
    set_2 = set(xrange(500, 1500))
    intersection_len = len(set_1.intersection(set_2))
    len_sums += intersection_len
print len_sums

这是我的 Rust 代码：

use std::collections::HashSet;

fn main() {
    let mut len_sums = 0;
    for _ in 0..100000 {
        let set_1: HashSet<i32> = (0..1000).collect();
        let set_2: HashSet<i32> = (500..1500).collect();
        let intersection_len = set_1.intersection(&set_2).count();
        len_sums += intersection_len;
    }
    println!("{}", len_sums);
}

我相信这些大致相同。我得到以下性能结果：

time python set_performance.py
50000000

real    0m11.757s
user    0m11.736s
sys 0m0.012s

和

rustc set_performance.rs -O       
time ./set_performance 50000000

real    0m17.580s
user    0m17.533s
sys 0m0.032s

使用 cargo 和 --release 生成相同的结果。

我意识到Python的set是用C实现的，所以预计会很快，没想到比Rust还快。难道它不需要做 Rust 不需要的额外类型检查吗？

也许我在编译 Rust 程序的过程中遗漏了一些东西，是否还有其他我应该使用的优化标志？

另一种可能是代码并不完全等价，Rust 正在做不必要的额外工作，我是否遗漏了什么？

Python版本：

In [3]: import sys

In [4]: sys.version
Out[4]: '2.7.6 (default, Jun 22 2015, 17:58:13) \n[GCC 4.8.2]'

Rust 版本

$ rustc --version
rustc 1.5.0 (3d7cd77e4 2015-12-04)

我正在使用 Ubuntu 14.04，我的系统架构是 x86_64。

Answer 1

性能问题归结为 HashMap 和 HashSet 的默认哈希实现。 Rust 的默认哈希算法是一种很好的通用算法，它还可以防止某些类型的 DOS 攻击。但是，它不适用于非常小或非常大的数据量。

一些分析显示 make_hash<i32, std::collections::hash::map::RandomState> 占用了总运行时间的大约 41%。自 Rust 1.7, you can choose which hashing algorithm to use. Switching to the FNV hashing algorithm 起大大加快程序速度：

extern crate fnv;

use std::collections::HashSet;
use std::hash::BuildHasherDefault;
use fnv::FnvHasher;

fn main() {
    let mut len_sums = 0;
    for _ in 0..100000 {
        let set_1: HashSet<i32, BuildHasherDefault<FnvHasher>> = (0..1000).collect();
        let set_2: HashSet<i32, BuildHasherDefault<FnvHasher>> = (500..1500).collect();
        let intersection_len = set_1.intersection(&set_2).count();
        len_sums += intersection_len;
    }
    println!("{}", len_sums);
}

在我的机器上，与 Python 的 9.203 秒相比，这需要 2.714 秒。

如果你制作相同的，Rust 代码需要 0.829 秒，而 Python 代码需要 3.093 秒。

Answer 2

当我将集合构建移出循环并仅重复交集时，当然对于这两种情况，Rust 都比 Python 2.7.

快

我只读过 Python 3 (setobject.c)，但 Python 的实现有一些优点。

它利用了两个 Python 集合对象使用相同散列函数的事实，因此它不会重新计算散列。 Rust HashSets 的哈希函数具有实例唯一键，因此在交集期间，它们必须使用另一组的哈希函数重新哈希一组中的键。

另一方面，Python 必须为每个匹配的散列调出一个动态键比较函数，如 PyObject_RichCompareBool，而 Rust 代码使用泛型并将专门化散列函数和比较代码对于 i32。在 Rust 中散列 i32 的代码看起来相对便宜，并且删除了大部分散列算法（处理超过 4 个字节的输入）。

似乎是集合的构造将 Python 和 Rust 区分开来。事实上，不仅仅是构造，还有一些重要的代码运行也破坏了 Rust HashSet。（这可以改进，在此处提交错误：#31711）

Answer 3

抛开散列，Python 当你以错误的方式与一个微小的和一个巨大的集合相交时，Python 会超越以前的 Rust 版本。例如。这个 code on playground:

use std::collections::HashSet;
fn main() {
    let tiny: HashSet<i32> = HashSet::new();
    let huge: HashSet<i32> = (0..1_000).collect();
    for (left, right) in &[(&tiny, &huge), (&huge, &tiny)] {
        let sys_time = std::time::SystemTime::now();
        assert_eq!(left.intersection(right).count(), 0);
        let elapsed = sys_time.elapsed().unwrap();
        println!(
            "{:9}ns starting from {:4} element set",
            elapsed.subsec_nanos(),
            left.len(),
        );
    }
}

当运行使用 1.32 或更早版本的 Rust 而不是当前版本时，表明您真的想在两个集合中较小的一个集合上调用交集方法（即使在边界情况下，一个集为空）。通过调用此函数而不是交集方法，我获得了不错的性能提升：

fn smart_intersect<'a, T, S>(
    s1: &'a HashSet<T, S>,
    s2: &'a HashSet<T, S>,
) -> std::collections::hash_set::Intersection<'a, T, S>
where
    T: Eq + std::hash::Hash,
    S: std::hash::BuildHasher,
{
    if s1.len() < s2.len() {
        s1.intersection(s2)
    } else {
        s2.intersection(s1)
    }
}

Python中的方法平等对待这两个集合（至少在 3.7 版本中是这样）。

PS这是为什么呢？假设小集合 Sa 有 A 项，大集合 Sb 有 B 项，散列一个键花费 Th 时间，Tl(X) 时间在具有 X 元素的集合中定位散列键。那么：

Sa.intersection(&Sb) 成本 A * (Th + Tl(B))
Sb.intersection(&Sa) 成本 B * (Th + Tl(A))

假设散列函数很好并且桶很多（因为如果我们担心交集的性能，那么我们应该确保集合是有效的开始）然后 Tl(B) 应该打开与 Tl(A) 相提并论，或者至少 Tl(X) 应该比与集合大小的线性比例小得多。因此，决定操作成本的是 A 与 B。

PS is_disjoint 和 union 也存在同样的问题和解决方法（复制大集合并添加一些元素比复制大集合更便宜复制小集并添加很多，但不是很大）。 A pull request 被合并了，所以这个差异从 Rust 1.35 开始就消失了。

为什么 Python 设置交集比 Rust HashSet 交集更快？

Why is Python set intersection faster than Rust HashSet intersection?

python

hashset

rust