सुरक्षित और तेज़ एफएफटी

Question

हर्ब सटर के आकर्षक व्याख्यान Not your father's C++ से प्रेरित, मैंने माइक्रोसॉफ्ट के विजुअल स्टूडियो 2010 का उपयोग कर सी ++ के नवीनतम संस्करण पर एक और नज़र डालने का फैसला किया। मुझे विशेष रूप से हर्ब के इस दावे से रूचि थी कि सी ++ "सुरक्षित और तेज़" है क्योंकि मैं बहुत सारे प्रदर्शन-महत्वपूर्ण कोड लिखें।

बेंचमार्क के रूप में, मैंने विभिन्न भाषाओं में एक ही साधारण एफएफटी एल्गोरिदम लिखने का प्रयास करने का फैसला किया।

#include <complex> 
#include <vector> 

using namespace std; 

// Must provide type or MSVC++ barfs with "ambiguous call to overloaded function" 
double pi = 4 * atan(1.0); 

void fft(int sign, vector<complex<double>> &zs) { 
    unsigned int j=0; 
    // Warning about signed vs unsigned comparison 
    for(unsigned int i=0; i<zs.size()-1; ++i) { 
     if (i < j) { 
      auto t = zs.at(i); 
      zs.at(i) = zs.at(j); 
      zs.at(j) = t; 
     } 
     int m=zs.size()/2; 
     j^=m; 
     while ((j & m) == 0) { m/=2; j^=m; } 
    } 
    for(unsigned int j=1; j<zs.size(); j*=2) 
     for(unsigned int m=0; m<j; ++m) { 
      auto t = pi * sign * m/j; 
      auto w = complex<double>(cos(t), sin(t)); 
      for(unsigned int i = m; i<zs.size(); i+=2*j) { 
       complex<double> zi = zs.at(i), t = w * zs.at(i + j); 
       zs.at(i) = zi + t; 
       zs.at(i + j) = zi - t; 
      } 
     } 
} 

ध्यान दें कि यह समारोह केवल n तत्व वैक्टर के लिए काम करता है, जहां n एक अभिन्न है:

मैं का उपयोग करता है निर्मित में complex प्रकार और vector संग्रह निम्नलिखित सी ++ 11 कोड के साथ आया था दो की शक्ति। कोई भी n के लिए काम करता है जो तेजी से एफएफटी कोड की तलाश में है FFTW पर देखना चाहिए।

मैं यह समझ के रूप में, पारंपरिक xs[i] एक vector अनुक्रमण के लिए सी से वाक्य रचना सीमा जाँच करता है नहीं है, परिणामस्वरूप, सुरक्षित स्मृति नहीं है और इस तरह के गैर नियतात्मक भ्रष्टाचार और स्मृति पहुँच उल्लंघन के रूप में स्मृति त्रुटियों की एक स्रोत हो सकता है । तो मैंने इसके बजाय xs.at(i) का उपयोग किया।

अब, मैं चाहता हूं कि यह कोड "सुरक्षित और तेज़" हो, लेकिन मैं सी ++ 11 विशेषज्ञ नहीं हूं इसलिए मैं इस कोड में सुधार के लिए पूछना चाहता हूं जो इसे अधिक मूर्ख या कुशल बना देगा?

Answer 1

मुझे लगता है कि आप() के उपयोग में अत्यधिक "सुरक्षित" हैं। आपके ज्यादातर मामलों में उपयोग की जाने वाली अनुक्रमणिका को लूप में कंटेनर के आकार से बाधित होने के रूप में तुच्छ रूप से सत्यापित किया जा सकता है।

उदा।

