🏴 📽️ ♥️ Asm.js अभ्यास 👩🏿‍💼 👴🏿 🛎️

इस शांत दिन, मैं पी की गणना के लिए एल्गोरिदम और कार्यान्वयन की तलाश कर रहा था। एल्गोरिदम के कुछ असंख्य थे, लेकिन एल्गोरिथ्म और सी में इसके कार्यान्वयन का वर्णन करने वाला एक पोस्ट था।
एल्गोरिथ्म इसकी गति के साथ लुभावना है, हालांकि यह एक हेक्स प्रतिनिधित्व का उत्पादन करता है, लेकिन यह सिर्फ इतना हुआ कि मुझे js पर एक विकल्प की आवश्यकता थी। तात्कालिक, व्यावहारिक रूप से, नियमित js के लिए प्रसंस्करण ने बहुत खराब आंकड़े दिखाए, जब 1,000,000 संकेत गिनने में काम लिया ... 48 सेकंड (4GHz FF)।
एस्माज के साथ कैसे खिलवाड़ हुआ और वह किन पत्थरों से मिला, इसका पता कट के नीचे लगाया जा सकता है।

अधीर के लिए, परिणाम जीथब है ।

एक त्वरित नज़र के बाद, यह स्पष्ट हो गया कि हमें सभी पीढ़ी के साथ काम को एएसएम मॉड्यूल में स्थानांतरित करने की आवश्यकता नहीं थी, लेकिन केवल दो कार्यों का उपयोग किया गया था: एक्सपम और श्रृंखला। क्योंकि expm को अंदर श्रृंखला कहा जाता है, फिर हमें मॉड्यूल से केवल श्रृंखला का निर्यात करना चाहिए।

मूल विशेषताएं

