الكمال توفي. محلل

تم تخصيص سلسلة من المقالات لوصف النهج الأمثل لتنفيذ أدوات تحليل التعليمات البرمجية الثابتة ، المصممة للمتخصصين. الهدف من العمل هو المناهج والنماذج والتقنيات للحصول على أقصى أداء للأداة مع تقليل تعقيد تطوير ودعم / تغيير الأداة. تتناول هذه المقالة كيفية تسريع المحلل اللغوي وتقليل استهلاك الذاكرة. المقالة منظمة بحيث يقرأ القارئ الدليل الذي كتبه Terrence Parr.

باستخدام ANTLR على أكمل وجه


يعمل ANTLR بشكل أفضل بين حوالي 1 كيلوبايت و 10 كيلوبايت ؛ لن يتم تحليل الملفات الأكبر حجمًا بواسطة هذه المكتبة بأقصى سرعة. كما يصبح تقريبًا تصحيح العمل على الملفات الكبيرة أمرًا مستحيلاً. السبب الرئيسي الذي يجعلك تحتاج إلى الاحتفاظ ببيانات الإدخال الخاصة بالمحلل ضمن الحدود المحددة هو أن خوارزميات التنبؤ بالفرع لـ ANTLR تستخدم المكدس بشكل نشط ، لذا فأنت بحاجة إلى التخلص من الحلقات في القواعد عندما تستدعي قاعدة واحدة نفسها من خلال العديد من القواعد الأخرى ، بما في ذلك بعض القواعد شروط التنشيط لمثل هذا الاتصال ، خذ بعين الاعتبار مثال:

var f = fun a(b) { b = 10; return b; }

يمكن وصف هذا الرمز بالقواعد التالية:

start: stmt* EOF;
stmt: varDecl | funDecl | expr ';' | 'return' expr ';';
varDecl: 'var' id '=' expr;
expr: id ('=' expr)? | number;
funDecl: 'fun' id '(' id* ')' '{' stmt* '}'

من السهل أن ترى أن STMT يسمى داخل قاعدة funDecl ، والتي تشكل حلقة يمكن أن تتسبب في التطبيقات الحقيقية في ملف بحجم 100 كيلوبايت في الحصول على 4 غيغابايت من ذاكرة الوصول العشوائي لأقصى قدر من الأداء ، أو حتى القدرة على العمل ، وهو موقف غير مقبول على الإطلاق .

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

للقيام بذلك ، في ANTLR يمكنك تجاوز طريقة org.antlr.v4.runtime.Lexer # nextToken من lexer ، حيث يمكنك تنفيذ وظيفة الالتفاف:

  override def nextToken(): Token = super.nextToken() match {
      case x: RScanToken if x.getType == foldOpen => buildFoldToken(x)
      case x: Token => x
  }

  def buildFoldToken(start: RScanToken): RScanToken = {
    val (token, list) = createFoldBlockBody(
      mutable.MutableList[RScanToken]()
        ++ List(start.asInstanceOf[RScanToken])
    )
    val result = new RScanToken(path, _tokenFactorySourcePair, foldBlock, Lexer.DEFAULT_TOKEN_CHANNEL, start.getStartIndex, token.getStopIndex)
    result.setLine(start.getLine)
    result.setCharPositionInLine(start.getCharPositionInLine)
    result.setFoldedTokens(list)
    result
  }

  private def createFoldBlockBody(list: mutable.MutableList[RScanToken]): (RScanToken, mutable.MutableList[RScanToken]) = {
    var current: RScanToken = null
    while (current == null || current.getType != Token.EOF && current.getType != foldClose) {
      current = nextToken().asInstanceOf[RScanToken]
      list += current
    }
    if (current.getType == Token.EOF)
      throw new IllegalStateException()
    (current, list)
  }

يجب استكمال القواعد بقواعد:

startJavaScript 
    :   HashBangLine? jsFileBody? EOF
    ;

startFoldBlock
   :   block EOF
   ;

block
    :   LBRACE stmtList? RBRACE
    |   FoldBlock 
//     ,
//     startFoldBlock
    ;

باستخدام هذا النهج ، لن تتم معالجة محتويات الالتواء مرة أخرى ، حيث ستمتص الخوارزمية العودية الرموز المميزة وحفظها.

تنمو سرعة المعالجة من 2 إلى 10 مرات ، ويصبح الفرق ملحوظًا بشكل خاص في ملفات js المصغرة.

