सी ++ कोड

Question

की रनटाइम दक्षता को कैसे ढूंढें मैं एक प्रोग्राम की दक्षता को खोजने की कोशिश कर रहा हूं जिसे मैंने हाल ही में स्टैक ओवरफ्लो पर पोस्ट किया है।

How to efficiently delete elements from a vector given an another vector

अन्य उत्तर मैं chrono वस्तु का उपयोग कर रहा के साथ अपने कोड की दक्षता में तुलना करने के लिए।

क्या रनटाइम दक्षता की जांच करने का यह सही तरीका है?

यदि नहीं तो कृपया उदाहरण के साथ ऐसा करने का एक तरीका सुझाएं।

Code on Coliru

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <chrono> 
#include <ctime> 
using namespace std; 

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{ 
    if(!vDestination.empty() && !vSource.empty()) 
    { 
     for(auto i: vSource) { 
      vDestination.erase(std::remove(vDestination.begin(), vDestination.end(), i), vDestination.end()); 
     } 
    } 
} 

int main() { 
    vector<int> v1={1,2,3}; 
    vector<int> v2={4,5,6}; 
    vector<int> v3={1,2,3,4,5,6,7,8,9}; 
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now(); 
    remove_elements(v3,v1); 
    remove_elements(v3,v2); 
    std::chrono::steady_clock::time_point end= std::chrono::steady_clock::now(); 
    std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() <<std::endl; 
    for(auto i:v3) 
     cout << i << endl; 
    return 0; 
} 

आउटपुट

Time difference = 1472 
7 
8 
9 

Answer 1

यह क्रम दक्षता जांच के लिए एक सही तरीका है?

ऐसा करने का सबसे अच्छा तरीका नहीं दिखता है।

1. मान हल कर रहे हैं: मैं अपने विधि में निम्नलिखित खामियों को देखते हैं। Branch prediction एक ही एल्गोरिदम के साथ क्रमबद्ध बनाम अनुक्रमित मानों का परीक्षण करते समय हास्यास्पद प्रभाव का पर्दाफाश कर सकता है। संभावित फिक्स: क्रमबद्ध और बिना छेड़छाड़ और परिणामों की तुलना दोनों पर परीक्षण।
2. मान हार्ड कोड कोड हैं। सीपीयू कैश tricky thing है और यह हार्ड-कोड किए गए मानों और वास्तविक जीवन वाले परीक्षणों के बीच सूक्ष्म अंतर पेश कर सकता है। वास्तविक दुनिया में आप हार्ड-कोडित मानों पर इन परिचालनों को निष्पादित करने की संभावना नहीं रखते हैं, ताकि आप उन्हें किसी फ़ाइल से पढ़ सकें या यादृच्छिक उत्पन्न कर सकें।
3. बहुत कम मूल्य। आपके कोड का निष्पादन समय टाइमर परिशुद्धता से बहुत छोटा है।
4. आप केवल एक बार कोड चलाते हैं। यदि आप अन्य सभी मुद्दों को ठीक करते हैं और दो बार कोड चलाते हैं, तो दूसरा रन कैश गर्म होने के कारण पहले की तुलना में बहुत तेज़ हो सकता है: बाद के रनों में पहले से कम cache misses कम होता है।
5. आप निश्चित आकार डेटा पर एक बार कोड चलाते हैं।
   • क्रमबद्ध अवर्गीकृत डेटा बनाम
   • v3 फिट बैठता है सीपीयू कैश बनाम v3 आकार सीपीयू कैश से अधिक है: यह अन्यथा सही परीक्षण कम से कम से कम चार बार निम्नलिखित मानकों के एक कार्तीय उत्पाद कवर करने के लिए चलाने के लिए बेहतर होगा। उन मामलों पर भी विचार करें जब (v1.length() + v3.length()) * sizeof(int) कैश फिट बैठता है या नहीं, (v1.length() + v2.length() + v3.length()) * sizeof(int) सभी संयोजनों के लिए कैश फिट करता है या नहीं।

Answer 2

अपने दृष्टिकोण के साथ सबसे बड़ी मुद्दे हैं:

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

2) संकलक के लिए स्वतंत्र है अपने कोड को पुन: व्यवस्थित। आम तौर पर यह सुनिश्चित करना बहुत मुश्किल है कि आप जिस कोड को समय दे रहे हैं, समय की जांच करने के लिए कॉल के बीच निष्पादित होगा (और उस मामले के लिए और कुछ भी नहीं)। एक तरफ, आप ऑप्टिमाइज़ेशन डायल कर सकते हैं, लेकिन दूसरी तरफ आप अनुकूलित कोड को मापना चाहते हैं।

एक समाधान पूरे कार्यक्रम अनुकूलन को बंद करना और दूसरी संकलन इकाई में समय कॉल करना है।

एक और संभावित समाधान आपके परीक्षण के आसपास मेमोरी बाड़ का उपयोग करना है, उदाहरण के लिए

std::atomic_thread_fence(std::memory_order_seq_cst); 

(#include <atomic> और एक सी ++ 11-सक्षम कंपाइलर की आवश्यकता है)।

इसके अलावा, आप यह देखने के लिए प्रोफाइलर डेटा के साथ अपने माप को पूरक करना चाहते हैं कि एल 1/2/3 कैश का उपयोग कैसे किया जाता है, मेमोरी बाधाएं, निर्देश रिटायर दर इत्यादि। दुर्भाग्यवश इंटेल x86 के लिए सबसे अच्छा टूल वाणिज्यिक है (vtune), लेकिन एएमडी x86 पर एक समान उपकरण मुफ्त (codeXL) है।

Answer 3

आप अपने लिए माप करने के लिए Celero जैसे बेंचमार्किंग लाइब्रेरी का उपयोग करने और प्रदर्शन माप के कठिन हिस्सों से निपटने पर विचार कर सकते हैं, जबकि आप उस कोड पर ध्यान केंद्रित करते हैं, जिसे आप अनुकूलित करने का प्रयास कर रहे हैं। अधिक जटिल उदाहरण कोड मैं अपने पिछले प्रश्न (How to efficiently delete elements from a vector given an another vector) के जवाब में लिंक करने के बाद में उपलब्ध हैं, लेकिन एक सरल उपयोग के मामले इस प्रकार दिखाई देगा:

BENCHMARK(VectorRemoval, OriginalQuestion, 100, 1000) 
{ 
    std::vector destination(10000); 
    std::generate(destination.begin(), destination.end(), std::rand); 
    std::sample(destination.begin(), destination.end(), std::back_inserter(source), 
     100, std::mt19937{std::random_device{}()})  

    for (auto i: source) 
     destination.erase(std::remove(destination.begin(), destination.end(), i), 
      destination.end());  
}