为什么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。

- Akavall

---

当我将建立集合的过程移出循环，只重复交集操作时，对于两种情况而言，Rust 的速度比 python2.7 更快。因此，问题略有偏差。 - bluss

@bluss 说得好，我的电脑上 rust 只比它慢了一点点，0m4.168s 对比 0m3.838s。而且初始化也花费了不少时间。再次感谢。 - Akavall

@bluss 但是如果我在PyPy3上使用set1 & set2，我得到的时间是1.0秒对比2.3秒，所以Python又重新领先了；P - Veedrac

Answer 1

当我将构建集合的操作从循环中移出，只重复交集操作时，在两个语言的情况下，Rust 比 Python 2.7 更快。

我只阅读了 Python 3 的 setobject.c，但是 Python 的实现有一些优点。

Python 利用了 Python 集合对象都使用相同哈希函数的事实，因此不会重新计算哈希。Rust 的 HashSet 对象具有唯一的实例密钥，因此在计算交集时必须使用另一个集合的哈希函数对密钥进行重新哈希。

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

---

看起来正是构建集合的操作使得 Python 和 Rust 有所不同。实际上，不仅是构建，还有一些显著的代码运行用于销毁 Rust 的 HashSet。 （这可以改进，在此处报告错误：#31711）

- bluss

---

Rust的HashSet具有实例唯一的键（key）用于其哈希函数，因此在交集期间，必须使用另一个集合的哈希函数重新哈希一个集合的键。这能被优化吗？我想可能会在BuilderHashDefault上添加一个方法或仅比较两个HashSet/HashMap实例之间的构建器（builder）来优化哈希再计算的情况。这样，你可以在需要执行交集/并集/...操作的集合上使用相同的构建器或等效构建器。 - Matthieu M.

由于元素需要并且会被重新哈希（它们被提供给另一组中的 contains_key 函数），为什么该方法要求两个集合都使用相同类型的哈希函数，即为什么只有一个通用类型参数 S: BuildHasher + Default？ - Stein

Answer 2

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

一些分析显示，make_hash<i32, std::collections::hash::map::RandomState>占据了总运行时间的约41%。从Rust 1.7开始，您可以选择使用哪个哈希算法。切换到FNV哈希算法可以显著加快程序速度：

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);
}

在我的机器上，这个操作只需要2.714秒，而Python则需要9.203秒。

如果您对代码进行相同的更改以将set构建移出循环，那么Rust代码只需要0.829秒，而Python代码则需要3.093秒。

- Shepmaster

Answer 3

除了哈希之外，当你以错误的方式交错一个小集合和一个巨大的集合时，Python比Rust的早期版本更快。例如，这个代码片段：

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时间，在具有X个元素的集合中定位一个哈希键需要Tl(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也存在同样的问题和解决方法（复制大集合并添加几个元素要比复制小集合并添加很多元素便宜，但不是非常便宜）。自Rust 1.35以来，已合并一个拉取请求，因此这种差异已经消失。

- Stein

---

你可以试试是否可以提交一个标准库的 PR 来实现这个。似乎对于每个人来说，这都是一个足够安全的更改。 - Shepmaster

也许有人会反对为那些事先知道左集合较小甚至更糟的人收费，因为他们知道由于缓慢的哈希函数或其他原因需要左集合存在？无论如何，至少应该记录下来，但现在它没有被记录（我所查看的地方）。 - Stein

经过仔细检查代码（https://github.com/rust-lang/rust/tree/master/src/libstd/collections/hash/set.rs），似乎并没有太多的思考，因此尝试提供修复方法以及错误报告。 - Stein

顺便提一下，Scala中的默认Set也有相同的性能问题：需要先放置小集合。 - Stein