Python insieme intersezione è più veloce quindi Rust HashSet intersezione

Question

Ecco il mio codice 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 

E qui è il mio codice 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); 
} 

Credo che queste siano o meno equivalente. Ottengo i seguenti risultati di performance:

time python set_performance.py 
50000000 

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

e

rustc set_performance.rs -O  
time ./set_performance 50000000 

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

(costruzione con cargo e --release dare lo stesso risultato).

Mi rendo conto che Python set è implementato in C, e quindi dovrebbe essere veloce, ma non mi aspettavo che fosse più veloce di Rust. Non dovrebbe fare controlli di tipo extra che Rust non dovrebbe?

Forse mi manca qualcosa nel modo in cui compilo il mio programma Rust, ci sono altri flag di ottimizzazione che dovrei usare?

Un'altra possibilità è che il codice non è realmente equivalente, e Rust sta facendo inutili lavori extra, mi manca qualcosa?

Python Versione:

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 versione (lo so 1.6 è fuori)

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

Sto usando ubuntu 14.04 e la mia architettura del sistema è x86_64.

Answer 1

Quando sposto il set-building dal loop e ripeto solo l'intersezione, per entrambi i casi, ovviamente, Rust è più veloce di Python 2.7.

Ho letto solo Python 3 (setobject.c), ma l'implementazione di Python ha alcune cose da fare.

Utilizza il fatto che entrambi gli oggetti set Python utilizzano la stessa funzione di hash, quindi non ricalcola l'hash.Rust HashSet s hanno chiavi di istanza-univoche per le loro funzioni di hash, quindi durante l'intersezione devono rehash chiavi da un set con la funzione hash dell'altro set.

D'altra parte, Python deve chiamare una funzione di confronto delle chiavi dinamiche come PyObject_RichCompareBool per ogni hash di corrispondenza, mentre il codice Rust utilizza i generici e specializzerà la funzione di hash e il codice di confronto per i32. Il codice per l'hashing dello i32 in Rust sembra relativamente economico e gran parte dell'algoritmo di hash (gestione di input più lunghi di 4 byte) viene rimosso.

---

E sembra che sia la costruzione dei set che set Python e la ruggine a parte. E infatti non solo la costruzione, c'è un codice significativo in esecuzione per distruggere anche i Rust HashSet s. (Questo può essere migliorato, archiviato bug qui: #31711)

Answer 2

Il problema di prestazioni si riduce all'implementazione di hashing predefinita di HashMap e HashSet. L'algoritmo di hash predefinito di Rust è un buon programma generico che impedisce anche alcuni tipi di attacchi DOS. Tuttavia, non funziona bene per quantità molto piccole o molto grandi di dati.

Alcuni profili hanno mostrato che make_hash<i32, std::collections::hash::map::RandomState> occupava circa il 41% del tempo di esecuzione totale. A partire da Rust 1.7, è possibile scegliere quale algoritmo di hashing utilizzare. Passaggio alle FNV hashing algorithm accelera notevolmente il programma:

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

Sulla mia macchina, questo prende 2.714s rispetto a Python di 9.203s.

Se si effettua lo stesso changes to move the set building out of the loop, il codice Rust accetta 0,829 rispetto ai 3.093 del codice Python.