Why is Python set intersection faster than Rust HashSet intersection?

Question

Here is my Python code:

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 

Here is my Rust code:

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

I believe these are roughly equivalent. I get the following performance results:

time python set_performance.py 50000000  real    0m11.757s user    0m11.736s sys 0m0.012s 

and

rustc set_performance.rs -O        time ./set_performance 50000000  real    0m17.580s user    0m17.533s sys 0m0.032s 

Building with cargo and --release give the same result.

I realize that Python's set is implemented in C, and so is expected to be fast, but I did not expect it to be faster than Rust. Wouldn't it have to do extra type checking that Rust would not?

Perhaps I'm missing something in the way I compile my Rust program, are there any other optimizations flags that I should be using?

Another possibility is that the code is not really equivalent, and Rust is doing unnecessary extra work, am I missing anything?

Python version:

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 version

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

I am using Ubuntu 14.04 and my system architecture is x86_64.

Answer 1

When I move the set-building out of the loop and only repeat the intersection, for both cases of course, Rust is faster than Python 2.7.

I've only been reading Python 3 (setobject.c), but Python's implementation has some things going for it.

It uses the fact that both Python set objects use the same hash function, so it does not recompute the hash. Rust HashSets have instance-unique keys for their hash functions, so during intersection they must rehash keys from one set with the other set's hash function.

On the other hand, Python must call out to a dynamic key comparison function like PyObject_RichCompareBool for each matching hash, while the Rust code uses generics and will specialize the hash function and comparison code for i32. The code for hashing an i32 in Rust looks relatively cheap, and much of the hashing algorithm (handling longer input than 4 bytes) is removed.

---

It appears it's the construction of the sets that sets Python and Rust apart. And in fact not just construction, there's some significant code running to destruct the Rust HashSets as well. (This can be improved, filed bug here: #31711)