2010-11-23 10 views
12

क्या आपको लगता है कि फ़ंक्शन हैडॉन में ऑप्टिमाइज़ेशन के लिए जगह है (नीचे देखें)?बिट-ऑपरेशंस का पालन करने के लिए अनुकूलन का मौका?

मैं ने स्वीकार किया कि __int64unsigned __int64 करने से तर्क प्रकार बदलने के लिए तेजी से समारोह बना दिया है, इस प्रकार मैं thougt शायद वहाँ अभी भी अनुकूलन के लिए एक मौका है।

अधिक जानकारी में: मैं connect four गेम लिख रहा हूं। हाल ही में मैंने प्रोफाइलर बहुत नींद का उपयोग किया और यह पहचाना कि हैडॉन अधिकांश सीपीयू-टाइम का उपयोग करता है। फ़ंक्शन एक प्लेयर के लिए कनेक्ट-चार-बोर्ड के बिटबोर्ड-प्रतिनिधित्व का उपयोग करता है। यह कार्य स्वयं ही fourstones बेंचमार्क के स्रोतों में पाया गया। bitboard प्रतिनिधित्व पीछा कर रहा है:

. . . . . . . TOP 
5 12 19 26 33 40 47 
4 11 18 25 32 39 46 
3 10 17 24 31 38 45 
2 9 16 23 30 37 44 
1 8 15 22 29 36 43 
0 7 14 21 28 35 42 BOTTOM 

समारोह:

// return whether newboard includes a win 
bool haswon(unsigned __int64 newboard) 
{ 
    unsigned __int64 y = newboard & (newboard >> 6); 
    if (y & (y >> 2 * 6)) // check \ diagonal 
     return true; 
    y = newboard & (newboard >> 7); 
    if (y & (y >> 2 * 7)) // check horizontal - 
     return true; 
    y = newboard & (newboard >> 8); 
    if (y & (y >> 2 * 8)) // check/diagonal 
     return true; 
    y = newboard & (newboard >> 1); 
    if (y & (y >> 2))  // check vertical | 
     return true; 
    return false; 
} 

धन्यवाद!

संपादित करें: सीपीयू x86, 32 बिट आर्किटेक्चर है, मैं विजुअल स्टूडियो 2008 एक्सप्रेस संस्करण से कंपाइलर का उपयोग कर रहा हूं। अनुकूलन झंडे/ओ 2/ओई/जीएल हैं।

मैंने फ़ंक्शन हैसन 2 की कोशिश की जो बेन जैक्सन ने सुझाव दिया। माइक्रोसॉफ्ट कंपाइलर की असेंबली, रिलीज संस्करणों (/ ओ 2/ओई/जीएल) के लिए डिफ़ॉल्ट अनुकूलन झंडे के साथ, लगभग कोई रनटाइम अंतर नहीं दिखाती है। ऐसा लगता है कि जीसीसी की तुलना में वीसी-कंपाइलर लाभ नहीं ले सकता है कि इसे सख्त क्रम में प्रत्येक शर्त का मूल्यांकन नहीं करना चाहिए।

परिणाम: haswon मूल: haswon

बेन जैक्सन से haswon2: haswon2

EDIT2: haswon की विधानसभा:

00401A10 mov   eax,dword ptr [esp+4] 
00401A14 mov   ecx,dword ptr [esp+8] 
00401A18 push  ebx 
00401A19 push  esi 
00401A1A push  edi 
00401A1B mov   edx,eax 
00401A1D mov   edi,ecx 
00401A1F shrd  edx,edi,6 
00401A23 mov   esi,edx 
00401A25 shr   edi,6 
00401A28 and   esi,eax 
00401A2A and   edi,ecx 
00401A2C mov   edx,esi 
00401A2E mov   ebx,edi 
00401A30 shrd  edx,ebx,0Ch 
00401A34 shr   ebx,0Ch 
00401A37 and   edx,esi 
00401A39 and   ebx,edi 
00401A3B or   edx,ebx 
00401A3D je   `anonymous namespace'::haswon+35h (401A45h) 
00401A3F mov   al,1 
00401A41 pop   edi 
00401A42 pop   esi 
00401A43 pop   ebx 
00401A44 ret    
00401A45 mov   edx,eax 
00401A47 mov   edi,ecx 
00401A49 shrd  edx,edi,7 
00401A4D mov   esi,edx 
00401A4F shr   edi,7 
00401A52 and   esi,eax 
00401A54 and   edi,ecx 
00401A56 mov   edx,esi 
00401A58 mov   ebx,edi 
00401A5A shrd  edx,ebx,0Eh 
00401A5E shr   ebx,0Eh 
00401A61 and   edx,esi 
00401A63 and   ebx,edi 
00401A65 or   edx,ebx 
00401A67 jne   `anonymous namespace'::haswon+2Fh (401A3Fh) 
00401A69 mov   edx,eax 
00401A6B mov   edi,ecx 
00401A6D shrd  edx,edi,8 
00401A71 mov   esi,edx 
00401A73 shr   edi,8 
00401A76 and   esi,eax 
00401A78 and   edi,ecx 
00401A7A mov   edx,esi 
00401A7C mov   ebx,edi 
00401A7E shrd  edx,ebx,10h 
00401A82 shr   ebx,10h 
00401A85 and   edx,esi 
00401A87 and   ebx,edi 
00401A89 or   edx,ebx 
00401A8B jne   `anonymous namespace'::haswon+2Fh (401A3Fh) 
00401A8D mov   edx,eax 
00401A8F mov   esi,ecx 
00401A91 shrd  edx,esi,1 
00401A95 shr   esi,1 
00401A97 and   esi,ecx 
00401A99 and   edx,eax 
00401A9B mov   eax,edx 
00401A9D mov   ecx,esi 
00401A9F shrd  eax,ecx,2 
00401AA3 shr   ecx,2 
00401AA6 and   eax,edx 
00401AA8 and   ecx,esi 
00401AAA or   eax,ecx 
00401AAC jne   `anonymous namespace'::haswon+2Fh (401A3Fh) 
00401AAE pop   edi 
00401AAF pop   esi 
00401AB0 xor   al,al 
00401AB2 pop   ebx 
00401AB3 ret  
+3

