फॉर लूप

Question

के लिए सबसे तेज़ भाषा मैं एक विश्लेषणात्मक मॉडल के निर्माण के लिए सबसे अच्छी प्रोग्रामिंग भाषा का पता लगाने की कोशिश कर रहा हूं। प्राथमिक विचार गति है जिस पर यह लूप के लिए चलाएगा।

कुछ विस्तार:

• मॉडल एक सरणी से तत्व का एक सेट पर (, ~ 30 प्रविष्टि प्रति 12 चक्र से अधिक) कई प्रदर्शन करने के लिए आपरेशन की जरूरत है - वहाँ ~ 300k पंक्तियाँ, और ~ 150 स्तंभ हैं सरणी में इनमें से अधिकतर ऑपरेशन प्रकृति में तार्किक हैं, उदाहरण के लिए, यदि स्थान (i) = 1, तो j (i) = 2.
• मैंने ऑक्टेव का उपयोग करके इस मॉडल का एक पुराना संस्करण बनाया है - इसे चलाने के लिए ~ 55 अमेज़ॅन ईसी 2 m2.xlarge इंस्टेंस पर घंटे (और यह ~ 10 जीबी मेमोरी का उपयोग करता है, लेकिन मैं इसमें अधिक मेमोरी फेंकने के लिए पूरी तरह से खुश हूं)। ऑक्टेव/मैटलैब तत्ववार तार्किक परिचालन नहीं करेगा, इसलिए लूपों की एक बड़ी संख्या की आवश्यकता है - मुझे अपेक्षाकृत निश्चित है कि मैंने जितना संभव हो सदिश किया है - जो लूप शेष हैं। मुझे इस कोड के साथ काम करने के लिए ऑक्टो-मल्टीकोर मिल गया है, जो कुछ सुधार करता है (जब मैं इसे 8 ईसी 2 कोर पर चलाता हूं तो 30% की गति में कमी आती है), लेकिन फ़ाइल लॉकिंग आदि के साथ अस्थिर हो जाती है। + मैं हूं वास्तव में रन-टाइम में एक कदम परिवर्तन की तलाश में - मुझे पता है कि वास्तव में मैटलैब का उपयोग करने से मुझे कुछ बेंचमार्क देखने से 50% सुधार मिल सकता है, लेकिन यह लागत-निषिद्ध है। इसे शुरू करते समय मूल योजना वास्तव में इसके साथ एक मोंटे कार्लो चलाने के लिए थी, लेकिन 55 घंटों में एक रन, यह पूरी तरह अव्यवहारिक है।
• इसका अगला संस्करण ग्राउंड अप से एक पूर्ण पुनर्निर्माण होगा (आईपी कारणों से मैं कुछ और नहीं कर पाऊंगा), इसलिए मैं किसी भी प्रोग्रामिंग भाषा के लिए पूरी तरह से खुला हूं। मैं ऑक्टेव/मैटलैब से सबसे ज्यादा परिचित हूं, लेकिन आर, सी, सी ++, जावा में डब किया है। यदि समाधान में डेटाबेस को डेटा संग्रहीत करना शामिल है तो मैं भी कुशल w/SQL हूं। मैं इसके लिए कोई भी भाषा सीखूंगा - ये जटिल कार्यक्षमता नहीं हैं जिसे हम ढूंढ रहे हैं, अन्य कार्यक्रमों के साथ इंटरफेसिंग नहीं, आदि, इसलिए वक्र सीखने के बारे में बहुत चिंतित नहीं हैं।

तो वह सब कहा साथ, क्या सबसे तेजी से प्रोग्रामिंग भाषा विशेष रूप से छोरों के लिए के लिए है? एसओ और Google, फोरट्रान और सी बबल की खोज से शीर्ष पर, लेकिन एक या दूसरे में गोता लगाने से पहले कुछ और सलाह की तलाश है।

धन्यवाद!

Answer 1

पूर्ण गति के मामले में, शायद फोरट्रान सी के बाद, सी ++ के बाद। व्यावहारिक अनुप्रयोग में, तीनों में से किसी एक में अच्छी तरह लिखित कोड, एक मूल संकलक के साथ संकलित बहुत तेज होना चाहिए।

संपादित करें- आम तौर पर आप एक संकलित भाषा के विरुद्ध किसी संकलित भाषा के साथ किसी भी प्रकार के लूप या फोर्किंग (उदा। अगर बयान) कोड के साथ बेहतर प्रदर्शन देखने जा रहे हैं।

