जो समय की विस्तृत रिपोर्ट प्रत्येक संकलक चरण से बर्बाद प्रिंट जीसीसी में -ftime-report विकल्प नहीं है ।
मैं Ubuntu 12.04 जीसीसी 4.6.3 और इस कोड के साथ 64-बिट अपनी स्थिति पुन: पेश करने के लिए इस्तेमाल कर रहा हूँ:
#include <vector>
using namespace std;
int main()
{
vector<double> d;
d.push_back(5.7862517058766);
/* ... N lines generated with
perl -e 'print(" d.push_back(",rand(10),");\n") for 1..100000'
*/
d.push_back(3.77195464257674);
return d.size();
}
(विभिन्न N के लिए -ftime-report outputs हैं wall समय पर पृष्ठभूमि लोड की वजह से गलत था पीसी, हां, user time पर देखने के usr):
एन = 10000
$ g++ -ftime-report ./pb10k.cpp
Execution times (seconds)
...
expand vars : 1.48 (47%) usr 0.01 (7%) sys 1.49 (44%) wall 1542 kB (2%) ggc
expand : 0.11 (3%) usr 0.01 (7%) sys 0.10 (3%) wall 19187 kB (30%) ggc
...
TOTAL : 3.18 0.15 3.35 64458 kB
एन = 100 000
$ g++ -ftime-report ./pb100k.cpp
Execution times (seconds)
....
preprocessing : 0.49 (0%) usr 0.28 (5%) sys 0.59 (0%) wall 6409 kB (1%) ggc
parser : 0.96 (0%) usr 0.39 (6%) sys 1.41 (0%) wall 108217 kB (18%) ggc
name lookup : 0.06 (0%) usr 0.07 (1%) sys 0.24 (0%) wall 1023 kB (0%) ggc
inline heuristics : 0.13 (0%) usr 0.00 (0%) sys 0.20 (0%) wall 0 kB (0%) ggc
integration : 0.03 (0%) usr 0.00 (0%) sys 0.04 (0%) wall 4095 kB (1%) ggc
tree gimplify : 0.22 (0%) usr 0.00 (0%) sys 0.23 (0%) wall 36068 kB (6%) ggc
tree eh : 0.06 (0%) usr 0.00 (0%) sys 0.14 (0%) wall 5678 kB (1%) ggc
tree CFG construction : 0.08 (0%) usr 0.01 (0%) sys 0.10 (0%) wall 38544 kB (7%) ggc
....
expand vars : 715.98 (97%) usr 1.62 (27%) sys 718.32 (83%) wall 18359 kB (3%) ggc
expand : 1.04 (0%) usr 0.09 (1%) sys 1.64 (0%) wall 190836 kB (33%) ggc
post expand cleanups : 0.09 (0%) usr 0.01 (0%) sys 0.15 (0%) wall 43 kB (0%) ggc
....
rest of compilation : 1.94 (0%) usr 2.56 (43%) sys 102.42 (12%) wall 63620 kB (11%) ggc
TOTAL : 739.68 6.01 866.46 586293 kB
तो, वहाँ में भारी एन के लिए कुछ अतिरिक्त काम है "विस्तार वार्स" चरण। यह चरण बिल्कुल इस पंक्ति में है: cfgexpand.c:4463 (टीवी_VAR_EXPAND मैक्रो के बीच)।
दिलचस्प तथ्य: मेरे कस्टम संकलित 32-बिट जी ++ 4.6.2 (~ 20 सेकंड के लिए एन = 100000) के साथ मेरे पास बहुत छोटा संकलन समय है।
मेरे जी ++ और उबंटू जी ++ के बीच क्या अंतर है? उबंटू में जीसीसी स्टैक प्रोटेक्शन (-fstack-protect विकल्प) turning on by default है। और यह सुरक्षा सिर्फ "वार्स का विस्तार करने के लिए" चरण जोड़ा जाता है (स्रोतों cfgexpand.c:1644,expand_used_vars() में पाया; उल्लेख here):
एन = 100000, ढेर रक्षक विकल्प के साथ अक्षम -fno-stack-protector (अपने कोड के लिए इसका इस्तेमाल करते हैं):
callgrind अंदर जीसीसी शुरू करने के बाद
:
$ g++ -ftime-report -fno-stack-protector pb100k.cpp 2>&1 |egrep 'TOTAL|expand vars'
expand vars : 0.08 (0%) usr 0.01 (1%) sys 0.09 (0%) wall 18359 kB (3%) ggc
TOTAL : 23.05 1.48 24.60 586293 kB
चलने का समय 24 सेकंड, है से 800
अद्यतन नीचे (वालग्रिंड से कॉल-ग्राफ़ प्रोफाइलिंग टूल), मैं कह सकता हूं कि एन स्टैक वैरिएबल हैं। यदि स्टैक रक्षक सक्षम है, तो उन्हें तीन ओ (एन^2) एल्गोरिदम के साथ "विस्तार वर्र्स" चरण में संभाला जाता है। असल में एन^2 सफल संघर्ष विच्छेदन और 1,5 * एन^2 बिट मैनिप्लेशंस और कुछ नेस्टेड लूप तर्क हैं।
स्टैक चर की संख्या इतनी अधिक क्यों है? क्योंकि आपके कोड में प्रत्येक डबल स्थिरता को ढेर में अलग-अलग स्लॉट में सहेजा जाता है। फिर इसे अपने स्लॉट से लोड किया जाता है और कॉलिंग कन्वेंशन के रूप में पारित किया जाता है (x86 में स्टैक के शीर्ष के माध्यम से; x86_64 में रजिस्ट्रार के माध्यम से)। मजाकिया तथ्य: push_back के साथ कोड के सभी कोड -fstack-protector के साथ संकलित या -fno-stack-protector के साथ समान है; स्थिरांक का ढेर लेआउट भी वही है।गैर-पुश_बैक कोड के केवल कुछ स्टैक लेआउट ऑफसेट प्रभावित होते हैं (-S और diff -u के साथ दो रनों की जांच की गई)। सक्षम स्टैक रक्षक द्वारा कोई अतिरिक्त कोड नहीं बनाया गया था।
स्टैक रक्षक की सक्षमता संकलक के अंदर कुछ व्यवहार को मोटे तौर पर बदल देती है। यह कह नहीं सकता कि वास्तव में कहां (नोट: जुआन एम। बेल्लो रिवास द्वारा callgraph.tar.gz के साथ स्टैक निशान की तुलना के साथ इस मोड़ को ढूंढना संभव है)।
/* Since we do not track exact variable lifetimes (which is not even
possible for variables whose address escapes), we mirror the block
tree in the interference graph. Here we cause all variables at this
level, and all sublevels, to conflict. */
if (old_sv_num < this_sv_num)
{
new_sv_num = stack_vars_num;
for (i = old_sv_num; i < new_sv_num; ++i)
for (j = i < this_sv_num ? i : this_sv_num; j-- > old_sv_num ;)
add_stack_var_conflict (i, j);
}
}
add_stack_var_conflict(i,j)
में बदल जाता है:
पहले बड़ा एन * (N + 1)/2 = हे (एन^2) की पैदल दूरी पर ढेर चर के जोड़े के बीच संघर्ष के बारे में जानकारी निर्धारित करने की expand_used_vars_for_block (tree block, level) समारोह में है
- आवंटन (एक बार चर प्रति) की ... ओह आकार के साथ एक बिटमैप, गतिशील आकार जो एन बिट्स
- बड़ा हो जाएगा थोड़ा जे
के साथ संघर्ष के लिए वर की bitmask i'th में स्थापित करने के साथ 363,210
- मैं
के साथ संघर्ष के लिए j'th वर के bitmask में थोड़ा की स्थापना दूसरा एन^2 add_alias_set_conflicts में टहलने के नहीं है। यह प्रत्येक जोड़ी के लिए objects_must_conflict_p के साथ चेक टाइप करता है। यह जांचता है, यदि दो चर एक ही प्रकार के हैं (अधिकांश जोड़े हैं; यह टाइप-आधारित उपनाम विश्लेषण है, TBAA)। यदि नहीं, add_stack_var_conflict कहा जाता है; इस एन^2 लूप घोंसला से केवल एन ऐसे कॉल हैं।
अंतिम विशाल पैदल दूरी पर ढेर वार्स की qsort आईएनजी (ओ (NlogN)) और एन * (एन 1)/2 = हे (एन^2) सभी गैर परस्पर विरोधी जोड़े को खोजने के लिए चलना के साथ partition_stack_vars() समारोह में है।
Sort the objects by size.
For each object A {
S = size(A)
O = 0
loop {
Look for the largest non-conflicting object B with size <= S.
/* There is a call to stack_var_conflict_p to check for
* conflict between 2 vars */
UNION (A, B)
offset(B) = O
O += size(B)
S -= size(B)
}
}
समारोह stack_var_conflict_p बस की जाँच करता है है वहाँ कुछ मैं-वें चर में संघर्ष bitmask और वहाँ (जे-वें बिट j-वें चर के साथ संघर्ष ध्वज के रूप में सेट किया गया है के साथ: यहाँ cfgexpand.c फ़ाइल से partition_stack_vars की स्यूडोकोड है bitmap_bit_p(i->conflict_mask,j) पर कॉल करें)। यहां वास्तव में बुरी खबर यह है कि कॉलग्रिंड कहता है कि प्रत्येक संघर्ष जांच सफल रही थी, और यूनियन तर्क प्रत्येक जोड़ी के लिए छोड़ दिया गया है।
तो, ओ (एन^2) बिट सेट और ओ (एन^2/2) बिट चेक द्वारा बहुत समय बर्बाद हो जाता है; और यह सब काम कुछ भी अनुकूलित करने में मदद नहीं करता है। और हाँ, यह सब -O0 का हिस्सा है और -fstack-protector द्वारा ट्रिगर किया गया है।
UPDATE2:
ढेर पर चर के तत्काल या आस्थगित आवंटित करने के लिए, लगता है, महत्वपूर्ण मोड़ expand_one_varcfgexpand.c from 4.6 है जांच में:
1110 else if (defer_stack_allocation (var, toplevel))
1111 add_stack_var (origvar);
1112 else
1113 {
1114 if (really_expand)
1115 expand_one_stack_var (origvar);
1116 return tree_low_cst (DECL_SIZE_UNIT (var), 1);
1117 }
(expand_one_stack_var यहाँ केवल तेज संस्करण में बुलाया गया था, कॉलग्रिंड के अनुसार)
-fstack-protect सक्षम होने पर स्थगित आवंटन को मजबूर किया जाता है (कभी-कभी इसे सभी स्टैक चरों को पुन: व्यवस्थित करने की आवश्यकता होती है)।यहां तक कि कुछ "द्विघात समस्या" है, जो के बारे में एक टिप्पणी अब हमें भी परिचित लग रहा है:
969 /* A subroutine of expand_one_var. VAR is a variable that will be
970 allocated to the local stack frame. Return true if we wish to
971 add VAR to STACK_VARS so that it will be coalesced with other
972 variables. Return false to allocate VAR immediately.
973
974 This function is used to reduce the number of variables considered
975 for coalescing, which reduces the size of the quadratic problem. */
976
977 static bool
978 defer_stack_allocation (tree var, bool toplevel)
979 {
980 /* If stack protection is enabled, *all* stack variables must be deferred,
981 so that we can re-order the strings to the top of the frame. */
982 if (flag_stack_protect)
983 return true;
यहाँ (ढेर आवंटन -O2 और अधिक से अधिक पर भी टाल जाता है) एक प्रतिबद्ध है: http://gcc.gnu.org/ml/gcc-patches/2005-05/txt00029.txt जो जोड़ा यह तर्क
कितना समय लंबा है? –
अधिकांश कंपाइलर्स बस 100,000+ लाइन फ़ाइलों के लिए अनुकूलित नहीं हैं। –
8 जीबी मेमोरी के साथ मेरी क्वाड कोर मशीन पर कई मिनट लग गए। सौभाग्य से, यह अंत में सफलतापूर्वक संकलित किया गया था। – synaptik