🎟️ 🧟 👩‍🎨 टेम्पलेट्स या कांटा बम संकलन चरणों के बारे में कुछ विवरण 👶🏼 👆🏿 🎚️

हाल ही में सकारात्मक टेम्पलेट्स को इंस्टेंट करने में दिलचस्पी बनी। इंटरनेट पर शब्द कोड ब्लोट का उपयोग किया जाता है । C ++ के लिए, इसका मतलब संकलक द्वारा उत्पन्न कोड में ~~अनियंत्रित~~ वृद्धि हो सकता है। इस तथ्य के कारण कोड बढ़ाया जाता है कि एक नए फ़ंक्शन की तात्कालिकता में तर्कों को अधिक सुविधाजनक प्रकार में परिवर्तित करने की तुलना में एक उच्च प्राथमिकता है। यानी टेम्पलेट टी फू (टी ए); int और char दो भिन्न कार्य हैं। एक फ़ंक्शन या तो टेम्पलेट्स को अस्वीकार करके, या स्पष्ट प्रकार के रूपांतरण का उपयोग करके प्राप्त किया जा सकता है।
लेकिन चलो समस्या को अंदर बाहर करते हैं और कोड की न्यूनतम लाइनों से सबसे बड़े संभव आकार की निष्पादन योग्य फ़ाइल प्राप्त करने का प्रयास करते हैं।
परिणाम बहुत प्रभावशाली नहीं था - मुझे केवल 60 लाइनों के कोड की 53 एमबी मिली। और फिर केवल तीन परीक्षण किए गए संकलकों में से एक और संकलन के कई घंटों की लागत पर। 14MB की मात्रा के लिए अधिकतम मात्रा / लाइन अनुपात 2.3MB / पंक्ति है।
यह कैसे और क्यों हुआ - कट के तहत।

साधन

4GB मेमोरी वाला एक लैपटॉप,
Intel® Core (TM) i3-2330M CPU @ 2.20GHz प्रोसेसर,
लिनक्स ओएस 3.7.3-101.fc17.x86_64
और एक अक्षम स्वैप विभाजन।
स्वैप को उसी कारण से निष्क्रिय करना पड़ा, जिस कारण पोस्ट शीर्षक में कांटा बम दिखाई दिया। कार्य की पर्याप्त बड़ी मात्रा के साथ, संकलक ने सभी मेमोरी को खा लिया और डिस्क के साथ सक्रिय रूप से विनिमय करना शुरू कर दिया, जो मशीन को कसकर और स्थायी रूप से लटका दिया।

संकलक संस्करण:

g ++ (GCC) 4.7.2 20120921 (रेड हैट 4.7.2-2)
Intel® C ++ Intel® 64 कंपाइलर XE Intel® 64, संस्करण 13.1.1.163 पर चलने वाले अनुप्रयोगों के लिए 20130313 बनाएँ
क्लैंग संस्करण 3.3 (ट्रंक 179304)

लंबी सरणियाँ

सबसे आसान तरीका उस पर संकलन और स्ट्रिंग फ़ंक्शन के चरण की एक सरणी को व्यवस्थित करना है। इस तरह:

template<long n> inline void nop(){nop<n-1>();asm("nop"); } template<> inline void nop<0>() {asm("nop");} int main(int argc, char ** argv) { nop<LVL>(); return 0; }

नतीजतन, मुख्य () फ़ंक्शन खाली ~~बेकार~~ एनओपी संचालन से भरा होना चाहिए।

अनुक्रम एनओपी का आकार सैद्धांतिक रूप से पुनरावृत्ति की गहराई से निर्धारित होता है। जी ++ मन कहता है कि अधिकतम गहराई 17 और 1024 सी ++ 11 के लिए है।

मन से बोली

-फेटप्लेट-गहराई = एन
टेम्पलेट क्लासेस के लिए अधिकतम तात्कालिकता गहराई को n पर सेट करें। टेम्पलेट तात्कालिकता गहराई पर एक सीमा की आवश्यकता है
टेम्प्लेट क्लास की तात्कालिकता के दौरान अंतहीन मंदी का पता लगाने के लिए। ANSI / ISO C ++ के अनुरूप कार्यक्रमों पर भरोसा नहीं करना चाहिए
अधिकतम गहराई 17 से अधिक (सी ++ 11 में 1024 में बदल गई)। डिफ़ॉल्ट मान 900 है, क्योंकि कंपाइलर बाहर चला सकता है
कुछ स्थितियों में 1024 मारने से पहले स्टैक स्पेस।