एक उदाहरण देने के लिए, एक हालिया प्रोजेक्ट पर मैं काम कर रहा था, डेटा आकार और परिचालन लगभग 3/4 आकार के बारे में आप किस बारे में बात कर रहे हैं, लेकिन आपके कोड की तरह, वेक्टरेशन के लिए बहुत कम कमरा था , और महत्वपूर्ण लूपिंग की आवश्यकता है। कोड को मैटलैब से सी ++ में परिवर्तित करने के बाद, रनटाइम 16-18 घंटों से नीचे 25 मिनट तक चला गया।

Answer 2

डेटा कैसे संग्रहीत किया जाता है? आपका निष्पादन समय आपकी भाषा की तुलना में I/O (विशेष रूप से डिस्क या बदतर, नेटवर्क) द्वारा अधिक प्रभावित होता है।

पंक्तियों पर मानते हुए ऑर्थोगोनल हैं, मैं सी # के साथ जाऊंगा और सभी समांतरता का फायदा उठाने के लिए PLINQ का उपयोग करूंगा।जब यह सीपीयू हिट

पाश के लिए

Answer 3

यह इस से कोई और अधिक जटिल दिखता है:

for(int i = 0; i != 1024; i++)

mov r0, 0   ;;start the counter  
top: 

;;some processing 

add r0, r0, 1  ;;increment the counter by 1 
jne top: r0, 1024 ;;jump to the loop top if we havn't hit the top of the for loop (1024 elements) 

;;continue on 

करने के लिए अनुवाद आपको बता सकते हैं, यह पर्याप्त रूप से सरल है आप वास्तव में यह बहुत अनुकूलित नहीं कर सकते अच्छी तरह से [1] ... एल्गोरिदम स्तर की ओर फिर से ध्यान दें।

समस्या पर पहली कटौती कैश इलाके को देखने के लिए है। मैट्रिक्स गुणा के क्लासिक उदाहरण को देखें और i और j अनुक्रमणिका को स्वैप करें।

संपादित करें: एक दूसरे कटौती के रूप में, मैं अपने डेटा का 'मैट्रिक्स' में पुनरावृत्तियों और बस्तियों के बीच डेटा निर्भरता के बीच डाटा-निर्भरता के लिए एल्गोरिथ्म का मूल्यांकन सुझाव है। यह समांतरता के लिए एक अच्छा उम्मीदवार हो सकता है।

[1] कुछ माइक्रो -Otimimizations संभव हैं, लेकिन वे उन गतिशीलताओं का उत्पादन नहीं करेंगे जिन्हें आप ढूंढ रहे हैं।

Answer 4

आप क्या चर्चा कर रहे हैं के लिए, फोरट्रान शायद अपनी पहली पसंद है। निकटतम दूसरा स्थान शायद C++ है। इस तरह के कार्य के लिए सी पर कुछ गति प्राप्त करने के लिए कुछ सी ++ पुस्तकालय "अभिव्यक्ति टेम्पलेट्स" का उपयोग करते हैं। यह पूरी तरह से निश्चित नहीं है कि वे आपको कोई अच्छा काम करेंगे, लेकिन सी ++ कम से कम सी के रूप में तेज़ हो सकता है, और संभवतः कुछ हद तक तेज़ हो सकता है।

कम से कम सिद्धांत में, कोई कारण नहीं है कि एडा भी प्रतिस्पर्धी नहीं हो सकता है, लेकिन यह इतना लंबा रहा है क्योंकि मैंने इसे इस तरह से कुछ भी करने के लिए उपयोग किया है, क्योंकि मैं इसे अनुशंसा करने में संकोच नहीं करता - क्योंकि यह अच्छा नहीं है, लेकिन क्योंकि मैंने अभी तक वर्तमान एडीए कंप्यूटर्स का ट्रैक नहीं रखा है, जो समझदारी से उन पर टिप्पणी करने के लिए पर्याप्त हैं।

Answer 5

~300k * ~150 * ~30 * ~12 = ~16G पुनरावृत्तियों, है ना? किसी भी सभ्य CPU पर किसी संकलित भाषा में मिनटों (यदि सेकंड नहीं) के मामले में आदिम परिचालनों की यह संख्या पूरी होनी चाहिए। फोरट्रान, सी/सी ++ इसे लगभग समान रूप से अच्छी तरह से करना चाहिए। जावा और सी # जैसी प्रबंधित भाषाएं, केवल एक छोटे मार्जिन (यदि बिलकुल भी) द्वारा पीछे आती हैं।

यदि आपको 55 घंटे चलने वाले ~ 16 जी पुनरावृत्तियों की समस्या है, तो इसका मतलब है कि वे आदिम होने से बहुत दूर हैं (प्रति सेकंड 80k? यह हास्यास्पद है), तो शायद हमें और जानना चाहिए। (जैसा कि पहले से ही सुझाव दिया गया था, डिस्क एक्सेस सीमित प्रदर्शन है? क्या यह नेटवर्क का उपयोग है?)

Answer 6

