خبرة في تحسين العمليات الحسابية من خلال إنشاء رمز ثنائي JVM الديناميكي

في مشروعي الصغير حول نمذجة المتغيرات العشوائية ، واجهت مشكلة الأداء المنخفض في حساب التعبيرات الرياضية التي أدخلها المستخدم ، ولفترة طويلة كنت أبحث عن طرق مختلفة لحلها: حاولت كتابة مترجم بلغة C ++ على أمل أن يكون سريعًا ، فكتبت الرمز الثانوي الخاص بي. كانت الفكرة الأكثر نجاحًا هي إنشاء فئات JVM وتحميلها في وقت التشغيل.



بعد التعرف على KMath ، قررت تعميم هذا التحسين على مجموعة متنوعة من الهياكل الرياضية والعوامل المحددة عليها.



KMath هي مكتبة للرياضيات وجبر الكمبيوتر تستخدم بشكل مكثف البرمجة الموجهة نحو السياق في Kotlin. يفصل KMath الكيانات الرياضية (الأرقام والمتجهات والمصفوفات) والعمليات عليها - يتم توفيرها ككائن منفصل ، والجبر المطابق لنوع المعاملات ، الجبر <T> .

import scientifik.kmath.operations.*

ComplexField {
   (i pow 2) + Complex(1.0, 3.0)
}

وبالتالي ، بعد كتابة منشئ الرموز الثنائية ، مع الأخذ في الاعتبار تحسينات JVM ، يمكنك الحصول على حسابات سريعة لأي كائن رياضي - يكفي تحديد العمليات عليها في Kotlin.

API

بادئ ذي بدء ، كان من الضروري تطوير واجهة برمجة تطبيقات للتعبيرات وبعد ذلك فقط انتقل إلى قواعد اللغة وشجرة بناء الجملة. كما جاءت بفكرة ذكية لتعريف الجبر على التعبيرات نفسها لتقديم واجهة أكثر سهولة.



أساس التعبير API بالكامل هو واجهة Expression <T> ، وأسهل طريقة لتنفيذها هي تحديد طريقة الاستدعاء مباشرة من المعلمات المحددة أو ، على سبيل المثال ، التعبيرات المتداخلة. تم دمج تطبيق مماثل في وحدة الجذر كمرجع ، وإن كان أبطأ.

interface Expression<T> {
   operator fun invoke(arguments: Map<String, T>): T
}

تعتمد عمليات التنفيذ الأكثر تقدمًا بالفعل على MST. وتشمل هذه:

• مترجم MST ،
• مولد فئة MST.

تتوفر بالفعل واجهة برمجة تطبيقات لتحليل التعبيرات من سلسلة إلى MST في فرع KMath dev ، كما هو الحال مع أكثر أو أقل من مُنشئ كود JVM النهائي.



دعنا ننتقل إلى MST. يوجد حاليًا أربعة أنواع من العقد في MST:

• طرفية:
  
  
  • الرموز (أي المتغيرات)
  • أعداد؛
• عمليات أحادية
• العمليات الثنائية.

أول شيء يمكنك القيام به هو تجاوز وحساب النتيجة من البيانات المتاحة. من خلال تمرير معرف العملية في الجبر الهدف ، على سبيل المثال "+" ، والوسيطات ، على سبيل المثال 1.0 و 1.0 ، يمكننا أن نأمل في النتيجة إذا تم تحديد هذه العملية. خلاف ذلك ، عند التقييم ، سيقع التعبير مع استثناء.







للعمل مع MST ، بالإضافة إلى لغة التعبير ، هناك أيضًا الجبر - على سبيل المثال ، MstField:

import scientifik.kmath.ast.*
import scientifik.kmath.operations.*
import scientifik.kmath.expressions.*

RealField.mstInField { number(1.0) + number(1.0) }() // 2.0

نتيجة الطريقة المذكورة أعلاه هي تنفيذ Expression <T> الذي ، عند استدعائه ، يتسبب في اجتياز الشجرة التي تم الحصول عليها عن طريق تقييم الوظيفة التي تم تمريرها إلى mstInField .

رمز الجيل

لكن هذا ليس كل شيء: عند العبور ، يمكننا استخدام معلمات الشجرة كما نحب ولا نقلق بشأن ترتيب الإجراءات وحالة العمليات. هذا هو ما يتم استخدامه لتوليد الرمز الثانوي.



