Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Դինամիկ տիպերով լեզուների ստատիկ օպտիմալացման մեթոդները

Վարդանյան, Վահագն Գևորգի (2016) Դինամիկ տիպերով լեզուների ստատիկ օպտիմալացման մեթոդները. PhD thesis, ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (1188Kb) | Preview
    [img]
    Preview
    PDF (Thesis)
    Available under License Creative Commons Attribution.

    Download (2997Kb) | Preview

      Abstract

      В настоящее время широкое распространение получили программы на динамических языках программирования. Традиционным способом выполнения программ на таких языках являлась интерпретация. Однако, с ростом применения этих языков и сложности приложений, все больше возрастают требования к производительности программ на языках с динамическими типами. Многие современные реализации этих языков используют технологию многоуровневой (гибридной) динамической компиляции (JIT-компиляция)1, что позволяет применять широкий класс оптимизаций и тем самым достигать лучшей производительности. При динамической компиляции время, затраченное на компиляцию, добавляется к общему времени выполнения. Поэтому важно соблюдать баланс между сложностью выполняемых оптимизаций и временем задержки запуска программы. Использование многоуровневого (гибридного) динамического компилятора позволяет достичь этого баланса. Такое решение обеспечивает быстрый запуск программы, начиная выполнение на уровне интерпретации. Далее, наиболее часто исполняющиеся участки кода выполняются на уровне динамического компилятора с применением разных оптимизаций, для генерации более качественного машинного кода. Использование такой архитектуры тем более актуально для современных многоядерных процессоров, позволяя запускать потоки компиляции параллельно с потоком выполнения на разных ядрах, и тем самым минимизировать паузы при интерактивном взаимодействии. Многоуровневая архитектура также позволяет эффективно реализовывать спекулятивную компиляцию2, что является одним из важных методов обеспечения быстродействия динамических языков программирования. Эта технология основывается на профиле выполнения программы и позволяет применять известные алгоритмы оптимизации статических языков к языкам с динамическими типами. Такие оптимизации выполняются (и являются корректными) только в предположении, что собранные при профилировании типы данных остаются неизменными. В случае нарушения этого условия выполнение возобновляется на предыдущем уровне компиляции. Такой процесс называется деоптимизацией. При использовании многоуровневой архитектуры на первом уровне выполнения собирается необходимый профиль программы, которая используется на следующих уровнях для реализации спекулятивных оптимизаций. Производительность многоуровневых JIT-компиляторов может быть существенно увеличена за счет оптимизаций, применяемых на всех уровнях выполнения. Методы статической оптимизации3 широко известны и используются во многих индустриальных компиляторах, в том числе и в современных многоуровневых (гибридных) компиляторах. Однако сложность оптимизации многоуровневых компиляторов языков с динамическими типами состоит в том, что реализация оптимизации на одном уровне может привести к негативному эффекту на других уровнях и, в целом, негативно повлиять на производительность. Например, с одной стороны, в целях улучшения производительности следует обеспечивать выполнение максимального количества «горячих» (часто выполняемых)4 участков кода на оптимизирующих уровнях компиляции. С другой стороны, важно обеспечить минимальное количество деоптимизаций (обратных переходов на неоптимизирующие уровни выполнения). Таким образом, при реализации оптимизаций на каждом уровне необходимо учитывать всю инфраструктуру многоуровневого динамического компилятора в целом. Dynamically typed languages have gain popularity during the last decade. One of the examples of such languages is JavaScript. In recent years, JavaScript has become one of the most popular web development languages. Its usage evolved beyond the small web-applications to areas such as operating systems and server-side applications. JavaScript is used in many modern and massive applications, such as Node.js, Gmail, Google docs, etc. Moreover, JavaScript is the main language for developing user applications in some operation systems (e.g. Tizen OS, Firefox OS). Hence, many modern engines for dynamically typed languages use just-in-time (JIT) compilation to produce optimized binary code. Due to increasing popularity many companies such as Apple (JavaScriptCore compiler), Google (V8 compiler), Mozilla (SpiderMonkey compiler) and Microsoft (ChakraCore compiler) have produced and are continuing to develop their own JIT-compilers for dynamically typed languages. JIT compilers are limited in complexity of optimizations they can perform at runtime without delaying the execution. To maintain a trade-off between quick startup and doing sophisticated optimizations, compiler engines usually use multiple tiers: lower tier JITs generate less efficient code, but can start almost immediately (e.g. even with interpretation), while higher tier JITs aim at generating effective code for hot places, but at the cost of long compilation time. One of the well-known and effective methods of optimizing dynamically typed languages is speculative compilation. Design of multitier architecture allows effective implementation of speculative optimizations: during the execution on the lower tiers, profile for program is collected. This profile is used then in the higher levels of execution for organizing speculative optimizations. These optimizations are based on the assumption that the state of the program will not change during execution and usually are built on specialization of types and values. If the optimized code encounters a case it cannot handle (for example, when type of the variable does not correspond to profile information), it bails to lower tiers. Such transition is called deoptimization. 21 optimizing levels of compilation. On the other hand, it is important to minimize number of deoptimizations. Hence, the optimizations must be designed to consider all the levels of the multitier infrastructure entirely. The applications written on dynamically typed langugaes are becoming massive and more complex. It is important to constantly improve multitier JIT architectures to meet requirements of the increasing complexity of applications and support new features of processors. This work is dedicated to analysis, design and development of static optimizations for modern multi-tier dynamic compilers. Ներկայումս լայն տարածում են ստացել ոչ տիպականացված սկրիպտային լեզուներով գրված ծրագրերը: Ծրագրավորման այդտեսակ լեզուներից լայն տարածում ունի JavaScript-ը: Համակարգիչների և ներդրված համակարգերի արդյունավետության բարձրացման հետ մեկտեղ JavaScript լեզվի գործածումը հնարավոր դարձավ ոչ միայն վեբ կայքերում օգտագործվող փոքր ծավալով սկրիպտային ծրագրերում, այլ նաև այնպիսի ծավալուն ծրագրերում ինչպիսին են Gmail-ը և Google docs-ը: JavaScript լեզուն նաև օգտագործվում է Node.js սերվարային ծրագրավորման համակարգում: Ավելին, որոշ օպերացիոն համակարգեր JavaScript լեզուն օգտագործում են որպես հիմնական ծրագրավորման լեզու: Այդպիսի համակարգերի օրինակներ են Tizen և FirefoxOS օպերացիոն համակարգերը: Որպես հետևանք` առաջանում է սկրիպտային ծրագրերի արդյունավետության բարձրացման պահանջարկ: Դինամիկ տիպերով լեզուների ժամանակակից իրականացումների մեծամասնությունը մեքենայական կոդի գեներացման համար օգտագործում է դինամիկ կոմպիլյացիաի մեթոդը: Դինամիկ կոմպիլյացիայի ընթացքում կարևոր է ապահովել հավասարակշռություն օգտագործվող օպտիմալացումների բարդության և ծրագրի մեկնարկի հետաձգման միջև: Հավասարակշռություն ապահովելու նպատակով օգտագործվում է բազմամակարդակ դինամիկ կոմպիլյացիաի մեթոդը, որը թույլ է տալիս առանց հետաձգման սկսել ծրագրի կատարումը կոմպիլյացիայի առաջին մակարդակում (այս մակարդակում կատարվում են միան պարզ օպտիմալացումներ), իսկ հաճախ օգտագործվող կոդի հատվածների թարգմանությունը կատարվում է օպտիմալացնող մակարդակներում ավելի որակյալ մեքենայական կոդ ստանալու նպատակով:

      Item Type: Thesis (PhD)
      Additional Information: Դինամիկ տիպերով լեզուների ստատիկ օպտիմալացման մեթոդները. Static optimizations for programs with dynamically typed languages.
      Uncontrolled Keywords: Վարդանյան Վահագն Գևորգի, Vardanyan Vahagn
      Subjects: Mechanical Engineering and Machine Science
      Divisions: UNSPECIFIED
      Depositing User: NLA Circ. Dpt.
      Date Deposited: 11 Oct 2016 17:18
      Last Modified: 26 Oct 2016 11:21
      URI: http://etd.asj-oa.am/id/eprint/3589

      Actions (login required)

      View Item