सी ++ पर हस्ताक्षर किए और अहस्ताक्षरित लंबे गति बनाम पूर्णांक

Question

आज, मैंने देखा है कि कई सरल बिटवाइज़ और अंकगणितीय आपरेशनों की गति मेरी 64-बिट पीसी पर int, unsigned, long long और unsigned long long के बीच काफी अलग है।

विशेष रूप से, unsigned के लिए long long के लिए निम्न लूप लगभग दोगुना है, जिसकी मुझे उम्मीद नहीं थी।

int k = 15; 
int N = 30; 
int mask = (1 << k) - 1; 
while (!(mask & 1 << N)) { 
    int lo = mask & ~(mask - 1); 
    int lz = (mask + lo) & ~mask; 
    mask |= lz; 
    mask &= ~(lz - 1); 
    mask |= (lz/lo/2) - 1; 
} 

(पूर्ण कोड here)

यहाँ समय (सेकंड में) कर रहे हैं (g++ -O, -O2 और -O3 के लिए):

1.834207723 (int) 
3.054731598 (long long) 
1.584846237 (unsigned) 
2.201142018 (unsigned long long) 

इस समय बहुत संगत (यानी 1% कर रहे हैं मार्जिन)। -O ध्वज के बिना, प्रत्येक एक लगभग धीमा है, लेकिन सापेक्ष गति समान हैं।

क्या इसके लिए कोई स्पष्ट कारण है? वेक्टरेशन 32-बिट प्रकारों के लिए हो सकता है, लेकिन मैं नहीं देख सकता कि long long और unsigned long long के बीच अंतर कहां से आता है। क्या कुछ ऑपरेशन दूसरों के मुकाबले कुछ प्रकारों पर बहुत धीमे हैं, या क्या यह सामान्य बात है कि 64-बिट प्रकार धीमे हैं (यहां तक ​​कि 64-बिट आर्किटेक्चर पर भी)?

रुचि रखने वालों के लिए, यह लूप {1,2,...,30} के सभी सबसेट्स पर बिल्कुल 15 तत्वों के साथ loops। यह 15 बिट्स सेट के साथ 1<<30 से कम सभी इंटीग्रियों पर लूपिंग (क्रम में) द्वारा किया जाता है। वर्तमान स्थिति के लिए, यह 155117520 पुनरावृत्तियों है। मुझे अब इस स्निपेट का स्रोत नहीं पता है, लेकिन this पोस्ट कुछ और बताता है।

संपादित

यह विधानसभा कोड है कि विभाजन तेजी से बनाया जा सकता है जब प्रकार अहस्ताक्षरित है से लगता है। मुझे लगता है कि यह समझ में आता है, क्योंकि हमें साइन बिट के लिए खाते नहीं हैं।

इसके अलावा, 32-बिट संचालन movl और अन्य xxxl निर्देश, का उपयोग करते हुए 64-बिट संचालन movq और xxxq का उपयोग करें।

संपादित 2

पोस्ट मैं जुड़ा हुआ पढ़ने के बाद, मैं सूत्र वहाँ पर दिया उपयोग करने का फैसला:

T k = 15; 
T N = 30; 
T mask = (1 << k) - 1; 
while (!(mask & 1 << N)) { 
    T t = mask | (mask - 1); 
    mask = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(mask) + 1)); 
} 

इस कोड को ऊपर पोस्ट के समय का लगभग एक तिहाई में चलाता है, और सभी चार प्रकार के लिए एक ही समय का उपयोग करता है।

Answer 1

अपने कोड में सबसे धीमी आपरेशन

mask |= (lz/lo/2) - 1 

32-बिट प्रभाग 64-बिट विभाजन की तुलना में काफी तेजी से होता है है। उदाहरण के लिए, आइवी ब्रिज पर, 32 बिट आईडीआईवी 1 9 -26 घड़ियों लेता है जबकि 64 बिट आईडीआईवी 28-103 घड़ियों विलंबता लेता है।

हस्ताक्षरित संस्करण हस्ताक्षरित से भी तेज है क्योंकि 2 से विभाजन बिना हस्ताक्षर किए मामले में सरल बिट शिफ्ट है और कोई आकार विस्तार कॉल (सीडीक्यू, सीक्यूओ) नहीं है।

अहस्ताक्षरित मामले में

सरल सा बदलाव रहते हुए किए है

[1] http://www.agner.org/optimize/instruction_tables.pdf