जेएस पर कॉनवे के जीवन का लेखन और अनुकूलन

हाल ही में अपने हम्सटर के डिजाइन को अपडेट करते हुए, मैंने सोचा - लेकिन क्या मुझे 404 वीं त्रुटि के साथ कुछ असामान्य पेज बनाना चाहिए? चूंकि मैं बचपन में कॉनवे के जीवन से प्रभावित था (जैसा कि कई पाठकों के लिए संभव है), मैंने इसे जेएस पर लागू करने का फैसला किया।

ऐसा लगता है कि जीवन में क्या मुश्किल है: यदि एक व्यस्त सेल में 2 या 3 पड़ोसी हैं, तो यह रहता है, अगर इसमें बिल्कुल 3 खाली कोशिकाएं हैं, तो क्या यह पैदा होता है? इस लेख में मैं एल्गोरिथ्म के मेरे अनुकूलन और कैनवास पर प्रतिपादन के बारे में बात करूंगा, जावास्क्रिप्ट में पूर्णांक / बाइनरी अंकगणित के कुछ स्पष्ट क्षण नहीं।

आगे देखते हुए, अंतिम परिणाम यहां देखा जा सकता है , स्रोत वहां दिखाई दे रहे हैं (और यहां तक ​​कि सीसी बीवाई लाइसेंस के तहत)।

हम सरल तरीके से चलते हैं

for(y=1;y<maxy-1;y++)//We do not process 1px border for(x=1;x<maxx-1;x++) { sum = data[readpage][y-1][x-1] + data[readpage][y-1][x ] + data[readpage][y-1][x+1] + data[readpage][y ][x-1] + data[readpage][y ][x+1] + data[readpage][y+1][x-1] + data[readpage][y+1][x ] + data[readpage][y+1][x+1]; if(sum==3 || (sum==2 && data[readpage][y][x])) data[writepage][y][x] = 1; else data[writepage][y][x] = 0; setColor(data[writepage][y][x]); drawCell(x,y); } 

यह निश्चित रूप से काम करता है, लेकिन केवल एक ही समस्या है - i7-3820@4.3Ghz और फ़ायरफ़ॉक्स 12 पर - यह कोड केवल 8.5 एफपीएस (फ्रेम प्रति सेकंड) की गणना और आकर्षित करने का प्रबंधन करता है। एक त्वरित परीक्षण से पता चलता है कि यह प्रतिपादन है जो धीमा हो जाता है।

अनुकूलन का प्रतिपादन

हम एक पिक्सेल तभी खींचेंगे जब वह बदल गया हो - 67 FPS।

क्योंकि प्रत्येक सेल के संदर्भ में वर्तमान रंग को बदलना बहुत मुश्किल ऑपरेशन है, हम 2 पास में ड्रा करेंगे, पहले सभी जन्म कोशिकाओं, फिर सभी मृत: 80 फ्रेम प्रति सेकंड। चूंकि सभी गणना किए गए फ़ील्ड मुझ पर प्रदर्शित नहीं किए गए हैं (ताकि दुनिया के अंत के साथ टकराव से "ग्लिच" दिखाई न दें), मैं स्क्रीन पर अदृश्य कोशिकाओं को आकर्षित करने की कोशिश नहीं कर रहा हूं - 125 एफपीएस।

व्यवहार में एक ऑफ-स्क्रीन कैनवस में आरेखण ने कोई त्वरण नहीं दिया, इसके विपरीत एक दृश्यमान कैनवास की नकल करने के कारण थोड़ी गिरावट आई।

यह केवल सेटटाइमआउट से फ्रेम को शुरू करने के लिए ही रहता है लेकिन रिक्वेस्टएनिमेशन फ़्रेम - ताकि एनीमेशन को तब न खींचा जाए जब उपयोगकर्ता इसे नहीं देखता है (उदाहरण के लिए, यदि पृष्ठ कुछ ब्राउज़र टैब में है)