क्या आप हाथ से कोडित असेंबलर डालने के साथ सबसे अच्छे नहीं हो सकते हैं? मान लीजिए कि आपको पोर्टेबिलिटी की आवश्यकता नहीं है।

कि और एक अनुकूलित एल्गोरिथ्म की मदद करनी चाहिए (और शायद डेटा पुनर्गठन?)।

आप एक से अधिक एल्गोरिदम कोशिश करते हैं और उन्हें प्रोफ़ाइल कर सकते हैं।

Answer 7

क्लोजर जैसी आलसी लोडिंग भाषा के बारे में क्या। यह एक लिस्प है इसलिए अधिकांश लिस्पी बोलीभाषाओं में लूप की कमी होती है लेकिन इसमें कई अन्य रूप हैं जो सूची प्रसंस्करण के लिए अधिक मूर्खतापूर्वक संचालित करते हैं। यह आपके स्केलिंग मुद्दों को भी मदद कर सकता है क्योंकि ऑपरेशन थ्रेड सुरक्षित हैं और क्योंकि भाषा कार्यात्मक है क्योंकि इसका कम दुष्प्रभाव होता है। यदि आप सूची में सभी आइटम ढूंढना चाहते थे जो 'i' मूल्यों पर काम करने के लिए मूल्य थे तो आप ऐसा कुछ कर सकते हैं।