التأثير على عملية ANTLR للتحسين المقترح على مثال العديد من ملفات جافا سكريبت:
ملفالحجم كيلو بايتقبل التحسين ، مللي ثانيةبعد التحسين ، مللي ثانية
تطبيع وتحميل metadata.js1018391372
إعادة كتابة المراجع الحية8899528
dom.umd.min.js130438526607
response.pure.umd.min.js139516686495
tsserver.js8151362857117787

بدون التحسين ، يتم تنفيذ العمل في خيط واحد ، مع التحسين ، إذا أمكن ، تكون المعالجة متوازية.

تم تنفيذ الإطلاق على جهاز مزود بذاكرة وصول عشوائي بسعة 64 غيغابايت ، و Intel® Core (TM) i7-9700K CPU @ 3.60GHz ، OpenJDK Runtime Environment.12TOpenJDK (بناء 11.0.4 + 11).

مفاتيح بدء تشغيل JVM: -Xmx4G -XX: + UseG1GC -XX: MaxHeapFreeRatio = 30 -XX: MinHeapFreeRatio = 10
لملف tsserver.js ، المفتاح هو -Xmx32G ، بينما وصل استهلاك الذاكرة إلى 22 جيجابايت! بينما يتم تحليل الملفات المصغرة التي تصل إلى 200 كيلوبايت مع التحسين بحد أقصى للذاكرة يبلغ 128 ميجابايت في الوضع المتوازي دون الحاجة إلى أن يقوم جامع البيانات المهملة بتحميل المعالج ، بحد أقصى 2٪!

التنميط


يدعم ANTLR تحديد ملفات تعريف المحلل اللغوي / المحلل في وقت التشغيل. لتمكينه ، تحتاج إلى استدعاء الطريقة: org.antlr.v4.runtime.Parser # setProfile قبل تنفيذ أي قواعد. ثم يمكنك الحصول على جميع المعلومات ، على سبيل المثال بهذه الطريقة:

    private def printProfileInfo(parser: AbstractRScanParser, tokenStream: TokenStream): Unit = {
      // do the actual parsing
      val parseInfo = parser.getParseInfo
      val atn = parser.getATN
      for (di <- parseInfo.getDecisionInfo if di.ambiguities.size() > 0) {
        val ds = atn.decisionToState.get(di.decision)
        val ruleName = parser.ruleName(ds.ruleIndex)
        log.debug("Ambiguity in rule '" + ruleName + "' -> {}", di)
        log.debug("=========================")
        log.debug(tokenStream.getText)
        log.debug("=========================")
      }
    }

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

استنتاج


تقترح هذه المقالة طريقة لتحسين عمل القواعد النحوية الرسمية التي يتم تنفيذها باستخدام مكتبة ANTLR ، على الرغم من أنه يمكن تجربة النهج نفسه لتطبيقه على مكتبات أخرى أيضًا. ميزة التحسين هي تقليل عدد التحولات إلى الأمام للتحقق من دفق رمز الإدخال المميز. كما يسمح لك بتحليل الملفات الكبيرة (أكثر من 1 ميجابايت) بتكلفة ذاكرة 512 ميجابايت للمعالجة أحادية الخيوط ، في حين أن نقص التحسين سيتطلب ذاكرة أكبر 50 مرة للعمل السريع باستخدام نفس القواعد.

كود المصدر متاح على جيثب. يرصد هذا المشروع لإثبات عمل التحسين. تم تبسيط المشروع قدر الإمكان ، يوصى ببدء الدراسة في فصل GrammarTester ، وقد تم تكوينه لبدء التشغيل ، ما عليك سوى تسجيل المسار إلى المجلد ببيانات الإدخال. انتبه لمفتاح rscan.tester.cache.dir ، سيتم كتابة الملفات المؤقتة في هذا المجلد ، تم إصلاح تحليل الملف الناجح في هذا المجلد ولن يسمح للمحلل بتحليله مرة أخرى - مناسب لإصلاح الأخطاء. في الوقت الحالي ، تم اختبار القواعد النحوية على 17 ألف ملف من العقدة_النماذج التي تم إنشاؤها لتطبيق التفاعل الأساسي. تم تجاهل وحدات العقدة المتداخلة فقط.

في المقالة التالية ، سننظر في خيارات لتنظيم البيانات ونموذج R (انعكاس) للتمثيل الأمثل لبيانات المصدر ككائنات تحليل بأقل استهلاك للذاكرة ، والقدرة على تنفيذ خوارزميات البحث للعناصر ذات التعقيد O (1) ، وسنكون قادرين على الحفظ على القرص في شكل متسلسل جميع الأشياء ، بالإضافة إلى أجزاء اختبار الوحدة من الأداة.

Source: https://habr.com/ru/post/undefined/


All Articles