फर्श पर कॉल से बचें()

Question

मैं कोड के एक टुकड़े पर काम कर रहा हूं जहां मुझे यूवीएस (2 डी बनावट निर्देशांक) से निपटने की ज़रूरत है जो 0 से 1 रेंज में जरूरी नहीं हैं। एक उदाहरण के रूप में, कभी-कभी मुझे एक यूवी घटक मिल जाएगा जो 1.2 है।

u -= floor(u) 
v -= floor(v) 

इस का कारण बनता है 1.2 0.2 जो वांछित परिणाम है बनने के लिए करना: इस संभाल करने में मैं एक रैपिंग जो निम्न कार्य करके खपरैल का कारण बनता है को लागू करने कर रहा हूँ। यह नकारात्मक मामलों को भी संभालता है, जैसे -0.4 0.6 बन रहा है।

हालांकि, फर्श पर ये कॉल धीमी हैं। मैंने इंटेल वीट्यून का उपयोग करके अपना आवेदन प्रोफाइल किया है और मैं सिर्फ इस मंजिल के संचालन के दौरान चक्रों की एक बड़ी मात्रा खर्च कर रहा हूं।

इस मुद्दे पर कुछ पृष्ठभूमि पढ़ने के बाद, मैं निम्नलिखित कार्य के साथ आया हूं जो थोड़ा तेज़ है लेकिन अभी भी वांछित होने के लिए बहुत कुछ छोड़ देता है (मैं अभी भी प्रकार के रूपांतरण दंड इत्यादि कर रहा हूं)।

int inline fasterfloor(const float x) { return x > 0 ? (int) x : (int) x - 1; } 

मैं कुछ गुर कि इनलाइन विधानसभा लेकिन कुछ भी बिल्कुल सही काम करते हैं या किसी भी महत्वपूर्ण गति सुधार करने के लिए लगता है कि के साथ पूरा किया जाता है देखा है।

क्या किसी को इस तरह के परिदृश्य को संभालने के लिए कोई चाल पता है?

Answer 1

आपके यू, वी मूल्यों की अधिकतम इनपुट सीमा क्या है? यदि यह काफी छोटी सीमा है, उदा। -5.0 से +5.0 तक, फिर फर्श जैसे महंगा कार्यों को कॉल करने के बजाय, जब तक आप रेंज के भीतर नहीं पहुंच जाते, तब तक बार-बार 1.0 को जोड़ना/घटा देना तेज होगा।

Answer 2

यदि मानों की संख्या पर्याप्त हो सकती है, तो शायद आप फर्श मान को बाइनरी-खोज कर सकते हैं। उदाहरण के लिए, मान -2 < = एक्स < 2 हो सकता है यदि ...

if (u < 0.0) 
{ 
    if (u < 1.0) 
    { 
    // floor is 0 
    } 
    else 
    { 
    // floor is 1 
    } 
} 
else 
{ 
    if (u < -1.0) 
    { 
    // floor is -2 
    } 
    else 
    { 
    // floor is -1 
    } 
} 

मैं इस बारे में कोई गारंटी नहीं - मैं नहीं जानता कि कैसे तुलना की दक्षता फर्श के साथ तुलना - लेकिन यह लायक हो सकता है कोशिश कर रहे हैं।

Answer 3

एक और मूर्खतापूर्ण विचार है कि सिर्फ अगर रेंज छोटा है काम कर सकते हैं ...

नाव बिटवाइज़ आपरेशन का उपयोग करने से प्रतिपादक निकालें, तो एक लुकअप तालिका का उपयोग एक मुखौटा कि mantissa से अवांछित बिट्स मिटा खोजने के लिए। Renormalising मुद्दों से बचने के लिए फर्श को खोजने के लिए इसका उपयोग करें (बिंदु के नीचे बिट्स मिटाएं)।

संपादित करें मैंने इसे "बहुत मूर्खतापूर्ण, साथ ही एक बनाम बनाम -व मुद्दे" के रूप में हटा दिया। चूंकि इसे किसी भी तरह से ऊपर उठाया गया है, इसलिए इसे हटाया गया है और मैं यह तय करने के लिए दूसरों को छोड़ दूंगा कि यह कितना मूर्ख है।

Answer 4