निश्चित रूप से यह फ़ंक्शन प्रति चाल एक बार चलता है? अगर यह 1 माइक्रोसॉन्ड या 1 मिलीसेकंड लेता है तो इससे कोई फर्क क्यों पड़ता है? –

+0

यह लगभग निश्चित रूप से अनुकूलन की आवश्यकता नहीं है। – Paul

+4

फ़ंक्शन को अल्फा-बीटा गेम-पेड़ खोज के भीतर दो अन्य कार्यों द्वारा बुलाया जाता है। अन्य कार्य 'getMoves' हैं जो जीत या ज़ुगज़वांग के लिए परीक्षण करते हैं, और 'मूल्यांकन' करते हैं जो परीक्षण करते हैं कि बोर्ड में जीत शामिल है या नहीं। समारोह वास्तव में अक्सर कहा जाता है। –

उत्तर

17

इस संस्करण के पीछे विचार str से बचने के लिए है आईसीटी परीक्षण आदेश (मध्यवर्ती रिटर्न, संकलक एक समय में स्थिति एक मूल्यांकन करने के लिए मजबूर क्रम में) और साथ ही शाखाओं में कई के साथ जुड़े यदि बयान:

// return whether newboard includes a win 
bool haswon2(uint64_t newboard) 
{ 
    uint64_t y = newboard & (newboard >> 6); 
    uint64_t z = newboard & (newboard >> 7); 
    uint64_t w = newboard & (newboard >> 8); 
    uint64_t x = newboard & (newboard >> 1); 
    return (y & (y >> 2 * 6)) | // check \ diagonal 
      (z & (z >> 2 * 7)) | // check horizontal - 
      (w & (w >> 2 * 8)) | // check/diagonal 
      (x & (x >> 2));  // check vertical | 
} 

क्या तुम सच में लगता है कि कर सकते हैं अनुकूलन के एक सभ्य स्तर के साथ स्थानांतरित मूल्यों के लिए डब्ल्यू, एक्स, वाई और जेड के "उपनाम" के रूप में। इसका मतलब है कि अंतिम रिटर्न स्टेटमेंट पूरे ऑपरेशन को कंपाइलर के साथ खेलने के लिए एक बड़े सूप में फेंकता है। मेरे सिस्टम पर यह संस्करण मूल के रनटाइम का केवल 65% लेता है (प्रत्येक बार एक यादृच्छिक स्थिति उत्पन्न करने के ऊपरी भाग सहित)। यदि बोर्ड मुख्य रूप से गैर-विजेता हैं तो यह एक बड़े प्रतिशत से जीत सकता है।

प्रत्येक के disassembly (gcc -O3 से) को देखते हुए मूल संस्करण, वास्तव में कम है इसलिए संभव है कि तंग भीतरी पाश है कि वास्तव में मदद करता है में शाखाओं की कमी है।

+0

मुझे इसे मारो, +1 :) –

+0

क्या कोई कारण है कि संकलक मूल अनुकूलन से इन अनुकूलन को निष्पादित नहीं कर सका? मुझे वास्तव में कोई कारण नहीं दिख रहा है (कोई पॉइंटर्स या एलियासिंग समस्याएं नहीं हैं, कोई सर लुकअप या साइड इफेक्ट्स नहीं हैं जो इस तरह के कोड रीडरिंग को प्रतिबंधित कर सकती हैं। तो क्या यह सिर्फ जीसीसी के कंपाइलर का पर्याप्त मामला नहीं है, या कुछ है मूल कोड के पहलू का अर्थ है कि यह * स्वचालित रूप से आपके जैसे कोड में परिवर्तित नहीं किया जा सकता है? – jalf

+0

यदि संकलक देख सकता है कि पहली स्थिति से परे कोई साइड इफेक्ट नहीं था और सभी स्थितियां एक ही परिणाम में विलय हो गईं (वास्तव में यह उस भाग को समझता है) ऐसा लगता है जैसे यह हो सकता है। शायद हाल ही में 'क्लैंग' इंस्टॉल वाला कोई व्यक्ति उस कंपाइलर को आजमा सकता है? –

संबंधित मुद्दे