मुझे मानकों में विशिष्ट संख्या नहीं मिली। केवल यह बिंदु पाया गया कि पुनरावृत्ति की अधिकतम गहराई कार्यान्वयन द्वारा निर्धारित की जाती है:
सी ++ 03 के लिए 4.7.1.14
सी ++ 11 के लिए 4.7.1.15
जिसकी पुष्टि अनुभव से हुई। एक बड़े पर्याप्त LVL के लिए, कंपाइलर दुर्घटनाग्रस्त हो गया। Cl ++ द्वारा चकित, जो 2 ¹³ पर दुर्घटनाग्रस्त हो गया, g ++ और icpc के विपरीत 2 ¹⁷ तक पहुंच गया।

टीमों द्वारा विधानसभा को बाहर किया गया था:

  clang++ -DLVL=$(( 2**$n)) -o list$n ./list.cc -ftemplate-depth=3000000 -O$x g++ -DLVL=$(( 2**$n)) -o list$n ./list.cc -ftemplate-depth=3000000 -O$x icpc -DLVL=$(( 2**$n)) -o list$n ./list.cc -O$x

अंदर

स्क्रिप्ट का निर्माण

 #/bin/bash MIN=0 MAX=19 for i in 2; do mkdir -p attempt$i cd attempt$i for CXX in clang++ g++ icpc do mkdir -p $CXX cd $CXX for O in O0 O1 O2 O3 Os do mkdir -p $O cd $O (while :;do free -m |grep Mem|awk '{print $3}' >> ./memory;sleep 1;done)& TIME=$! for i in $(seq $MIN $MAX) do # CMD="$CXX -$O ../../../fbomb.cc -DLVL=$i -o fbomb$i" #-save-temps=obj " CMD="$CXX -$O ../../../list.cc -DLVL=$(( 2 ** $i)) -o list$i -ftemplate-depth=3000000" #-save-temps=obj " echo $CMD $CMD sleep 5 sleep 5 done kill -9 $TIME cd .. done cd .. done cd .. done

बायनेरिज़ को क्रमिक रूप से और लंबे समय तक एकत्र किया गया था। प्रत्येक कंपाइलर के लिए, अनुकूलन के प्रत्येक स्तर के लिए। विधानसभा परिणाम रेखांकन में दिखाए जाते हैं। चार छवि स्तंभ:

समय पर प्रयुक्त स्मृति की निर्भरता। ये रेखांकन केवल संदर्भ के लिए हैं। संकलन के दौरान, एक्स-सर्वर और ब्राउज़र ने काम किया, हालांकि, मुख्य रुझान दिखाई दे रहे हैं।
बाइनरी फ़ाइल का आकार। अधिकतम निकला - 14 एमबी
वर्णों की संख्या। इनलाइन कीवर्ड संकलक के लिए एक सिफारिश है, इसलिए बड़े एन के लिए एनओपी को नियमित कार्यों में बांटा गया है। इनकी गणना निम्न प्रकार से की जाती है:
```
 nm --demangle ./list$i|grep nop|wc -l 
```
ईमानदार नोड्स की संख्या। Disassembler से परिकलित:
```
 objdump -d ./list$i|grep 'nop$'|wc -l 
```

यह केवल क्रोम में छवियों के पैमाने को सही ढंग से देखता है।
अन्य ब्राउज़रों के लिए

स्क्रीनशॉट

और सभी छवियों के साथ संग्रह का लिंक

तस्वीरें

एक ही संकलक के लिए विभिन्न अनुकूलन स्तरों की तुलना

संकलन के समय मेमोरी की खपत	निष्पादन योग्य फ़ाइल आकार	निष्पादन योग्य फ़ाइल में वर्णों की संख्या	संचालन की संख्या एनओपी