(def mylist ["i" "j" "i" "i" "j" "i"]) 
(map #(= "i" %) mylist) 

परिणाम

(true false true true false true)

Answer 8

किसी भी संकलित भाषा पाश पर ही मोटे तौर पर समान शर्तों का पालन करना चाहिए।

यदि आप अपनी शर्तों को अपनी शर्तों में तैयार कर सकते हैं, तो आप सीयूडीए या ओपनसीएल को देखना और GPU पर अपना मैट्रिक्स कोड चला सकते हैं - हालांकि यह बहुत सशर्त के साथ कोड के लिए कम अच्छा है।

आप पारंपरिक CPUs पर रहना चाहते हैं, तो आप SSE बिखराव/इकट्ठा होते हैं और bitmask संचालन के मामले में आपकी समस्या को तैयार करने के लिए सक्षम हो सकता है।

Answer 9

एपीएल।

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

A <- 2 3 4 5 6 8 10 
    ((2|A)/A) <- 0 
    A 
2 0 4 0 6 8 10 

पहली पंक्ति संख्या का एक वेक्टर के लिए एक सेट:

यहाँ एपीएल में से निपटने सरणी की सादगी का एक उदाहरण है। दूसरी पंक्ति वेक्टर में शून्य के साथ सभी विषम संख्याओं को प्रतिस्थापित करती है। तीसरी पंक्ति ए के नए मानों से पूछताछ करती है, और चौथी पंक्ति परिणामस्वरूप आउटपुट होती है।

ध्यान दें कि कोई स्पष्ट पाशन जैसे अदिश ऑपरेटर के रूप में, आवश्यक था '|' (शेष) स्वचालित रूप से आवश्यकतानुसार सरणी तक विस्तारित होता है। एपीएल में खोज और छंटाई के लिए अंतर्निहित प्राइमेटिव भी हैं, जो शायद इन परिचालनों के लिए अपने स्वयं के लूप लिखने से तेज़ होंगे।

विकिपीडिया एक अच्छा article on APL है, जो भी आईबीएम और Dyalog के रूप में आपूर्तिकर्ताओं के लिए लिंक प्रदान करता है है।

Answer 10

रूप @Rotsor ने कहा, 16 जी आपरेशन/55 घंटे प्रति सेकंड लगभग 80,000 संचालन, या एक आपरेशन हर 12.5 माइक्रोसेकंड है। यह प्रति ऑपरेशन बहुत समय है।

अपने छोरों इसका मतलब है कि खराब प्रदर्शन का कारण नहीं हैं, यह क्या में है अंतरतम पाश कि समय देने के लिए किया है। और ऑक्टवे एक व्याख्या की गई भाषा है। उस अकेले का मतलब आयाम की मंदी का एक आदेश है।

आप गति चाहते हैं, तो आपको पहले एक संकलित भाषा में होना चाहिए। फिर आपको प्रदर्शन ट्यूनिंग (उर्फ प्रोफाइलिंग) करने की आवश्यकता है या निर्देश स्तर पर डीबगर में केवल एक ही चरण की आवश्यकता है। यह आपको बताएगा कि यह वास्तव में दिल के दिल में क्या कर रहा है। एक बार जब आप इसे जहां बर्बाद नहीं कर रहा है चक्र, सजावटी हार्डवेयर, कोर, CUDA, आदि के लिए मिल गया है आप एक समानांतरवाद speedup दे देंगे। लेकिन यह है कि यदि आपके कोड को अनावश्यक रूप से कई चक्र ले जा रहा है क्या करना मूर्खतापूर्ण है। (Here's an example of performance tuning - a 43x speedup just by trimming the fat.)

मैं matlab, एपीएल, और अन्य vectorized भाषाओं के बारे में बात प्रतिसाददाताओं की संख्या विश्वास नहीं कर सकता। वे दुभाषिया हैं। वे आपको संक्षिप्त स्रोत कोड प्रदान करते हैं, जो पर पर निष्पादन जैसा ही नहीं है।जब यह नंगे धातु के नीचे आता है, तो वे एक ही हार्डवेयर के साथ हर दूसरी भाषा के रूप में अटक जाते हैं।

---

जोड़ा गया: आप को दिखाने के लिए मैं क्या मतलब है, मैं सिर्फ इस सी ++ कोड है, जो 16 जी संचालन करता है, यह छोटा सा विलायती पुराने लैपटॉप पर भाग गया, और यह 94 सेकंड ले लिया है, या यात्रा प्रति 6ns के बारे में। (मैं विश्वास नहीं कर सकता कि बच्चा 2 दिनों के लिए उस चीज़ को बैठता है।)

void doit(){ 
    double sum = 0; 
    for (int i = 0; i < 1000; i++){ 
    for (int j = 0; j < 16000000; j++){ 
     sum += j * 3.1415926; 
    } 
    } 
} 

Answer 11

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

Answer 12

किसी भी आधुनिक संकलित या JITted भाषा, 10 नैनो सेकंड या उससे कम की एक पाश भूमि के ऊपर दे रही यात्रा प्रति, आधुनिक प्रोसेसर पर काफी एक ही मशीन भाषा कोड के लिए नीचे प्रस्तुत करने के लिए जा रहा है,।

का हवाला देते हुए @Rotsor:

आप 55 घंटे चल रहा है ~ 16 जी पुनरावृत्तियों की एक समस्या है, तो इसका अर्थ है कि वे आदिम होने से बहुत दूर तो हो सकता है कर रहे हैं प्रति सेकंड (80k यह हास्यास्पद है?), हम और जानना चाहिए।

80k ऑपरेशंस प्रति सेकेंड लगभग 12.5 माइक्रोसॉन्ड प्रत्येक है - लूप ओवरहेड से 1000 से अधिक का एक कारक जो आप उम्मीद करेंगे।

मानते हुए कि आपका 55 घंटे रनटाइम सिंगल थ्रेडेड है, और यदि आपके प्रति आइटम ऑपरेशंस सुझाव के अनुसार सरल हैं, तो आप (रूढ़िवादी रूप से) 100x की गति प्राप्त करने में सक्षम होना चाहिए और इसे आसानी से एक घंटे से कम कर सकते हैं।

यदि आप अभी भी तेजी से दौड़ना चाहते हैं, तो आप बहु-थ्रेडेड समाधान लिखना चाहते हैं, इस मामले में एक अच्छी भाषा प्रदान करने वाली भाषा आवश्यक होगी। मैं PLINQ और C# 4.0 की तरफ झुकता हूं, लेकिन ऐसा इसलिए है क्योंकि मुझे पहले ही सी # - वाईएमएमवी पता है।

Answer 13

मैटलैब तत्व-वार लॉजिकल ऑपरेशंस करेगा और वे आम तौर पर काफी तेज़ होते हैं।

यहाँ अपने कंप्यूटर पर एक त्वरित उदाहरण (एएमडी Athalon 2.3GHz 3GB डब्ल्यू /) है:

d=rand(300000,150); 
d=floor(d*10); 

>> numel(d(d==1)) 
ans = 
    4501524 

>> tic;d(d==1)=10;toc; 
Elapsed time is 0.754711 seconds. 

>> numel(d(d==1)) 
ans = 
    0 
>> numel(d(d==10)) 
ans = 
    4501524 

सामान्य तौर पर मैंने पाया matlab के ऑपरेटरों बहुत तेजी से कर रहे हैं, तो आप सिर्फ व्यक्त करने के लिए तरीके खोजने के लिए अपने मैट्रिक्स ऑपरेटरों के मामले में सीधे एल्गोरिदम।

Answer 14

सी ++ लूप के साथ मैट्रिक्स चीजें करते समय तेज़ नहीं है। सी वास्तव में, विशेष रूप से खराब है। good math bad math देखें।

मुझे लगता है कि सी 99 में __restrict पॉइंटर्स हैं जो मदद करते हैं, लेकिन इसके बारे में ज्यादा नहीं जानते हैं।

फ़ोरट्रान संख्यात्मक कंप्यूटिंग के लिए अभी भी गोटो भाषा है।