مرحبا يا هبر! أقدم لكم ترجمة مقال "الثقوب الدودية في جافا سكريبت" بقلم ماثيوس بوس.
أجهزة الكمبيوتر هي آلات مثيرة للاهتمام. من الناحية النظرية ، يبدو لنا أنهم رياضيون ميكانيكيون مثاليون يعملون مع الأعداد وعمليات جيدة الأداء للجمع والضرب والطرح.
ومع ذلك ، فإن مثل هذا التجريد مضلل للغاية. يأخذنا بعيدًا عن الفهم بأن الكمبيوتر يعالج العمليات الحسابية المختلفة بسرعات مختلفة. إذا كنت تكتب بلغة جافا سكريبت (أو أي لغة أخرى) وتهتم بأداء الخوارزميات التي كتبتها ، فمن المهم جدًا فهم كيفية عمل أجهزة الكمبيوتر تحت الغطاء.
إذا علمنا ما هو قادر على الكمبيوتر ، فيمكننا استخدام أقصر المسارات أو الثقوب الدودية لجعل برامجنا أسرع بكثير مما توقعنا.
الثقب في عملية الحصول على ما تبقى من القسمة
ماذا يعني هذا بالضبط؟ دعونا نلقي نظرة على مثال: تخيل أننا نريد تنفيذ قائمة رنين . قائمة الحلقات هي قائمة ذات حجم ثابت يتم فيها نقل الإدخالات الأكبر من حجم القائمة إلى أعلى القائمة وفي دائرة. تعتبر قوائم الحلقات ملائمة جدًا للعديد من الأشياء - مثل جمع الإحصائيات لفترات زمنية محددة ، وبيانات التخزين المؤقت ، والمزيد ، ولكن انظر إلى هذا التنفيذ:
const list = new Array(15000) function set (i, item) {
ما مدى سرعة تنفيذ هذا الرمز؟ دعونا نجري اختبار سرعة بسيط
console.time() for (var i = 0; i < 1e9; i++) { set(i, i) } console.timeEnd()
على جهاز الكمبيوتر الخاص بي ، استغرق الأمر حوالي 4 ثوانٍ مقابل 1 مليار إدخال. ليس سيئًا.
ومع ذلك ، دعنا نطبق ثقبًا دوديًا حسابيًا ونغير حجم الصفيف إلى رقم سحري:
// 15000 16384 const list = new Array(16384) function set (i, item) { // % - , // // , i list[i % list.length] = item }
دعنا نحاول تشغيل اختبار الأداء مرة أخرى. على جهاز الكمبيوتر ، اكتمل الاختبار في حوالي 1.5 ثانية. زيادة أكثر من الضعف بسبب تغيير الحجم البسيط. لفهم سبب حدوث ذلك ، يجب أن نفهم ما يلي ، تحت غطاء المحرك ، يعمل الكمبيوتر مع الأرقام ذات القاعدة 2. من المهم معرفة ما إذا كان لدينا ما تبقى من القسمة (٪ العملية). مثل هذا الحساب أبسط بكثير إذا كان الرقم مضاعفًا لـ 2 (2 ^ n) b 16384 هو 2 ^ 14. في الواقع ، ينظر الكمبيوتر إلى الرقم في شكل ثنائي ويأخذ ببساطة آخر n بت.
على سبيل المثال: ماذا سيحدث عند إجراء مثل هذه العملية 353500٪ 16384؟ سيبدو الرقم 353500 في التمثيل الثنائي مثل 1010110010011011100. نظرًا لأن 16384 == 2 ^ 14 - نحتاج إلى أخذ آخر 14 بت - 10101 (10010011011100) أو 9 346.
يمكننا استخدام هذه المعرفة فيما يتعلق بثقب دودي آخر. بالنسبة لجهاز الكمبيوتر ، من السهل جدًا أخذ آخر عدد من وحدات البت. في الواقع ، من الضروري فقط إنتاج ثنائي و (تشغيل &) برقم (2 ^ n) - 1
const list = new Array(16384) function set (i, item) {
بتشغيل اختبار الأداء مرة أخرى على جهاز الكمبيوتر الخاص بي ، سنرى أن وقت التنفيذ سينخفض إلى ~ 1s أو ستكون هناك زيادة في الأداء بمقدار أربعة أضعاف مقارنةً بالتشغيل الأول. وكل هذا بسبب فهم كيفية عمل الكمبيوتر.
يمكن للمترجمين أو VMs الذكية القيام بهذا النوع من التحسين من خلال تحويل عملية الحصول على الباقي من وراء الكواليس إلى عملية أحادية الاتجاه والعكس صحيح. في الواقع ، أحدث إصدار من V8 Javascript VM (لم يتم تنفيذه في NodeJS) يفعل ذلك تمامًا.
الثقب العددي
آخر molehill مفيد هو فهم كيفية عمل قراءة وكتابة الأرقام. هل تذكر كيف استخدمنا أجهزة كمبيوتر 32 بت وكيف حصلنا على 64 بت؟ وحتى 32 بت كان لدينا 16 بت. ماذا يعني هذا بالضبط؟ عادة نفكر في الأمر بهذه الطريقة - مقدار ذاكرة الوصول العشوائي الموجودة على الكمبيوتر. 2 ^ 32 = 4294967296 أو 4 جيجابايت ، مما يعني أنه لا يمكننا الوصول إلا إلى 4 جيجابايت من الذاكرة على جهاز كمبيوتر 32 بت. عندما نكتب برنامج JS ، لا نحتاج عادةً إلى التفكير في الأمر ، لأننا عادةً لا نستخدم الكثير من الذاكرة.
ومع ذلك ، من المهم جدًا فهم الفرق بين أجهزة الكمبيوتر 32 بت و 64 بت. منذ أن تلقت المعالجات تسجيلات 64 بت على أجهزة الكمبيوتر 64 بت ، أصبحت العمليات أسرع مرتين من أجهزة الكمبيوتر 32 بت ، حيث كان لديك تسجيلات 32 بت فقط.
كيف يمكننا استخدام المعلومات حول هذا الثقب الدودي؟
دعونا نكتب برنامجًا بسيطًا ينسخ Uint8Array إلى آخر. إذا لم تكن على دراية بـ Unit8Arrays ، فهي مشابهة جدًا للمخازن المؤقتة في NodeJS ، أو ببساطة ذاكرة "نظيفة".
function copy (input, output) { // input.length <= output.length for (var i = 0; i < input.length; i++) { // 8- (byte) output[i] = input[i] } }
مرة أخرى ، دعنا نقيس السرعة عن طريق إجراء اختبار الأداء.
// 1MB Uint8Arrays const input = new Uint8Array(1024 * 1024) const output = new Uint8Array(1024 * 1024) console.time() for (var i = 0; i < 1e4; i++) { copy(input, output) } console.timeEnd()
على جهاز الكمبيوتر الخاص بي ، اكتمل البرنامج في حوالي 7.5 ثانية. كيف يمكننا استخدام الثقب الدودي لتسريع؟ باستخدام Uint8Array ، نقوم بنسخ 8 بتات فقط في المرة الواحدة ، ولكن باستخدام كمبيوتر 64 بت ، يمكننا نسخ 64 بت من المعلومات في نفس الوقت. يمكننا القيام بذلك في JavaScript عن طريق تحويل Uint8Array إلى Float64Array قبل النسخ ، وهو ما لن يكلفنا شيئًا.
function copy (input, output) { // input.length <= output.length // 64- // , // 64- // BigInts JavaScript, BigInt64Array. const input64 = new Float64Array(input.buffer, input.byteOffset, input.length / 8) const output64 = new Float64Array(output.buffer, output.byteOffset, output.length / 8) for (var i = 0; i < input64.length; i++) { // 64- output64[i] = input64[i] } }
من خلال تشغيل اختبارات الأداء مرة أخرى ، نحصل على وقت تشغيل قدره ثانية واحدة ، مما يمنح زيادة في السرعة تبلغ 8 أضعاف.
بالنسبة للنسخ ، يكون الحل المقبول هو استخدام طريقة array.set (otherArray) لـ Uint8Array ، والتي تعطينا نسخًا في التعليمات البرمجية الأصلية - وهو أسرع بكثير من أي ثقب دودي آخر. كمرجع ، سيعطي هذا نتيجة تنفيذ 0.2 ~ ثانية في اختبارنا على جهاز الكمبيوتر الخاص بي ، وهو أسرع 5 مرات من الحل السابق.
مجرة JavaScript مليئة بالثقوب
سيساعدك استخدام الثقوب الدودية المذكورة أعلاه على جعل الكثير من الخوارزميات الواقعية أسرع بكثير. هناك العديد من الثقوب الدودية. مفضلتي هي Math.clz32 ، وهي طريقة تُرجع عدد بتات الصفر البادئة في تمثيل ثنائي 32 بت لرقم. يمكننا استخدام هذه الطريقة للعديد من الخوارزميات المثيرة للاهتمام. لقد استخدمته لتسريع تنفيذ حقول البت 4 مرات ، مما أدى إلى انخفاض استهلاك الذاكرة 4 مرات وسمح لي بفرز الأرقام في بعض الحالات بشكل أسرع.
يسمح لك فهم المبادئ الأساسية للكمبيوتر بكتابة أسرع البرامج التي نحتاجها. هذه المعرفة مهمة حتى عندما تكتب بلغة عالية المستوى مثل JavaScript.
ملاحظة:
شكر خاص للمساعدة في ترجمة وتعديل الترجمة إلى Olga Pereverzeva