विभिन्न अनुकूलन स्तरों पर विभिन्न संकलक की तुलना

संकलन के समय मेमोरी की खपत	निष्पादन योग्य फ़ाइल आकार	निष्पादन योग्य फ़ाइल में वर्णों की संख्या	संचालन की संख्या एनओपी

2 ¹⁷ icpc संकलक के लिए अधिकतम फ़ाइल आकार 14MB था। जी ++ के लिए - 12 एमबी। दोनों O0 पर। अनुकूलन स्तर O0 इनलाइन प्रतिस्थापन का प्रदर्शन नहीं करता है, इसलिए, nop <long> वर्णों की संख्या nop परिचालनों की संख्या के साथ मेल खाती है।

लम्बे पेड़

एक रेखीय डेटा संरचना के लिए, उत्पन्न फ़ाइल का आकार कम से कम अधिकतम डिफ़ॉल्ट पुनरावृत्ति गहराई (क्लेंग ++ के लिए 256, जी ++ के लिए 900) तक सीमित है। इसके चारों ओर पाने के लिए, आप एक पेड़ बनाने की कोशिश कर सकते हैं। संकलन चरण वृक्ष की अधिकतम सैद्धांतिक गहराई है (sizeof (लंबी) -1) == 63. और 2 ⁶⁴ बाइट्स किसी भी डिस्क को ओवरफ्लो करेंगे। व्यावहारिक सीमा बहुत कम है।
एक पेड़ का उपयोग करना, हम पुनरावृत्ति की अधिकतम गहराई से परे नहीं जाते हैं।
स्रोत कोड 19 लाइनें लेता है और इस तरह दिखता है:

 #ifndef LVL # define LVL 3 #endif long x = 0; template<int N=LVL, long I=0> struct foo{ inline static double bar(double m) {x++;return foo<N-1,I>::bar(m) + foo<N-1,((1<<(LVL-N))|I)>::bar(m) + I;}; }; template<long I> struct foo<0,I>{ inline static double bar(double m) {x++; return m;} }; #include <iostream> int main(int argc, char **argv){ double ret = foo<>::bar(argc); std::cout << x << " " << ret << std::endl; return int(ret); }

परिणाम एक पेड़ है, जिसके प्रत्येक नोड का अपना प्रकार है। प्रत्येक प्रकार की संख्या की एक जोड़ी की विशेषता है:

एन - स्तर संख्या;
मैं स्तर पर नोड संख्या हूं।

एक स्तर के अंदर प्रत्येक नोड को 0 से एन तक गिना जाता है।

मैंने यहाँ nop के साथ कोई गड़बड़ नहीं की, मैंने इसके अलावा का उपयोग किया ग्लोबल लॉन्ग x - का उपयोग सही असेंबली को नियंत्रित करने के लिए किया गया था। परिणामस्वरूप, 2 ^{LVL + 1} लौटाया जाता है।

टीमों द्वारा विधानसभा को बाहर किया गया था:

  clang++ -DLVL=$n -o fbomb$n ./fbomb.cc -O$x g++ -DLVL=$n -o fbomb$n ./fbomb.cc -O$x icpc -DLVL=$n -o fbomb$n ./fbomb.cc -O$x

ऊपर के रूप में एक ही परिदृश्य में।
Clang ++ के लिए अधिकतम LVL 18 था। G ++ और icpc - 16 के लिए, भले ही विकल्प --std = c ++ 11 निर्दिष्ट किया गया हो या नहीं। संकलक स्मृति से बाहर भाग गया।

यह केवल क्रोम में छवियों के पैमाने को सही ढंग से देखता है।
अन्य ब्राउज़रों के लिए

स्क्रीनशॉट

और सभी छवियों के साथ संग्रह का लिंक

पेड़ के लिए चित्र

संकलन के समय मेमोरी की खपत	निष्पादन योग्य फ़ाइल आकार	निष्पादन योग्य फ़ाइल में वर्णों की संख्या

संकलन के समय मेमोरी की खपत	निष्पादन योग्य फ़ाइल आकार	निष्पादन योग्य फ़ाइल में वर्णों की संख्या

अधिकतम फ़ाइल आकार:

43 एमबी के लिए icpc -O0 -DLVL = 17;
क्लैंग ++ -O0 -DLVL = 17 के लिए 42 एमबी;
22 ++ के लिए g ++ -O0 -DLVL = 16।

स्पष्ट तात्कालिकता

43 एमबी - इतना छोटा नहीं है, लेकिन क्या रैम की दी गई राशि से फ़ाइल को और भी बड़ा करना संभव है? यह संभव हो गया, लेकिन केवल तीन कंपाइलरों में से एक - आईसीपीसी। इसके लिए आपको बाहरी टेम्पलेट्स और स्पष्ट तात्कालिकता का उपयोग करने की आवश्यकता है।
हम स्रोत कोड को थोड़ा संशोधित करते हैं ताकि उसके विवरण में टेम्पलेट के सभी मापदंडों को इंगित किया जाए। हम स्रोत कोड को तीन फाइलों में विभाजित करते हैं - टेम्पलेट का एक विवरण, मुख्य कार्य और उपप्रकार का आंशिक इंस्ट्रक्शन:

fbomb.hh

 extern long x; template<int L=LVL, int N=L, long I=0> struct foo{ inline static double bar(double m) {x++;return foo<L,N-1,I>::bar(m) + foo<L,N-1,((1<<(LN))|I)>::bar(m) + I;}; }; template<int L, long I> struct foo<L,0,I>{ inline static double bar(double m) {x++; return m;} };

main.cc

 #include "fbomb.hh" //for i in $(seq 0 13);do echo "extern template struct foo<LVL,L,$i>;";done #define L (LVL-5) extern template struct foo<LVL,L,0>; extern template struct foo<LVL,L,1>; extern template struct foo<LVL,L,2>; extern template struct foo<LVL,L,3>; ... extern template struct foo<LVL,L,30>; extern template struct foo<LVL,L,31>; #include <iostream> long x = 0; int main(int argc, char **argv){ double ret = foo<LVL>::bar(argc); std::cout << x << " " << ret << std::endl; return int(ret); }

part.cc

 template class foo<LVL, _L, _I>;

यह पता चला कि जी ++ -c main.cc -DLVL = 21 मानक के संस्करण की परवाह किए बिना स्मृति के साथ-साथ एक पूर्ण तात्कालिकता की कमी के कारण क्रैश। क्लैंग ++ के लिए भी यही स्थिति। Icpc एक सेकंड से भी कम समय में main.cc को संकलित करती है। हालाँकि, उप-संकलन को लागू करने में 4 घंटे से अधिक का समय लगा:

 for i in $(seq 0 31);do echo -n "$i:";date; icpc -O2 -c ./part.cc -o part21_16_$io -DLVL=21 -D_L=16 -D_I=$i;sleep 10; done

उप-संकलन के दौरान मेमोरी की खपत

लिंकिंग में एक मिनट से भी कम समय लगा। परिणाम एक 53MB फ़ाइल है। इस फ़ाइल को -O2 के साथ बनाया गया था। -O0 एक बड़ा आकार देगा, लेकिन परिणाम के समय ~~और अर्थहीनता के~~ कारण मैंने इसे कई बार पुनर्निर्माण नहीं किया।

सबसे बड़ा अनुपात / लाइनों की संख्या = 2.3MB / रेखा पहले भाग (icpc -O0 list.cc) से सरणी के लिए प्राप्त किया गया था
मीट्रिक बेशक मज़ाक है, लेकिन मज़ेदार है। २.३ - अधिकतम जो हुआ। मुझे यह जानकर ख़ुशी होगी कि किसी को बड़ा रुख मिलेगा।

हम सभी को शुभकामनाएँ।

अपडेट : स्ट्रिप नहीं किया, लेकिन यह आवश्यक होगा। मैंने सोचा था कि कुछ किलोबाइट थे - लेकिन यह आकार के प्रतिशत के रूप में निकला, और काफी बड़ा था। पट्टी के बाद, अधिकतम आकार 37 एमबी (53 से) तक गिर गया। और 8.6MB (14 से)। तदनुसार, अनुपात 1.43 एमबी / रेखा है।