C ++ 2011 में मल्टीथ्रेडेड क्विकॉर्ट

निजी तौर पर, C ++ में मेरे सभी विश्वासों के लिए, मेरा मानना ​​है कि 2011 के संस्करण में भी, यह भाषा मल्टीटास्किंग और मल्टीथ्रेडिंग के मामले में बेहद अनफ्रेंडली है। खुद को समझाने के एक और प्रयास के रूप में, मैंने मल्टी-थ्रेडेड क्विकसॉर्ट बनाने की कोशिश की।

इस एल्गोरिथ्म में, यह विभाजन चरण के बाद, समानांतर में उप-भागों को क्रमबद्ध करने के लिए निकलता है।

यहाँ मेरी भोली बाइक है:

int naive_quick_sort(std::vector<Type>::iterator begin, std::vector<Type>::iterator end) { auto const sz = end - begin; if (sz <= 1) return 0; auto pivot = begin + sz/2; auto const pivot_v = *pivot; std::swap(*pivot, *(end - 1)); auto p = std::partition(begin, end, [&](const Type& a) { return a < pivot_v; } ); std::swap(*p, *(end - 1)); if (sz > 4096) { auto left = std::async(std::launch::async, [&]() { return naive_quick_sort(begin, p); }); naive_quick_sort(p + 1, end); } else { naive_quick_sort(begin, p); naive_quick_sort(p + 1, end); } return 0; } void quick_sort(std::vector<Type>& arr) { naive_quick_sort(arr.begin(), arr.end()); } 

कार्यान्वयन बेहद सरल है, लेकिन यह कुछ बिंदुओं पर ध्यान देने योग्य है। एक निश्चित स्थिर 4096 है, जो समानांतर निष्पादन को अक्षम करने पर सीमा निर्धारित करता है। ऐसा अर्थ क्यों? मुझे नहीं पता सामान्य ज्ञान की न्यूनतम भावना के साथ हवा से लिया गया। जब समानता सक्रिय होती है, तो बाएं सरणी की छंटनी को एक और धागे में एसिंक्स के माध्यम से शुरू किया जाता है, और दाएं को वर्तमान धागे में पहले की तरह क्रमबद्ध किया जाता है। जब आप फ़ंक्शन संदर्भ से बाहर निकलते हैं, तो यह गारंटी दी जाती है कि async माध्यम से लॉन्च किया गया कार्य पूरा हो जाएगा (वे इसके पूरा होने की प्रतीक्षा करेंगे)।

परंपरागत रूप से, एक निर्वात में गोलाकार घोड़ों की पुजारोमेका। तीन उम्मीदवार:

• उपरोक्त कार्यान्वयन (async के माध्यम से)
• यह एक ही है, लेकिन एक धागे में ( if (sz > 4096) प्रतिस्थापित करें if (false) )
• std::sort() ( naive_quick_sort(arr.begin(), arr.end()) std::sort(arr.begin(), arr.end()) साथ बदलें std::sort(arr.begin(), arr.end()) )

प्रकार int64 (एक संकेत के साथ) के 50,000,000 तत्वों की एक सरणी को सॉर्ट किया गया है। 10 प्रयोग किए जाते हैं, और औसत माना जाता है। मान अनियमित रूप से उत्पन्न होते हैं:

 std::tr1::uniform_int<Type> uniform( std::numeric_limits<Type>::min(), std::numeric_limits<Type>::max()); std::mt19937_64 engine; void generate(std::vector<Type>& v) { std::for_each(v.begin(), v.end(), [](Type& i) { i = uniform(engine); }); } 

यह न पूछें कि बड़े एंडियन से गोल-यात्रा यहां और पीछे क्यों की जाती है। यह जावा में एक अन्य कार्यक्रम के साथ तुलना करने के लिए किया गया था। समय को मापने के दौरान, केवल "शुद्ध समय" को ध्यान में रखा जाता है।

कंपाइलर वीएस 2011, 64-बिट। इंटेल कोर i5 2.53GHz प्रोसेसर, 4 कोर।

   async()   std::sort() --------- --------------- ------------ ------------ 1 2512 6555 7309 2 2337 6320 6977 3 2450 6516 7180 4 2372 6388 6933 5 2387 7074 7189 6 2339 7399 7040 7 2434 6875 7040 8 2562 7060 7187 9 2470 7050 7145 10 2422 6846 6898 --------- --------------- ------------ ------------  2428.5 6808.3 7089.8 

समय मिलीसेकंड में है।

यह तीन गुना तेजी से कहीं बाहर निकलता है। अजीब छोटे अंतराल std::sort() इस तथ्य के कारण सबसे अधिक संभावना है कि डेटा "अच्छा" है, और मेरा सरल कार्यान्वयन बस उन्हें वहन करता है। यह देखा जा सकता है कि std::sort() समय विचलन बहुत कम है। फिर भी, डेटा की परवाह किए बिना stl::sort() समय स्थिर है।

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

यदि आप रुचि रखते हैं, तो नीचे एक डेटा जनरेटर सहित इस बाइक का पूरा पाठ है।

डेटा संग्रह और पीढ़ी:

 call "%VS110COMNTOOLS%..\..\VC\vcvarsall.bat" amd64 && ^ cl /Ox /DWIN32 sort_async.cpp && ^ sort_async generate 

चेतावनी! जनरेटर 8 गीगा के लिए डेटा बनाएगा।

विधानसभा और प्रयोग:

 call "%VS110COMNTOOLS%..\..\VC\vcvarsall.bat" amd64 && ^ cl /Ox /DWIN32 sort_async.cpp && ^ sort_async 

