विकास और निष्पादन की गति C में प्राप्त नहीं होती है

क्रॉस-प्लेटफ़ॉर्म और क्रॉस-हार्डवेयर ऑप्टिमाइज़ेशन के बारे में लेख की निरंतरता में, 5 फ़ील्ड्स और 10,000,000 पंक्तियों की तालिका के माध्यम से पूर्ण पास के साथ खोज कार्य के उदाहरण से, और इस कार्य की अनिवार्यता यहां तक ​​कि इंडेक्स खोज के साथ, मैं दिखाऊंगा कि 3.5-5.3 बार का उपयोग करके ऐसी खोज को कैसे तेज किया जाए। C ++ हार्डवेयर प्लेटफॉर्म की परवाह किए बिना।
पिछले लेख में, हमने खोज को 1.3 गुना बढ़ाने में कामयाब रहे: GitHub.com
हम वास्तविक रूप से भाषा निर्माण का वर्णन नहीं करेंगे, लेकिन वास्तविक कार्य के चरणों में से एक को हल करते समय C ++ के फायदे बताएंगे।
हम अभी भी MSVC11 (MSVS2012) और GCC 4.7.2 के तहत क्रॉस-प्लेटफॉर्म लिखते हैं, और हम उनमें C का उपयोग करते हैं और आंशिक रूप से लागू मानक C ++ 11।
समझ की सादगी के लिए, हम अभी भी सूचकांक खोज के बिना लिख ​​रहे हैं, लेकिन इस समाधान का उपयोग बाद में सूचकांक खोज में किया जाएगा।

1. सी ++ में कट्टर समाधान

यह सी में वास्तव में कट्टर समाधान की तरह दिखता था। इसका कारण यह है कि दुर्भाग्य से सी डेवलपर्स के लिए, आपको 3840 फ़ंक्शन बनाने और कहीं भी कोई गलती नहीं करनी है। जबकि सी-डेवलपर्स उन्हें लिखते हैं, हम उन्हें बहुत सम्मान के साथ व्यवहार करेंगे, और मैं दिखाऊंगा कि कैसे सी ++ संकलक आपके लिए इन 3840 कार्यों को लिख सकते हैं। वह इसे जल्दी नहीं करेगा, लेकिन सी-डेवलपर्स की तुलना में तेजी से और अधिक सटीक रूप से परिमाण के आदेश उन्हें लिखेंगे।
यह बहुत सरल है, डीबीएमएस के सिद्धांत में एक विधेय ( selectivity ) की चयनात्मकता जैसी कोई चीज है - एक स्थिति (विधेय) के अनुसार उपयुक्त तालिका पंक्तियों का प्रतिशत। स्थिति की चयनात्मकता कम है, पहले इसकी तुलना करना आवश्यक है, और जितनी जल्दी हम महसूस करेंगे कि रेखा फिट नहीं होती है। यानी निम्नलिखित परिस्थितियों में तुलना से छुटकारा पाएं।
वास्तविक DBMS में, इसके लिए, ऑप्टिमाइज़र आंकड़े एकत्र करता है और डेटा वितरण अनुसूची के आधार पर चयनात्मकता की गणना के लिए आवश्यक सूत्र का चयन करता है। मुझे लगता है कि खेतों की गणना के साथ असतत गणित और कॉम्बिनेटरिक्स आज आपके लिए पर्याप्त हैं, इसलिए सादगी के लिए हम डेटा के समान वितरण की गणना से कार्डिनैलिटी के लिए चयनशीलता पर विचार करेंगे। (कॉलम की कार्डिनैलिटी कॉलम में अद्वितीय मूल्यों का प्रतिशत है।)
चयनात्मकता (पंक्तियों की संख्या) के बराबर होगी:
selectivity = c_array_size * (1 + field.end – field.begin) / cardinality;
सरणी का आकार और समान रूप से वितरित डेटा के लिए कार्डिनैलिटी संकलन चरण में हमारे लिए जाना जाता है। और हम रनटाइम पर प्रत्येक क्षेत्र के लिए खोज स्थितियों की सीमाएं प्राप्त करते हैं और चयनात्मकता की गणना करते हैं।
फिर हम छोटी से शुरू होने वाली चयनात्मकता बढ़ाने के लिए खेतों का चयन करते हैं। और चयनित फ़ील्ड संख्याओं के क्रम के आधार पर, हम सबसे इष्टतम फ़ंक्शन के संख्यात्मक सूचकांक बनाते हैं, जिसे हम तब खोज करने के लिए कहते हैं।
खोज स्थितियों, या बल्कि बहुरूपी कक्षाओं के प्रत्येक संस्करण के लिए अनुकूलित कार्य, हम दो नेस्टेड टेम्पलेट के साथ उत्पन्न करते हैं:

1. खोज स्थितियों की उपस्थिति के लिए सभी विकल्पों की गणना करना (जैसा कि पिछले C ++ समाधान में मामला था)
2. खोज शब्दों के क्रम के सभी विकल्पों की गणना करना

कुल मिलाकर, (2^5)*5! = 32*120 = 3840 का एक सरणी बनाया और आबाद किया गया है (2^5)*5! = 32*120 = 3840 (2^5)*5! = 32*120 = 3840 वस्तुओं के साथ अलग-अलग कार्यान्वयन, लेकिन एक सामान्य आधार सार पूर्वज के साथ।
एक क्षेत्र के लिए अधिक से अधिक के लिए रेंज चेक हमेशा एक साथ चलते हैं। हम स्वतंत्र रूप से विनिमय नहीं करेंगे या एक क्षेत्र के लिए न्यूनतम और अधिकतम मूल्यों के सत्यापन को संरेखित नहीं करेंगे ताकि संकलन समय में देरी न हो।
अब देखते हैं कि कोड कैसा दिखेगा।

2. निर्भरता कम करना

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

 /* Row */ struct T_cash_account_row { // Fields: enum T_field_enum { amount_of_money_e, gender_e, age_e, code_e, height_e, /*<<<<<- add fields here (with index) */ last_e /*<<<<<- add included fields here (without index) */ }; static_assert(last_e > 0, "Number of indexed fields in enum of T_cash_account_row must be greater than 0!"); unsigned code:20; // 0 - 1000000 unsigned gender:1; // 0 - 1 unsigned age:7; // 0 - 100 unsigned amount_of_money:20; // 0 - 1000000 unsigned height:9; // 0 – 300 // Get field value template<int field_enum> inline typename std::enable_if<field_enum == code_e, decltype(code)>::type get_field_value() const { return code; } template<int field_enum> inline typename std::enable_if<field_enum == gender_e, decltype(gender)>::type get_field_value() const { return gender; } template<int field_enum> inline typename std::enable_if<field_enum == age_e, decltype(age)>::type get_field_value() const { return age; } template<int field_enum> inline typename std::enable_if<field_enum == amount_of_money_e, decltype(amount_of_money)>::type get_field_value() const { return amount_of_money; } template<int field_enum> inline typename std::enable_if<field_enum == height_e, decltype(height)>::type get_field_value() const { return height; } template<int field_enum> inline typename std::enable_if<field_enum == last_e, bool>::type get_field_value() const { return true; } static_assert(5 == last_e, "Add/delete new field-case and correct this assert!"); }; /* ----------------------------------------------------------------------- */ 

enum T_field_enum डिफ़ॉल्ट रूप से enum T_field_enum में हमेशा 0 ( C ++ 03 7.2 गणन घोषणापत्र ) से शुरू होने वाले क्रम में मान होते हैं।
std::enable_if<> #include <type_traits> से #include <type_traits> लाइब्रेरी आपको कुछ विशेष पैरामीटर पैरामीटर मानों के लिए केवल फ़ंक्शन / कक्षाओं के उदाहरण प्राप्त करने की अनुमति देता है। अन्यथा, एक प्रतिस्थापन त्रुटि तात्कालिकता के दौरान होती है, और SFINAE के सिद्धांत के अनुसार (प्रतिस्थापन-विफलता-एक-न-एक त्रुटि) , जब एक प्रतिस्थापन त्रुटि होती है, एक संकलन त्रुटि नहीं होती है, और एक फ़ंक्शन उदाहरण बस बनाया जाता है। मानक में अधिक विवरण ( C ++ 03 14.8.2 टेम्पलेट तर्क कटौती )।
यह विभिन्न प्रकार के आवश्यक क्षेत्रों को एक्सेस करने के लिए आवश्यक है, जैसे कि टेम्पलेट टेम्पलेट पैरामीटर, इस तरह से:
auto code = row->get_field_value<T_cash_account_row::code_e>();
हमारे मामले में, सभी 5 फ़ील्ड एक ही प्रकार के हैं और कोई भी बिना std::enable_if<> , लेकिन हम आगे सोचते हैं। मेरे उदाहरण में, आप किसी भी 5 फ़ील्ड को बदल सकते हैं और गेटर्स संकलित करेंगे और ठीक काम करेंगे। मान लीजिए कि यदि हमने उन्हें एक टेम्पलेट फ़ंक्शन के विशेषज्ञता के माध्यम से बनाया है, तो हमें विभिन्न प्रकारों तक पहुंचते समय त्रुटियां मिलेंगी, उदाहरण के लिए, ऐसा कोड संकलित नहीं होगा:

 /* Row */ struct T_cash_account_row { // Fields: enum T_field_enum { amount_of_money_e, gender_e, age_e, code_e, height_e, /*<<<<<- add fields here (with index) */ last_e /*<<<<<- add included fields here (without index) */ }; static_assert(last_e > 0, "Number of indexed fields in enum of T_user_row must be greater than 0!"); unsigned code:20; // 0 - 1000000 unsigned gender:1; // 0 - 1 unsigned age:7; // 0 - 100 unsigned amount_of_money:20; // 0 - 1000000 int height; // 0 – 300 // Get field value template<int field_enum> inline unsigned get_field_value(); template<int field_enum> inline int get_field_value(); static_assert(5 == last_e, "Add/delete new field-case and correct this assert!"); }; template<> inline unsigned T_cash_account_row::get_field_value<T_cash_account_row::code_e>() { return code; } template<> inline unsigned T_cash_account_row::get_field_value<T_cash_account_row::gender_e>() { return gender; } template<> inline unsigned T_cash_account_row::get_field_value<T_cash_account_row::age_e>() { return age; } template<> inline unsigned T_cash_account_row::get_field_value<T_cash_account_row::amount_of_money_e>() { return amount_of_money; } template<> inline int T_cash_account_row::get_field_value<T_cash_account_row::height_e>() { return height; } template<> inline unsigned T_cash_account_row::get_field_value<T_cash_account_row::last_e>() { return 1; } /* ----------------------------------------------------------------------- */ int main() { T_cash_account_row *row = new T_cash_account_row; auto code = row->get_field_value<T_cash_account_row::code_e>(); return 0; } 

कंपाइलर स्वाभाविक रूप से get_field_value<>() फ़ंक्शन के लिए अस्पष्ट कॉल के बारे में एक त्रुटि फेंक देगा। Ideone.com
हमारा संस्करण ठीक संकलित करता है: ideone.com
हमने इसे गेटर्स के साथ सही कर लिया है, अब हम पिछले लेख से पदोन्नति के समान टेम्पलेट के अनरोलिंग का उपयोग करेंगे, लेकिन निर्माणकर्ता के लिए नहीं, बल्कि फ़ंक्टर के लिए (एक फ़न्क्टर एक ओवरलोड ऑपरेटर कॉल operator()(…) साथ एक वर्ग है):

 // The templated functor of unrolling of the input templated functor (reusable) template<unsigned unroll_count, template<unsigned> class T> struct T_unroll_functor { T_unroll_functor<unroll_count-1, T> next_unroll; T<unroll_count-1> functor; template<typename T1, typename T2> inline bool operator()(T1 const& val1, T2 const& val2) { return next_unroll(val1, val2) && functor(val1, val2); } }; // End of unroll template<template<unsigned> class T> struct T_unroll_functor<0, T> { template<typename T1, typename T2> inline bool operator()(T1 const&, T2 const&) { return true; } }; // ------------------------------------------------------------------------- 

इस पदोन्नति के last_e , हम last_e टेम्पलेट के मूल्य के आधार पर प्रत्येक फ़ील्ड के लिए तुलना का विस्तार करेंगे और अपने टेम्पलेट last_e माध्यम से फ़ील्ड तक पहुंच प्राप्त करेंगे।
और हम struct T_test_pred को निम्नानुसार तैनात करेंगे:

 // The filters for each search variant (range_filters) template<typename T_row, unsigned index_pred> struct T_custom_filter : T_filter<T_row> { // Test predicates functor for unrolling template<unsigned field_num> struct T_test_pred { bool inline operator()(T_row *const __restrict row, T_range_filters *const __restrict range_filters) const { typedef typename T_row::T_field_enum T_field_enum; // Without fields where use_filter==0 return ( T_filter<T_row>::template T_get_use_filter<index_pred, field_num>::value || (row->template get_field_value<static_cast<T_field_enum>(field_num)>() >= range_filters->begin.template get_field_value<static_cast<T_field_enum>(field_num)>()&& row->template get_field_value<static_cast<T_field_enum>(field_num)>() <= range_filters->end.template get_field_value<static_cast<T_field_enum>(field_num)>()) ); } }; // ----------------------------------------------------------------------- // search virtual size_t search(T_row *const __restrict array_ptr, const size_t c_array_size, T_row *const __restrict result_ptr, T_range_filters *const __restrict range_filters) final { size_t result_size = 0; size_t i; // loop index T_unroll_functor<T_row::last_e, T_test_pred> test_predicate; for(i = 0; i < c_array_size; ++i) { if(test_predicate(array_ptr + i, range_filters)) result_ptr[result_size] = array_ptr[i], ++result_size; } return result_size; } }; // ------------------------------------------------------------------------- 

मैं यह भी ध्यान देता हूं कि अब कक्षाओं में T_filter<>, T_custom_filter<> T_optimized_search<> एक टेम्प्लेट पैरामीटर T_row , जिसमें तालिका पंक्ति प्रकार पारित हो गया है - हमारे मामले में, T_cash_account_row ।
अब टेबल फ़ील्ड्स की संख्या, नाम और प्रकार के सभी परिवर्तन T_cash_account_row अंदर विशेष रूप से केंद्रित हैं, और संपूर्ण खोज कोड स्वचालित रूप से टेम्प्लेट कक्षाओं से उत्पन्न होता है, आपको बस वांछित लाइन के प्रकार के साथ टेम्प्लेट की आवश्यकता होती है:
T_optimized_search<T_cash_account_row> optimized_search; // C++ optimized search
यहाँ परिणामी कार्य कोड का लिंक दिया गया है: GitHub.com
यह उदाहरण स्पष्ट रूप से दिखाता है कि क्यों कोड टीम-लीड और प्रदर्शन-वास्तुकार के महत्वपूर्ण क्षेत्रों में न केवल मॉड्यूल के बाहरी इंटरफेस पर ध्यान देना चाहिए, बल्कि इन इंटरफेस के माध्यम से प्रसारित वस्तुओं के प्रकारों पर भी ध्यान देना चाहिए। हमारे मामले में, ये हैं: T_cash_account_row T_range_filters । T_cash_account_row में टेम्पलेट T_cash_account_row माध्यम से मापदंडों को पारित करने की क्षमता निर्धारित करने के बाद, हम टेम्पलेट प्रमोशन के माध्यम से मॉड्यूल के डेवलपर द्वारा और अधिक लचीले कार्यान्वयन के साथ-साथ टीडीडी परीक्षण में विकास तकनीक का उपयोग करते समय परीक्षणों का अधिक लचीला कार्यान्वयन निर्धारित करते हैं, जिसे मैं अगले लेख में दिखाऊंगा।
कंपाइलर MSVC11 (MSVS2012) और CPU कोर i5 K750 के एक कोर पर, परिणाम इस प्रकार है:

उत्पन्न पंक्तियाँ: 10,000,000
C ++ - खोज रहा है ...
C ++ - अनुकूलित खोज में 0.056000 सेकंड लगे।
मिली पंक्तियाँ: 38
सी-सर्चिंग ...
सी-सर्च में 0.074000 सेकंड लगे।
C ++ की तुलना में C ++ तेज: 1.321429 बार
मिली पंक्तियाँ: 38

जैसा कि आप देख सकते हैं, C ++ कोड C कोड की तुलना में 1.3 गुना तेज है। test_predicate फ़ंक्शन का परिणामी कोडांतरक कोड अभी भी पिछले C ++ संस्करण, test_pradicate_enum_cpp.asm के समान है ।
"TortoiseDiff से विस्मयादिबोधक चित्र"

लेकिन अब हमने सभी परिवर्तनों को एक स्थान पर केंद्रित कर दिया है, जिससे इस खोज मॉड्यूल के उपयोग में बहुत सुविधा होगी।
इसके अलावा, हमने एक और, और अधिक उत्पादक अनुकूलन के लिए कोड तैयार किया।

3. त्वरण 3.5 से - 5.3 बार

अक्सर C ++ पर ऐसे लेख होते हैं जहां संकलन-समय की गणना या, उदाहरण के लिए, टेम्प्लेट पर प्रमुख संख्याओं की खोज पर विचार किया जाता है। लेख दिलचस्प हैं, लेकिन जैसा कि लेखक खुद नोटिस करते हैं: "मैं आपको बताऊंगा कि पूरी तरह से बेकार चीज कैसे करें।"
मैं आपको बताता हूं कि संकलन का उपयोग करके संकलन-समय की गणना और अनुकूलन से ध्यान देने योग्य खोज त्वरण कैसे प्राप्त करें।

3.1 सरल टेम्पलेट गणना

आइए हम जो कुछ भी चाहते हैं उसके सरलतम से शुरू करें, हम संकलन-समय की तथ्यात्मक गणना को लागू करते हैं:

 template <unsigned N> struct factorial : std::integral_constant<unsigned, N * factorial<N-1>::value> {}; template <> struct factorial<0> : std::integral_constant<unsigned, 1> {}; 

स्थैतिक सरणी std::array<> के बराबर तत्वों की संख्या (2^5)*5! = 3840 साथ बनाने के लिए हमें भाज्य गणना की आवश्यकता है (2^5)*5! = 3840 (2^5)*5! = 3840 ।
असतत गणित और कॉम्बिनेटरिक्स से यह ज्ञात है कि अद्वितीय तत्वों के विभिन्न क्रमपरिवर्तन की संख्या उनकी संख्या के भाज्य के बराबर है। और तत्वों की उपस्थिति के लिए विकल्पों की संख्या तत्वों की संख्या के 2 डिग्री है। (बेशक, यह हमारे लिए बिल्कुल महत्वपूर्ण नहीं है कि लापता तत्वों को कैसे पुन: व्यवस्थित किया जाता है, और अतिरिक्त विकल्पों की अनुपस्थिति संकलन को गति दे सकती है, लेकिन मैं इस लेख को यथासंभव सरल बनाने की कोशिश कर रहा हूं।)
अब देखते हैं कि संरचना के अंदर क्या अनुकूलन होंगे
struct T_custom_filter पर struct T_custom_filter ।
सबसे पहले, यह अब index_order पैरामीटर को भी स्वीकार करता है। और दूसरी बात यह है कि इसमें खोजे गए अनवांटेड फनकार को बदल दिया गया है।

 // The filters for each search variant (range_filters) template<typename T_row, unsigned index_pred, unsigned index_order = 0> struct T_custom_filter : T_filter<T_row> { // Test predicates functor for unrolling template<unsigned field_num> struct T_test_pred { bool inline operator()(T_row *const __restrict row, T_range_filters *const __restrict range_filters) const { typedef typename T_row::T_field_enum T_field_enum; // Without fields where use_filter==0 enum { ordered_field_number = T_filter<T_row>::template T_number_field<index_order, field_num>::value }; return ( T_filter<T_row>::template T_get_use_filter<index_pred, ordered_field_number>::value || (row->template get_field_value<static_cast<T_field_enum>(ordered_field_number)>() >= range_filters->begin.template get_field_value<static_cast<T_field_enum>(ordered_field_number)>() && row->template get_field_value<static_cast<T_field_enum>(ordered_field_number)>() <= range_filters->end.template get_field_value<static_cast<T_field_enum>(ordered_field_number)>()) ); } }; // ----------------------------------------------------------------------- // search virtual size_t search(T_row *const __restrict array_ptr, const size_t c_array_size, T_row *const __restrict result_ptr, T_range_filters *const __restrict range_filters) final; }; // ------------------------------------------------------------------------- 

पहले की तरह, T_get_use_filter टेम्पलेट किसी दिए गए index_pred इंडेक्स के लिए number_filter फ़ील्ड द्वारा फ़िल्टर का उपयोग (या उपयोग नहीं) के लिए एक ध्वज देता है।

 // whether to use the filter for a given predicate? (strictly at compile time) template <unsigned index_pred, unsigned number_filter> struct T_get_use_filter : std::integral_constant<bool, !(index_pred & 1<<number_filter)> {}; 

T_number_field<> टेम्प्लेट, index_order आधार पर - फ़ील्ड्स की तुलना करने के लिए इंडेक्स और field_num के फ़ील्ड नंबर से, हमें ordered_field_number नंबर ordered_field_number प्राप्त करने के लिए फ़ील्ड नंबर get_field_value<static_cast<T_field_enum>(ordered_field_number)>() ।

3.2 अधिक जटिल टेम्पलेट गणना

अब और कठिन। हम टेम्प्लेट क्लास T_number_field<> में फ़ील्ड ऑर्डर की गणना को लागू करते हैं। फ़ील्ड ऑर्डर इंडेक्स index_order निम्नानुसार उत्पन्न होता है - उदाहरण के लिए, 5 फ़ील्ड के लिए इंडेक्स निम्न सूत्र का उपयोग करके संकलित किया गया है:
index_order = field0 + 5*field1 + 5*4*field2 + 5*4*3*field3 + 5*4*3*2*field4;
जहां फ़ील्ड 1 - 0 से 4 तक फ़ील्ड नंबर (5 उपलब्ध में से), तुलना करते समय पहले आ रहा है; फ़ील्ड 2 - 0 से 3 तक फ़ील्ड संख्या (शेष 4 में से), तुलना करते समय दूसरा आ रहा है; ...; और फ़ील्ड 5 पिछले से आने वाले (0 शेष से) फ़ील्ड की संख्या है, क्योंकि यह हमेशा 0 होता है, फिर इसे छोड़ा जा सकता है:
index_order = field0 + 5*field1 + 5*4*field2 + 5*4*3*field3;
या, जो समान है:
index_order = field0 + 5*(field1 + 4*(field2 + 3*(field3)));
किसी के लिए यह आसान हो सकता है कि किसी एक संख्या के रूप में इंडेक्स_ऑर्डर के वैल्यू को परिकलस सिस्टम के एक वैरिएबल बेस के साथ, जहां field0 0 बेस 5 के साथ पहला अंक है (5 मान 0-4 ले सकते हैं), field0 1 में बेस 4 के साथ दूसरा अंक है (4 मान ले सकते हैं -3), और इसी तरह। इस प्रकार (5!) संयोजन हम किसी भी क्षेत्र क्रमपरिवर्तन को सांकेतिक कर सकते हैं। बेहतर समझ के लिए, संभावना सिद्धांत की मूल बातें या असतत गणित से खोज के साथ खुद को परिचित करना उचित है।
विज़ुअली, इसे निम्नानुसार दर्शाया जा सकता है: कोष्ठक () उपलब्ध सबसे कम प्राथमिकता मूल्य (उच्चतम प्राथमिकता), वर्ग [] - उपलब्ध से इसकी संख्या और घुंघराले {} - क्षेत्र की वास्तविक संख्या को दर्शाते हैं। उदाहरण के लिए, शुरू में हमारे पास निम्न प्राथमिकताओं के साथ 5 क्षेत्र हैं: 5, 3, 1, 2, 4

 फ़ील्ड संख्या: 0 1 2 3 4
 प्राथमिकता की तुलना करें: 5 3 (1) 2 4 - [2] - वर्तमान क्षेत्र संख्या (फ़ील्ड 0) {2}
 प्राथमिकता की तुलना करें: 5 3 (2) 4 - [2] - वर्तमान क्षेत्र संख्या (फ़ील्ड 1) {3}
 प्राथमिकता की तुलना करें: 5 (3) 4 - [1] - वर्तमान क्षेत्र संख्या (फ़ील्ड 2) {1}
 प्राथमिकता की तुलना करें: 5 (4) - [1] - वर्तमान क्षेत्र संख्या (फ़ील्ड 3) {4}
 प्राथमिकता की तुलना करें: (5) - [0] - वर्तमान क्षेत्र संख्या (फ़ील्ड 4) {0}

index_order = field0 + 5*(field1 + 4*(field2 + 3*(field3))); में संख्याओं को प्रतिस्थापित करना: index_order = field0 + 5*(field1 + 4*(field2 + 3*(field3)));
हमें सूचकांक मूल्य मिलता है: index_order = 2 + 5*(2 + 4*(1 + 3*(1))) = 92;
बाद में हम दिखाएंगे कि रन-टाइम फ़ंक्शन T_optimized_search::get_index_order(). में यह कैसे लागू किया जाता है T_optimized_search::get_index_order().
अब, पदोन्नति के परिणामस्वरूप, यह सूचकांक संकलन चरण में हमारे लिए जाना जाता है, और उलटा समस्या यह है कि संकलन के समय में प्रत्येक क्षेत्र के लिए सीरियल नंबर कैसे प्राप्त किया जाए।
सबसे पहले, वर्ग कोष्ठक में संख्याओं को प्राप्त करना सीखें []। हमारे विशेष मामले में, "वर्तमान क्षेत्र संख्याएँ" निम्न प्रकार से पाई जाती हैं, जो हमें index_order = 2 + 5*(2 + 4*(1 + 3*(1))) = 92 लिए index_order = 2 + 5*(2 + 4*(1 + 3*(1))) = 92 :

 field0 = index_order% 5 = 92% 5 = 2;
 field1 = (index_order / 5)% 4 = (92/5)% 4 = 2;
 field2 = (index_order / (5 * 4))% 3 = (92/5 * 4)% 3 = 1;
 फ़ील्ड 3 = (इंडेक्स_ऑर्डर / (5 * 4 * 3))% 2 = (92/5 * 4 * 3)% 2 = 1;
 फ़ील्ड 4 = 0;

संकलन-समय में, निम्न टेम्पलेट वर्ग ऐसा करता है:

 // Get the sequence number the remaining field for the number_filter, after removal of all previous template <unsigned index_order, unsigned number_filter, unsigned index = T_row::last_e> struct T_number_remaining_field : std::integral_constant<unsigned, T_number_remaining_field<index_order / index, number_filter - 1, index - 1>::value> {}; // End of unroll template <unsigned index_order, unsigned index> struct T_number_remaining_field<index_order, 0, index> : std::integral_constant<unsigned, index_order % index> {}; // ------------------------------------------------------------------------- 

और हम T_number_remaining_field<index_order, number_filter>::value बराबर "वर्तमान फ़ील्ड नंबर" का मान प्राप्त करते हैं, इस तरह से टेम्पलेट को त्वरित रूप से T_number_remaining_field<index_order, number_filter>::value ।
एक ऐसा क्षण है जहां कुछ भ्रमित हो सकते हैं: कोई सोच सकता है कि ( number_filter=0 ), यानी। T_number_remaining_field<index_order, 0>::value दो मापदंडों के साथ आंशिक विशेषज्ञता को तुरंत लागू किया जाता है:
template <unsigned index_order, unsigned index> struct T_number_remaining_field<index_order, 0, index>
जहाँ index_order को index_order और 0 को index में प्रतिस्थापित किया जाता है। लेकिन ऐसा है नहीं!
मानक ( C ++ 03 14.8.2 टेम्पलेट तर्क कटौती ) के अनुसार, पहले डिफ़ॉल्ट मानों को index = T_row::last_e लिए प्रतिस्थापित किया index = T_row::last_e और वास्तव में हमारी तात्कालिकता T_number_remaining_field<index_order, 0, T_row::last_e>::value । और फिर विशेषज्ञता के लिए एक अपील है:
template <unsigned index_order, unsigned index> struct T_number_remaining_field<index_order, 0, index>
और 5 क्षेत्रों के शून्य वर्तमान क्षेत्र संख्या ( T_row::last_e=5 ) के लिए हमें आवश्यक रूप से index_order % 5 मिलता है।
हमने वर्ग कोष्ठक में उन लोगों के "वर्तमान क्षेत्र संख्या" को खोजने के लिए एक विधि लागू की है। अब हमें घुंघराले ब्रेसेस {} में वास्तविक क्षेत्र संख्याओं की प्राप्ति को लागू करने की आवश्यकता है।
जैसा कि हमने अपने दृश्य प्रतिनिधित्व से देखा, वर्ग कोष्ठक में "" वर्तमान क्षेत्र संख्याएँ [] हमेशा कर्ली ब्रेसिज़ में वास्तविक फ़ील्ड संख्याओं से मेल नहीं खाती {}। यदि आप नीचे से ऊपर तक बढ़ते क्रम में गिने हुए कार्डों के एक डेक की कल्पना करते हैं, तो शुरू में उनकी संख्या डेक में उनके क्रम के साथ मेल खाएगी। लेकिन कार्डों को बीच से बाहर निकालने से, जो कार्ड उनके ऊपर हैं वे हर बार डेक में यूनिट संख्या को उनकी वास्तविक संख्या के सापेक्ष कम कर देंगे।
हमारे मामले में, यह इस तथ्य की ओर जाता है कि सभी क्षेत्रों में वास्तविक संख्या {} और निम्न प्राथमिकता मूल्य () (उच्च प्राथमिकता, जो पहले हटा दी गई थी), एक "वर्तमान क्षेत्र मूल्य" [], जिसका वास्तविक संख्या और प्राथमिकता मूल्य कम होता है अधिक। इस तरह के ऑफसेट की गणना निम्नलिखित टेम्पलेट कक्षाओं द्वारा की जाती है:

  // Get 1 or 0 offset if current_field (for number_filter) affect to number_field template <unsigned index_order, unsigned number_filter, unsigned number_field> struct T_offset { enum { current_field = T_number_remaining_field<index_order, number_filter>::value, value = (current_field <= number_field)?1:0 }; }; // Get offset of number_field (enum in row-type) for number_filter template <unsigned index_order, unsigned number_filter, unsigned number_field> struct T_offset_number_field { enum { offset = T_offset<index_order, number_filter-1, number_field>::value, value = T_offset_number_field<index_order, number_filter-1, number_field + offset>::value + offset }; }; // End of unroll template <unsigned index_order, unsigned number_field> struct T_offset_number_field<index_order, 0, number_field> : std::integral_constant<unsigned, 0> {}; 

और अंत में, हम निम्नलिखित टेम्पलेट वर्ग के साथ वास्तविक क्षेत्र संख्या प्राप्त करते हैं:

  // (Main) Get number of field (enum in row-type) for number_filter template <unsigned index_order, unsigned number_filter> struct T_number_field { enum { remaining_field = T_number_remaining_field<index_order, number_filter>::value, value = remaining_field + T_offset_number_field<index_order, number_filter, remaining_field>::value }; }; // ------------------------------------------------------------------------- 

हो गया।

3.3 नेस्टेड टेम्पलेट प्रचार

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

 template<typename T_row> class T_optimized_search { // unroll tamplates template<unsigned index_pred> struct T_unroll_find { template<unsigned index_order> struct T_unroll_order { template<typename T> T_unroll_order(T &filters) { filters[index_pred + index_order*(1<<T_row::last_e)].reset( new T_custom_filter<T_row, index_pred, index_order>() ); } }; T_unroll_constructor<factorial<T_row::last_e>::value, T_unroll_order> fill_ordered_filter; template<typename T> T_unroll_find(T &filters) : fill_ordered_filter(filters) {} }; // ------------------------------------------------------------------------- std::array<std::unique_ptr<T_filter<T_row>>, (1<<T_row::last_e)*factorial<T_row::last_e>::value> filters; T_unroll_constructor< 1<<T_row::last_e, T_unroll_find> fill_filter; public: T_optimized_search() : fill_filter(filters) {} // C++ optimized search inline size_t search(T_row *const __restrict array_ptr, const size_t c_array_size, T_row *const __restrict result_ptr, T_range_filters *const __restrict range_filters) { auto const& filter = filters[T_filter<T_row>::get_index_pred(range_filters) + T_filter<T_row>::get_index_order(range_filters)*(1<<T_row::last_e)]; return filter->search(array_ptr, c_array_size, result_ptr, range_filters); } }; // ------------------------------------------------------------------------- 

compile-time struct T_unroll_find<> , struct T_unroll_order<> .
run-time get_index_pred() – , get_index_order() – .
:

  // Get index of T_test_pred version for current search range static inline const unsigned get_index_pred(T_range_filters *const __restrict range_filters) { unsigned result = 0; for(size_t i = 0; i < T_row::last_e; ++i) result |= range_filters->use_filter[i]?(1<<i):0; return result; } // ------------------------------------------------------------------------- 

get_index_order() . , struct T_cash_account_row get_bitf_size() – ( , switch/case, constexpr, .. compile-time, MSVC11 ):

 /* Row */ struct T_cash_account_row { ... // Get cardinality template<int field_enum> // constexpr // not supported in the MSVS2012(MVCC11) static inline const unsigned int get_bitf_size() { return (field_enum == gender_e)? 1: (field_enum == age_e)? 100: (field_enum == height_e)? 300: (field_enum == code_e)? 1000000: (field_enum == amount_of_money_e)?1000000: 0; static_assert(5 == last_e, "Add/delete new field-case and correct this assert!"); } }; 

( ):
selectivity = c_array_size * (1 + field.end – field.begin) / cardinality;
, /:

  // The unrolling filling of selectivity in a compile-time template<unsigned field_num> struct T_selectivity_fill { T_selectivity_fill(std::map<unsigned, unsigned> *const __restrict ordered_filters, T_range_filters *const __restrict range_filters) { // selectivity for each field-filter const unsigned selectivity = range_filters->use_filter[field_num]? ((1 + range_filters->end.template get_field_value<field_num>() - range_filters->begin.template get_field_value<field_num>() )*c_array_size / T_row::template get_bitf_size<field_num>()) // cardinality :c_array_size; ordered_filters->insert(std::make_pair(field_num, selectivity)); } }; // Get index of T_test_pred version for current search range static inline const unsigned get_index_order( T_range_filters *const __restrict range_filters) { unsigned result = 0; std::map<unsigned, unsigned> ordered_filters; T_unroll_constructor<T_row::last_e, T_selectivity_fill> selectivity_fill(&ordered_filters, range_filters); unsigned multiplexor = 1; for(size_t i = 0; i < T_row::last_e; ++i) { unsigned cur_index = 0, min_index = 0; unsigned field_num = ordered_filters.cbegin()->first; unsigned min = c_array_size; for(auto const& it : ordered_filters) { if (it.second < min) min = it.second, field_num = it.first, min_index = cur_index; ++cur_index; } ordered_filters.erase(field_num); result += min_index*multiplexor; multiplexor *= (T_row::last_e - i); } return result; } // ------------------------------------------------------------------------- 

std::map<> , . , , std::map<> , . . , get_index_order , :
index_order = field1 + 5*(field2 + 4*(field3 + 3*(field4)));
3840 , run-time , .
test_predicate C++ – , : github.com asm .
« TortoiseDiff»

4.

C++: GitHub.com
GCC4.7.2 –O3 –march=native, CPU Core i5 K750 exe- 1.3 :

Generated rows: 10000000
C++-Searching…
C++-optimized search took 0.017000 seconds.
Found rows: 38
C-Searching…
C-search took 0.090000 seconds.
The C++ faster than C: 5.294118 times
Found rows: 38

MSVC11(MSVS2012) /O2 /Ob2 /Oi, CPU Core i5 K750 exe- 1.42 :

उत्पन्न पंक्तियाँ: 10000000
C ++ - खोज ...
C ++ - अनुकूलित खोज में 0.021000 सेकंड लगे।
मिली पंक्तियां: 38
सी-सर्चिंग ...
सी-सर्च में 0.074000 सेकंड लगे।
C ++ की तुलना में C ++ तेज: 3.523809 बार
मिली पंक्तियाँ: 38

जैसा कि हम देख सकते हैं, रनटाइम सी में 74 सेंट से गिर गया, सी ++ में 21ms तक, अर्थात्। गति 3.5 गुना बढ़ गई । बहुत बढ़िया। GCC , 5.3 . - , SIMD- cache-prefetch. PGO , , 3840 .
, , C++. C++ – C.
, C , . क्योंकि , C , , .
C: GitHub.com
C- diff : GitHub.com
GCC4.7.2 –O3 –march=native, CPU Core i5 K750 :

Generated rows: 10000000
C-optimized-Searching…
C-optimized-search took 0.049000 seconds.
Found rows: 38
C-Searching…
C-search took 0.086000 seconds.
The C++ faster than C: 1.755102 times
Found rows: 38

MSVC11 /O2 /Ob2 /Oi, CPU Core i5 K750 :

Generated rows: 10000000
C-optimized-Searching…
C-optimized-search took 0.045000 seconds.
Found rows: 38
C-Searching…
C-search took 0.074000 seconds.
The C++ faster than C: 1.644444 times
Found rows: 38

C C++ 2 — 3 .
GCC C 1.8 5.3 C++, MSVC C 1.6 3.5 C++. C C++ , .

5. निष्कर्ष

, C++– - 3.5-5.3 .
C, C++, .. . C – C++– – , – copy-paste.
, Java C#, .. generics , . Java C# – .
, - Index Hash Join Bitmap AND, Index Organized Tables Index Only Scan. , -. 0.15 3.6 Core i5 K750, , . GPU – distributed states, . web- FastCGI boost::asio. .