कंपाइलर एक गुणा में एक अनुमानित अतिरिक्त लूप को अनुकूलित क्यों नहीं कर सकता (या नहीं)?

Question

यह एक सवाल है जो Mysticial द्वारा शानदार जवाब पढ़ने के दौरान दिमाग में आया: why is it faster to process a sorted array than an unsorted array? शामिल प्रकार के लिए

प्रसंग:

const unsigned arraySize = 32768; 
int data[arraySize]; 
long long sum = 0; 

अपने जवाब में वे बताते हैं कि इंटेल संकलक (आईसीसी) का अनुकूलन इस:

for (int i = 0; i < 100000; ++i) 
    for (int c = 0; c < arraySize; ++c) 
     if (data[c] >= 128) 
      sum += data[c]; 

... इस के बराबर कुछ में:

for (int c = 0; c < arraySize; ++c) 
    if (data[c] >= 128) 
     for (int i = 0; i < 100000; ++i) 
      sum += data[c]; 

अनुकूलक यह स्वीकार कर रहा है कि ये समकक्ष हैं और इसलिएहै, आंतरिक लूप के बाहर शाखा को ले जा रहा है। बहुत चालाक!

लेकिन ऐसा क्यों नहीं करता?

for (int c = 0; c < arraySize; ++c) 
    if (data[c] >= 128) 
     sum += 100000 * data[c]; 

उम्मीद है कि मिस्टिक (या कोई और) समान रूप से शानदार जवाब दे सकता है। मैंने पहले कभी उस अन्य प्रश्न में चर्चा की गई अनुकूलन के बारे में कभी नहीं सीखा है, इसलिए मैं इसके लिए वास्तव में आभारी हूं।

Answer 1

संकलक आम तौर पर

for (int c = 0; c < arraySize; ++c) 
    if (data[c] >= 128) 
     sum += 100000 * data[c]; 

में

for (int c = 0; c < arraySize; ++c) 
    if (data[c] >= 128) 
     for (int i = 0; i < 100000; ++i) 
      sum += data[c]; 

नहीं बदल सकते हैं क्योंकि बाद हस्ताक्षर किए पूर्णांक अतिप्रवाह करने के लिए ले जा सकता है, जहां पूर्व नहीं करता है। यहां तक ​​कि हस्ताक्षरित दो के पूरक पूर्णांक के अतिप्रवाह के लिए गारंटीकृत लपेटने वाले व्यवहार के साथ, यह परिणाम बदल देगा (यदि data[c] 30000 है, तो उत्पाद सामान्य 32-बिट int एस के लिए -1294967296 बन जाएगा, जबकि 100000 बार 30000 से sum जोड़ना होगा अगर, यह ओवरफ्लो नहीं होता है, तो 3000000000 तक sum बढ़ाएं)। ध्यान दें कि एक ही अहस्ताक्षरित मात्रा के लिए रखती है, विभिन्न संख्या के साथ, 100000 * data[c] के अतिप्रवाह आम तौर पर एक कमी सापेक्ष 2^32 कि अंतिम परिणाम में प्रकट नहीं करना चाहिए परिचय होगा।

हालांकि यह

for (int c = 0; c < arraySize; ++c) 
    if (data[c] >= 128) 
     sum += 100000LL * data[c]; // resp. 100000ull 

में बदलने सकता है, अगर, हमेशा की तरह, long long पर्याप्त int से बड़ा है।

ऐसा क्यों नहीं करता है, मैं नहीं बता सकता, मुझे लगता है कि यह Mysticial said है, "जाहिर है, यह लूप-इंटरचेंज के बाद लूप-कॉलिंग पास नहीं चलाता है"।

ध्यान दें कि पाश-इंटरचेंज ही आम तौर पर मान्य (हस्ताक्षरित पूर्णांक के लिए) नहीं है,

for (int c = 0; c < arraySize; ++c) 
    if (condition(data[c])) 
     for (int i = 0; i < 100000; ++i) 
      sum += data[c]; 

के बाद से अतिप्रवाह को जन्म दे सकता है, जहां

for (int i = 0; i < 100000; ++i) 
    for (int c = 0; c < arraySize; ++c) 
     if (condition(data[c])) 
      sum += data[c]; 

नहीं होगा। के बाद से हालत सभी data[c] जोड़ा एक ही हस्ताक्षर कर रहे हैं कि यह सुनिश्चित करता है यह, कोषेर यहाँ है, इसलिए यदि एक अतिप्रवाह, दोनों करते हैं।

मुझे यह भी यकीन नहीं होगा कि संकलक ने इसे ध्यान में रखा है, हालांकि (@ माइस्टिसियल, क्या आप data[c] & 0x80 जैसी स्थिति के साथ प्रयास कर सकते हैं या तो यह सकारात्मक और नकारात्मक मूल्यों के लिए सच हो सकता है?)। मैं compilers अमान्य अनुकूलन कर दिया था (उदाहरण के लिए, कुछ साल पहले, मैंने एक आईसीसी (11.0 था, iirc) का उपयोग प्रवेश किए गए 32-बिट-पूर्णांक करने वाली डबल 1.0/n जहां n एक unsigned int था में रूपांतरण। दो बार था के बारे में के रूप में जीसीसी के आउटपुट के रूप में तेज़। लेकिन गलत, 2^31, ओओएस से बहुत सारे मूल्य बड़े थे।)।