إنشاء الكود في kmath-ast عبارة عن تجميع معلمات لفئة JVM. الإدخال هو MST والجبر الهدف ، الإخراج هو التعبير <T> مثيل .



توفر الفئة المقابلة ، AsmBuilder ، وبعض الامتدادات الأخرى طرقًا لبناء كود ثانوي بشكل إلزامي أعلى ObjectWeb ASM. إنها تجعل اجتياز MST وتجميع الفئة تبدو نظيفة وتتطلب أقل من 40 سطرًا من التعليمات البرمجية.



ضع في اعتبارك الفئة التي تم إنشاؤها للتعبير "2 * x" ، يتم عرض شفرة مصدر Java التي تم فك تجميعها من الرمز الثانوي:

package scientifik.kmath.asm.generated;

import java.util.Map;
import scientifik.kmath.asm.internal.MapIntrinsics;
import scientifik.kmath.expressions.Expression;
import scientifik.kmath.operations.RealField;

public final class AsmCompiledExpression_1073786867_0 implements Expression<Double> {
   private final RealField algebra;

   public final Double invoke(Map<String, ? extends Double> arguments) {
       return (Double)this.algebra.add(((Double)MapIntrinsics.getOrFail(arguments, "x")).doubleValue(), 2.0D);
   }

   public AsmCompiledExpression_1073786867_0(RealField algebra) {
       this.algebra = algebra;
   }
}

أولا، استدعاء و ولدت الأسلوب هنا ، والذي المعاملات رتبت بالتسلسل (لأنها أعمق في شجرة)، ثم إضافة المكالمة . بعد الاستدعاء ، تم تسجيل طريقة الجسر المقابلة. بعد ذلك ، تمت كتابة حقل الجبر والمنشئ . في بعض الحالات ، عندما لا يمكن وضع الثوابت ببساطة في مجموعة ثوابت الفئة ، يتم أيضًا كتابة حقل الثوابت ، مصفوفة java.lang.Object .



ومع ذلك ، نظرًا للعديد من حالات الحافة والتحسينات ، فإن تنفيذ المولد معقد نوعًا ما.

تحسين استدعاءات الجبر

لاستدعاء عملية من الجبر ، تحتاج إلى تمرير معرفها والوسيطات:

RealField { binaryOperation("+", 1.0, 1.0) } // 2.0

ومع ذلك ، فإن مثل هذه المكالمة باهظة الثمن من حيث الأداء: من أجل اختيار الطريقة التي تريد الاتصال بها ، ستنفذ RealField بيان جدول مكلف نسبيًا ، وتحتاج أيضًا إلى تذكر أمر الملاكمة. لذلك ، على الرغم من إمكانية تمثيل جميع عمليات MST في هذا النموذج ، فمن الأفضل إجراء مكالمة مباشرة:

RealField { add(1.0, 1.0) } // 2.0

لا توجد اتفاقية خاصة لتعيين معرفات العمليات للطرق في تطبيقات الجبر <T> ، لذلك كان علينا إدخال عكاز كتب فيه يدويًا أن "+" ، على سبيل المثال ، يتوافق مع طريقة الإضافة. يوجد أيضًا دعم للمواقف المواتية عندما يمكنك العثور على طريقة لمعرف العملية بنفس الاسم والعدد المطلوب من الوسائط وأنواعها.