यदि आप विजुअल सी ++ का उपयोग कर रहे हैं, तो "आंतरिक कार्यों को सक्षम करें" कंपाइलर सेटिंग जांचें। यदि सक्षम है तो इसे अधिकतर गणित कार्यों को तेजी से (फर्श समेत) बनाना चाहिए। नकारात्मकता यह है कि किनारे के मामलों (जैसे नाएन) को संभालना गलत हो सकता है, लेकिन एक गेम के लिए, आपको परवाह नहीं है।

Answer 5

आपरेशन आप चाहते हैं (बल्कि युगल की तुलना में तैरता के लिए fmodf) fmod समारोह का उपयोग कर व्यक्त किया जा सकता:

#include <math.h> 
u = fmodf(u, 1.0f); 

संभावना काफी अच्छा है कि अपने संकलक लिए सबसे कारगर तरीका है कि काम करता है में यह कार्य करेगा।

वैकल्पिक रूप से, आप अंतिम-बिट परिशुद्धता के बारे में कितने चिंतित हैं?क्या आप अपने नकारात्मक मूल्यों पर कम बाध्य डाल सकते हैं, जैसे कुछ जानते हुए कि वे कभी भी -16.0 से नीचे नहीं हैं? यदि हां, तो कुछ इस तरह आप एक सशर्त है, जो काफी उपयोगी होने की संभावना है की बचत होगी अगर यह कुछ है कि मज़बूती से अपने डेटा के साथ शाखा-भविष्यवाणी की जा सकती है:

u = (u + 16.0); // Does not affect fractional part aside from roundoff errors. 
u -= (int)u;  // Recovers fractional part if positive. 

(उस बात के लिए, क्या के आधार पर अपने डेटा जैसा दिखता है और आप जिस प्रोसेसर का उपयोग कर रहे हैं, यदि उनमें से एक बड़ा हिस्सा नकारात्मक है लेकिन बहुत छोटा अंश 16.0 से नीचे है, तो आप पाएंगे कि आपके सशर्त इंट-कास्टिंग करने से पहले 16.0f जोड़ना आपको एक गति प्रदान करता है क्योंकि यह आपके बनाता है सशर्त अनुमानित। या आपका कंपाइलर एक सशर्त शाखा के अलावा कुछ और कर सकता है, जिस स्थिति में यह उपयोगी नहीं है; बिना परीक्षण किए और उत्पन्न असेंबली को देखना मुश्किल है।)

Answer 6

एस ओ आप वास्तव में तेजी से फ्लोट-> int रूपांतरण चाहते हैं? AFAIK int-> फ्लोट रूपांतरण तेजी से है, लेकिन कम से कम एमएसवीसी ++ पर एक फ्लोट-> int रूपांतरण एक छोटे से सहायक फ़ंक्शन, ftol() को आमंत्रित करता है, जो मानक जटिल रूपांतरण सुनिश्चित करने के लिए कुछ जटिल सामग्री करता है। यदि आपको इस तरह के सख्त रूपांतरण की आवश्यकता नहीं है, तो आप कुछ असेंबली हैकरी कर सकते हैं, मानते हैं कि आप x86- संगत CPU पर हैं।

यहाँ एक तेजी से नाव करने के लिए पूर्णांक जो नीचे दौर, MSVC++ इनलाइन विधानसभा सिंटेक्स के उपयोग के लिए एक समारोह है (यह आप सही विचार वैसे भी देना चाहिए):

inline int ftoi_fast(float f) 
{ 
    int i; 

    __asm 
    { 
     fld f 
     fistp i 
    } 

    return i; 
} 

MSVC++ 64-बिट आप करेंगे पर 64 बिट कंपाइलर इनलाइन असेंबली को अस्वीकार करने के बाद बाहरी .asm फ़ाइल की आवश्यकता है। वह फ़ंक्शन मूल रूप से लोड फ्लोट (Fld) के लिए कच्चे x87 FPU निर्देशों का उपयोग करता है, फिर फ्लोट को पूर्णांक (fistp) के रूप में स्टोर करता है। (चेतावनी का नोट: आप सीधे सीपीयू पर रजिस्टरों को ट्वीव करके इस्तेमाल किए गए राउंडिंग मोड को बदल सकते हैं, लेकिन ऐसा नहीं करते हैं, आप एमएसवीसी के पाप और कॉस के कार्यान्वयन सहित बहुत सी चीजें तोड़ देंगे!)