double series (int m, int id) /* This routine evaluates the series sum_k 16^(id-k)/(8*k+m) using the modular exponentiation technique. */ { int k; double ak, eps, p, s, t; double expm (double x, double y); #define eps 1e-17 s = 0.; /* Sum the series up to id. */ for (k = 0; k < id; k++){ ak = 8 * k + m; p = id - k; t = expm (p, ak); s = s + t / ak; s = s - (int) s; } /* Compute a few terms where k >= id. */ for (k = id; k <= id + 100; k++){ ak = 8 * k + m; t = pow (16., (double) (id - k)) / ak; if (t < eps) break; s = s + t; s = s - (int) s; } return s; } double expm (double p, double ak) /* expm = 16^p mod ak. This routine uses the left-to-right binary exponentiation scheme. */ { int i, j; double p1, pt, r; #define ntp 25 static double tp[ntp]; static int tp1 = 0; /* If this is the first call to expm, fill the power of two table tp. */ if (tp1 == 0) { tp1 = 1; tp[0] = 1.; for (i = 1; i < ntp; i++) tp[i] = 2. * tp[i-1]; } if (ak == 1.) return 0.; /* Find the greatest power of two less than or equal to p. */ for (i = 0; i < ntp; i++) if (tp[i] > p) break; pt = tp[i-1]; p1 = p; r = 1.; /* Perform binary exponentiation algorithm modulo ak. */ for (j = 1; j <= i; j++){ if (p1 >= pt){ r = 16. * r; r = r - (int) (r / ak) * ak; p1 = p1 - pt; } pt = 0.5 * pt; if (pt >= 1.){ r = r * r; r = r - (int) (r / ak) * ak; } } return r; }

मूल टेम्पलेट।

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

 (function (window) { "use strict"; //  var buffer = new ArrayBuffer(BUFFER_SIZE); //       var functionNameOrStuctureName = (function (stdlib, env, heap) { "use asm"; //  //   return { methodNameExport: methodNameInModule, methodName2Export: methodName2InModule, }; //   return methodNameInModule })( { //    (stdlib) Uint8Array: Uint8Array, Int8Array: Int8Array, Uint16Array: Uint16Array, Int16Array: Int16Array, Uint32Array: Uint32Array, Int32Array: Int32Array, Float32Array:Float32Array, Float64Array:Float64Array, Math: Math }, { //  (env) NTP:NTP }, buffer //  ,  ,    > 4096    0 ); })(window); // wrapper end

"TypeError: asm.js प्रकार की त्रुटि: asm.js मॉड्यूल की वापसी एक्सपोर्ट स्टेटमेंट के साथ समाप्त होनी चाहिए" क्रैश की एक त्रुटि , सुनिश्चित करें कि मॉड्यूल कुछ लौटाता है। यदि यह उम्मीद के मुताबिक लौटता है, तो आपको यह सुनिश्चित करने की आवश्यकता है कि चर की घोषणाएं सही हैं। घोषणा के बाद, मुझसे एक गलती हुई, मैंने एक अंतर चर के साथ कुछ और करने की कोशिश की।
मुझे उम्मीद है कि बुनियादी चीजें पहले ही पता चल चुकी हैं, लेकिन अभी भी:

  function f1(i, d) { i = i | 0; // integer ,  i   d = +d; // double ,  d     var char = new Uint8Array(heap); // ,       var i2 = 0; //    (     fixnum) var d2 = 0.0; //      i2 = i2 | 0; //  fixnum  integer return +d2; //    double     double }

नुकसान नंबर 1: चर और मॉड्यूल कार्य

मैं पहले सभी चर घोषित करता था, और उसके बाद ही उन्हें मूल्य प्रदान करता था। Asm.js में, सब कुछ कुछ पेचीदा है: सबसे पहले, हम उन सभी चरों की घोषणा करते हैं, जिनका उपयोग हम क्लोजर के माध्यम से करते हैं, और गणितीय पुस्तकालय के कार्यों को भी यहाँ वर्णित किया जाना चाहिए, और नीचे नहीं कहा जाना चाहिए।
यहाँ क्या हुआ:

  "use asm"; //  stdlib  var floor = stdlib.Math.floor; //       ,    var pow = stdlib.Math.pow; //    ,    var tp1 = 0; //     var tp = new stdlib.Float64Array(heap); //    var ntp = env.NTP | 0; //       env,

वेरिएबल को इनिशियलाइज़ करके और इसे फंक्शन असाइन करके फ़ंक्शंस नहीं बनाए जा सकते हैं। इसलिए, फ़ंक्शन का पालन करते हैं।

  function expm(p, ak) { //  }

खराबी # 2: मॉड्यूल कार्यों में चर।

लेकिन मॉड्यूल फ़ंक्शन के शरीर में, आपको पहले इनपुट पर प्राप्त चर के प्रकार को इंगित करना चाहिए, फिर आंतरिक चर को इनिशियलाइज़ करना चाहिए, और यदि यह int है, तो var i = 0, यदि डबल है, तो var d = 0.0, यदि सरणी है, तो नए और प्रकार से हीप के साथ एक सरणी इसे पारित कर दिया, और ints आरंभीकृत होने के बाद, मैं उन्हें सलाह देता हूं कि मैं उन्हें "इनिशियलाइज़" करूं, मुझे फॉर्म i = i | 0 असाइन करके। वैसे: सी की शैली में अग्रिम में चर का आरंभ वैकल्पिक है। फॉर्म 1e-17 की संख्या सीमा से बाहर जाने की त्रुटि देती है, 0.00000000000000001 का उपयोग करें
आउटपुट:

  function expm(p, ak) { p = +p; ak = +ak; var i = 0; var pt = 0.0; // .... i = i | 0; ntp = ntp | 0; //  }

नुकसान # 3: तुलना और पुनरावृत्तियों

सच कहूं, यहां मैं लंबे समय तक हंसता रहा, लेकिन इंट और इंट की तुलना के अधीन नहीं हैं । यदि आप i == k या i <l जैसे कुछ करते हैं, तो जैसे त्रुटि के साथ संकलन
"TypeError: asm.js टाइप त्रुटि: एक तुलना के तर्क दोनों पर हस्ताक्षर किए, अहस्ताक्षरित या युगल होने चाहिए, इंट और इंट दिए गए हैं । "
Int और पूर्णांक (i == 0) की तुलना करके थोड़ी हंसी जोड़ी गई
"TypeError: asm.js टाइप त्रुटि: एक तुलना के तर्क दोनों पर हस्ताक्षर किए, अहस्ताक्षरित या युगल होने चाहिए, फिक्सेनम और इंट दिए गए हैं । "
केवल फ़्लोटिंग-पॉइंट संख्याएँ ठीक कर रही हैं (उदा। Pt == 1.0)।
नतीजतन, अगर आप अभी भी एक और इंट के साथ तुलना करना चाहते हैं। प्रपत्र के निर्माण की घोषणा करना आवश्यक है (i। 0) <(ntp | 0) |
पुनरावृत्तियों के रूप में, यह सिर्फ "आकर्षक" है: हम सभी के बजाय i ++ से परिचित हैं, हमारे पास i = (i | 0) + 1 | 0।
परिणाम:

  if ((tp1 | 0) == 0) { // vars for (i = 1; (i | 0) < (ntp | 0); i = (i | 0) + 1 | 0) { // surprise, read more) } }

नुकसान नंबर 4: गणितीय और अन्य बाहरी कार्य।

यहां सब कुछ सरल है, यदि आप फर्श, पाप, आदि का उपयोग करना चाहते हैं, तो आपको उन्हें मॉड्यूल की शुरुआत में घोषित करने की आवश्यकता है (तुरंत "एसम का उपयोग करें")। यदि मैं एक फ़ंक्शन में stdlib.Math.floor लिखता हूं, तो मुझे रिटर्न प्रकार की त्रुटि मिलती है। स्पष्ट रूप से वस्तु के गुणों तक पहुँचने के कारण।

ख़तरा # 5: बफ़र्स।

और यहाँ सब कुछ बहुत दिलचस्प है। जब हम इंडेक्स i के साथ / अरे एरे को मान देना / सेट करना चाहते हैं, तो हम क्या करते हैं? गिरफ्तारी [i]। माना कि हम ऐसा करते हैं, लेकिन तब हमें फॉर्म की त्रुटि मिलती है।

  arr[i] = +1;

"TypeError: asm.js टाइप त्रुटि: इंडेक्स एक्सप्रेशन को स्थानांतरित नहीं किया गया है; एक Int8 / Uint8 पहुंच »होनी चाहिए
हम सूक्ष्म रूप से संकेत देते हैं कि एक बदलाव होना चाहिए। एक गुरु में, मुझे दाईं ओर 2 की शिफ्ट मिली।

  arr[i >> 2] = +1;

"TypeError: asm.js टाइप त्रुटि: शिफ्ट राशि 3 होनी चाहिए"
हम विनम्रतापूर्वक संकेत देते हैं कि वह तीन होना चाहिए।

  arr[i << 3 >> 3] = +1;

यह अंत में निकलता है। बाईं ओर शिफ्ट होने के साथ, हमने दाईं ओर शिफ्ट के लिए मुआवजा दिया। ऐसा लगता है कि सब कुछ समान है, लेकिन यह काम करता है।

श्रम का परिणाम

 /** * Created with JetBrains WebStorm. * User: louter * Date: 12.09.13 * Time: 17:49 */ (function (window) { "use strict"; var ihex; var NTP = 25; var buffer = new ArrayBuffer(1024 * 1024 * 8); var series = (function (stdlib, env, heap) { "use asm"; var floor = stdlib.Math.floor; var pow = stdlib.Math.pow; var tp1 = 0; var tp = new stdlib.Float64Array(heap); var ntp = env.NTP | 0; function expm(p, ak) { p = +p; ak = +ak; var i = 0; var j = 0; var p1 = 0.0; var pt = 0.0; var r = 0.0; // float as double i = i | 0; j = j | 0; ntp = ntp | 0; if ((tp1 | 0) == 0) { tp1 = 1 | 0; tp[0] = +1; for (i = 1; (i | 0) < (ntp | 0); i = (i | 0) + 1 | 0) { tp[(i << 3) >> 2] = +(+2 * tp[((i - 1) << 3) >> 3]); } } if (ak == 1.0) { return +0; } for (i = 0; (i | 0) < (ntp | 0); i = (i | 0) + 1 | 0) { if (+tp[i << 3 >> 3] > p) { break; } } pt = +tp[(i - 1) << 3 >> 3]; p1 = +p; r = +1; for (j = 0; (j | 0) <= (i | 0); j = (j | 0) + 1 | 0) { if (p1 >= pt) { r = +16 * r; r = r - (+(floor(r / ak))) * ak; p1 = p1 - pt; } pt = 0.5 * pt; if (pt >= 1.) { r = r * r; r = r - (+(floor(r / ak))) * ak; } } return +r; } function series(m, id) { m = m | 0; id = id | 0; var k = 0; var ak = 0.0; var eps = 0.0; var p = 0.0; var s = 0.0; var t = 0.0; eps = 0.00000000000000001; k = 0 | 0; for (k; (k | 0) < (id | 0); k = (k | 0) + 1 | 0) { ak = +8 * (+(k | 0)) + (+(m | 0)); p = (+(id | 0) - +(k | 0)); t = +expm(p, ak); s = s + t / ak; s = s - floor(s); } for (k = (id | 0); (k | 0) <= ((id + 100) | 0); k = (k | 0) + 1 | 0) { ak = +8 * (+(k | 0)) + (+(m | 0)); t = pow(+16, +(id | 0) - (+(k | 0))) / +ak; if (t < eps) break; s = s + t; s = s - floor(s); } return +s; } return series; })( { Uint8Array: Uint8Array, Int8Array: Int8Array, Uint16Array: Uint16Array, Int16Array: Int16Array, Uint32Array: Uint32Array, Int32Array: Int32Array, Float32Array:Float32Array, Float64Array:Float64Array, Math: Math }, { NTP:NTP }, buffer ); ihex = function (x, nhx, chx) { var i, y, hx = "0123456789ABCDEF"; y = Math.abs(x); for (i = 0; i < nhx; i++) { y = 16. * (y - (y | 0)); chx[i] = hx[y | 0]; } }; window.pi = function (id) { var pid, s1, s2, s3, s4 , hex = []; s1 = series(1, id); s2 = series(4, id); s3 = series(5, id); s4 = series(6, id); pid = 4 * s1 - 2 * s2 - s3 - s4; pid = pid - (pid | 0) + 1; ihex(pid, 16, hex); return { hex: hex.join('').substr(0, 10), fraction:pid }; }; })(window);

PS मुझे नहीं पता कि कौन या क्या गलत है, लेकिन (!) किसी कारण से संकलित कार्यक्रम ने asm.s की तुलना में बदतर परिणाम उत्पन्न किए।

अर्थात्,

समय ./pi 1,000,000
>> वास्तविक 0m2.161s
>> उपयोगकर्ता 0m2.149s
>> sys 0m0.001s

कंसोल.टाइम ('एस');
पीआई (1,000,000);
कंसोल.टाइम ईंड ('एस');
>> s: 1868.5ms

और यह भी:
समय ./pi 10000000
>> वास्तविक 0m25.345s
>> उपयोगकर्ता 0m25.176s
>> sys 0m0.019s

कंसोल.टाइम ('एस');
पीआई (10,000,000);
कंसोल.टाइम ईंड ('एस');
>> s: 22152.83ms

विश्वास नहीं होता? इसकी जाँच करें। उपरोक्त पोस्ट में कार्यक्रम का स्रोत कोड। मेरे स्रोतों को भी ऊपर इंगित किया गया है।

युपीडी:
मैं यह जाँचने के लिए testASM.js को gitub पर रखता हूँ कि क्या asmjs काम करता है या नहीं। कनेक्ट करने के बाद, चर window.asmjs (बूल) दिखाई देता है। testASM.js और testASM.min.js