अजगर सेट चौराहे तेजी से तो जंग HashSet चौराहे है

Question

यहाँ मेरी अजगर कोड है:

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 

और यहाँ मेरी जंग कोड है:

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 के साथ इमारत एक ही परिणाम दे)।

मुझे लगता है कि अजगर के set सी में कार्यान्वित किया जाता है, और इतनी तेजी से होने की उम्मीद है, लेकिन मैं इसे जंग की तुलना में तेजी होने की उम्मीद नहीं थी। क्या अतिरिक्त प्रकार की जांच करना नहीं होगा कि जंग नहीं होगी?

शायद मैं अपने जंग कार्यक्रम को संकलित करने के तरीके में कुछ खो रहा हूं, क्या कोई अन्य अनुकूलन झंडे हैं जिनका उपयोग करना चाहिए?

एक और संभावना यह है कि कोड वास्तव में समकक्ष नहीं है, और जंग अनावश्यक अतिरिक्त काम कर रही है, क्या मुझे कुछ याद आ रहा है?

अजगर संस्करण:

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 संस्करण (मैं जानता हूँ कि 1.6 बाहर है)

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

मैं ubuntu 14.04 उपयोग कर रहा हूँ और मेरे प्रणाली वास्तुकला x86_64 है।

Answer 1

जब मैं लूप के सेट-बिल्डिंग को स्थानांतरित करता हूं और केवल छेड़छाड़ दोहराता हूं, दोनों मामलों के लिए, जंग पाइथन 2.7 से तेज है।

मैं केवल पायथन 3 (setobject.c) पढ़ने किया गया है, लेकिन अजगर के कार्यान्वयन इसके लिए जा रहा कुछ चीजें है।

यह इस तथ्य का उपयोग करता है कि दोनों पायथन सेट ऑब्जेक्ट्स एक ही हैश फ़ंक्शन का उपयोग करते हैं, इसलिए यह हैश को पुन: सम्मिलित नहीं करता है।जंग HashSet के पास उनके हैश फ़ंक्शंस के लिए इंस्टेंस-अनन्य कुंजी हैं, इसलिए छेड़छाड़ के दौरान उन्हें एक सेट से अन्य सेट के हैश फ़ंक्शन के साथ कुंजी को रीहाश करना होगा।

दूसरी तरफ, पाइथन को प्रत्येक मिलान हैश के लिए PyObject_RichCompareBool जैसे गतिशील कुंजी तुलना फ़ंक्शन को कॉल करना होगा, जबकि जंग कोड जेनेरिक का उपयोग करता है और i32 के लिए हैश फ़ंक्शन और तुलना कोड का विशेषज्ञ होगा। जंग में i32 हैशिंग के लिए कोड अपेक्षाकृत सस्ता दिखता है, और हैशिंग एल्गोरिदम का अधिकांश (4 बाइट्स से अधिक इनपुट को संभालने) को हटा दिया जाता है।

---

ऐसा प्रतीत होता है कि यह है कि सेट अजगर और जंग के अलावा सेट के निर्माण है। और वास्तव में केवल निर्माण नहीं, जंग HashSet एस को भी नष्ट करने के लिए कुछ महत्वपूर्ण कोड चल रहे हैं। (इसमें सुधार किया जा सकता है, यहां बग दायर किया गया: #31711)

Answer 2

प्रदर्शन समस्या HashMap और HashSet के डिफ़ॉल्ट हैशिंग कार्यान्वयन के लिए उबलती है। जंग का डिफ़ॉल्ट हैश एल्गोरिदम एक अच्छा सामान्य उद्देश्य है जो कुछ प्रकार के डॉस हमलों के खिलाफ भी रोकता है। हालांकि, यह बहुत छोटी या बहुत बड़ी मात्रा में डेटा के लिए बहुत अच्छा काम नहीं करता है।

कुछ प्रोफाइलिंग से पता चला कि 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); 
} 

, इस अजगर के 9.203s की तुलना में लेता है 2.714s।

यदि आप एक ही changes to move the set building out of the loop बनाते हैं, तो रूट कोड पायथन कोड के 3.0 9 3 की तुलना में 0.829 लेता है।