आप CPU पर SSE समर्थन ग्रहण कर सकते हैं (या वहाँ एक आसान तरीका एक SSE का समर्थन codepath बनाने के लिए है) यदि आप भी कोशिश कर सकते हैं:

#include <emmintrin.h> 

inline int ftoi_sse1(float f) 
{ 
    return _mm_cvtt_ss2si(_mm_load_ss(&f));  // SSE1 instructions for float->int 
} 

... जो मूल रूप से एक ही है (लोड नाव तो के रूप में पूर्णांक की दुकान) लेकिन एसएसई निर्देशों का उपयोग कर, जो थोड़ा तेज़ हैं।

उनमें से एक को महंगे फ्लोट-टू-इंट केस को कवर करना चाहिए, और किसी भी अंतर-से-फ्लोट रूपांतरणों को अभी भी सस्ता होना चाहिए। माइक्रोसॉफ्ट-विशिष्ट होने के लिए खेद है, लेकिन यह वह जगह है जहां मैंने समान प्रदर्शन किया है और मुझे इस तरह के बड़े लाभ मिले हैं। यदि पोर्टेबिलिटी/अन्य कंपाइलर्स एक समस्या है तो आपको कुछ और देखना होगा, लेकिन ये फ़ंक्शन 100+ घड़ियों वाले एक सहायक फ़ंक्शन के विपरीत < 5 घड़ियों को ले जाने वाले दो निर्देशों को संकलित कर सकते हैं।

Answer 7

यह एक कास्टिंग लागत का समाधान नहीं करता लेकिन गणितीय सही होना चाहिए:

int inline fasterfloor(const float x) { return x < 0 ? (int) x == x ? (int) x : (int) x -1 : (int) x; } 

Answer 8

आप पाशन कर रहे हैं और सूचकांक निर्देशांकों के रूप में यू और वी का उपयोग कर, बजाय के निर्देशांकों को प्राप्त करने के लिए एक नाव फर्श, रख एक ही मूल्य की एक फ्लोट और int दोनों और उन्हें एक साथ बढ़ाएं। आवश्यकता होने पर यह आपको उपयोग करने के लिए एक समान पूर्णांक देगा।

Answer 9

पुराना सवाल, लेकिन मैं इसे पार कर गया और यह मुझे थोड़ा सा दृढ़ बना दिया कि इसे संतोषजनक उत्तर नहीं दिया गया है।

टीएल; डीआर: * ** इनलाइन असेंबली, इंट्रिनिक्स या इसके लिए दिए गए किसी अन्य समाधान का उपयोग न करें! इसके बजाय, तेजी से/असुरक्षित गणित अनुकूलन ("-फैस्ट-गणित -फनसाफ-गणित-अनुकूलन -फनो-गणित-त्रुटि" जी ++ में संकलित) के साथ संकलित करें।फर्श() इतनी धीमी क्यों है क्योंकि यह कास्ट ओवरफ्लो (FLT_MAX किसी भी आकार के स्केलर पूर्णांक प्रकार में फिट नहीं होता है) में ग्लोबल स्टेटस बदलता है, जिससे वे सदिश करना असंभव हो जाता है जब तक आप सख्त आईईईई -754 संगतता अक्षम नहीं करते , जो आपको शायद वैसे भी भरोसा नहीं करना चाहिए। इन झंडे के साथ संकलन समस्या व्यवहार को अक्षम करता है।

कुछ टिप्पणी:

अदिश रजिस्टरों के साथ

1. इनलाइन विधानसभा, vectorizable नहीं है जो तेजी से प्रदर्शन को रोकता है जब अनुकूलन के साथ संकलन। यह भी आवश्यक है कि वर्तमान में वेक्टर रजिस्टरों में संग्रहीत किसी भी प्रासंगिक मूल्य को स्टैक पर फेंक दिया जाए और स्केलर रजिस्टरों में पुनः लोड किया जाए, जो हाथ-अनुकूलन के उद्देश्य को हरा देता है।