private val methodNameAdapters: Map<Pair<String, Int>, String> by lazy {
    hashMapOf(
        "+" to 2 to "add",
        "*" to 2 to "multiply",
        "/" to 2 to "divide",
...

private fun <T> AsmBuilder<T>.findSpecific(context: Algebra<T>, name: String, parameterTypes: Array<MstType>): Method? =
    context.javaClass.methods.find { method ->
...
        nameValid && arityValid && notBridgeInPrimitive && paramsValid
    }

مشكلة رئيسية أخرى هي الملاكمة. إذا نظرنا إلى تواقيع طريقة Java التي تم الحصول عليها بعد تجميع نفس RealField ، فسنرى طريقتين:

public Double add(double a, double b)

// $FF: synthetic method
// $FF: bridge method
public Object add(Object var1, Object var2)

بالطبع ، من الأسهل عدم الإزعاج بالملاكمة وإلغاء العبوة واستدعاء طريقة الجسر: ظهرت هنا بسبب محو النوع ، من أجل تنفيذ طريقة الإضافة (T ، T): T بشكل صحيح ، النوع T في واصفها تم محوه بالفعل إلى java.lang . الكائن .



استدعاء إضافة مباشرة من زوجي ليس مثاليًا أيضًا ، لأن القيمة المعادة هي البوكسيت (هناك مناقشة حول هذا في YouTrack Kotlin ( KT-29460 ) ، ولكن من الأفضل تسميتها من أجل حفظ مجموعتين من كائنات الإدخال إلى java.lang في أحسن الأحوال .Number وعلبته ل مضاعفة .



استغرق الأمر أطول وقت لحل هذه المشكلة. لا تكمن الصعوبة هنا في إنشاء استدعاءات للطريقة البدائية ، ولكن في حقيقة أنك تحتاج إلى الجمع في المكدس بين كلا النوعين البدائيين (مثل مزدوج) وأغلفةهما ( java.lang.Double ، على سبيل المثال) ، وإدراج الملاكمة في الأماكن الصحيحة (على سبيل المثال ، java.lang.Double.valueOf ) و unboxing ( doubleValue ) - لم تكن هناك حاجة على الإطلاق للعمل مع أنواع التعليمات في bytecode.



كانت لدي أفكار لتعليق تجريدي المكتوب فوق الرمز الثانوي. للقيام بذلك ، كان علي أن أتعمق أكثر في ObjectWeb ASM API. انتهى بي الأمر بالانتقال إلى الخلفية Kotlin / JVM ، وفحصت فئة StackValue بالتفصيل(جزء مكتوب من الرمز الثانوي ، والذي يؤدي في النهاية إلى الحصول على بعض القيمة على مكدس المعامل) ، اكتشف الأداة المساعدة للنوع ، والتي تتيح لك العمل بشكل ملائم مع الأنواع المتوفرة في الرمز الثانوي (العناصر الأولية ، العناصر ، المصفوفات) ، وإعادة كتابة المولد مع استخدامه. تم حل مشكلة ما إذا كان سيتم تخزين القيمة على المكدس أو فكها عن طريق إضافة ArrayDeque يحمل الأنواع المتوقعة من المكالمة التالية.

  internal fun loadNumeric(value: Number) {
        if (expectationStack.peek() == NUMBER_TYPE) {
            loadNumberConstant(value, true)
            expectationStack.pop()
            typeStack.push(NUMBER_TYPE)
        } else ...?.number(value)?.let { loadTConstant(it) }
            ?: error(...)
    }

الاستنتاجات

في النهاية ، تمكنت من إنشاء مولد أكواد باستخدام ObjectWeb ASM لتقييم تعبيرات MST في KMath. يعتمد اكتساب الأداء على اجتياز MST البسيط على عدد العقد ، نظرًا لأن الرمز الثانوي خطي ولا يضيع الوقت في اختيار العقدة والتكرار. على سبيل المثال ، بالنسبة للتعبير الذي يحتوي على 10 عقد ، يكون الفارق الزمني بين التقييم مع الفئة التي تم إنشاؤها والمترجم الفوري من 19 إلى 30٪.



بعد فحص المشكلات التي واجهتها ، توصلت إلى الاستنتاجات التالية:

• تحتاج إلى دراسة إمكانيات وأدوات مساعدة ASM على الفور - فهي تبسط التطوير بشكل كبير وتجعل الكود قابلاً للقراءة ( النوع ، InstructionAdapter ، GeneratorAdapter ) ؛
• MaxStack , , — ClassWriter COMPUTE_MAXS COMPUTE_FRAMES;
• ;
• , , , ;
• , — , , ByteBuddy cglib.

شكرا للقراءة.



مؤلفو المقال:



ياروسلاف سيرجيفيتش بوستوفالوف ، MBOU “Lyceum № 130 سميت على اسم الأكاديمي Lavrentyev "، عضو مختبر النمذجة الرياضية تحت قيادة Voytishek Anton Vatslavovich



تاتيانا أبراموفا ، باحثة في مختبر أساليب تجارب الفيزياء النووية في JetBrains Research .