शायद एल्गोरिथ्म का अनुकूलन करने के लिए जाना है ...

मौजूदा अनुकूलन विधियाँ

Hashlife के पास लगभग अनंत क्षेत्रों में गति में चैम्पियनशिप है - मोटे तौर पर बोलते हुए, क्षेत्र को क्वाड-ट्री में विभाजित किया गया है, और समान ब्लॉकों की गणना नहीं की जाती है, और कैश से परिणाम तुरंत लिया जाता है। यहां समस्या यह है कि इस तरह के एक एल्गोरिथ्म "धीरे से पॉप" होता है, स्मृति का एक गुच्छा खाता है, और हमारे क्षेत्र (256 * 192) के लिए - यह एक इलेक्ट्रॉन माइक्रोस्कोप के साथ नाखूनों को हथौड़ा करने जैसा है।

एल्गोरिदम का एक और समूह गणना से फ़ील्ड ब्लॉकों के बहिष्कार पर काम करता है जहां यह खाली है (या कोई परिवर्तन नहीं हैं)। लेकिन मेरे मामले में, मैदान लगभग हमेशा गतिविधि से भरा होता है, इसलिए गति में वृद्धि होगी, लेकिन शानदार नहीं।

एक और तरीका यह है कि बदलती कोशिकाओं की एक कतार को संग्रहीत किया जाए और सरणी में राशि को तुरंत अपडेट किया जाए। यानी X * Y * 8 ऑपरेशन करने के बजाय, हम केवल (पिछले चरण में परिवर्तित कोशिकाओं की संख्या) * 8 करते हैं। बेशक, कतार के साथ काम करने के लिए महत्वपूर्ण ओवरहेड है, लेकिन यहां तक ​​कि घने क्षेत्र के लिए, 3-5 गुना का त्वरण प्राप्त करना आसान है (बड़े कमजोर भरे खेतों के लिए, यह काफी अच्छा एल्गोरिदम है)।

लेकिन मैं अपने तरीके से जाऊंगा

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