2. आपके द्वारा उल्लिखित विधि के साथ एसएसई cvttss2si का उपयोग करते हुए इनलाइन असेंबली वास्तव में संकलक अनुकूलन के साथ लूप के लिए सरल से मेरी मशीन पर धीमी है। यह संभावना है क्योंकि आपका कंपाइलर रजिस्ट्रार आवंटित करेगा और पाइपलाइन स्टालों से बेहतर होगा यदि आप इसे कोड के पूरे ब्लॉक को एक साथ सदिश करने की अनुमति देते हैं। कुछ आंतरिक आश्रित श्रृंखलाओं के साथ इस तरह के कोड के एक छोटे टुकड़े के लिए और लगभग स्पिल्ज पंजीकरण का कोई मौका नहीं है, इसलिए एएसएम() से घिरा हाथ से अनुकूलित कोड से भी बदतर होने का बहुत कम मौका है।

3. इनलाइन असेंबली विजुअल स्टूडियो 64-बिट बिल्ड में असमर्थ, असमर्थित है, और पढ़ने के लिए बेहद मुश्किल है। Intrinsics एक ही चेतावनी के साथ ही ऊपर सूचीबद्ध लोगों से पीड़ित हैं।

4. अन्य सभी सूचीबद्ध तरीके केवल गलत हैं, जो धीमे होने की तुलना में तर्कसंगत रूप से खराब हैं, और वे प्रत्येक मामले में इस तरह के मामूली प्रदर्शन में सुधार देते हैं कि यह दृष्टिकोण की मजबूती को न्यायसंगत नहीं ठहराता है। (int) (x + 16.0) -16.0 इतना खराब है कि मैं इसे भी स्पर्श नहीं करूंगा, लेकिन आपकी विधि भी गलत है क्योंकि यह फर्श (-1) को -2 के रूप में देती है। गणित कोड में शाखाओं को शामिल करना भी एक बहुत बुरा विचार है जब यह इतना महत्वपूर्ण है कि मानक पुस्तकालय आपके लिए नौकरी नहीं करेगा। तो आपका (गलत) तरीका अधिक ((int) x) (x x0.0) जैसा दिखना चाहिए, शायद एक मध्यवर्ती के साथ ताकि आपको दो बार fpu move निष्पादित करने की आवश्यकता न हो। शाखाएं कैश मिस का कारण बन सकती हैं, जो प्रदर्शन में किसी भी वृद्धि को पूरी तरह से अस्वीकार कर देगी; भी, अगर गणित errno अक्षम है, तो int को कास्टिंग किसी भी मंजिल() कार्यान्वयन की सबसे बड़ी शेष बाधा है। यदि आप नकारात्मक पूर्णांक के लिए सही मान प्राप्त करने के बारे में/वास्तव में/परवाह नहीं करते हैं, तो यह उचित अनुमान हो सकता है, लेकिन जब तक आप अपना उपयोग केस बहुत अच्छी तरह से नहीं जानते हैं, तब तक मैं इसका जोखिम नहीं उठाऊंगा।

5. मैंने बिटवाई कास्टिंग और राउंडिंग-थ्रू-बिट -स्क का उपयोग करने की कोशिश की, जैसे कि एसयूएन का नया प्लिब कार्यान्वयन एफएमओडीएफ में करता है, लेकिन सही होने के लिए बहुत लंबा समय लगा और मेरी मशीन पर कई बार धीमा था, यहां तक ​​कि प्रासंगिक कंपाइलर के बिना भी अनुकूलन झंडे। बहुत संभावना है, उन्होंने कुछ प्राचीन सीपीयू के लिए कोड लिखा था जहां फ्लोटिंग प्वाइंट ऑपरेशंस तुलनात्मक रूप से बहुत महंगा थे और वहां कोई वेक्टर एक्सटेंशन नहीं थे, वेक्टर रूपांतरण संचालन अकेले रहने दें; यह अब किसी भी सामान्य आर्किटेक्चर AFAIK पर मामला नहीं है। सन भी क्वैक 3 द्वारा उपयोग किए जाने वाले तेज़ व्यस्त वर्ग() नियमित रूप से जन्मस्थान का जन्मस्थान है; अब अधिकांश आर्किटेक्चर पर इसके लिए एक निर्देश है। सूक्ष्म अनुकूलन के सबसे बड़े नुकसान में से एक यह है कि वे जल्दी से पुराने हो जाते हैं।