Answer 2

कंपाइलर में विभिन्न पास होते हैं जो अनुकूलन करते हैं। आम तौर पर प्रत्येक पास में या तो कथन या लूप अनुकूलन पर अनुकूलन किया जाता है। वर्तमान में कोई मॉडल नहीं है जो लूप हेडर पर आधारित लूप बॉडी का अनुकूलन करता है। यह पता लगाना मुश्किल है और कम आम है।

ऑप्टिमाइज़ेशन जो किया गया था लूप इनवेरिएंट कोड गति था। यह तकनीकों के एक सेट का उपयोग करके किया जा सकता है।

Answer 3

ठीक है, मुझे लगता है कि कुछ कंपाइलर इस तरह के अनुकूलन कर सकते हैं, यह मानते हुए कि हम पूर्णांक अंकगणित के बारे में बात कर रहे हैं।

उसी समय, कुछ कंपाइलर ऐसा करने से इंकार कर सकते हैं क्योंकि गुणा के साथ दोहराव वाले जोड़ को प्रतिस्थापित करने से कोड के अतिप्रवाह व्यवहार में परिवर्तन हो सकता है। unsigned अभिन्न प्रकारों के लिए इसे कोई फर्क नहीं पड़ता है, क्योंकि उनके अतिप्रवाह व्यवहार पूरी तरह से भाषा द्वारा निर्दिष्ट किए जाते हैं। लेकिन हस्ताक्षरित लोगों के लिए यह शायद (शायद 2 के पूरक मंच पर नहीं) हो सकता है। यह सच है कि हस्ताक्षरित अतिप्रवाह वास्तव में सी में अपरिभाषित व्यवहार की ओर जाता है, जिसका अर्थ यह है कि अतिप्रवाह अर्थशास्त्र को पूरी तरह से अनदेखा करना बिल्कुल ठीक होना चाहिए, बिट नहीं सभी कंपेलर ऐसा करने के लिए बहादुर हैं। यह अक्सर "सी एक उच्च स्तरीय असेंबली भाषा" भीड़ से बहुत आलोचना खींचती है। (याद रखें कि क्या हुआ जब जीसीसी सख्त अलियासिंग अर्थ विज्ञान के आधार पर शुरू की अनुकूलन?)

ऐतिहासिक रूप से, जीसीसी एक संकलक कि क्या यह इस तरह कठोर कदम उठाने के लिए लेता के रूप में दिखाया गया है, लेकिन अन्य compilers कथित साथ रहना पसंद कर सकते हैं "उपयोगकर्ता द्वारा लक्षित" व्यवहार भले ही यह भाषा द्वारा अपरिभाषित है।

Answer 4

इस उत्तर से जुड़ा हुआ विशेष मामले पर लागू नहीं होता है, लेकिन यह सवाल शीर्षक पर लागू होता है, और भविष्य के पाठकों के लिए दिलचस्प हो सकता है:

कारण परिमित परिशुद्धता के लिए बार-बार फ्लोटिंग प्वाइंट इसके बराबर नहीं है गुणा करने के लिए।पर विचार करें:

float const step = 1e-15; 
float const init = 1; 
long int const count = 1000000000; 

float result1 = init; 
for(int i = 0; i < count; ++i) result1 += step; 

float result2 = init; 
result2 += step * count; 

cout << (result1 - result2); 

डेमो: http://ideone.com/7RhfP

Answer 5

वहाँ अनुकूलन के इस प्रकार के लिए एक वैचारिक बाधा है। उदाहरण के लिए कहते हैं और बदलाव के साथ गुणा की जगह - संकलक लेखकों strength reduction पर प्रयास के एक बहुत खर्च करते हैं। वे सोचने के लिए उपयोग करते हैं कि गुणा खराब है। तो एक मामला जहां किसी को दूसरी तरफ जाना चाहिए आश्चर्यजनक और counterintuitive है। तो कोई भी इसे लागू करने के लिए सोचता है।

Answer 6

लोग हैं, जो विकसित करने और बनाए रखने के compilers समय और ऊर्जा का एक सीमित मात्रा में अपने काम पर खर्च करने के लिए है, तो वे आम तौर पर उनके उन सबसे के बारे में क्या चीज़ पर ध्यान केंद्रित करना चाहते हैं: तेजी से कोड में अच्छी तरह से लिखा मोड़ कोड। वे मूर्ख कोड को तेज़ कोड में बदलने के तरीके खोजने के लिए अपना समय बिताना नहीं चाहते हैं- यही कोड समीक्षा है।एक उच्च स्तरीय भाषा में, "मूर्ख" कोड हो सकता है जो एक महत्वपूर्ण विचार व्यक्त करता है, जिससे इसे तेजी से बनाने के लिए डेवलपर्स के समय के लायक हो जाते हैं - उदाहरण के लिए, शॉर्ट कट वनों की कटाई और धारा संलयन कुछ प्रकार के आलसी के आसपास बनाए गए हास्केल कार्यक्रमों को अनुमति देता है उत्पादित डेटा संरचनाओं को तंग लूप में संकलित करने के लिए जो स्मृति आवंटित नहीं करते हैं। लेकिन उस तरह का प्रोत्साहन बस गुणा में लूप के अलावा मोड़ने के लिए लागू नहीं होता है। यदि आप इसे तेज करना चाहते हैं, तो इसे गुणा के साथ लिखें।