मैं फ़ील्ड को बिट फॉर्म (32 मान प्रति तत्व तत्व) में संग्रहीत करूंगा। जेएस में 32-बिट संख्या संग्रहीत और व्याख्या की गई है जैसे कि हस्ताक्षरित (!) पूर्णांक, लेकिन अगर हम 32 बिट्स के लिए कम से कम एक इकाई को क्रॉल करते हैं, तो हम एक वास्तविक संख्या प्राप्त कर सकते हैं। एक और दिलचस्प विशेषता यह है कि JS, >> और >>> में 2 राइट शिफ्ट कमांड हैं। >>> इस बात में भिन्न है कि यह संख्या को अहस्ताक्षरित करता है (और शून्य स्थान को "धकेल देता है, हस्ताक्षरित नहीं)।" यह एक ऐसी पारी है जिसका उपयोग हमें संख्याओं के साथ काम करने के लिए करना होगा, जहां हम सभी 32 बिट्स का उपयोग करते हैं।

अब जब हम बाईं से दाईं ओर की रेखा के साथ जाते हैं, तो हम तुरंत 3 लगातार कोशिकाओं का मान प्राप्त कर सकते हैं: मान और 7। इन कोशिकाओं की राशि की गणना करने के लिए - हम 8 संभावित संयोजनों के लिए एक लुकअप तालिका बनाएंगे, और क्रमबद्ध सरणी को एक बार भी एक्सेस नहीं करने के लिए - हम इसे एक संख्या में धकेलेंगे:

 // Bitcounting trick: // IN CNT CNTBIN // 000 0 00 // 001 1 01 // 010 1 01 // 011 2 10 // 100 1 01 // 101 2 10 // 110 2 10 // 111 3 11 // Magik lookup number = 0b00000000000000001110100110010100 // Least significant ^ // in octal 0164624 

अब हम सरणी में अतिरिक्त कॉल के बिना एक बार में 3 कोशिकाओं की राशि की गणना कर सकते हैं:

 sum = (0164624 >> ((value& 7)<<1)) & 3; 

इसी तरह, हम ऊपरी और निचली रेखाओं पर राशि की गणना कर सकते हैं। उस सेल को स्वयं बाहर करने के लिए जिसके चारों ओर हम योग की गणना करते हैं - मध्य रेखा में हम & 7 के बजाय 5 करते हैं। इस प्रकार, हमें एरे को एक्सेस किए बिना 3 पंक्तियों से 3 sums मिला।

अगला, हमें सेल की नई स्थिति प्राप्त करने की आवश्यकता है - फिर से हम एक लुकअप टेबल करेंगे, 3 बिट्स राशि (अधिकतम 8), 1 बिट - पुराने राज्य में जाएंगे:

 /*state_lookup = [ //Old cell state //0 1 0 , 0 // 0 SUM , 0 , 0 // 1 , 0 , 1 // 2 , 1 , 1 // 3 , 0 , 0 // 4 , 0 , 0 // 5 , 0 , 0 // 6 , 0 , 0 // 7 , 0 , 0 // 8 ];*/ state_lookup = 0340; //0b0000000011100000; 

अब हम इस तरह की शाखा के बिना एक नया राज्य प्राप्त कर सकते हैं:

 (0340 >>> ((sum<<1) | (v2&1)))&1 

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

हम के रूप में जन्म कोशिकाओं प्राप्त कर सकते हैं:

 need_draw = (new_state ^ data[readpage][y ][x]) & new_state; 

और मृत:

 need_draw = (new_state ^ data[readpage][y ][x]) & ~new_state; 

अगर ज़रूरत_ वापस == 0 है, तो आपको कुछ भी आकर्षित करने की आवश्यकता नहीं है, अन्यथा, हम 32 बिट्स पर जाते हैं और आवश्यक परिवर्तन आकर्षित करते हैं।

अंतिम कोड दृश्य स्रोत में दिखाई दे रहा है, मैं यहां नहीं आउंगा।

मैं यह भी नोट कर सकता हूं कि देशी अनुप्रयोगों के खुश लेखकों में 512 एकल-बिट मानों की एक देखने की मेज हो सकती है - सीधे 9-बिट पुराने वातावरण से एक नया राज्य प्राप्त करें। एक लुकअप टेबल 64 बाइट्स लेती है, और बिल्कुल L1 कैश लाइन में फिट होगी ... एह, सपने, सपने ...

परिणाम

अंतिम गति मुझे पूरी तरह से सूट करती है, यहां तक ​​कि पुराने कंप्यूटरों पर भी प्रदर्शन में एक निश्चित अंतर है (एनीमेशन कोड प्रति सेकंड 30 से अधिक फ्रेम खींचने की कोशिश नहीं करता है)।

ब्राउज़र	प्रतिपादन के साथ एफपीएस	प्रतिपादन के बिना एफपीएस
फ़ायरफ़ॉक्स 12	473	1545
IE 9	209	451
क्रोम 19	274	1210

उल्लेखनीय है, फ़ायरफ़ॉक्स में हार्डवेयर त्वरण को अक्षम करते समय, प्रतिपादन के साथ गति ~ 1.5 गुना कम हो जाती है। लेकिन कुल मिलाकर, मुझे खुशी है कि फायरफॉक्स क्रोम द्वारा निर्धारित प्रदर्शन के स्तर तक पहुंच गया है।

आप यहां खुद को परख सकते हैं: प्रतिपादन के साथ , बिना प्रतिपादन के ।

तैयार फॉर्म में परिणाम यहां दिखाई दे रहा है । वैसे, यदि आप अनजाने में मेरी साइट पर क्या जाम देखते हैं - इसके बारे में 3@14.by पर लिखने के लिए स्वतंत्र महसूस करें, मैं आपसे उनके बारे में सीखना चाहता हूं ...

आगे अनुकूलन के लिए और सामान्य रूप से जीवन के बारे में विचार हैं - टिप्पणियों में!