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

这是我的生锈代码：

^{pr2}$

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

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正在做不必要的额外工作，我是否遗漏了什么？在

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]'

锈版

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

我使用的是Ubuntu14.04，我的系统架构是x86_64。在

Answer 1

抛开散列不谈，当你以错误的方式相交于一个很小的集合和一个巨大的集合时，Python会超越之前版本的Rust。E、 g.这个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(),
        );
    }
}

当使用Rust的1.32或更早版本而不是当前版本运行时，会显示您确实希望对两个集合中较小的一个调用交集方法（即使在边界情况下，其中一个集是空的）。通过调用此函数而不是交叉方法，我获得了很好的性能提升：

^{pr2}$

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

这是为什么？ 假设小集Sa有A项，大集Sb有B项，散列一个键需要花费时间，Tl（X）时间在具有X个元素的集合中定位散列键。然后：

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

假设hash函数是好的，bucket足够多（因为如果我们担心交集的性能，那么我们应该确保集合在开始时是有效的），那么Tl（B）应该与Tl（A）相当，或者至少Tl（X）应该比集合大小的线性伸缩小得多。因此，决定操作成本的是A和B。在

PS同样的问题和解决方法存在于is_disjoint和{}也有一点（复制大集合并添加一些元素比复制小集合并添加大量元素要便宜，但不会很大）。A pull request被合并在一起，所以这种差异在Rust 1.35之后就消失了。在

Answer 2

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

一些分析显示，make_hash<i32, std::collections::hash::map::RandomState>占用了整个运行时的41%。从Rust 1.7开始，您可以选择使用哪种哈希算法。切换到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);
}

在我的机器上，这需要2.714s，而Python是9.203s

如果使用相同的changes to move the set building out of the loop，Rust代码需要0.829秒，而Python代码是3.093秒

Answer 3

当我将set building移出循环，只重复交集时，当然，对于这两种情况，Rust比python2.7快。在

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

它使用这样一个事实，即两个Python set对象使用相同的哈希函数，因此不重新计算哈希。RustHashSet的哈希函数有实例唯一的键，因此在交集期间，它们必须用另一个集的哈希函数重新散列键。在

另一方面，Python必须为每个匹配的散列调用一个动态键比较函数，比如PyObject_RichCompareBool，而Rust代码使用泛型并将i32的哈希函数和比较代码进行专门化。{4}的哈希算法比cd3}的哈希处理要便宜得多。在

---

似乎是集合的构造把Python和Rust分开了。事实上，不仅仅是构造，还有一些重要的代码在运行以破坏Rust HashSets。（这是可以改进的，在这里输入错误：#31711）