for(unsigned int i=0; i<zs.size()-1; ++i) { 
    ... 
    auto t = zs.at(i); 

केवल वही जिन्हें मैं छोड़ दूंगा() + (i + j) s। यह तुरंत स्पष्ट नहीं है कि वे हमेशा बाधित होंगे (हालांकि अगर मैं वास्तव में अनिश्चित था तो शायद मैं मैन्युअल रूप से जांच करूँगा - लेकिन मैं इस मामले में राय रखने के लिए पर्याप्त एफएफटी से परिचित नहीं हूं)।

int m=zs.size()/2; 
pi * sign 
2*j 

और zs.at (मैं j +) दो बार गणना की जाती है:

भी कुछ तय संगणना प्रत्येक पाश यात्रा के लिए बार-बार की जा रही हैं।

यह संभव है कि ऑप्टिमाइज़र इन्हें पकड़ सके - लेकिन यदि आप इसे प्रदर्शन के रूप में महत्वपूर्ण मानते हैं, और आपके टाइमर इसका परीक्षण कर रहे हैं, तो मैं उन्हें लूप से बाहर निकाल दूंगा (या, zs.at के मामले में (i + j), बस पहले उपयोग पर एक संदर्भ लें) और देखें कि क्या टाइमर को प्रभावित करता है।

ऑप्टिमाइज़र का दूसरा अनुमान लगाने की बात करते हुए: मुझे यकीन है कि .size() को कॉल कम से कम एक आंतरिक सदस्य चर के लिए एक सीधी कॉल के रूप में रेखांकित किया जाएगा - लेकिन यह कितनी बार आप इसे कॉल करते हैं zs.size() और zs.size() - 1 अपफ्रंट के लिए स्थानीय चर प्रस्तुत करने के साथ भी प्रयोग करें। वे भी इस तरह से रजिस्टरों में डाल दिया जा सकता है।

मुझे नहीं पता कि इसमें कितना अंतर है (यदि कोई है) यह सब आपके कुल रनटाइम पर होगा - इसमें से कुछ को पहले ही ऑप्टिमाइज़र द्वारा पकड़ा जा सकता है, और इसमें शामिल गणनाओं की तुलना में मतभेद छोटे हो सकते हैं - लेकिन एक शॉट के लायक है।

मेरी एकमात्र टिप्पणी मूर्खतापूर्ण होने के लिए, वास्तव में, यह आकार() एक std :: size_t देता है (जो आम तौर पर एक हस्ताक्षरित int के लिए टाइपिफ़ होता है - लेकिन इसके बजाय उस प्रकार का उपयोग करने के लिए यह अधिक मूर्खतापूर्ण है)। यदि आप ऑटो का उपयोग करना चाहते थे लेकिन चेतावनी से बचें तो आप 0 को उल प्रत्यय जोड़ने का प्रयास कर सकते हैं - सुनिश्चित नहीं है कि मैं कहूंगा कि यह मूर्खतापूर्ण है। मुझे लगता है कि आप यहां इटरेटर्स का उपयोग न करने में मूर्खता से कम हैं, लेकिन मैं देख सकता हूं कि आप ऐसा क्यों नहीं कर सकते (आसानी से)।

अद्यतन

मैं अपने सभी सुझावों एक कोशिश दे दी है और वे सभी एक औसत दर्जे का प्रदर्शन में सुधार के लिए किया था - मैं + j और 2 * जे precalcs छोड़कर - वे वास्तव में एक मामूली मंदी की वजह से! मुझे लगता है कि उन्होंने या तो एक कंपाइलर अनुकूलन को रोका या इसे कुछ चीजों के लिए रजिस्टरों का उपयोग करने से रोका।

कुल मिलाकर मुझे> 10% perf मिला। उन सुझावों के साथ सुधार। मुझे संदेह है कि अगर लूप के दूसरे ब्लॉक को कूदने से बचने के लिए थोड़ा सा रिफैक्टर किया गया था - और एसएसई 2 निर्देश सेट को सक्षम करने से यह काफी बढ़ावा दे सकता है (मैंने इसे आजमाया और मामूली मंदी देखी)।

मुझे लगता है कि कॉस और पाप कॉल के लिए एमकेएल जैसे कुछ का उपयोग करने के साथ रिफैक्टरिंग, अधिक, और कम भंगुर, सुधार देना चाहिए। और उन चीजों में से कोई भी भाषा निर्भर नहीं होगा (मुझे पता है कि इसकी मूल रूप से एफ # कार्यान्वयन की तुलना में तुलना की जा रही थी)।

अद्यतन 2

मुझे लगता है कि पूर्व की गणना zs.size उल्लेख करना भूल गया() एक फर्क था।

अद्यतन 3

भी कहने के लिए (ओ पी करने के लिए टिप्पणी में @xeo द्वारा याद दिला दी जब तक) है कि मैं < जे जांच निम्नलिखित ब्लॉक एक std :: स्वैप करने के लिए नीचे उबला हुआ जा सकता है भूल गया। यह अधिक मूर्खतापूर्ण है और कम से कम कलाकार के रूप में - सबसे बुरे मामले में लिखित के समान कोड में इनलाइन होना चाहिए। दरअसल जब मैंने ऐसा किया तो मैंने प्रदर्शन में कोई बदलाव नहीं देखा। अन्य मामलों में यदि चालक उपलब्ध हैं तो यह प्रदर्शन लाभ का कारण बन सकता है।