फ़ाइल Sort_async.cpp:

 #include <vector> #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <iomanip> #include <future> #include <random> #include <chrono> #include <cstdlib> const int ITERATIONS_NUM = 10; const int DATA_SIZE = 50000000; typedef __int64 Type; inline void endian_swap(Type& x) { x = (0x00000000000000FF & (x >> 56)) | (0x000000000000FF00 & (x >> 40)) | (0x0000000000FF0000 & (x >> 24)) | (0x00000000FF000000 & (x >> 8)) | (0x000000FF00000000 & (x << 8)) | (0x0000FF0000000000 & (x << 24)) | (0x00FF000000000000 & (x << 40)) | (0xFF00000000000000 & (x << 56)); } std::tr1::uniform_int<Type> uniform( std::numeric_limits<Type>::min(), std::numeric_limits<Type>::max()); std::mt19937_64 engine; void generate(std::vector<Type>& v) { std::for_each(v.begin(), v.end(), [](Type& i) { i = uniform(engine); }); } void check_sorted(const std::vector<Type>& v, const std::string& msg) { for (auto i = 0; i < v.size() - 1; ++i) { if (v[i] > v[i + 1]) { std::cout << "\nUnsorted: " << msg << "\n"; std::cout << "\n" << i << "\n"; std::cout << v[i] << " " << v[i + 1] << "\n"; std::exit(1); } } } std::string data_file_name(const int i, const std::string& suffix) { std::ostringstream fmt; fmt << "trash_for_sort_" << i << suffix << ".bin"; return fmt.str(); } void save_file(std::vector<Type> array, const std::string& name) { std::for_each(array.begin(), array.end(), [](Type& i) { endian_swap(i); }); std::ofstream os(name.c_str(), std::ios::binary|std::ios::out); auto const bytes_to_write = array.size() * sizeof(array[0]); std::cout << "Saving " << array.size() << " bytes to " << name << "\n"; os.write((char *)&array[0], bytes_to_write); } int main_generate(int argc, char* argv[]) { std::cout << "Generation\n"; for (auto i = 0; i < ITERATIONS_NUM; ++i) { std::vector<Type> unsorted(DATA_SIZE); generate(unsorted); save_file(unsorted, data_file_name(i, "")); std::cout << "Sorting...\n"; std::sort(unsorted.begin(), unsorted.end()); check_sorted(unsorted, "check sorted array"); save_file(unsorted, data_file_name(i, "_sorted")); } return 0; } void load_file(std::vector<Type>& array, const std::string& name) { std::cout << "Loading " << name; array.resize(DATA_SIZE, 0); std::ifstream is(name.c_str(), std::ios::binary|std::ios::in); auto const to_load = array.size() * sizeof(array[0]); is.read((char *)&array[0], to_load); if (is.gcount() != to_load) { std::cerr << ", Bad file " << name << ", loaded " << is.gcount() << " words but should be " << to_load << "\n"; std::exit(1); } std::for_each(array.begin(), array.end(), [](Type& v){ endian_swap(v); }); } int naive_quick_sort(std::vector<Type>::iterator begin, std::vector<Type>::iterator end) { auto const sz = end - begin; if (sz <= 1) return 0; auto pivot = begin + sz/2; auto const pivot_v = *pivot; std::swap(*pivot, *(end - 1)); auto p = std::partition(begin, end, [&](const Type& a) { return a < pivot_v; } ); std::swap(*p, *(end - 1)); if (sz > 4096) { auto left = std::async(std::launch::async, [&]() { return naive_quick_sort(begin, p); }); naive_quick_sort(p + 1, end); } else { naive_quick_sort(begin, p); naive_quick_sort(p + 1, end); } return 0; } void quick_sort(std::vector<Type>& arr) { naive_quick_sort(arr.begin(), arr.end()); } int main(int argc, char* argv[]) { if (argc == 2 && !std::strcmp(argv[1], "generate")) return main_generate(argc, argv); std::vector<double> times; auto times_sum = 0.0; for (auto i = 0; i < ITERATIONS_NUM; ++i) { std::vector<Type> unsorted; load_file(unsorted, data_file_name(i, "")); std::vector<Type> verify; std::cout << ", "; load_file(verify, data_file_name(i, "_sorted")); check_sorted(verify, "verify array"); std::cout << ", Started"; auto start = std::chrono::high_resolution_clock::now(); quick_sort(unsorted); auto stop = std::chrono::high_resolution_clock::now(); std::cout << ", Stopped, "; auto duration = std::chrono::duration<double>(stop - start).count(); std::cout << duration; check_sorted(unsorted, "sorted array"); const auto match = unsorted == verify; std::cout << (match ? ", OK" : ", DON'T MATCH"); times.push_back(duration); times_sum += duration; std::cout << "\n"; } auto const average = times_sum / ITERATIONS_NUM; auto const max_element = *std::max_element(times.begin(), times.end()); auto const min_element = *std::min_element(times.begin(), times.end()); auto const average_fixed = (times_sum - max_element - min_element) / (ITERATIONS_NUM - 2); std::cout << "Average: " << average << "s, " << "Average without max/min: " << average_fixed << "s." << std::endl; } 

पर्दे की ओर, प्रोसेसर की लोडिंग की एक तस्वीर। जब सिस्टम एक टाईबैक का उपयोग कर रहा होता है, तो प्रत्येक पुनरावृत्ति में फटने स्पष्ट दिखाई देते हैं।



additive

माइक्रोसॉफ्ट का एक दिलचस्प लेख, डायनेमिक टास्क पैरेलिज्म, जिसमें मल्टी-थ्रेडेड क्विकॉर्ट का एक संस्करण भी दिखाया गया है।